0

今天我在解决一个关于 topcoder 的问题，我必须按照奥运会的奖牌对国家进行排序。我有一个 STL 容器里面没有一个国家赢得vector<pair<vector<int>, string> > v;的vector<int>金、银和铜牌。我必须按照黄金、白银、青铜和国家（字母顺序）的特定顺序对结构进行排序。

我使用了 sort(v.begin(), v.end()) 但这种排序仅按配对中的第一个值，即按金、银和铜牌排序，当 g、s、b 奖牌时，它不按字母顺序对国家进行排序两个国家是一样的。

4

3 回答 3

3

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

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());
于 2012-07-18T00:31:44.340 回答
2

如果您确实编写了您描述的代码，它将完全按照您的意愿执行：

比较.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;
}

比较.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.firstvs. ，然后只有当s 相等时才rhs.first转到lhs.secondvs .。如果你看一下 的定义，它也会按字典顺序进行比较——也就是说，它比较vs. ，然后只有当s 相等时才转到vs. ，依此类推。这正是您在这里所追求的比较顺序。rhs.secondfirststd::vectorlhs[0]rhs[0]lhs[1]rhs[1][0]

从您的评论中，听起来您想要反转数值的正常排序顺序，而不是国家名称。为此，您必须定义自己的比较器。但请注意，问题不在于 pair 和 vector 没有按照你想要的方式排序——它们确实如此——而是 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);
  }
};

（请注意，我将竭尽全力只使用==and <。这在您的情况下无关紧要，因为您只是在比较整数，但是 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 with 4 golds is ahead of everyone else. Then US and RU, with 3 golds each, are sorted by silvers; US, with 2 silvers, comes first. Then BE, DE, and FR, with 1 gold each, and the same number of silvers, and the same number of bronzes, are sorted alphabetically.

于 2012-07-18T01:10:24.320 回答
0

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

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;
    }
};
于 2012-07-18T00:44:27.593 回答