11

値に基づいて std::map の上位 n キーを取得するにはどうすればよいですか? たとえば、値として最大の値を持つ上位 10 個のキーのリストを取得する方法はありますか?
次のようなマップがあるとします。

mymap["key1"]= 10;
mymap["key2"]= 3;
mymap["key3"]= 230;
mymap["key4"]= 15;
mymap["key5"]= 1;
mymap["key6"]= 66;
mymap["key7"]= 10;

そして、他のキーと比較して値が大きい上位 10 個のキーのリストのみが必要です。たとえば、mymap のトップ 4 は次のとおりです。

key3
key6
key4 
key1
key10

注:
値は一意ではなく、実際には各キーの出現回数です。そして、最も発生したキーのリストを取得したい

注2：
マップが適切な候補ではなく、何かを提案したい場合は、c ++ 11に従ってください。その時点ではブーストを使用できません。

注 3:
使用する場合、std::unordered_multimap<int,wstring>他に選択肢はありますか?

4

7 に答える 7

26

a の順序は、map値ではなくキーに基づいており、順序を変更することはできないため、 を反復処理して、検出mapされた上位 10 個のリストを維持するか、Potatoswatterpartial_sort_copy()のコメントに従って、上位N 個の値を抽出する必要があります。

std::vector<std::pair<std::string, int>> top_four(4);
std::partial_sort_copy(mymap.begin(),
                       mymap.end(),
                       top_four.begin(),
                       top_four.end(),
                       [](std::pair<const std::string, int> const& l,
                          std::pair<const std::string, int> const& r)
                       {
                           return l.second > r.second;
                       });

オンライン デモを参照してください。

別のタイプのコンテナーを選択する方が適切な場合がありboost::multi_indexますが、調査する価値があります。

...異なるソートとアクセスセマンティクスを持つ1つ以上のインデックスを維持するコンテナの構築を可能にします。

于 2013-07-31T07:21:13.617 に答える
3 
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main(int argc, const char * argv[])
{
    map<string, int> entries;

    // insert some random entries
    for(int i = 0; i < 100; ++i)
    {
        string name(5, 'A' + (char)(rand() % (int)('Z' - 'A') ));
        int number = rand() % 100;

        entries.insert(pair<string, int>(name, number));
    }

    // create container for top 10
    vector<pair<string, int>> sorted(10);

    // sort and copy with reversed compare function using second value of std::pair
    partial_sort_copy(entries.begin(), entries.end(),
                      sorted.begin(), sorted.end(),
                      [](const pair<string, int> &a, const pair<string, int> &b)
    {
        return !(a.second < b.second);
    });

    cout << endl << "all elements" << endl;

    for(pair<string, int> p : entries)
    {
        cout << p.first << "  " << p.second << endl;
    }

    cout << endl << "top 10" << endl;

    for(pair<string, int> p : sorted)
    {
        cout << p.first << "  " << p.second << endl;
    }

    return 0;
}
于 2013-07-31T07:56:55.707 に答える
2

マッピング先の値でソートしないだけでなくstd::map(そのような値にはソート順序が定義されている必要はありません)、その要素の再配置が許可されないため++ map[ "key1" ];、値をキーにマッピングする仮想構造で行うと、後方マッピングが無効になります。 .

あなたの最善の策は、キーと値のペアを別の構造に入れ、後方マッピングが必要なときにそれを値でソートすることです。常に後方マッピングが必要な場合は、値が変更されるたびに削除、変更、および再追加する必要があります。

既存のマップを新しい構造に分類する最も効率的な方法はstd::partial_sort_copy、(今のところ) Al Bundy が示しているように、 です。

于 2013-07-31T07:21:09.553 に答える
1

あなたが探しているアルゴリズムはnth_elementです。これは、範囲を部分的に並べ替えて、n 番目の要素が完全に並べ替えられた範囲内の場所になるようにします。たとえば、上位 3 つの項目を降順で表示したい場合は、(疑似 C++ で) 次のように記述します。

nth_element(begin, begin + 3, end, predicate)

問題は、nth_element が std::map で機能しないことです。したがって、データ構造をペアのベクトルに変更することをお勧めします (処理するデータの量によっては、とにかくこれがより高速なデータ構造であることがわかる場合があります)。したがって、あなたの例の場合、次のように書きます。

typedef vector<pair<string, int>> MyVector;
typedef MyVector::value_type ValueType;

MyVector v; 

// You should use an initialization list here if your
// compiler supports it (mine doesn't...)
v.emplace_back(ValueType("key1", 10));
v.emplace_back(ValueType("key2", 3));
v.emplace_back(ValueType("key3", 230));
v.emplace_back(ValueType("key4", 15));
v.emplace_back(ValueType("key5", 1));
v.emplace_back(ValueType("key6", 66));
v.emplace_back(ValueType("key7", 10));

nth_element(v.begin(), v.begin() + 3, v.end(), 
    [](ValueType const& x, ValueType const& y) -> bool
    {
        // sort descending by value
        return y.second < x.second;
    });

// print out the top three elements
for (size_t i = 0; i < 3; ++i)
    cout << v[i].first << ": " << v[i].second << endl;
于 2013-07-31T08:06:49.220 に答える
1

マップされた値はインデックス化されていないため、すべてを読み取って最大の 10 個の値を選択する必要があります。

std::vector<mapped_type> v;
v.reserve(mymap.size());

for(const auto& Pair : mymap)
 v.push_back( Pair.second );

std::sort(v.begin(), v.end(), std::greater<mapped_type>());

for(std::size_t i = 0, n = std::min<int>(10,v.size()); i < n; ++i)
  std::cout << v[i] << ' ';

もう 1 つの方法は、2 つのマップまたはバイマップを使用することです。したがって、マップされた値は順序付けられます。

于 2013-07-31T07:33:22.720 に答える
1 
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <cassert>
#include <iterator>
using namespace std;

class MyMap
{
public:
    MyMap(){};
    void addValue(string key, int value)
    {
        _map[key] = value;
        _vec.push_back(make_pair(key, value));
        sort(_vec.begin(), _vec.end(), Cmp());
    }
    vector<pair<string, int> > getTop(int n)
    {
        int len = min((unsigned int)n, _vec.size());
        vector<Pair> res;
        copy(_vec.begin(), _vec.begin() + len, back_inserter(res));
        return res;
    }
private:
    typedef map<string, int> StrIntMap;
    typedef vector<pair<string, int> > PairVector;
    typedef pair<string, int> Pair;
    StrIntMap  _map;
    PairVector _vec;
    struct Cmp: 
        public binary_function<const Pair&, const Pair&, bool>
    {
        bool operator()(const Pair& left, const Pair& right)
        {
            return right.second < left.second;
        }
    };
};

int main()
{
    MyMap mymap;
    mymap.addValue("key1", 10);
    mymap.addValue("key2", 3);
    mymap.addValue("key3", 230);
    mymap.addValue("key4", 15);
    mymap.addValue("key6", 66);
    mymap.addValue("key7", 10);

    auto res = mymap.getTop(3);

    for_each(res.begin(), res.end(), [](const pair<string, int> value)
                                        {cout<<value.first<<" "<<value.second<<endl;});
}
于 2013-07-31T08:19:55.320 に答える