Почему мультикарта позволяет дублировать пары ключ-значение?

Question

РЕДАКТИРОВАТЬ: Пожалуйста, обратите внимание, я НЕ спрашиваю, почему мультикарта не может содержать дубликаты ключей .

Каково обоснование мультикарты, позволяющей дублировать пары ключ-значение?(не keys )

#include <map>
#include <string>
#include <iostream>

int
main(int argc, char** argv)
{
    std::multimap<std::string, std::string> m;
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "C"));
    std::cout << m.size() << std::endl;
    return 0;
}

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

Интуитивно понятно, что это не согласуется с поведением C ++ std::map, где insert не всегда меняет карту (в отличие от operator[]).

Есть ли за этим обоснование или оно просто произвольно?

Answer 1

Мультикарта имеет только предикат, упорядочивающий ключи.У него нет способа определить, равны ли значения.Является ли значение «A» дубликатом значения «a»?Без второго предиката для значений невозможно сказать.Поэтому даже не имеет смысла говорить о дублированных значениях в мультикарте.

Если вам нужен контейнер, который хранит пары и обеспечивает уникальность обеих частей пары, посмотрите boost::multi_index_container.Он очень гибкий, но в результате принимает множество аргументов.

Answer 2

РЕДАКТИРОВАТЬ: Этот ответ больше не отвечает на текущий вопрос. Я сохраню его таким, какой он есть, потому что за него проголосовали, поэтому он должен быть полезен для некоторых.

multi in multimap означает тот факт, что одна и та же клавиша может встречаться , кратная раз.

Стандарт не ограничивает типиспользуется в качестве значения, поэтому нельзя предполагать, что operator==() определено.Поскольку мы не хотим, чтобы результат вашего кода зависел от того, определен оператор == () или нет, он никогда не используется.

std::multimap не является заменой std::map.Как вы заметили, он ведет себя по-разному, когда один и тот же ключ вставляется несколько раз.Если вы хотите поведение std::map, используйте std::map.

Существует также std::multiset.

Рационально: иногда хочется сохранить все старые записи для одного и того жеключ вокруг. [TBD: вставьте какой-нибудь пример сюда]

Лично я почти никогда не пользуюсь std::multimap.Если мне нужно несколько записей для одного и того же ключа, я обычно полагаюсь на std::map<std::vector<T> >.

Answer 3

Значения могут быть дубликатами, потому что они не обязательно должны быть сопоставимы друг с другом.Контейнер не может ничего делать со значениями, кроме как скопировать их в. Это позволяет использовать такие типы, как multimap< int, my_class >.

Если дублирующиеся пары ключ-значение нежелательны, тогда используйте set< pair< T, U > > и используйте lower_bound, чтобы найти первыйсоответствует данному ключу.

Answer 4

Мое рассуждение состоит в том, что мультикарта основана на поиске / вставке ключа, а не на значении. Так что значение одинаковых ключей одинаково или нет, не играет роли при вставке элементов.

23.3.2 шаблон класса multimap

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

Answer 5

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

Если вы хотите иметь некоторую структуру данных словаря, которая допускает дублирующиеся ключи, но не пары ключ-значение, вы должны убедиться, что значения сопоставимы.

Допустим, у нас есть какая-то игра, в которой есть 2D мир квадратных полей, и вы можете размещать предметы на полях. Вы можете иметь multimap<Field, Item>, что позволит вам хранить два одинаковых предмета на поле. Здесь не обязательно сравнивать предметы.

Answer 6

«multimap» предназначен для поддержки «нескольких» ключей в отличие от простых «map» .Так как он допускает несколько ключей, он не будет беспокоиться об их значениях, поэтому он показывает 3 элемента в вашем примере.Другое отличие состоит в том, что нельзя иметь operator [] для multimap.