C ++ (стиль Hashmap) Идеальная структура данных для этого сценария?

Question

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

• Каждый элемент будет иметь уникальный ключ.Будет нет вероятность коллизий, потому что каждый элемент хеширует свой ключ. РЕДАКТИРОВАТЬ: * Ключ представляет собой 32-разрядный UINT. *
• Все элементы уникальны и, следовательно, могут рассматриваться как набор .
• Требуются только операции добавления и получения, , а не удаления.Они должны быть быстрыми, так как они будут использоваться несколько сотен тысяч раз в обычном цикле!
• Порядок, в котором хранятся элементы, не имеет значения .
• Скорость важнее, чем потребление памяти ... хотя она не может быть слишком жадной!

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

Я знаю, что существует бесчисленное множествоСтруктуры данных C ++ в стиле Hashmap / Dictionary с реализациями, которые построены так, чтобы удовлетворять различным критериям, поэтому, если кто-то может предложить один идеал для этой ситуации, то это будет оценено.

Большое спасибо

Редактировать:

Я нашел этот отрывок на SO, который, кажется, предполагает, что unordered_map будет хорошо?

hash_map и unordered_map обычно реализуются с помощью хеш-таблиц.Таким образом, порядок не поддерживается.unordered_map insert / delete / query будет O (1) (постоянное время), где map будет O (log n), где n - количество элементов в структуре данных.Так что unordered_map работает быстрее, и если вам не важен порядок элементов, то предпочтительнее, чем map.Иногда вы хотите сохранить порядок (упорядоченный по ключу), и для этой карты будет выбор.

Answer 1

Что касается встроенных решений, я бы порекомендовал google :: dens_hash_map.Они действительно быстрые, особенно для цифровых клавиш.Вам нужно будет выбрать конкретный ключ, который будет зарезервирован как «empty_key».Кроме того, вот действительно хорошее сравнение различных реализаций хэш-карт.

Выдержка

Library         Linux-intCPU (sec)  Linux-strCPU (sec)   Linux PeakMem (MB)
glib            3.490               4.720                24.968
ghthash         3.260               3.460                61.232
CC’s hashtable  3.040               4.050                129.020
TR1             1.750               3.300                28.648
STL hash_set    2.070               3.430                25.764
google-sparse   2.560               6.930                5.42/8.54
google-dense    0.550               2.820                24.7/49.3
khash (C++)     1.100               2.900                6.88/13.1
khash (C)       1.140               2.940                6.91/13.1
STL set (RB)    7.840               18.620               29.388
kbtree (C)      4.260               17.620               4.86/9.59
NP’s splaytree  11.180              27.610               19.024

Однако, при установке "delete_key" эта карта такжевыполнить удаление.Поэтому, возможно, можно будет создать собственное решение, которое будет еще более эффективным.Но, кроме этой второстепенной точки, любая хеш-карта должна точно соответствовать вашим потребностям (обратите внимание, что «карта» является упорядоченной древовидной картой и, следовательно, медленнее).

Answer 2

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

РЕДАКТИРОВАТЬ: я предполагаю, что ключи строковые, а не простые значения, такие как целые числа

Answer 3

То, что вам нужно, определенно звучит как хэш-набор, в C ++ это может быть либо std::tr1::unordered_set, либо в Boost.Unordered.

P.S. Тем не менее, обратите внимание, что TR1 не все же стандарт, и вам, вероятно, потребуется получить Boost для реализации.

Answer 4

То, что вы ищете, это unordered_set. Вы можете найти его в Boost, TR1 или C ++ 0x. Если вы хотите связать ключ со значением, то unordered_map делает то же самое - и в Boost / TR1 / C ++ 0x.

Answer 5

Похоже, что std::unordered_set будет соответствовать всем требованиям, но, не зная больше о ключе, трудно сказать.Мне любопытно, как вы можете гарантировать, что не будет возможности столкновения: это подразумевает небольшой (меньше размера таблицы) конечный набор ключей.В этом случае может быть более эффективно сопоставить ключи с маленьким целым и использовать std::vector (с пустыми слотами для записей, которых нет).