Мультисеть без сравнения?

Question

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

Я вижу, что шаблон multiset хочет Compare для заказа мультимножества. Для меня порядок не важен, важны только цифры. Если я полностью опущу Compare, что произойдет? Работает ли мультисеть без проблем для моих пользовательских ключей? Если я не могу использовать std::multiset, каковы мои альтернативы?

Answer 1

Если вы можете сравнивать ключи только на равенство, тогда вы не можете использовать std::multiset. Для ассоциативных контейнеров ваш тип ключа должен иметь строгий слабый порядок , наложенный операцией сравнения.

Строгий слабый порядок не обязательно должен быть числовым.

[Для использования в ассоциативном контейнере вам фактически не нужно сравнение на равенство. Эквивалентность ключа определяется !compare(a, b) && !compare(b, a).]

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

Answer 2

Вы не можете использовать std::multiset, если у вас нет строгого слабого порядка. Ваши варианты:

1. Наложение строго-слабого порядка на ваши данные. Если ваш ключ представляет собой «линейную» структуру данных, обычно лучше сравнить его лексикографически.

2. Используйте неупорядоченный эквивалент контейнера, например, boost::unordered_multiset. Для этого вам нужно будет сделать свой собственный тип данных хэширующим, что зачастую проще, чем навязывать какой-либо порядок.

Answer 3

Если вы полностью опустите Compare, он получит значение по умолчанию, равное less (которое дает результат оператора <, примененного к вашему ключу) - который может или не может даже компилироваться для вашего ключа.key.

Причиной наличия упорядочения является то, что он позволяет реализации быстрее искать элементы по их ключу (при вставке, удалении и т. д.). Чтобы понять, почему, представьте себе поиск слов в словаре.Традиционные словари используют алфавитный порядок, что облегчает поиск слов.Если бы вы готовили словарь для языка, который нелегко упорядочить - скажем, пиктографический язык - тогда либо было бы очень трудно найти слова в нем вообще (вам пришлось бы искать весь словарь), либо выпопытайтесь найти логичный способ упорядочить их (например, поместив сначала все рисунки, которые можно нарисовать, одним штрихом пера, затем двумя линиями и т. д.) - потому что даже если бы этот порядок был совершенно произвольным, это могло бы сделать поискзаписи в словаре гораздо более эффективны.

Точно так же, даже если ваши ключи не нужно упорядочивать для собственных целей и не имеют естественного порядка, вы обычно можете определить порядок, который хорошдостаточно, чтобы решить эти проблемы.Порядок должен быть транзитивным (если a<b и b<c, то a<c) и строгим (никогда не возвращать true для a<a), асимметричным (a<b и b>a никогда не равны true).В идеале он должен упорядочить все элементы (если a & b отличаются от a<b или b<a), хотя вы можете избежать неприятностей с этим, не будучи истинными (то есть строгое слабое упорядочение ) - хотя это довольно технически.

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

Answer 4

Итак, у вас есть два важных критерия, которые вы перечислили.

1. Вам нет дела до заказа
2. сравнение ключей ничего не значит

и один предположил,

1. тот факт, что вы используете multiset, подразумевает, что существует множество случаев

Итак, почему бы не использовать std::vector или std::dequeили std::list?тогда вы можете воспользоваться различными алгоритмами, которые могут использовать проверку на равенство (например, count_if и т. д.)