В чем разница между std:: multimap и std:: map>

Я обнаружил, что у них есть один ключ и несколько значений, которые уникальны.

4 69
c++ structuremap containers key-value-store multimap

4 ответа:

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

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

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

41

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 равна 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;
}

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

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

все эти контейнеры обеспечивают o(log (n)) доступ с их find / equal_range.

65
map::insert

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

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

multimap::insert

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

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

12

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

9