Как вы говорите I assume the buckets can get big..., лучше использовать std::list. Поиск является линейным в обоих случаях, но добавление элементов является постоянным в std::list.
I guess they're all the same, since data isn't ordered - Нет, это не так. Если бы они были, был бы только один контейнер. Каждый контейнер имеет свои преимущества и недостатки, для разных ситуаций используются разные контейнеры.
Немного информации о векторе:
std::vector имеет емкость , поэтому он имеет методы capacity() и size(). Они оба разные. Итак, предположим, что емкость равна 4, и у вас есть 2 элемента, тогда размер будет равен 2. Итак, добавление еще одного элемента увеличит размер (будет 3), и все это очень быстро.
Но что происходит, когда вам нужно добавить 5+ элементов, а емкость равна 4? Выделена совершенно новая память, все старые элементы скопированы в новую память, все старые элементы уничтожены (их деструкторы называются, если пользовательские типы). Тогда старая память должна быть освобождена . Это дорогие операции, если вы думаете, что добавление / удаление элементов будет происходить чаще.
Вы можете избежать этого, используя метод std::vector::reserve, чтобы заранее зарезервировать часть памяти и не перераспределять новую память все время и копировать все снова и снова. Но это полезно, когда вы знаете приблизительный размер этих векторов. Я полагаю, что в вашей ситуации это не так (резервирование большого объема памяти также не является хорошим решением - вам не следует тратить память просто так ) Так что, опять же, я бы предпочел std :: list.
Или двойной хеш.
В любом случае, такое выделение новой памяти и копирование объектов не будут происходить так часто, так как std::vector «умный» и когда выделяет новое пространство, он не увеличивает емкость только с 1 элементом или чем-то еще. Я думаю, что это удваивает, но я не уверен в этом. Argh, я не знаю, как именно это называется на английском языке .. Возможно, что-то вроде "накопительное время / память" или "накопительная сложность":? Не знаю: /
ПРИМЕЧАНИЕ: Что бы вы ни выбрали, я бы посоветовал вам обратить внимание на хэш-функцию. Это самое важное здесь. Контейнер хэша НЕ должен иметь слишком много элементов с одинаковым хэшем. Поэтому я советую искать хорошую хэш-функцию, и тогда это не будет иметь большого значения.
Надеюсь, что помог ((
)
РЕДАКТИРОВАТЬ: я бы порекомендовал вам эту статью - сравнение std::vector и std::deque - это отлично - сравнивает использование памяти (выделение, освобождение, увеличение), использование процессора и т. Д. рекомендую целый сайт для таких статей - их не так много, но они действительно хорошо написаны.