Добрый день. Существует обертка на некоторым контейнером, которая занимается тем, что вставляет в этот контейнер указатели и периодически достает элемент, который имеет наименьшее значение ключа ( тип ключа unsigned long ). Дело в том, что в этом контейнере может хранится ~40M этих указателей. И вставка в контейнер происходит достаточно интенсивно. Сейчас работает std::multimap, он дает в принципе достаточно приемлимое время вставки, но пока максимальное число элементов ~2M. Настораживает потребление памяти этим map которое, будет при 40M и скорость (ведь у него время поиска log(n), если я не ошибаюсь). Пробовал использовать хэшированные контейнеры, но в моей реализации все время съедает операции с вектором, при помощи которого он реализован, даже если место заранее резервировать, по времени он работает примерно так же как и multimap. Вопросов несколько:
1. Имеет ли смысл выносить вставку в контейнер в отдельный поток (запрос элемента из контейнера не намного реже вставки)? Если имеет, то как это обычно организовывается?
2. Имеет ли смысл использовать для map свой аллокатор?
3. Какой же контейнер все таки выбрать?