c++ STL按整数和字符串的向量排序

Question

今天，我在topcoder上解决了一个问题，在这个问题中，我必须根据奥运会奖牌对国家进行排序。我有一个STL容器vector<pair<vector<int>, string> > v;的vector<int>不包含金，银和铜牌由一个国家赢得。我必须按照金、银、铜和国家(字母顺序)的特定顺序对结构进行排序。

我使用了sort(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

如果你真的写了你描述的代码，它将会做你想做的事情：

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，然后是US)，然后是铜牌(尽管这不是我的输入)，然后是名称(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枚金牌领先于其他所有人。然后是美国和俄罗斯，各有3枚金牌，按银牌排序；美国，有2枚银牌，排在第一位。然后是BE、DE和FR，每个都有1个黄金，相同数量的银牌和相同数量的青铜器，按字母顺序排序。

Answer 3

你需要一个自定义的比较器，这样STL排序才能比较你的向量。最简单的方法是将向量定义为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;
    }
};