c++ - 根据 C++ 中动态生成的数字对列表进行排序

Question

我有一个对象列表(在本例中为“移动”)，我想根据它们的计算评估对其进行排序。所以，我有列表，以及一堆与列表中的元素“关联”的数字。我现在想对 List 元素进行排序，第一个元素的关联数最低，最后一个元素的关联数最高。订购元素后，我可以丢弃相关号码。我该怎么做？

这是我的代码的样子(有点):

list<Move> moves = board.getLegalMoves(board.turn);

for(i = moves.begin(); i != moves.end(); ++i)
{
    //...
    a = max; // <-- number associated with current Move
}

Answer 1

我会建议 Schwartzian transform种类。制作一个新的 vector (我推荐 vector 以进行更有效的排序)成对的关联值，以及指向其项目的指针。对成对的 vector 进行排序，然后从排序后的 vector 中重新生成列表。自 operator<在 std::pair 上定义通过对中的第一项和第二项进行比较，您将得到正确的排序。

例子:

#include <algorithm> // gives you std::sort
#include <utility>   // gives you std::pair

typedef double CostType;
typedef std::pair<CostType, Move*> Pair;

// Create the vector of pairs
std::vector<Pair> tempVec;
tempVec.reserve(moves.size());
for (std::list<Move>::iterator i = moves.begin(); i != moves.end(); ++i)
{
    CostType cost   = calcCost(*i);
    Move*    ptrToI = &(*i);
    tempVec.push_back(Pair(cost, ptrToI));
}

// Now sort 'em
std::sort(tempVec.begin(), tempVec.end());

// Regenerate your original list in sorted order by copying the original
// elements from their pointers in the Pair.
std::list<Move> sortedMoves;
for (std::vector<Pair>::iterator i = tempVec.begin(); i != tempVec.end(); ++i)
{
    sortedMoves.push_back(*(i->second));
}

请注意，您需要一个 calcCost我在这里假设的功能。如果您的比较值计算非常耗时，则此方法比创建比较函数更有优势。这样，您只需支付计算 N 次比较的成本，而不是 2 * N * log(N)。