Как я могу отсортировать карту STL по значению?

Question

Как реализовать сортировку карт STL по значению?

Например, у меня есть карта m:

map<int, int> m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;

Я бы хотел отсортировать эту карту по значению m. Итак, если я распечатаю карту, я бы хотел получить результат следующим образом:

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

Как я могу отсортировать карту таким образом? Есть ли способ, которым я могу иметь дело с ключом и значением с отсортированными значениями?

Answer 1

Извлеките все пары ключ-значение сначала в set<pair<K, V> >, где set создан с функтором меньше, чем сравнивает только второе значение пары.Таким образом, ваш код по-прежнему работает, даже если ваши значения не все различны.

Или сбросьте пары ключ-значение в vector<pair<K, V> >, а затем отсортируйте этот вектор с тем же функтором, меньшим, чем функтор.

Answer 2

Вы можете построить вторую карту со значениями первой карты в качестве ключей и ключами первой карты в качестве значений.

Это работает, только если все значения различны.Если вы не можете этого допустить, вам нужно построить мультикарту вместо карты.

Answer 3

Интересно, как мне реализовать сортировку карты STL по значению.

Вы не можете по определению . Карта - это структура данных, которая сортирует свой элемент по ключу.

Answer 4

Вы должны использовать Boost.Bimap для такого рода вещей.

Answer 5

Основываясь на идее @ swegi, я реализовал решение в c ++ 11 , используя multimap:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
multimap<int, int> mm;

for(auto const &kv : m)
    mm.insert(make_pair(kv.second, kv.first));  // Flip the pairs.

for(auto const &kv : mm)
    cout << "m[" << kv.second << "] = " << kv.first << endl;  // Flip the pairs again.

Код на Ideone

Я также реализовал решение C ++ 11, основанное на идее @Chris, с использованием вектора пар. Для правильной сортировки я предоставляю лямбда-выражение как функтор сравнения:

map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}};
using mypair = pair<int, int>;

vector<mypair> v(begin(m), end(m));

sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; });

for(auto const &p : v)
    cout << "m[" << p.first << "] = " << p.second << endl;

Код на Ideone

Первое решение более компактно, но оба решения должны иметь примерно одинаковую производительность. Вставка в multimap имеет значение O (log n) , но это необходимо сделать для n записей, в результате чего O (n log n), Сортировка вектора во втором решении также приводит к O (n log n) .

Я также попробовал идею @Chris об использовании набора пар. Однако, это не будет работать, если значения не все различны. Использование функтора, который сравнивает только второй элемент пары, не помогает. Если вы сначала вставите make_pair(1, 1) в набор, а затем попытаетесь вставить make_pair(2, 1), то вторая пара не будет вставлена, потому что обе пары рассматриваются как идентичные в этом наборе. Вы можете увидеть этот эффект здесь на Ideone .

Answer 6

Я только что задал похожий вопрос в своей книге на С ++. Ответ, который я придумал, может быть не очень эффективным:

int main()
{
    string s;
    map<string, int> counters;

    while(cin >> s)
        ++counters[s];

    //Get the largest and smallest values from map
    int beginPos = smallest_map_value(counters);
    int endPos = largest_map_value(counters);

    //Increment through smallest value to largest values found
    for(int i = beginPos; i <= endPos; ++i)
    {
        //For each increment, go through the map...
        for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it)
        {
            //...and print out any pairs with matching values
            if(it->second == i)
            {
                cout << it->first << "\t" << it->second << endl;
            }
        }
    }
    return 0;
}

//Find the smallest value for a map<string, int>
int smallest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int lowest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second < lowest)
            lowest = it->second;
    }
    return lowest;
}

//Find the largest value for a map<string, int>
int largest_map_value(const map<string, int>& m)
{
    map<string, int>::const_iterator it = m.begin();
    int highest = it->second;
    for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it)
    {
        if(it->second > highest)
            highest = it->second;
    }
    return highest;
}

Answer 7

Я нашел это в thispointer .В примере сортируется std :: map по всем значениям int.

#include <map>
#include <set>
#include <algorithm>
#include <functional>

int main() {

    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
            { "bbb", 62 }, { "ccc", 13 } };

    // Declaring the type of Predicate that accepts 2 pairs and return a bool
    typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;

    // Defining a lambda function to compare two pairs. It will compare two pairs using second field
    Comparator compFunctor =
            [](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
            {
                return elem1.second < elem2.second;
            };

    // Declaring a set that will store the pairs using above comparision logic
    std::set<std::pair<std::string, int>, Comparator> setOfWords(
            mapOfWordCount.begin(), mapOfWordCount.end(), compFunctor);

    // Iterate over a set using range base for loop
    // It will display the items in sorted order of values
    for (std::pair<std::string, int> element : setOfWords)
        std::cout << element.first << " :: " << element.second << std::endl;

    return 0;
}

Answer 8

Создайте другую карту, предоставьте функцию less (), основанную на значении, а не ключе, И функция должна вернуть true, если значение1 <= </strong> значение2 (не строго <).В этом случае элементы с нечеткими значениями также могут быть отсортированы.</p>