3

文字列と整数 (カウント) のペアを持つベクトルがあり、カウントに従ってすべてを並べ替えましたが、リストに 2 つ以上の繰り返しがある場合は文字列も並べ替える必要があります。例えば;

3 お試し 2 おいしい 2 abc

したがって、リストには 2 が 2 つあるため、yummy の前に abc を指定する必要があります。私のコードは次のようになります。

vector<pair<string, int> > values(hash_table.begin(), hash_table.end());

sort(values.begin(), values.end(), sort_reverse);


bool sort_reverse(const pair<string, int> &a, const pair<string, int> &b) {
  return a.second > b.second;
}
4

4 に答える 4

7

デフォルトの小なり比較の代わりに大なり比較を使用して、任意の範囲のソートを反転できます。

std::sort(values.begin(), values.end(), std::greater<std::pair<string, int>>());

または、反復の順序を逆にすることもできます。

std::sort(values.rbegin(), values.rend());

編集secondペアの最初と次のペアで辞書式に比較するように比較基準を変更する場合firstは、独自の比較関数を提供できます。上記の例のように、厳密な弱い順序付けも満たす必要があります。辞書式比較は、次のように実装するのは簡単std::tieです:

#include <tuple>

template<typename T1, typename T2>
struct pair_backwards_greater
{
  bool operator()(const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs) const
  {
    return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first);
  }
};

それから

std::sort(values.begin(), values.end(), pair_backwards_greater<string, int>());

ファンクターを手動で記述する代わりに、単純なラムダ式を使用するオプションもあります。

  std::sort(values.begin(), values.end(),
            [](const std::pair<std::string, int> &lhs, const std::pair<std::string, int> &rhs) 
            {
              return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first); 
            }  
           );

std::tieには C++11 ライブラリのサポートが必要ですが、 と には C++03 の代替実装がboost::tieありstd::tr1::tieます。ラムダ式には、C++11 言語のサポートが必要です。

于 2013-08-22T05:25:43.383 に答える
4

1 回のヒットで両方のフィールドを並べ替えるには:

bool sort_pair(const std::pair<std::string, int> &a, const std::pair<std::string, int> &b) 
{
    return (a.second > b.second) ||  
        ( 
            (a.second == b.second)  &&
            (a.first > b.first)
    );
}

void sortVector(std::vector<std::pair<std::string, int> >& values)
{
    std::sort(values.begin(), values.end(), sort_pair);
}

既存のエントリも参照

于 2013-08-22T05:41:52.767 に答える
2

値自体を考慮する必要があります。

bool sort_reverse(const pair<string, int> &a, const pair<string, int> &b) {
    return (a.second > b.second) || ((a.second == b.second) && (a.first > b.first));
}
于 2013-08-22T05:29:39.590 に答える
1

少し異なる代替案を提案したいと思います。これは の利点を紹介しますstable_sort。

typedef std::pair<int, std::string> CNP;

bool byName(CNP const& left, CNP const& right) { return left.second < right.second; }
bool byCount(CNP const& left, CNP const& right) { return left.first < right.first; }

std::sort(values.begin(), values.end(), byName);

std::stable_sort(values.begin(), values.end(), byCount);

これが機能するのは、同等の要素 (等しいと比較される要素) の場合、stable_sortそれらの相対的な順序が維持されるためです (sort可能性はありますが、保証はされません)。

したがって、あなたが持っていると想像してください[ (3, "apple"), (2, "zorro"), (2, "banana") ]：

  • 名前でソートすると、次のようになります。[ (3, "apple"), (2, "banana"), (2, "zorro") ]
  • カウントによる安定ソート：[ (2, "banana"), (2, "zorro"), (3, "apple") ]

もちろん、中間ステップが必要ない場合は、より複雑な述語で単一の並べ替えを使用する方が効率的です。ただし、すでに名前でソートされているリストを受け取った場合はstable_sort、カウント順を適用するだけでより高速になる可能性があります。

最後に、リストが基準に従ってソートされているかどうか (またはそうでないか) を確認する簡単なトリックを示します。

template <typename C, typename P>
bool is_sorted(C const& list, P comp) {
    typedef typename C::const_reference CR;

    auto const reversed = [](CR left, CR right) { return comp(right, left);  };

    return std::adjacent_find(list.begin(), list.end(), reversed) == list.end();
}

注: C++11 にはis_sortedメソッドがありますが、もちろんコンテナーではなくイテレーターで表現されます。

于 2013-08-22T06:21:55.100 に答える