Контейнер, подобный карте

#c #data-structures

#c #структуры данных

Вопрос:

Мне нужен специальный контейнер, который похож на мультимап двух типов: T1 и T2 : каждая «строка» в контейнере содержит T1 и T2 . Требования, которые мне нужны от него, таковы:

Быстрая вставка строки ( T1 и T2 ), O (log n) в multimap, что нормально.
Быстрый запрос всех строк, которые содержат T1 , O (log n) в multimap, который в порядке.
Быстрое удаление строки на основе T1 и T2 , O(k * log n) в multimap, что плохо.

Есть ли лучший контейнер для этих требований в библиотеках Boost или SGI STL?
Редактировать:
Если это кому-нибудь поможет, T1 это enum и T2 — пара из двух int s.

1. Если вы можете добавить какое-либо представление о свойствах T1 и T2, это было бы полезно.

2. @CaptainGiraffe: добавлено при редактировании.

3. В зависимости от типов T1 и T2 , возможно boost::unordered_multimap ?

4. @Chad: у него все еще низкая производительность на 3.

5. За пределами реальной базы данных нет структуры данных, которая давала бы вам все требуемые характеристики производительности сразу. Это очень редкая комбинация функциональных возможностей, требующая эффективного использования значения в качестве ключа, но только для операций удаления. Насколько вам действительно нужна меньшая, чем линейная производительность при удалении?

Ответ №1:

Рассматривали ли вы возможность использования a std::set ?

Использование ваших элементов в качестве единого составного ключа:

Вставка и удаление рассматриваются как обычно.
Поиск выполняется с помощью комбинации lower_bound и upper_bound (оба O(log N)), которая работает, поскольку вы можете определить минимальные и максимальные элементы для вашей пары.

1. Как я могу определить минимум и максимум для моей пары?

2. @Dani: пара лексически упорядочена, поэтому, если у вас есть pair<T,U> пара, состоящая из минимума T и минимума U , будет минимальной парой, а также для максимума. Если вы используете числа, вы можете включить <limits> , а затем использовать: std::numeric_limits<T>::min() чтобы получить минимум для вашего типа.