Эффективное удаление элементов в tr1 :: unordered_map

Question

Я экспериментирую с tr1 :: unordered_map и наткнулся на проблему, как эффективно удалять элементы. Метод «erase» предлагает удалить либо по ключу, либо по итератором. Я бы предположил, что последний будет более эффективным, так как первый предположительно включает в себя неявную операцию поиска. С другой стороны, мои исследования в интернете выяснили, что итераторы могут стать недействительными после вызова метод insert ().

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

Answer 1

Весь смысл неупорядоченных контейнеров в том, чтобы иметь максимально быстрое время поиска. Беспокоиться о времени, которое требуется, чтобы стереть элемент по ключевым звукам, как классический пример преждевременной оптимизации.

Answer 2

Если это имеет для вас большое значение, потому что вы используете итератор по какой-то другой причине, тогда C ++ 0x говорит о std::unordered_map (цитата из FDIS) в 23.2.5 / 11:

Члены insert и emplace не должны влиять на действительность итераторов, если (N + n)

Я не проверял, имеет ли спецификация tr1 такую ​​же гарантию, но это довольно логичнона ожидаемую реализацию.

Если вы можете использовать эту гарантию, то вы можете защитить свои итераторы до определенного момента.Однако, как говорит Марк, поиск в unordered_map должен быть быстрым.Хранение ключа, а не итератора, хуже, чем сохранение индекса, а не итератора в vector, но лучше, чем эквивалент map.

Answer 3

Да, insert() может сделать недействительными все итераторы.Поэтому я не думаю, что есть способ избежать (неявного) поиска.Хорошей новостью является то, что последний, вероятно, будет дешевым.