Entfernung zwischen std::set begin() und std::set iterator in O(logn)

Brauche ich, um zu finden, die den index eines Elements in std::set. Dieser index kann dargestellt werden, wie der Abstand der iterator von Anfang an.
Ein Weg kann sein:

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

Diese eindeutig in O(n) Zeit. Aber wir wissen, dass der Abstand von der Wurzel, die in einem binären Suchbaum durchgeführt durch die intern festgelegt werden können, finden sich in O(log n) Zeit.

Ist deren irgendeiner Weise zu implementieren, die gleichen zu finden, der index in O(log n) Zeit in C++ festlegen?

  • Warum würden Sie müssen den index?
  • Sind Sie sicher, dass es möglich ist, um den Abstand in O(log n) Zeit in einem binären Suchbaum? set ist in der Regel ein rot-schwarz-Baum, die nicht über eine Menge von Informationen auf den einzelnen Knoten, über wie viele Elemente sind in Ihrer linken und rechten Teilbäume jeweils. Denken Sie daran, dass Sie sind nicht auf der Suche für die Entfernung direkt aus der Wurzel, Sie suchen für die Gesamtzahl der Blätter auf der linken Seite des Blattes, die Sie haben.
  • Ohh, so dass Ihr nicht jede Möglichkeit zur Berechnung der index in O(logn) in der R-B-Baum dann?
InformationsquelleAutor divanshu | 2012-09-21
  1. 3

    Können Sie sortiert std::vector<int>. Wenn es sortiert ist, können Sie finden element im O(log n). Und können Sie finden Abstand in konstanter Zeit O(1).

    Durch sortiert vector-ich meine, dass nach jeder insertion (oder nach vielen Einfügungen) Sie std::sort(v.begin(), v.end());

    Wenn Ihr Datentyp in std::set<T> ist nicht so leicht, wie int - können Sie beide behalten - std::set<T> sortiert und Vektor-Iteratoren std::vector<std::set<T>::iterator>. Aber könnte es nicht trivial zu halten, diese Strukturen zu synchronisieren. Vielleicht können Sie fügen Sie einige gerne Stellung zu T? Oder halten std::set<std::pair<T,int>, comp_first_of_pair<T>> wo comp_first_of_pair ist nur für set sortiert nur durch T und die zweite int ist für das halten der position im Satz?

    Nur ein paar Ideen - haben auch O(1) Distanz Zeit...

    • Aber die Sortierung nach jeder Einfügung in std::vector würden die mich Kosten O(nlogn). Wo ist der Vorteil?
    • 1) Sie können die Sortierung nur nach einer Reihe von aufeinanderfolgenden Einfügungen. 2) die Kosten der Aufnahme in std::set<> ist O(log n) - n Einfügungen: O(n Log n). 3) Vielleicht sind Sie insert einmal - aber die Tests Strecke viele Male....
    • Danke @PiotrNycz 🙂
    InformationsquelleAutor PiotrNycz
  2. 4

    Können Sie die Funktion std::set<>::find suchen für ein element x und berechnen Sie die Entfernung der erste iterator des Satzes.

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

    Jedoch, wie die Kommentare zeigen die Laufzeit der Abstand hängt von der Art der iterator verwendet. Im Fall des Satzes dies ist ein bidirektionaler iterator und Distanz ist O(n).

    • Das ist O(log n + m), obwohl. Aber das beste, was Sie tun können, ist, soweit ich weiß.
    • Aber std::distance ist O(N) hier.
    • Ich weiß, über std::Entfernung, aber dies ist implementiert die gleiche Weise wie in der SCHRIFTLICHEN Frage und auf jeden Fall ist O(n).
    InformationsquelleAutor Danvil
  3. 1

    Können Sie nicht verwenden matematics mit bidirektionalen Iteratoren. Also nur akzeptable Weise zu zählen, indem Sie sich (wie viele int weniger als X, die Sie eingefügt eingestellt).

    Aber, wenn Sie sauber getrennt "data collection" und "data usage" Stufen - wahrscheinlich lohnt es sich zu ersetzen std::set mit sortiert std::vector. Seine schwieriger zu pflegen, sondern haben eigene Vorteile, einschließlich iterator matematics (so können Sie die Suche mit O(log n) mit std::binary_search und der Abstand O(1) )

    InformationsquelleAutor PSIAlt
  4. 1

    Wenn die Berechnung des index ist wirklich Ihren Engpass, dann sehe ich 2 Optionen:

    • Speichern Sie die index. Entweder in dem Knoten selbst oder in einem separaten std::map.
      Natürlich bedeutet dies, dass Sie zu halten dieser cache aktualisiert werden.
    • Verwenden std::vector. Das ist nicht so schlimm, wie es vielleicht auf den ersten Blick.
      Wenn Sie den vector immer sortiert, Sie können es verwenden, wie ein set.
      Die performance wird ähnlich sein set.
      Der größte Nachteil ist: der Knoten kann kopiert werden, eine Menge.
      (Dies kann kompensiert werden durch die Verwendung von Zeigern boost:shared_ptr oder std::unique_ptr [c++11])


      Zum nachschlagen eines Elements verwenden Sie std::lower_bound.

      Anstelle von insert/push_back Sie tun: insert( lower_bound(b,e,x), x )
    InformationsquelleAutor rtlgrmpf
  5. 1

    Finden Sie den index eines Elements in einer Menge in O(log(N)) eine geordnete Menge: https://www.geeksforgeeks.org/ordered-set-gnu-c-pbds/ . Umgesetzt wird dies als ein rot-schwarz Baum. Ich weiß, das Thema ist sehr alt, aber es könnte helfen, die Leser in die Zukunft.

    • Eher als link zu einer externen Ressource, bitte Auszug der relevanten Teile des es und fügen Sie es in Ihre Antwort.
    InformationsquelleAutor Robbinb1993
Schreibe einen Kommentar