Какой отсортированный контейнер STL использовать для быстрой вставки и поиска с помощью специального ключа?

Question

У меня есть некоторые данные с ключом, связанным с каждым элементом данных. Ключ состоит из двух частей: назовем их color и id. Я хочу перебрать контейнер по цвету, чтобы ускорить рендеринг, а также я хочу найти элементы в контейнере только по идентификатору.

Я попытался использовать для этого std :: map с ключом

class MyKey {
public:
  int color;
  int id;
  bool operator<(...)
  bool operator==(...)
};

Но я не могу предоставить оператор <, который сохранял бы данные, отсортированные по цвету, и в то же время позволял бы map :: find работать только с идентификатором (т. Е. Без информации о цвете). </p>

Я хочу, чтобы операции вставки и поиска выполнялись быстро (например, O (log (n))).

Есть идеи, какой контейнер я мог бы использовать для реализации этого?

Answer 1

Адаптируйте пример здесь из Boost.Multi_index на основе следующих модификаций:

typedef multi_index_container<
    MyKey,
    indexed_by<ordered_unique<identity<MyKey> >,
    ordered_non_unique<member<MyKey,int,&MyKey::color> >
  > 
> DataSet;

Answer 2

Попробуйте Boost.BiMap, это карта с 2 видами.

В противном случае есть более сложный Boost.MultiIndex.

Answer 3

Если вы предпочитаете писать свои собственные, а не использовать Boost (глупо, на мой взгляд), вы можете создать класс, содержащий две карты. Один для сопоставления цвета, а другой для идентификатора карты. Значения карты будут указателями. Вы бы определили операции вставки и поиска для вашего нового класса. Вставка будет new структурой данных и вставит указатель в обе карты. Операции поиска позволят найти элемент с использованием любой карты в зависимости от ситуации. Для операций удаления / удаления это немного сложнее: вам нужно найти структуру данных по карте, а затем удалить ее с обеих карт, вероятно, используя данные в структуре данных, чтобы найти другую запись карты. *