Ressourcen aus den Schlüsseln von std :: map stehlen erlaubt?

15

Ist es in C ++ in Ordnung, Ressourcen von einer Karte zu stehlen, die ich danach nicht mehr benötige? Genauer gesagt, ich habe einen std::mapmit std::stringSchlüsseln und möchte einen Vektor daraus konstruieren, indem ich die Ressourcen der maps-Schlüssel mit stehle std::move. Beachten Sie, dass ein solcher Schreibzugriff auf die Schlüssel die interne Datenstruktur (Reihenfolge der Schlüssel) des Schlüssels beschädigt, mapaber ich werde sie danach nicht mehr verwenden.

Frage : Kann ich dies ohne Probleme tun oder führt dies zu unerwarteten Fehlern, beispielsweise im Destruktor von, mapweil ich auf eine Weise darauf zugegriffen habe, std::mapdie nicht dafür vorgesehen war?

Hier ist ein Beispielprogramm:

#include<map>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
int main(int argc, char *argv[])
{
    std::vector<std::pair<std::string,double>> v;
    { // new scope to make clear that m is not needed 
      // after the resources were stolen
        std::map<std::string,double> m;
        m["aLongString"]=1.0;
        m["anotherLongString"]=2.0;
        //
        // now steal resources
        for (auto &p : m) {
            // according to my IDE, p has type 
            // std::pair<const class std::__cxx11::basic_string<char>, double>&
            cout<<"key before stealing: "<<p.first<<endl;
            v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second));
            cout<<"key after stealing: "<<p.first<<endl;
        }
    }
    // now use v
    return 0;
}

Es erzeugt die Ausgabe:

key before stealing: aLongString
key after stealing: 
key before stealing: anotherLongString
key after stealing: 

BEARBEITEN: Ich möchte dies für den gesamten Inhalt einer großen Karte tun und dynamische Zuordnungen durch das Stehlen von Ressourcen speichern.

Phinz
quelle
3
Was ist der Zweck dieses "Diebstahls"? So entfernen Sie das Element aus der Karte? Warum machen Sie das dann nicht einfach (löschen Sie das Element von der Karte)? Das Ändern eines constWerts ist immer UB.
Ein Programmierer
anscheinend wird es zu ernsthaften Fehlern führen!
Rezaebrh
1
Keine direkte Antwort auf Ihre Frage, aber: Was ist, wenn Sie keinen Vektor, sondern einen Bereich oder ein Paar Iteratoren zurückgeben? Das würde ein vollständiges Kopieren vermeiden. In jedem Fall benötigen Sie Benchmarks, um den Fortschritt der Optimierung zu verfolgen, und einen Profiler, um Hotspots zu finden.
Ulrich Eckhardt
1
@ ALX23z Haben Sie eine Quelle für diese Aussage? Ich kann mir nicht vorstellen, wie das Kopieren eines Zeigers teurer ist als das Kopieren eines ganzen Speicherbereichs.
Sebastian Hoffmann
1
@SebastianHoffmann es wurde auf der letzten CppCon erwähnt, nicht sicher, auf welchem ​​Vortrag, tho. Die Sache ist std::stringhat Short-String-Optimierung. Das bedeutet, dass es eine nicht triviale Logik beim Kopieren und Verschieben gibt und nicht nur beim Zeigertausch. Außerdem bedeutet das Verschieben die meiste Zeit das Kopieren - damit Sie sich nicht mit ziemlich langen Zeichenfolgen befassen. Der statistische Unterschied war sowieso gering und variiert im Allgemeinen sicherlich abhängig davon, welche Art von Zeichenfolgenverarbeitung durchgeführt wird.
ALX23z

Antworten:

18

Sie führen ein undefiniertes Verhalten aus, mit const_castdem Sie eine constVariable ändern . Tu das nicht. Der Grund dafür constist, dass Karten nach ihren Schlüsseln sortiert sind. Das Ändern eines Schlüssels an Ort und Stelle bricht also die zugrunde liegende Annahme, auf der die Karte basiert.

Sie sollten niemals verwenden const_cast, um constaus einer Variablen zu entfernen und diese Variable zu ändern.

Davon abgesehen hat C ++ 17 die Lösung für Ihr Problem: std::map's extractFunktion:

#include <map>
#include <string>
#include <vector>
#include <utility>

int main() {
  std::vector<std::pair<std::string, double>> v;
  std::map<std::string, double> m{{"aLongString", 1.0},
                                  {"anotherLongString", 2.0}};

  auto extracted_value = m.extract("aLongString");
  v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                                std::move(extracted_value.mapped())));

  extracted_value = m.extract("anotherLongString");
  v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                                std::move(extracted_value.mapped())));
}

