В чем разница между std :: multimap <key, value> и std :: map <key, std :: set <value>>

Ответы:

52

Multimap хранит пары (ключ, значение), где ключ и значение могут встречаться несколько раз.

map<key, set<value>>Будет хранить только каждое значение один раз для конкретного ключа. Для этого он должен иметь возможность сравнивать значения, а не только ключи.

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

Бо Перссон
источник
5
Итак, std :: multimap <key, value> похож на std :: map <key, std :: multiset <value>>, разница между ними в том, что более поздние значения отсортированы. Это правильно?
大 宝剑
2
Нет, std::multimap<key, value>позволяет использовать один и тот же ключ несколько раз, тогда как std::map<key, whatever>требует уникальности key.
Yixing Liu
74

A std::map- это ассоциативный контейнер, который позволяет вам иметь уникальный ключ, связанный со значением вашего типа. Например,

void someFunction()
{
    typedef std::map<std::string, int> MapType;
    MapType myMap;

    // insertion
    myMap.insert(MapType::value_type("test", 42));
    myMap.insert(MapType::value_type("other-test", 0));

    // search
    auto it = myMap.find("test");
    if (it != myMap.end())
        std::cout << "value for " << it->first << " is " << it->second << std::endl;
    else
        std::cout << "value not found" << std::endl;
}

A std::multimapравно a std::map, но ваши ключи больше не уникальны. Таким образом, вы можете найти ряд предметов, а не просто найти один уникальный предмет. Например,

void someFunction()
{
    typedef std::multimap<std::string, int> MapType;
    MapType myMap;

    // insertion
    myMap.insert(MapType::value_type("test", 42));
    myMap.insert(MapType::value_type("test", 45));
    myMap.insert(MapType::value_type("other-test", 0));

    // search
    std::pair<auto first, auto second> range = myMap.equal_range("test");
    for (auto it = range.first; it != range.second; ++it)
        std::cout << "value for " << it->first << " can be " << it->second << std::endl;
}

Это std::setпохоже на std::map, но не хранит ключ, связанный со значением. Он хранит только тип ключа и гарантирует, что он уникален в наборе.

У вас также есть std::multiset, который следует той же схеме.

Все эти контейнеры предоставляют доступ O (log (n)) с их find / equal_range.

typedef
источник
6
В функции Multimap эта строка std::pair<auto first, auto second> range = myMap.equal_range("test");не работает, потому что error: 'auto' not allowed in template argument. const auto range = myMap.equal_range("test")Вместо этого используйте .
vancexu 02
2
тип карты? Разве это не должно быть MapType в строке 4?
лолололол ол
не уверен, кто был первым, но одно очевидно является копией другого: cppbuzz.com/What-is-difference-between-map-and-multimap
idclev 463035818
1
ахах, cppbuzz очищает StackOverflow или что? Я сам написал этот ответ много лет назад, когда все еще ежедневно кодировал на C ++. И действительно, там 4-я опечатка, спасибо @lololololol
typedef
1
(и их копирование / вставка не удалось, они даже не отображают типы в шаблоне объявление std :: map: std :: map <std :: string, int>)
typedef
13
map::insert

Поскольку mapконтейнеры не допускают повторяющихся значений ключа, операция вставки проверяет для каждого вставленного элемента, существует ли уже в контейнере другой элемент с таким же значением ключа, если это так, элемент не вставляется, и его сопоставленное значение никоим образом не изменяется.

с другой стороны

multimap::insert 

можно вставить любое количество элементов с помощью одного и того же ключа.

http://www.cplusplus.com/reference/stl/map/
http://www.cplusplus.com/reference/stl/multimap/

Лука Ране
источник
Хорошая ссылка как на разницу, так и на то, как она работает внутри. ссылка
Rndp13
10

Последнее требует, чтобы значения могли быть упорядочены (либо через operator<функцию сравнения), а первое - нет.

Бьорн Поллекс
источник
Казалось бы, operator <работает одинаково как на карте, так и на мульти-карте? en.cppreference.com/w/cpp/container/map/operator_cmp
johnbakers
Да, но мой ответ касался порядка значений. Предположим, у вас есть тип Tбез упорядочивания. Вы можете использовать его для создания std::multimap<U, T>, но не можете использовать для создания std::map<U, std::set<T> >.
Björn Pollex