基於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; 

}