Und nicht using namespace std;. :) :)

druckermanly
quelle
Danke, ich werde es versuchen! Aber sind Sie sicher, dass ich nicht so machen kann wie ich? Ich meine, der mapwird sich nicht beschweren, wenn ich seine Methoden nicht aufrufe (was ich nicht tue) und vielleicht ist die interne Reihenfolge in seinem Destruktor nicht wichtig?
Phinz
2
Die Schlüssel der Karte werden erstellt const. Das Mutieren eines constObjekts erfolgt sofort nach UB, unabhängig davon, ob danach tatsächlich etwas darauf zugreift oder nicht.
HTNW
Diese Methode hat zwei Probleme: (1) Da ich alle Elemente extrahieren möchte, möchte ich nicht nach Schlüssel (ineffiziente Suche), sondern nach Iterator extrahieren. Ich habe gesehen, dass dies auch möglich ist, also ist das in Ordnung. (2) Korrigieren Sie mich, wenn ich falsch liege, aber für das Extrahieren aller Elemente entsteht ein enormer Aufwand (für das Ausbalancieren der internen Baumstruktur bei jeder Extraktion)?
Phinz
2
@phinz Wie Sie unter cppreference sehen können, extract wenn Iteratoren als Argument verwendet werden, hat sich die konstante Komplexität amortisiert. Ein gewisser Overhead ist unvermeidlich, aber wahrscheinlich nicht signifikant genug, um eine Rolle zu spielen. Wenn Sie spezielle Anforderungen haben, die hiervon nicht abgedeckt sind, müssen Sie Ihre eigenen implementieren map, um diese Anforderungen zu erfüllen. Die stdBehälter sind für den allgemeinen Gebrauch gedacht. Sie sind nicht für bestimmte Anwendungsfälle optimiert.
Walnuss
@HTNW Sind Sie sicher, dass die Schlüssel erstellt wurden const? In diesem Fall können Sie bitte angeben, wo meine Argumentation falsch ist.
Phinz
4

Ihr Code versucht, constObjekte zu ändern , sodass er ein undefiniertes Verhalten aufweist, wie die Antwort von druckermanly richtig hervorhebt .

Einige andere Antworten ( Phinz und Deuchie ) argumentieren, dass der Schlüssel nicht als constObjekt gespeichert werden darf, da das Knotenhandle , das sich aus dem Extrahieren von Knoten aus der Karte ergibt, den Nichtzugriffconst auf den Schlüssel ermöglicht. Diese Schlussfolgerung mag zunächst plausibel erscheinen, aber P0083R3 , das Papier, in dem die extractFunktionen eingeführt wurden , enthält einen eigenen Abschnitt zu diesem Thema, der dieses Argument ungültig macht:

Sorgen

In Bezug auf dieses Design wurden mehrere Bedenken geäußert. Wir werden sie hier ansprechen.

Undefiniertes Verhalten

Der theoretisch schwierigste Teil dieses Vorschlags ist die Tatsache, dass das extrahierte Element seinen konstanten Schlüsseltyp beibehält. Dies verhindert, dass Sie es verlassen oder ändern. Um dies zu lösen, haben wir die Schlüsselzugriffsfunktion bereitgestellt , die einen nicht konstanten Zugriff auf den Schlüssel in dem Element bietet, das vom Knotenhandle gehalten wird. Diese Funktion erfordert die Implementierung "magic", um sicherzustellen, dass sie bei Compiler-Optimierungen ordnungsgemäß funktioniert. Ein Weg, dies zu tun, ist mit einer Vereinigung von pair<const key_type, mapped_type> und pair<key_type, mapped_type>. Die Umwandlung zwischen diesen kann sicher unter Verwendung einer Technik erfolgen, die der std::launderbeim Extrahieren und Wiedereinsetzen verwendeten ähnlich ist .

Wir glauben nicht, dass dies ein technisches oder philosophisches Problem darstellt. Einer der Gründe , die Standard - Bibliothek existiert , ist nicht tragbar und magischen Code zu schreiben , dass der Client nicht in tragbaren C ++ schreiben kann (zB <atomic>, <typeinfo>, <type_traits>, etc.). Dies ist nur ein weiteres Beispiel. Alles, was Compiler-Anbieter benötigen, um diese Magie zu implementieren, ist, dass sie undefiniertes Verhalten in Gewerkschaften nicht zu Optimierungszwecken ausnutzen - und dies versprechen Compiler derzeit bereits (soweit es hier ausgenutzt wird).

