Реализация карты с несколькими индексами на C++

Question

Я реализую карту с несколькими индексами в C++ 11, которую я хочу оптимизировать для определенных функций. Проблема, которую я сейчас пытаюсь решить, состоит в том, чтобы не хранить ключевые элементы более одного раза. Но позвольте мне объяснить.

Проблема возникла при сортировке гистограмм для их наложения в разные комбинации. Гистограммы имели имена, которые можно было разделить на маркеры (свойства).

Вот особенности я хочу, чтобы моя карта свойство иметь:

1. Уметь перебрать свойства в любом порядке;
2. Возможность возврата контейнера с уникальными значениями для каждого свойства;
3. Накопить значения свойств в том порядке, в котором они поступают, но иметь возможность сортировать свойства с помощью пользовательского оператора сравнения после заполнения карты;

У меня есть working implementation в C++ 11, используя std::unordered_map с std::tuple как key_type. Я накапливаю значения свойств, когда они поступают в кортеж forward_lists. Предполагаемое использование - перебирать списки для создания ключей.

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

Я знаю, что boost::multi_index имеет аналогичную функциональность, но мне не нужны накладные расходы при сортировке по мере поступления ключей. Я бы хотел, чтобы новые значения свойств хранились последовательно и только сортируемый postfactum. Я также посмотрел boost::flyweight, но в простейшем подходе списки будут тогда flyweight<T> вместо T, и я бы не хотел этого делать. (Если это лучшее решение, я определенно мог бы с ним жить.)

Я знаю, что списки стабильны, т. Е. Как только элемент создан, его указатель и итератор остаются в силе даже после вызова list::sort(). Зная, что можно что-то сделать с картой, чтобы устранить избыточные копии элементов кортежа? Может ли помочь вам использовать специализированный распределитель карт?

Спасибо за предложения.

Answer 1

Ваша карта должна быть от кортежей итераторов до ваших контейнеров-опоры.

Напишите хэш разыменования итераторов и объедините результат.

Замените форвардные перечни контейнеров с наборами, которые в первом порядке обозначают хэш, а затем содержимое.

Сделайте поиск первым, находящимся в наборе, а затем выполнив поиск в хеше.

Если вам нужен другой заказ для реквизита, у вас есть другой контейнер с итераторами.