Какая разница между std:: multimap <ключ, значение> и std:: map <ключ, std:: set <значение>>

Ответ 1

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

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

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

Ответ 2

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.

Ответ 3

map::insert

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

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

multimap::insert 

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

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

Ответ 4

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