C++ STL：根據另一個的內容自定義排序一個向量

Question

這可能是最好的例子。我有兩個向量/列表：

People = {Anne, Bob, Charlie, Douglas} 
Ages = {23, 28, 25, 21} 

我想基於使用類似sort(People.begin(), People.end(), CustomComparator)他們的年齡人民排序，但我不知道怎麼寫了CustomComparator看時代，而不是人。

Answer 1

我會建議將這兩個列表合併到一個結構列表中。這樣，你可以簡單地定義operator <像dirkgently說。

Answer 2

而不是創建兩個獨立的矢量/列表，來處理這個通常的方式是創建一個包括姓名和年齡對象的單個向量/列表：

struct person { 
    std::string name; 
    int age; 
}; 

，我們將根據年齡排序在年齡定義一個比較，看起來：

struct by_age { 
    bool operator()(person const &a, person const &b) { 
     return a.age < b.age; 
    } 
}; 

那麼你的排序看起來是這樣的：

std::vector<person> people; 
// code to put data into people goes here. 

std::sort(people.begin(), people.end(), by_age()); 

編輯：至於爲類定義operator<或使用單獨的比較對象（如上所述）之間的選擇，這主要是一個問題，這個類是否有一個「顯而易見」的排序。

在我看來，排序人總是會按年齡發生並不一定很明顯。但是，如果在程序的上下文中，很明顯根據年齡對人進行排序除非你另有明確規定，那麼將比較作爲person::operator<而不是按照我的方式在單獨的比較類中實施是有意義的，上面已經做到了。

Answer 3

通常，您不會將要保存在不同容器中的數據放在一起。爲Person創建結構/類並重載operator<。

struct Person 
{ 
    std::string name; 
    int age; 
} 

bool operator< (const Person& a, const Person& b); 

或者，如果這是一些扔掉的東西：

typedef std::pair<int, std::string> Person; 
std::vector<Person> persons; 
std::sort(persons.begin(), persons.end()); 

std::pair已經實現了比較操作。

Answer 4

將它們保留在兩個單獨的數據結構中沒有意義：如果您重新訂購People，則不再有合理的映射到Ages。

template<class A, class B, class CA = std::less<A>, class CB = std::less<B> > 
struct lessByPairSecond 
    : std::binary_function<std::pair<A, B>, std::pair<A, B>, bool> 
{ 
    bool operator()(const std::pair<A, B> &left, const std::pair<A, B> &right) { 
     if (CB()(left.second, right.second)) return true; 
     if (CB()(right.second, left.second)) return false; 
     return CA()(left.first, right.first); 
    } 
}; 

std::vector<std::pair<std::string, int> > peopleAndAges; 
peopleAndAges.push_back(std::pair<std::string, int>("Anne", 23)); 
peopleAndAges.push_back(std::pair<std::string, int>("Bob", 23)); 
peopleAndAges.push_back(std::pair<std::string, int>("Charlie", 23)); 
peopleAndAges.push_back(std::pair<std::string, int>("Douglas", 23)); 
std::sort(peopleAndAges.begin(), peopleAndAges.end(), 
     lessByPairSecond<std::string, int>()); 

Answer 5

正如其他人已經指出，你應該考慮分組人和年齡。

如果您不能/不想，您可以爲它們創建一個「索引」，然後對該索引進行排序。例如：現在

// Warning: Not tested 
struct CompareAge : std::binary_function<size_t, size_t, bool> 
{ 
    CompareAge(const std::vector<unsigned int>& Ages) 
    : m_Ages(Ages) 
    {} 

    bool operator()(size_t Lhs, size_t Rhs)const 
    { 
     return m_Ages[Lhs] < m_Ages[Rhs]; 
    } 

    const std::vector<unsigned int>& m_Ages; 
}; 

std::vector<std::string> people = ...; 
std::vector<unsigned int> ages = ...; 

// Initialize a vector of indices 
assert(people.size() == ages.size()); 
std::vector<size_t> pos(people.size()); 
for (size_t i = 0; i != pos.size(); ++i){ 
    pos[i] = i; 
} 


// Sort the indices 
std::sort(pos.begin(), pos.end(), CompareAge(ages)); 

，第n個人的名字是people[pos[n]]其年齡ages[pos[n]]

Answer 6

傑裏棺材答案是完全清晰，正確。

一個只是有一個相關的問題是可以給予很好的討論話題... :)

我不得不重新排序矩陣對象的列（允許TMatrix < T>說）的基礎上（可以說序列）... TMatrix < T>類不提供對它的行的引用訪問（因此我不能創建一個結構來重新排序它......），但方便地提供了一個方法TMatrix < T> :: swap（row1，row2） ...

所以這是代碼：

TMatrix<double> matrix; 
vector<double> sequence; 
// 
// 1st step: gets indexes of the matrix rows changes in order to sort by time 
// 
// note: sorter vector will have 'sorted vector elements' on 'first' and 
// 'original indexes of vector elements' on 'second'... 
// 
const int n = int(sequence.size()); 
std::vector<std::pair<T, int>> sorter(n); 
for(int i = 0; i < n; i++) { 
    std::pair<T, int> ae; 
    ae.first = sequence[i]; 
    ae.second = i;    
    sorter[i] = ae; 
}   
std::sort(sorter.begin(), sorter.end()); 

// 
// 2nd step: swap matrix rows based on sorter information 
// 
for(int i = 0; i < n; i++) { 
    // updates the the time vector 
    sequence[i] = sorter[i].first; 
    // check if the any row should swap 
    const int pivot = sorter[i].second; 
    if (i != pivot) { 
     // 
     // store the required swaps on stack 
     // 
     stack<std::pair<int, int>> swaps; 
     int source = pivot; 
     int destination = i; 
     while(destination != pivot) { 
      // store required swaps until final destination 
      // is equals to first source (pivot) 
      std::pair<int, int> ae; 
      ae.first = source; 
      ae.second = destination; 
      swaps.push(ae); 
      // retrieves the next requiret swap 
      source = destination; 
      for(int j = 0; j < n; j++) { 
       if (sorter[j].second == source) 
        destination = j; 
        break; 
       } 
      } 
     }     
     // 
     // final step: execute required swaps 
     // 
     while(!swaps.empty()) { 
      // pop the swap entry from the stack 
      std::pair<int, int> swap = swaps.top(); 
      destination = swap.second;      
      swaps.pop(); 
      // swap matrix coluns 
      matrix.swap(swap.first, destination); 
      // updates the sorter 
      sorter[destination].second = destination; 
     } 
     // updates sorter on pivot 
     sorter[pivot].second = pivot; 
    } 
} 

我相信這仍然爲O（n log n）的，因爲每一行是不到位將交換隻是一個時間......

玩得開心！ :)