distanza tra std :: set begin() e std :: set iterator in O (logn)

Question

Ho bisogno di trovare l'indice di un elemento in std :: set. Questo indice può essere visualizzato come la distanza dell'iteratore dall'inizio. Un modo può essere:

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

Questo richiede chiaramente O (n). Ma sappiamo che la distanza dalla radice in un albero di ricerca binario implementato dall'insieme internamente può essere trovata nel tempo O (log n).

È il loro modo di implementare lo stesso per trovare l'indice nel tempo O (log n) nel set C++?

Answer 1

È possibile utilizzare ordinato std::vector<int> . Se è ordinato, puoi trovare l'elemento in O(log n). E puoi trovare la distanza in tempo costante O(1).

Con vettore ordinato voglio dire che dopo ogni inserimento (o dopo molti inserimenti) si fa std::sort(v.begin(), v.end());

Se il tipo all'interno std::set<T> non è come la luce come int - è possibile mantenere entrambi - std::set<T> e ordinati vettore di iteratori std::vector<std::set<T>::iterator> . Ma non poteva essere banale mantenere sincronizzate queste strutture. Forse puoi aggiungere una posizione simile a T? Oppure mantenere std::set<std::pair<T,int>, comp_first_of_pair<T>> dove comp_first_of_pair è solo per avere set ordinati solo per T e il secondo int è per mantenere la posizione nel set?

solo alcune idee - di avere anche O(1) momento distanza ...

Answer 2

È possibile utilizzare la funzione std::set<>::find per cercare un elemento x e calcolare lo distance sul primo iteratore del set.

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

Tuttavia, come i commenti indicano che il tempo di funzionamento della distanza dipende dal tipo di iteratore utilizzato. Nel caso di un set questo è un iteratore bidirezionale e la distanza è O (n).

Answer 3

Non è possibile utilizzare la matematica con iteratori bidirezionali. Quindi, solo il modo accettabile è quello di contare da solo (il numero int meno di X inserito nel set).

Ma, se si è in modo pulito separati "raccolta dati" e "fasi di utilizzo dei dati" - probabilmente vale la pena di sostituire std :: set con ordinato std :: vector. La sua più difficile da mantenere, ma hanno propri vantaggi, tra cui Matematica iteratore (in modo da poter ottenere la ricerca con O (log n) con std :: binary_search e la distanza con O (1))

Answer 4

Se il calcolo dell'indice è davvero il collo di bottiglia, poi vedo 2 opzioni:

• memorizzare l'indice. O nei nodi stessi o in un separato std::map. Ovviamente questo significa che devi tenere aggiornata questa cache.
• Utilizzare un std::vector. Non è così male come potrebbe sembrare in un primo momento. Se mantieni sempre il vettore ordinato, puoi usarlo come un set. Le prestazioni saranno simili a set. Il più grande svantaggio è che il nodo potrebbe essere copiato molto. (Questo può essere compensato utilizzando i puntatori, boost:shared_ptr o std::unique_ptr [solo C++ 11])
  Per cercare un elemento si utilizza std::lower_bound.
  Invece di inserimento/push_back fare: insert(lower_bound(b,e,x), x)