odległość między std :: set begin() i std :: set iterator w O (logn)

Question

Potrzebuję znaleźć indeks elementu w std :: set. Indeks ten można wizualizować jako odległość iteratora od początku. Jednym ze sposobów może być:

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

Wyraźnie wykonuje O (n). Ale wiemy, że odległość od katalogu głównego w drzewie wyszukiwania binarnego zaimplementowana wewnętrznie przez zestaw może być znaleziona w czasie O (log n).

Czy istnieje sposób ich wprowadzenia w celu znalezienia indeksu w czasie O (log n) w C++?

Answer 1

można użyć klasyfikowane std::vector<int> . Jeśli jest posortowana, możesz znaleźć element w O(log n). Możesz znaleźć odległość w stałym czasie O(1).

Przez segregowanych wektora To znaczy, że po każdym włożeniu (lub po wielu wstawek) robisz std::sort(v.begin(), v.end());

Jeśli typ wewnątrz std::set<T> nie jest tak lekki jak int - można trzymać zarówno - std::set<T> i sortowane wektor iteratorów std::vector<std::set<T>::iterator> . Ale nie jest łatwo utrzymać te struktury w synchronizacji. Może możesz dodać pozycję podobną do T? Lub zachowaj std::set<std::pair<T,int>, comp_first_of_pair<T>> gdzie comp_first_of_pair jest po prostu mieć set posortowane tylko przez T, a drugie int służy do utrzymywania pozycji w zestawie?

tylko kilka pomysłów - aby mieć czas na odległość nawet O(1) ...

Answer 2

Możesz użyć funkcji std::set<>::find, aby wyszukać element x i obliczyć wartość distance w pierwszym iteratorze zestawu.

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

Jednak, jak wskazują komentarze, czas wykonywania odległości zależy od zastosowanego typu iteratora. W przypadku zestawu jest to dwukierunkowy iterator, a odległość O (n).

Answer 3

Nie można używać matematyki z iteratorami dwukierunkowymi. Tak więc jedynym akceptowalnym sposobem jest policzenie przez siebie (ile razy wstawiłeś do zestawu).

Ale jeśli równo rozdzielone „zbieranie danych” i „Transmisja danych” etapy - chyba warto wymienić std :: set z posortowanej std :: vector. Jego trudniejsze do utrzymania, ale mają własne korzyści, w tym matematics iterator (dzięki czemu można uzyskać wyszukiwania z O (log n) z std :: binary_search a odległość z O (1))

Answer 4

Jeśli obliczanie indeksu jest naprawdę Twój wąskie gardło, a potem widzę 2 opcje:

• przechowywać indeksu. W samych węzłach lub w oddzielnym std::map. Oczywiście oznacza to, że musisz aktualizować tę pamięć podręczną.
• Użyj numeru std::vector. Nie jest tak źle, jak mogłoby się wydawać na początku. Jeśli wektor będzie zawsze sortowany, możesz go użyć jako set. Wydajność będzie podobna do wydajności set. Największą wadą jest: węzeł może być często kopiowany. (To może być kompensowane za pomocą wskaźników, boost:shared_ptr lub std::unique_ptr [C++ 11 tylko])
  Aby wyszukać element użyć std::lower_bound.
  Zamiast insert/push_back robisz: insert(lower_bound(b,e,x), x)