Wie bekomme ich einen unique_ptr aus einer priority_queue wieder heraus?

Athar

Kann mir gerade jemand verraten, wie das ohne const_cast gehen soll?
priority_queue bietet lediglich top() für den Elementzugriff an, was eine Referenz auf einen konstanten unique_ptr zurückgibt. Deswegen kann ich move() nicht einsetzen, release() auch nicht, copy-constructible sind unique_ptr sowieso nicht und einfach die Referenz nehmen geht auch nicht, da das Element sofort aus der priority_queue verschwinden muss (womit ja die Referenz ungültig werden würde).
Hab ich was übersehen?

314159265358979

Interessant. Der Standard hat hierfür wie es scheint tatsächlich keine Lösung parat - offenbar ein Bug. Sollte man mal reporten.

krümelkacker

Ich schätze, priority_queue, set und multiset lassen Dich nicht die gespeicherten Objekte ändern, da Du als Benutzer dann sonst die Sortierung versehentlich durcheinander bringen könntest. Der Sortierschlüssel sollte sich ja nicht verändern. Stattdessen könntest Du ja eine std::multimap<> nehmen.

Das ist schon irgendwie unbefriedigent. Aber ich finde es auch ein bisschen fragwürdig, Zeiger-artige Objekte in diesen Container einfügen zu wollen, da ja trotz const hintenrum der Sortierschlüssel verändert werden kann.

314159265358979

Man brauchte wohl eine Art .pop(), das mit std::move() .top() zurückgibt. Mit C++0x sollte das ja ohnehin kein Problem sein, das zu ändern. Und Code dürfte dadurch auch keine kaputt gemacht werde, oder überseh ich was?

krümelkacker

314159265358979 schrieb:

Man brauchte wohl eine Art .pop(), das mit std::move() .top() zurückgibt. Mit C++0x sollte das ja ohnehin kein Problem sein, das zu ändern. Und Code dürfte dadurch auch keine kaputt gemacht werde, oder überseh ich was?

Dass es in C++98/03 an dieser Stelle kein pop gibt, welches eine Kopie zurückgibt, liegt daran, dass man mit so einem Design keine starke Garantie bzgl Ausnahmesicherheit geben kann.

value_type pop_and_get_popped_value()
{
  value_type result ( std::move(this->non_const_top()) );
  this->pop();
  return result; // <-- Ausnahme?
}

Im Falle von move-only-Typen sehe ich aber keine andere Möglichkeit als ein kombiniertes "pop&getvalue" anzubieten. Wenn ein Move-Ctor eine Ausnahme schmeißt, hat man dann eben Pech gehabt.

brotbernd

top und pop sind aus Gründen der Exceptionsicherheit von einander getrennt (Und damit pop keine Kopie zurückgeben muss, was allerdings durch move ctors tatsächlich hinfällig wäre). Da ändert sich afaik auch mit c++11 nichts dran, denn auch move ctors können werfen. D.h. wenn pop das erste Element entfernt, eine rvalue Referenz zurückgibt und dann der move ctor eine Ausnahme wirft, ist das Element verloren. Außerdem hat natürlich nicht jeder Typ einen move ctor.
So ein pop macht also nur für Typen mit noexcept move ctor Sinn... nicht sehr generisch.

Ich denke hier hilft nur ein eigener unique_ptr spezialisierter push_heap/pop_heap Adapter.

Nexus

brotbernd schrieb:

Da ändert sich afaik auch mit c++11 nichts dran, denn auch move ctors können werfen.

Aber dürfen sie das auch? Würde nämlich exceptionsicheres Programmieren unnötig verkomplizieren.

Semantisch gesehen besteht jedenfalls kein Anlass dazu, da ein Move im Prinzip in jedem Fall über ein Swap implementiert werden kann, und letzteres bei korrekter Implementierung immer die Nothrow-Garantie unterstützt.

camper

So wie ich es sehe fehlt ein non-const overload für top(). Die Spezifikation könnte dann dahingehend lauten, dass falls diese Referenz dazu verwendet wird, das Objekt zu ändern, zwingend ein pop() die nächste Operation auf dem Adapter sein muss (um die Konsistenz zu wahren).

krümelkacker

Nexus schrieb:

Aber dürfen [move ctors exceptions schmeißen]? Würde nämlich exceptionsicheres Programmieren unnötig verkomplizieren.

Es ist nicht verboten. Mag sein, dass der eine oder andere Container dazu noch extra etwas zu sagen hat. Es gibt jedenfalls eine Hilfsfunktion move_if_noexcept, welche man statt move verwenden kann, wenn man im Falle von Ausnahme-schmeißenden Move-Ctors lieber auf den Copy-Ctor zurückfallen würde. Damit kann z.B. die vector<>-Klasse beim Vergrößern der Kapazität die starke Garantie bzgl Ausnahmesicherheit geben.

Nexus schrieb:

Semantisch gesehen besteht jedenfalls kein Anlass dazu, da ein Move im Prinzip in jedem Fall über ein Swap implementiert werden kann, und letzteres bei korrekter Implementierung immer die Nothrow-Garantie unterstützt.

Denke mal an Objekte, die aus mehreren kleineren zusammengesetzt werden. Z.B.

struct dings {
  std::string name;
  irgendwas_anderes bums;
};