Dies stellt eine Einschränkung für den Client dar, die, wenn diese Funktionen verwendet werden, std::pairnicht so spezialisiert werden kann, dass pair<const key_type, mapped_type>sie ein anderes Layout als haben pair<key_type, mapped_type>. Wir glauben, dass die Wahrscheinlichkeit, dass jemand dies tatsächlich tun möchte, praktisch Null ist, und im formalen Wortlaut beschränken wir jede Spezialisierung dieser Paare.

Beachten Sie, dass die Schlüsselelementfunktion der einzige Ort ist, an dem solche Tricks erforderlich sind, und dass keine Änderungen an den Containern oder Paaren erforderlich sind.

(Hervorhebung von mir)

LF
quelle
Dies ist eigentlich ein Teil der Antwort auf die ursprüngliche Frage, aber ich kann nur eine akzeptieren.
Phinz
0

Ich denke nicht, dass const_castÄnderungen in diesem Fall zu undefiniertem Verhalten führen, aber bitte kommentieren Sie, ob diese Argumentation korrekt ist.

Diese Antwort behauptet das

Mit anderen Worten, Sie erhalten UB, wenn Sie ein ursprünglich const-Objekt ändern, andernfalls nicht.

Die Zeile v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second));in der Frage führt also nicht genau dann zu UB, wenn das stringObjekt p.firstnicht als const-Objekt erstellt wurde. Beachten Sie nun, dass die Referenz überextract Zustände

Durch das Extrahieren eines Knotens werden die Iteratoren für das extrahierte Element ungültig. Zeiger und Verweise auf das extrahierte Element bleiben gültig, können jedoch nicht verwendet werden, solange sich das Element im Besitz eines Knotenhandles befindet. Sie können verwendet werden, wenn das Element in einen Container eingefügt wird.

Also, wenn ich extractdas node_handleentsprechende p, plebe weiterhin an seinem Lagerort. Aber nach der Extraktion darf ich movedie Ressourcen pwie im Code von druckermanlys Antwort wegnehmen . Dies bedeutet , dass pund damit auch das stringObjekt p.firstwurde nicht ursprünglich als konstantes Objekt erstellt.

Daher denke ich, dass die Änderung der mapSchlüssel des Benutzers nicht zu UB führt, und aus Deuchies Antwort geht hervor , dass auch die jetzt beschädigte Baumstruktur (jetzt mehrere gleiche leere Zeichenfolgenschlüssel) des mapnicht zu Problemen im Destruktor führt. Daher sollte der Code in der Frage zumindest in C ++ 17, in dem die extractMethode vorhanden ist, einwandfrei funktionieren (und die Aussage über gültige Zeiger gilt).

Aktualisieren

Ich bin jetzt der Ansicht, dass diese Antwort falsch ist. Ich lösche es nicht, weil andere Antworten darauf verweisen.

Phinz
quelle
1
Entschuldigung, Phinz, deine Antwort ist falsch. Ich werde eine Antwort schreiben, um dies zu erklären - es hat etwas mit Gewerkschaften und zu tun std::launder.
LF
-1

EDIT: Diese Antwort ist falsch. Freundliche Kommentare haben auf die Fehler hingewiesen, aber ich lösche sie nicht, weil in anderen Antworten darauf verwiesen wurde.

@druckermanly beantwortete Ihre erste Frage, die besagte, dass das mapgewaltsame Ändern der Schlüssel die Ordnungsmäßigkeit der mapinternen Datenstruktur (Rot-Schwarz-Baum) beeinträchtigt . Es ist jedoch sicher, die extractMethode zu verwenden , da sie zwei Dinge bewirkt: Bewegen Sie den Schlüssel aus der Karte und löschen Sie ihn dann, damit die Ordnungsmäßigkeit der Karte überhaupt nicht beeinträchtigt wird.

Die andere Frage, die Sie gestellt haben, ob sie beim Dekonstruieren Probleme verursachen würde, ist kein Problem. Wenn eine Karte dekonstruiert, ruft sie den Dekonstruktor jedes ihrer Elemente (mapped_types usw.) auf, und die moveMethode stellt sicher, dass es sicher ist, eine Klasse nach dem Verschieben zu dekonstruieren. Also mach dir keine Sorgen. Kurz gesagt, es ist die Operation move, die sicherstellt, dass es sicher ist, einen neuen Wert zu löschen oder der "verschobenen" Klasse neu zuzuweisen. Speziell für stringkann die moveMethode ihren Zeichenzeiger auf setzen nullptr, damit nicht die tatsächlichen Daten gelöscht werden, die beim Aufruf des Dekonstruktors der ursprünglichen Klasse verschoben wurden.


