расстояние между std :: set begin () и std :: set итератором в O (logn)

Question

расстояние между std :: set begin () и std :: set итератором в O (logn)

Мне нужно найти индекс элемента в std :: set. Этот индекс может быть визуализирован как расстояние итератора от начала.
Одним из способов может быть:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);

Это явно занимает O (N) время. Но мы знаем, что расстояние от корня в бинарном дереве поиска, реализованное внутренним заданием, может быть найдено за O (log n).

Есть ли какой-либо способ реализовать то же самое, чтобы найти индекс за время O (log n) в наборе C ++?

9

c++iterator set std stl

Решение

Другие решения

Вы можете использовать функцию std::set<>::find искать элемент x и вычислить расстояние до первого итератора множества.

std::distance(s.begin(), s.find(x))

Однако, как показывают комментарии, время выполнения расстояния зависит от типа используемого итератора. В случае множества это двунаправленный итератор, а расстояние равно O (n).

4

Вы не можете использовать математику с двунаправленными итераторами. Так что единственный приемлемый способ — это посчитать самостоятельно (сколько ИНТ меньше X вы вставили в набор).

Но если вы четко разделили этапы «сбора данных» и «использования данных» — возможно, стоит заменить станд :: набор с отсортированным станд :: вектор. Его сложнее поддерживать, но у него есть свои преимущества, включая математику итератора (так что вы можете получить поиск с помощью O (log n) с помощью станд :: binary_search и расстояние с O (1))

1

Если вычисление индекса действительно Ваше узкое место, тогда я вижу 2 варианта:

Сохраните индекс. Либо в самих узлах, либо в отдельном std::map,
Конечно, это означает, что вы должны держать этот кэш обновленным.
Использовать std::vector, Это не так плохо, как может показаться на первый взгляд.
Если вы сохраняете вектор всегда отсортированным, вы можете использовать его как set,
Производительность будет похожа на set,
Самый большой недостаток: узел может быть скопирован много раз.
(Это можно компенсировать с помощью указателей, boost:shared_ptr или же std::unique_ptr [только c ++ 11])

Чтобы найти элемент, который вы используете std::lower_bound,
Вместо insert / push_back вы делаете: insert( lower_bound(b,e,x), x )

1

Источник

Accepted Answer

Вы можете использовать отсортированный std::vector<int>, Если это отсортировано, вы можете найти элемент в O(log n), И вы можете найти расстояние в постоянном времени O(1),

Под отсортированным вектором я подразумеваю, что после каждой вставки (или после множества вставок) вы делаете std::sort(v.begin(), v.end());

Если ваш тип внутри std::set<T> не такой легкий как int — вы можете сохранить оба — std::set<T> и отсортированный вектор итераторов std::vector<std::set<T>::iterator>, Но было бы несложно поддерживать синхронизацию этих структур. Может быть, вы можете добавить какую-то похожую позицию T? Или держать std::set<std::pair<T,int>, comp_first_of_pair<T>> где comp_first_of_pair это просто иметь set отсортировано только по T а второй int для сохранения позиции в наборе?

Всего несколько идей — чтобы иметь даже O(1) расстояние время …

3