подталкивания multi_index: получить уникальные значения не-уникального ключа

Question

У меня есть boost::multi_index_container, элементы которого являются структурами, как это:

struct Elem { 
    A a; 
    B b; 
    C c; 
}; 

Главный ключ (в смысле базы данных) является composite_key из a и b. Другие ключи существуют для выполнения различных типов запросов.

Теперь мне нужно получить набор из всех разных значений c. Эти значения всех средства не уникальными, но перебор всех записей (хотя заказано), или с использованием std::unique кажется довольно отходы, учитывая, что числа различных значений c, как ожидается, будет < <, чем общая количество записей (скажем, от 10 до 1000).

Я пропустил простой способ получить этот результат более эффективно?

Answer 1

Я просмотрел документацию Boost.MultiIndex и не могу найти способ сделать то, что вы хотите. Мне интересно узнать, выполнимо ли это.

Возможно, самое лучшее, что вы можете сделать, это поддерживать std::map<C, size_t> (или хеш-карту) рядом с вашим multi_index_container и держать их обоих «синхронизированными».

Карта сопоставляет значение C с его количеством встречаемости (частотой). Это по существу гистограмма значений C. Каждый раз, когда вы добавляете Elem к вашему multi_index_container, вы увеличиваете соответствующую частоту в гистограмме. Когда вы удаляете Elem с multi_index_counter, вы уменьшаете соответствующую частоту в гистограмме. Когда частота достигает нуля, вы удаляете эту запись с гистограммы.

Чтобы получить набор различных значений C, вы просто перебираете пары <key,value> в гистограмме и смотрите на часть каждой пары парадов key. Если вы использовали std::map, то отдельные значения C выйдут отсортированы.

Если вы собираетесь рассматривать набор различных значений C только один раз (или редко), то описанный выше подход может быть чрезмерным. Более простой подход состоял бы в том, чтобы вставить все значения C в std::set<C> и затем выполнить итерацию по набору для получения различных значений C.

Вы сказали, что набор различных C намного меньше, чем общее число C. Поэтому подход std::set<C> должен тратить гораздо меньше места, чем копирование C на std::vector, сортировка вектора, а затем запуск std::unique.

Давайте сравним временную сложность копирования с множеством по сравнению с копированием в вектор, сортировкой, затем запуском unique. Пусть N - общее число значений C, а M - количество различных значений C. Установленный подход, по моим расчетам, должен иметь временную сложность O (N * log (M)). Так как M мало и мало растет с более высокими N, сложность эффективно становится O (N). С другой стороны, сортировка + уникальная техника должна иметь временную сложность O (N * log (N)).