Ein Kommentar erinnerte mich an den Punkt, den ich übersah, im Grunde hatte er Recht, aber eines stimme ich nicht ganz zu: Es const_castist wahrscheinlich kein UB. constist nur ein Versprechen zwischen dem Compiler und uns. Objekte, von denen festgestellt wird , dass sie in Bezug auf ihre Typen und Darstellungen in binärer Form constimmer noch ein Objekt sind, wie diejenigen, die es noch nicht constsind. Wenn das constweggeworfen wird, sollte es sich so verhalten, als wäre es eine normale veränderbare Klasse. In Bezug auf move: Wenn Sie es verwenden möchten, müssen Sie ein &anstelle von a übergeben const &. Da es sich also nicht um ein UB handelt, wird das Versprechen einfach gebrochen constund die Daten werden verschoben.

Ich habe auch zwei Experimente mit MSVC 14.24.28314 und Clang 9.0.0 durchgeführt, und sie ergaben das gleiche Ergebnis.

map<string, int> m;
m.insert({ "test", 2 });
m.insert({ "this should be behind the 'test' string.", 3 });
m.insert({ "and this should be in front of the 'test' string.", 1 });
string let_me_USE_IT = std::move(const_cast<string&>(m.find("test")->first));
cout << let_me_USE_IT << '\n';
for (auto const& i : m) {
    cout << i.first << ' ' << i.second << '\n';
}

Ausgabe:

test
and this should be in front of the 'test' string. 1
 2
this should be behind the 'test' string. 3

Wir können sehen, dass die Zeichenfolge '2' jetzt leer ist, aber offensichtlich haben wir die Ordnungsmäßigkeit der Karte gebrochen, weil die leere Zeichenfolge vorne platziert werden sollte. Wenn wir versuchen, bestimmte Knoten der Karte einzufügen, zu finden oder zu löschen, kann dies zu einer Katastrophe führen.

Auf jeden Fall können wir uns einig sein, dass es niemals eine gute Idee ist, die inneren Daten von Klassen unter Umgehung ihrer öffentlichen Schnittstellen zu manipulieren. Die find, insert, removeFunktionen und so verlassen hervor ihre Richtigkeit auf der Ordnung der inneren Datenstruktur, und das ist der Grund , warum wir von dem Gedanken an spähen nach innen bleiben weg sollten.

Deuchie
quelle
2
"Es ist kein Problem, ob es beim Dekonstruieren Probleme verursachen würde." Technisch korrekt, da das undefinierte Verhalten (Änderung eines constWertes) früher aufgetreten ist. Das Argument "Die move[Funktion] stellt sicher, dass es sicher ist, [ein Objekt] einer Klasse nach dem Verschieben zu dekonstruieren" gilt jedoch nicht: Sie können nicht sicher von einem constObjekt / einer Referenz verschieben, da dies eine Änderung erfordert constverhindert. Sie können versuchen, diese Einschränkung mithilfe von zu umgehen const_cast, aber an diesem Punkt gehen Sie bestenfalls auf ein tiefgreifendes implementierungsspezifisches Verhalten ein, wenn nicht auf UB.
hoffmale
@hoffmale Danke, ich habe übersehen und einen großen Fehler gemacht. Wenn Sie nicht darauf hingewiesen haben, könnte meine Antwort hier jemand anderen irreführen. Eigentlich sollte ich sagen, dass die moveFunktion a &anstelle von a const&nimmt. Wenn man also darauf besteht, dass er einen Schlüssel aus einer Karte herauszieht, muss er verwenden const_cast.
Deuchie
1
"Objekte, die als const bezeichnet werden, sind hinsichtlich ihrer Typen und Darstellungen in der binären Form immer noch ein Objekt, genau wie diejenigen, die nicht mit const versehen sind." Nein. const-Objekte können in einen Nur-Lese-Speicher gestellt werden. Außerdem ermöglicht const dem Compiler, über den Code nachzudenken und den Wert zwischenzuspeichern, anstatt Code für mehrere Lesevorgänge zu generieren (was einen großen Unterschied in Bezug auf die Leistung bedeuten kann). Die UB, die durch verursacht wird, const_castwird also widerlich sein. Es mag die meiste Zeit funktionieren, aber brechen Sie Ihren Code auf subtile Weise.
LF
Aber hier denke ich, dass wir sicher sein können, dass die Objekte nicht in den Nur-Lese-Speicher gestellt werden, weil extractwir uns danach von demselben Objekt bewegen dürfen, oder? (siehe meine Antwort)
Phinz
1
Entschuldigung, die Analyse in Ihrer Antwort ist falsch. Ich werde eine Antwort schreiben, um dies zu erklären - es hat etwas mit Gewerkschaften zu tun undstd::launder
LF