Мультисеть без сравнения?
Я хочу использовать multiset посчитать некоторые пользовательские ключи. Ключи не сопоставимы численно, сравнение двух ключей ничего не значит, но их равенство можно проверить.
я вижу это multiset шаблон хочет Compare заказать мультимножество. Для меня порядок не важен, важны только цифры. Если я опущу Compare полностью что происходит? Работает ли мультисеть без проблем для моих пользовательских ключей? Если я не могу использовать std::multiset каковы мои альтернативы?
4 ответа
Вы не можете использовать std::multiset если у вас нет строгого слабого порядка. Ваши варианты:
Наложить строго-слабый порядок на ваши данные. Если ваш ключ представляет собой "линейную" структуру данных, обычно лучше сравнить его лексикографически.
Используйте неупорядоченный контейнерный эквивалент, например,
boost::unordered_multiset, Для этого вам нужно сделать свой собственный тип данных хэш-, который часто проще, чем навязывать какой-то порядок.
Если вы можете сравнить ключи только на равенство, то вы не можете использовать std::multiset, Для ассоциативных контейнеров ваш тип ключа должен иметь строгий слабый порядок, наложенный операцией сравнения.
Строгий слабый порядок не обязательно должен быть числовым.
[Для использования в ассоциативном контейнере вам фактически не нужно сравнение на равенство. Ключевая эквивалентность определяется !compare(a, b) && !compare(b, a).]
Если вы действительно не можете определить порядок для ваших ключей, тогда ваш единственный вариант - использовать контейнер последовательностей пар ключ-значение и использовать линейный поиск для поиска. Излишне говорить, что это будет менее эффективно для операций, подобных множеству, чем multiset так что вы должны постараться создать порядок, если это возможно.
Если вы опустите Compare полностью, он получит значение по умолчанию, которое less (который дает результат < оператор применяется к вашему ключу) - который может или не может даже скомпилировать для вашего ключа.
Причиной наличия порядка является то, что он позволяет реализации быстрее искать элементы по их ключу (при вставке, удалении и т. Д.). Чтобы понять, почему, представьте себе поиск слов в словаре. Традиционные словари используют алфавитный порядок, что облегчает поиск слов. Если бы вы готовили словарь для языка, который нелегко упорядочить - скажем, пиктографический язык - тогда либо было бы очень трудно найти слова в нем вообще (вам нужно было бы искать весь словарь), либо вы Попытайтесь найти логичный способ упорядочить их (например, поместив сначала все рисунки, которые можно нарисовать, одним штрихом пера, затем двумя линиями и т. д.) - потому что даже если бы этот порядок был абсолютно произвольным, это могло бы сделать поиск Записи в словаре гораздо эффективнее.
Точно так же, даже если ваши ключи не нужно заказывать для собственных целей и не имеют естественного порядка, вы обычно можете определить порядок, который достаточно хорош для решения этих проблем. Порядок должен быть переходным (если a<b а также b<c затем a<c) и строгий (никогда не возвращать истину для a<a), асимметричный (a<b а также b>a никогда не правда) В идеале следует заказать все элементы (если a & b отличаются то либо a<b или же b<a), хотя вы можете избежать неприятностей с правдой (то есть строгим слабым порядком) - хотя это довольно технический вопрос.
Действительно, пожалуй, наиболее очевидное использование этого - это редкий случай, когда упорядочить элементы совершенно невозможно - в этом случае вы можете указать оператор сравнения, который всегда возвращает false. Это очень вероятно приведет к снижению производительности, но, по крайней мере, будет работать правильно.
Итак, у вас есть два важных критерия, которые вы перечислили.
- Вы не заботитесь о порядке
- сравнение ключей ничего не значит
и один предположил,
- тот факт, что вы используете
multisetподразумевает, что есть много случаев
Так почему бы не использовать std::vector или же std::deque или же std::list? тогда вы можете воспользоваться различными алгоритмами, которые могут использовать проверку на равенство (например, count_if так далее.)