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

Question

我有一个对象列表（在这种情况下为“移动”），我想根据他们的计算评估进行排序。所以，我有List，以及一些与列表中的元素“关联”的数字。我现在想要用第一个具有最低关联数的元素对List元素进行排序，而最后一个元素具有最高关联数。一旦项目是订单，我可以放弃相关的号码。我该怎么做呢？

这是我的代码看起来像（kind've）：

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排序。为相关值对创建一个新的向量（我推荐向量进行更有效的排序），并指向其项目的指针。对对的向量进行排序，然后从排序的向量中重新生成列表。由于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）。

Answer 2

也许你认为在你喜欢的方式在两个元素进行比较的比较功能。

bool compare_m (const Move &first,const Move &second) 
{ 
    if (first.thing_you_are_comparing_on() < second.thing_you_are_comparing_on()) return true; 
    else return false; 
} 

其中“thing_you_are_comparing_on”是移动类，让你想要订购的一些成员。我们在这里使用const来确保我们只比较而不是实际改变比较函数中的对象。然后，您可以致电名单上的排序方法与compare_m作为对比功能：

moves.sort(compare_m) 

一些需要注意的是，如果比较函数的计算是特别昂贵的它可能是值得的预先计算所有相关的等级号码在排序之前。

这将需要增加一些到移动类后存储等级使用：

class Move{ 
    //rest of move class 

    public: 
    int rank; 
}; 

list<Move>::iterator iter; 

for(iter = moves.begin(); iter != moves.end(); ++iter) 
{ 
    //... 
    (*iter).rank = max; // store the number associated with current Move 
} 

bool compare_rank (const Move &first,const Move &second) 
{ 
    if (first.rank < second.rank) return true; 
    else return false; 
} 

Answer 3

std::sort用于对STL集合进行排序。如果可以简单地比较要排序的集合中的元素通过调用operator<和有问题的集合是一个vector，然后排序很简单：

std::sort(collection.begin(), collection.end()); 

如果有问题的收集不是vector但list在你的情况，那么你可以不使用的std::sort普通版，但你可以使用std::list的版本而不是：

list<int> numbers; 
numbers.sort(); 

STL的sort，与STL中的大多数其他算法一起，有两种形式。一个是我们已经看到的简单版本，它只是使用operator<来比较两个元素。另一种是“预测”版本，而不是使用operator<使用您提供的比较functor。这是你需要在你的情况下使用。list有一个sort的预测版本，这是你需要在你的情况下使用。

您可以通过多种方式创建一个函子，但最有效的方法之一就是从std::unary_function或std::binary_function派生类，这取决于你的仿函数将多少个参数需要 - 在你的情况下，两个。重写函数调用操作，operator()并补充说，比较两个元素的代码：

class compare_functor : public std::binary_function<Move, Move, bool> 
{ 
public: 
    bool operator(const Move& lhs, const Move& rhs) const 
    { 
    int left_val = lhs.Value(); 
    int right_val = rhs.Value(); 
    return left_val < right_val; 
}; 

下面是一个完整的工作的例子，把一切融合在一起。在这个程序中，我没有列出Move s，而是列出了10 string s。每个string是6个随机字符。该列表通过调用generate_n来填充，该函数使用函子generator来创建每个随机字符串。然后，我通过调用copy并传递将值转储到标准输出的输出迭代器（ostream_iterator）来转储该字符串列表以及它们的值。每个字符串的值只是每个字符的数字值的总和，由函数strng_val计算。

然后我使用list的预测版本sort对列表进行排序。 sort使用的比较谓词是evaluator。然后，我最后将结果列表和字符串值再次转储到屏幕上，如上所示：

#include <cstdlib> 
#include <iostream> 
#include <list> 
#include <string> 
#include <algorithm> 
#include <ctime> 
#include <sstream> 

using namespace std; 

class generator 
{ 
public: 
    generator() { srand((unsigned)time(0)); } 
    string operator()() const 
    { 
     string ret; 
     for(int i = 0; i < 6; ++i) 
      ret += static_cast<char>((rand()/(RAND_MAX/26)) + 'A'); 
     return ret; 
    } 
}; 

unsigned string_val(const string& rhs) 
{ 
     unsigned val = 0; 
     for(string::const_iterator it = rhs.begin(); it != rhs.end(); ++it) 
      val += (*it)-'A'+1; 
     return val; 
}; 

class evaluator : public std::binary_function<string,string,bool> 
{ 
public: 
    bool operator()(const string& lhs, const string& rhs) const 
    { 
     return string_val(lhs) < string_val(rhs); 
    } 
}; 

class string_dumper : public std::unary_function<string, string> 
{ 
public: 
    string operator()(const string& rhs) const 
    { 
     stringstream ss; 
     ss << rhs << " = " << string_val(rhs); 
     return ss.str(); 
    } 
}; 

int main() 
{ 
    // fill a list with strings of 6 random characters 
    list<string> strings; 
    generate_n(back_inserter(strings), 10, generator()); 
    // dump it to the screen 
    cout << "Unsorted List:\n"; 
    transform(strings.begin(), strings.end(), ostream_iterator<string>(cout, "\n"), string_dumper()); 

    // sort the strings according to their numeric values computed by 'evaluator' 
    strings.sort(evaluator()); // because this is a 'list', we are using list's 'sort' 
    // dump it to the screen 
    cout << "\n\nSorted List:\n"; 
    transform(strings.begin(), strings.end(), ostream_iterator<string>(cout, "\n"), string_dumper()); 
    return 0; 

}