установить против вектора с пользовательским итератором

Question

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

Мне нужен контейнер, который обеспечивает проверку дубликатов на вставке (например, std::set, но позволяет мне изменять уже имеющиеся элементы (например, std::vector). Кроме того, поиск элементов должен быть относительно быстрым (что предпочтет * 1005) * снова). Было бы лучше использовать вектор и, возможно, пользовательский insert_iterator, проверяющий дубликаты, вместо изменения элементов набора путем их удаления и повторной вставки?

Спасибо

Answer 1

Что мешает вам использовать std::set?Если вам нужно изменить элемент, скопируйте его, сотрите его, а затем вставьте заново.

Answer 2

Вы изучали использование карты?

Ссылка

Карта может быть хорошим решением вашей проблемы.

Answer 3

Если у вас длинные строки и производительность критична, то вы можете застревать в специальном контейнере, который заключает в себе что-то вроде параллели vector<string> и set<string *>.Предоставьте пользовательский компаратор для набора, чтобы он разыменовывал указатель для сравнения.Чтобы изменить элемент, удалите указатель из набора, измените строку, а затем снова вставьте указатель.

Это немного запутанно, когда вы хотите удалить элементы контейнера, поэтому вы захотите использовать некоторую форму lazyудаление.В этот момент вы очень близки к полноценному пулу свободных объектов для ваших строк.

Если вы используете вектор строк в критичном для производительности коде, то следите за перераспределением векторов, котороевручную скопируйте каждую строку в новый фрагмент памяти.Вы можете обойти это, наблюдая за предстоящим перераспределением, создавая новый вектор пустых строк (предварительно зарезервированный для двойного размера), а затем используя string :: swap для каждого элемента, чтобы переместить старые данные в новый большой вектор.

Все станет намного лучше, когда семантика перемещения c ++ 0x станет широко доступной.