C++ STL按int和字符串排序

Question

今天我在topcoder上解决了一个问题，在这个问题中，我必须通过奥运会奖牌排序国家。我有一个STL容器vector<pair<vector<int>, string> > v;vector<int>不包含一个国家赢得的金，银和铜牌。我必须按照金，银，铜和国家（字母顺序）的顺序排列结构。

我使用排序（v.begin（），v.end（）），但这种排序只能通过第一个值，即金，银和铜，而不是按字母顺序排序的国家当g，s ，两国的b奖牌是一样的。

Answer 1

您必须提供您的比较功能对象。

typedef pair<vector<int>, string> Country; 
struct CmpCountry { 
    bool operator()(const Country& lhs, const Country& rhs) 
    { 
     if(lhs.first[0] != rhs.first[0]) 
      return lhs.first[0] > rhs.first[0]; 
     if(lhs.first[1] != rhs.first[1]) 
      return lhs.first[1] > rhs.first[1]; 
     if(lhs.first[2] != rhs.first[2]) 
      return lhs.first[2] > rhs.first[2]; 
     return lhs.second < rhs.second; 
    } 
}; 

// then, call sort as following 
std::sort(v.begin(), v.end(), CmpCountry()); 

Answer 2

您需要自定义比较器，以便STL排序可以比较您的向量。最简单的方法是将vector定义为struct，然后添加一个比较器。

struct country { 
    vector<int> medals; 
    string country_name; 
} 

struct compare { 
    bool operator()(country const &a, country const &b) { 
     for(int i = 0; i < 3; i++){ // 3 medals, right? 
      if(a.medals[i] != b.medals[i]) 
       return a.medals[i] < b.medals[i]; 
     //else both countries have same number of medals 
     return a.country_name < b.country_name; 
    } 
}; 

Answer 3

如果你真正写入您所描述的代码，它会做你想要什么：

compare.cpp：

#include <vector> 
#include <utility> 
#include <algorithm> 
#include <iostream> 

using namespace std; 

typedef pair<vector<int>, string> Country; 

int main(int, char*[]) { 
    vector<Country> v; 
    while (cin.good()) { 
    string name; 
    int g, s, b; 
    cin >> name >> g >> s >> b; 
    vector<int> c; 
    c.push_back(g); 
    c.push_back(s); 
    c.push_back(b); 
    v.push_back(make_pair(c, name)); 
    } 
    sort(v.begin(), v.end()); 
    for (vector<Country>::const_iterator it = v.begin(); it != v.end(); ++it) { 
    cout << it->second << " " << it->first[0] 
    << " " << it->first[1] << " " << it->first[2] << "\n"; 
    } 
    return 0; 
} 

compare.in：

US 3 2 1 
CA 4 1 3 
DE 1 3 5 
FR 1 3 5 
BE 1 3 5 
RU 3 1 2 

现在这样做：

$ clang++ -o compare compare.cpp 
$ ./compare < compare.in 
BE 1 3 5 
DE 1 3 5 
FR 1 3 5 
RU 3 1 2 
US 3 2 1 
CA 4 1 3 

请注意，它是按金牌排序（升序排列），先是BE/DE/FR，然后是RU/US，然后是CA，接下来的是银色（RU然后是美国），接下来是青铜色（虽然没有出现与我的投入），然后命名（BE，然后DE，然后FR）。正是你要求的。 （呃，实际上你问的是字母顺序，这是为g，s和b做数字顺序，这可能是你想要的（所以，例如，2枚金牌超过11枚）。如果没有，你必须编写你自己的比较函数，在比较它们之前将它们串联起来。）

那么，为什么这样工作？那么，如果您查看std::pair的定义，它将按字典顺序进行比较，即它比较lhs.first与rhs.first，然后仅在first等于时才会移至lhs.second与rhs.second。如果您查看std::vector的定义，它也会按字典顺序进行比较 - 即，它将lhs[0]与rhs[0]进行比较，然后仅在[0]等于时，才会转到lhs[1]与rhs[1]等等。这正是你在这之后的比较顺序。

从您的意见，这听起来像你想扭转数值的正常排序顺序，但不是国家名称。要做到这一点，你必须定义你自己的比较器。但请注意，问题不在于配对和向量不按您想要的方式排序 - 它们会这样做 - 但是int并不会按您想要的方式排序。

因为如果你明白这一点，所有这些都是微不足道的，而不是仅仅给出答案，我会一步一步解释它。

首先，这里是默认的排序是（实际上，不是字面上）要做的：

struct CountryComparator { 
    bool operator()(const Country& lhs, const Country& rhs) const { 
    if (!(lhs.first == rhs.first)) 
     return (lhs.first < rhs.first); 
    return (lhs.second < rhs.second); 
    } 
}; 

（请注意，我要我的方式只使用==和<这并未。在你的情况中无关紧要，因为你只是比较整数，但是STL是围绕这样的想法设计的，即即使在仅支持这两个运营商的类上，每个算法也应该工作，并且这是一个好习惯。）

扩大矢量比较使事情变得非常冗长，所以我们不要烦恼。如果实际上想要颠倒矢量的某些成员的排序顺序而不是其他的顺序，则必须这样做，但是您想要颠倒整个矢量的排序顺序，这与仅颠倒排序顺序相同矢量本身的顺序。所以，仅仅定义了这个：

struct CountryComparator { 
    bool operator()(const Country& lhs, const Country& rhs) const { 
    if (!(lhs.first == rhs.first)) 
     return (rhs.first < lhs.first); 
    return (lhs.second < rhs.second); 
    } 
}; 

现在，只需更改排序行：

sort(v.begin(), v.end(), CountryComparator()); 

现在让我们来试试吧：

$ ./compare < compare.in 
CA 4 1 3 
US 3 2 1 
RU 3 1 2 
BE 1 3 5 
DE 1 3 5 
FR 1 3 5 

CA以4枚金牌是每个人的未来。然后美国和RU，每个3金，按银色排序;美国，有2个银牌，是第一位。然后是BE，DE和FR，每个1金，同样数量的银器和相同数量的青铜器按字母顺序排序。