boost :: multi_index эффективность составных ключей
Долгое время читатель первый раз постер! Я поэкспериментирую с контейнером boost :: multi_index и у меня довольно глубокий вопрос, который, я надеюсь, может знать эксперт по бустам или контейнерам C ++ (мои знания в контейнерах C ++ довольно простые). Справочную документацию по составным ключам можно найти здесь: boost :: multi_index составные ключи.
При использовании составного ключа в документации указывается, что «Составные ключи сортируются по лексикографическому порядку, то есть сортировка выполняется по первому ключу, а затем по второму ключу, если первый равен, и т. Д.». Означает ли это, что структура хранится таким образом, что поиск определенного составного ключа из 2 частей займет O (n = 1) времени, т. Е. Контейнер отсортирован так, что имеется указатель непосредственно на каждый элемент, или выполняется повышение Контейнер извлекает список, который соответствует первой части составного ключа, а затем необходимо выполнить поиск элементов, соответствующих второй части ключа и, следовательно, медленнее?
Например, если бы я должен был поддерживать два контейнера вручную с использованием двух разных индексов и хотел бы найти элементы, которые соответствуют конкретному двухэтапному запросу, я бы, вероятно, отфильтровал бы первый контейнер для всех элементов, соответствующих 1-й части запроса, а затем отфильтровал бы результат для элементов, которые соответствуют 2-й части запроса. Таким образом, этот ручной метод будет эффективно включать два поиска. Эффективно ли делает это повышение или оно каким-то образом повышает эффективность за счет использования составных ключей?
Надеюсь, я объяснил себе здесь, но, пожалуйста, задавайте вопросы, и я сделаю все возможное, чтобы уточнить, что именно я имею в виду!
Решение
Поиск с использованием составных ключей не проходит никакой двухэтапной процедуры, как вы описали. composite_key-индуцированные упорядочения — это нормальные упорядочения, единственная особенность в этом состоит в его зависимости от двух или более ключей элемента, а не от одного.
Может быть, пример прояснит. Рассмотрим это использование composite_key:
struct element
{
int x,y,z;
};
typedef multi_index_container<
element,
indexed_by<
ordered_unique<
composite_key<
element,
member<element,int,&element::x>,
member<element,int,&element::y>,
member<element,int,&element::z>
>
>
>
> multi_t;
Результирующий контейнер в некотором смысле эквивалентен этому:
struct element_cmp
{
bool operator()(const element& v1, const element& v2)const
{
if(v1.x<v2.x)return true;
if(v2.x<v1.x)return false;
if(v1.y<v2.y)return true;
if(v2.y<v1.y)return false;
return v1.z<v2.z;
}
};
typedef std::set<element,element_cmp> set_t;
composite_key автоматически генерирует код, эквивалентный к element_cmp::operator()и дополнительно допускает поиск только по первым n ключам, но базовая структура данных не меняется в зависимости от случая использования std::set,
Другие решения
Других решений пока нет …