Ich habe eine Anwendung (C ++), die meiner Meinung nach von einer STL gut bedient werden würdepriority_queue. Die Dokumentatio sagt:

Priority_queue ist ein Containeradapter, dh, er wird über einem zugrunde liegenden Containertyp implementiert. Standardmäßig ist der zugrunde liegende Typ ein Vektor, es kann jedoch explizit ein anderer Typ ausgewählt werden.

un

Priority Queues sind ein Standardkonzept und können auf viele verschiedene Arten implementiert werden. Diese Implementierung verwendet Heaps.

Ich hatte vorherangenomme Dastop() istO(1), und daspush() wäre einO(logn) (die beiden Gründe, warum ich mich für das @ entschieden hapriority_queue an erster Stelle) - aber die Dokumentation bestätigt oder bestreitet diese Annahme weder.

Näher betrachtet heißt es in den Dokumenten zum Sequence-Konzept:

Die Komplexität des Einfügens und Löschens einzelner Elemente hängt von der Reihenfolge ab.

Daspriority_queue verwendet einvector (standardmäßig) als Heap, der:

... unterstützt den wahlfreien Zugriff auf Elemente, das ständige Einfügen und Entfernen von Elementen am Ende sowie das lineare Einfügen und Entfernen von Elementen am Anfang oder in der Mitte.

Ich schließe daraus, dass mit der Standardeinstellungpriority_queue, top() istO(1) undpush() istO(n).

Frage 1 Ist das richtig? top() access isO(1) undpush() istO(n)?)

Frage 2 Würde ich in der Lage sein zu erreichenO(logn) Effizienz aufpush() wenn ich ein @ benutzt haset (odermultiset) anstelle einervector für die Implementierung despriority_queue? Welche Konsequenzen hätte dies? Welche anderen Operationen würden als Folge leiden?

NB .: Ich mache mir Sorgen um die Zeiteffizienz, nicht um den Platz.