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

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

4 голосов
/ 16 февраля 2011

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

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

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

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

Не хватает ли мне простого способа получить этот результат более эффективно?

1 Ответ

1 голос
/ 17 февраля 2011

Я изучил документацию 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)).

...