0

今日、私はオリンピックで国をメダルでソートしなければならないトップコーダーの問題を解決していました。私は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;
}

比較:

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 より多い)。そうでない場合は、比較する前に、int を文字列化する独自の比較ファンクターを作成する必要があります。)

では、なぜこれが機能するのでしょうか。の定義を見るstd::pairと、辞書順で比較されます。つまり、lhs.firstvs.を比較し、 s が等しい場合にのみvs.rhs.firstに進みます。また、 の定義を見ると、辞書式の順序でも比較されます。つまり、 vs. を比較し、s が等しい場合にのみvs.に移動します。以下同様です。そして、それはまさにあなたがここで求めている比較順序です.lhs.secondrhs.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のみを使用するつもりはないことに注意して<ください。int を比較しているだけなので、これはあなたの場合は問題ではありませんが、STL は、すべてのアルゴリズムが唯一のクラスでも機能するはずであるという考えに基づいて設計されています。これら 2 つの演算子をサポートしており、これは良い習慣です。)

ベクトル比較を展開するとかなり冗長になるので、気にしないでください。ベクトルの一部のメンバーの並べ替え順序を実際に逆にしたい場合は、これを行う必要がありますが、ベクトル全体の並べ替え順序を逆にしようとしています。これは、並べ替えを逆にすることと同じです。ベクトル自体の順序。したがって、これを定義するだけです：

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

4 つのゴールドを持つ CA は、他の誰よりも進んでいます。次に、US と RU がそれぞれ 3 つの金を持ち、銀の順に並べ替えられます。2 銀メダルの US が 1 位です。次に、BE、DE、FR、それぞれ 1 ゴールド、同じ数のシルバーと同じ数のブロンズをアルファベット順に並べ替えます。

于 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 に答える