wobei std::string "move-enabled" ist, aber irgendwas_anderes nicht. Der Compiler wird hier, weil irgendwas_anderes keinen Move-Ctor hat, auch keinen Move-Ctor für dings generieren. Das ist aber leider verschenkte Performanz. Wenigstens ein Teil des Objekts könnte ja "gemovet" werden. Wenn eine Ausnahme selten bis gar nicht fliegt, könnte sich das lohnen. Und wenn Dir hier eine starke Garantie wichtig ist, dann verwendest Du auf Anwenderseite eben nur move_if_noexcept.

struct dings {
  std::string name;
  irgendwas_anderes bums;

  dings(dings const&) = default;
  dings(dings     &&) = default;
  dings& operator=(dings const&) = default;
  dings& operator=(dings     &&) = default;
};

So besitzt dings zwar einen Move-Ctor, allerdings einen, der nicht garantiert, keine Ausnahme zu schmeißen -- also keinen noexcept-move-ctor.

dings a = ...;
dings b = std::move_if_noexcept(a); // Kopieren
dings c = std::move(b);             // Move

Ich denke, in den anderen Fällen, wo automatisch (also ohne ein explizites std::move) der move-ctor verwendet wird, wäre das mit einer Ausnahme nicht besonders schlimm.

Der Grund, warum man also einen Ausnahme schmeißenden Move-Ctor anbieten wollen würde ist der, dass ein Teil des Objekts effizient "gemovet" werden kann und ein anderer Teil leider nur kopiert werden kann, wobei das Kopieren eine Ausnahme schmeißen könnte.

Nexus

Danke für die Antwort!

krümelkacker schrieb:

Es ist nicht verboten. Mag sein, dass der eine oder andere Container dazu noch extra etwas zu sagen hat. Es gibt jedenfalls eine Hilfsfunktion move_if_noexcept, welche man statt move verwenden kann, wenn man im Falle von Ausnahme-schmeißenden Move-Ctors lieber auf den Copy-Ctor zurückfallen würde.

Ja, eben, verkompliziert generische Programmierung. Und Nothrow-Garantie hat man auch nicht mehr.

krümelkacker schrieb:

Denke mal an Objekte, die aus mehreren kleineren zusammengesetzt werden. Z.B. [...] wobei std::string "move-enabled" ist, aber irgendwas_anderes nicht.

Das Problem ist ja hier, dass irgendwas_anderes nicht move-enabled ist, daher kann auch keine Nothrow-Garantie durchgesetzt werden. Ich schrieb ja "im Prinzip" und "bei korrekter Implementierung". Zumindest sehe ich nichts, was grundsätzlich gegen noexcept -Move-Operationen spricht, sofern die unterliegenden Typen dies ebenfalls unterstützen. Und am Ende der Kette hat man fundamentale Typen, die sowieso noexcept -movable sind.

Es ist genau das Gleiche wie bei swap() : Es kann nur die Nothrow-Garantie bieten, falls die zugrunde liegenden Typen dies auch tun.

krümelkacker schrieb:

Und wenn Dir hier eine starke Garantie wichtig ist, dann verwendest Du auf Anwenderseite eben nur move_if_noexcept.

Aber dann ist std::move_if_noexcept() wahrscheinlich sehr konservativ – wenn man nicht selbst Move-Konstruktor definiert und als noexcept kennzeichnet, wird eine Kopie gemacht? Ist etwas schade, da man sich so jeweils wieder um die Grossen Fünf kümmern muss. Da ist mir std::move() lieber, vor allem weil solche Kopier-Exceptions extrem selten auftreten.

krümelkacker

Nexus schrieb:

krümelkacker schrieb:

Und wenn Dir hier eine starke Garantie wichtig ist, dann verwendest Du auf Anwenderseite eben nur move_if_noexcept.

Aber dann ist std::move_if_noexcept() wahrscheinlich sehr konservativ – wenn man nicht selbst Move-Konstruktor definiert und als noexcept kennzeichnet, wird eine Kopie gemacht?

Nein. Die Regeln sind schon recht intelligent:

Implizit deklarierte Spezialfunktionen bekommen eine entsprechende exception-specification je nachdem, was diese Funktionen direkt für andere Funktionen aufrufen, ggf ein noexcept oder throw().
Eine per =default; deklarierte Funktion bekommt auch eine solche exception-specification ganz automatisch, ohne dass man hier selbst noexcept(fieser_langer_ausdruck) hinschreiben muss.
Ein Destruktor, den man selbst ohne exception-specification deklariert hat, bekommt automatisch ein noexcept(true) verpasst.

Was bedeutet das? Das bedeutet, dass z.B. die Klasse

struct xy {
  std::string x;
  std::string y;
};

"nothrow_move_constructible" und "nothrow_move_assignable" wird.

Nexus schrieb:

Ist etwas schade, da man sich so jeweils wieder um die Grossen Fünf kümmern muss. Da ist mir std::move() lieber, vor allem weil solche Kopier-Exceptions extrem selten auftreten.

Wenn Du keine starke Garantie bei einer "move construction" brauchst, nimm std::move. std::move_if_noexcept geht betrachtet übrigens nur den move-ctor und nichts anderes. Wenn Du selbst solche Funtionen implementierst, und ein noexcept wäre passend, sollte das noexcept nicht vergessen werden. Und sonst werden ja automatisch die richtigen exception-specs verwendet, sogar bei der =default;-Syntax.

Alle Angaben ohne Gewähr. Ich werde mir später nochmal die Regeln zu Gemüte führen... --- vielleicht nen kleinen Artikel drüber schreiben als Gedächtnisstütze.

kk

Nexus

Ah, das tönt schon mal viel besser. Danke