Ich muss den Index eines Elements in std :: set finden. Dieser Index kann als die Entfernung des Iterators vom Anfang visualisiert werden. Eine Möglichkeit kann sein:
%Vor%Dies dauert eindeutig O (n) Zeit. Aber wir wissen, dass die Entfernung von der Wurzel in einem binären Suchbaum, wie sie intern implementiert wird, in O (log n) Zeit gefunden werden kann.
Ist ihre Möglichkeit, dasselbe zu implementieren, um den Index in O (log n) -Zeit in C ++ zu finden, festgelegt?
Sie können sortierte std::vector<int> verwenden. Wenn es sortiert ist, können Sie das Element in O(log n) finden. Und Sie können Entfernung in konstanter Zeit O(1) finden.
Nach sortiertem Vektor meine ich, dass Sie nach jedem Einfügen (oder nach vielen Einfügungen) std::sort(v.begin(), v.end());
Wenn dein Typ in std::set<T> nicht so hell ist wie int - kannst du beides behalten - std::set<T> und sortierten Vektor von Iteratoren std::vector<std::set<T>::iterator> . Aber es könnte nicht trivial sein, diese Strukturen synchron zu halten. Vielleicht kannst du eine ähnliche Position zu T hinzufügen? Oder behalte std::set<std::pair<T,int>, comp_first_of_pair<T>> wo comp_first_of_pair ist nur set nur nach T sortiert und die zweite int dient dazu, die Position im Set zu halten?
Nur ein paar Ideen - um sogar O(1) Distanzzeit zu haben ...
Sie können die Funktion std::set<>::find verwenden, um nach einem Element x zu suchen und zu berechnen die Entfernung zum ersten Iterator des Sets.
Wie jedoch Kommentare angeben, hängt die Laufzeit der Entfernung vom Typ des verwendeten Iterators ab. Im Falle eines Satzes ist dies ein bidirektionaler Iterator und die Entfernung ist O (n).
Sie können matematics nicht mit bidirektionalen Iteratoren verwenden. Es ist also nur akzeptabel, selbst zu zählen (wieviele int weniger als X, die Sie in den Satz eingefügt haben).
Wenn Sie jedoch die Phasen "Datensammlung" und "Datennutzung" sauber getrennt haben, ist es wahrscheinlich sinnvoll, std :: set durch den sortierten std :: vector . Es ist schwieriger zu pflegen, aber hat eigene Vorteile, einschließlich Iterator-Matematik (so können Sie mit O (log n) mit std :: binary_search und der Entfernung mit O (1))
suchen Wenn der Index den
std::map .
Das bedeutet natürlich, dass Sie diesen Cache aktualisieren müssen. std::vector . Das ist nicht so schlimm, wie es zuerst aussehen könnte.
Wenn Sie den Vektor immer sortiert halten, können Sie ihn wie ein set verwenden.
Die Leistung wird ähnlich wie set sein.
Der größte Nachteil ist: Der Knoten wird möglicherweise viel kopiert.
(Dies kann durch Verwendung von Zeigern kompensiert werden, boost:shared_ptr oder std::unique_ptr [nur c ++ 11])
std::lower_bound . insert( lower_bound(b,e,x), x )