基于C++中动态生成的数字对列表进行排序

Question

我有一个对象列表(在这种情况下是"Move")我想根据他们的计算评估进行排序.所以,我有List和一堆与列表中的元素"关联"的数字.我现在想要使用具有最低关联数字的第一个元素和具有最高关联数字的最后一个元素对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变换排序.创建一个新的向量(我推荐用于更有效排序的向量)的关联值对,以及指向其项的指针.对对矢量进行排序,然后从排序后的矢量中重新生成列表.由于a 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).