Czy dozwolone jest kradzież zasobów z kluczy std :: map?

Czy w C ++ można ukraść zasoby z mapy, której już nie potrzebuję? Mówiąc dokładniej, załóżmy, że mam klucze std::mapz std::stringi chcę z niego zbudować wektor, kradnąc zasoby mapkluczy s za pomocą std::move. Zauważ, że taki dostęp do zapisu do kluczy psuje wewnętrzną strukturę danych (porządkowanie kluczy), mapale nie będę jej później używał.

Pytanie : Czy mogę to zrobić bez żadnych problemów, czy doprowadzi to do nieoczekiwanych błędów, na przykład w destruktorze, mapponieważ uzyskałem do niego dostęp w sposób, który std::mapnie był przeznaczony?

Oto przykładowy program:

#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;
}

Daje to wynik:

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

EDYCJA: Chciałbym to zrobić dla całej zawartości dużej mapy i zapisać dynamiczne przydziały dzięki kradzieży zasobów.

Robisz niezdefiniowane zachowanie, używając const_castdo modyfikowania constzmiennej. Nie rób tego Powodem jest constto, że mapy są sortowane według ich kluczy. Tak więc modyfikacja kluczowego miejsca narusza podstawowe założenie, na którym zbudowana jest mapa.

Nigdy nie należy używać const_castdo usuwania constze zmiennej i modyfikowania tej zmiennej.

Mając na uwadze powyższe, C ++ 17 ma rozwiązanie problemu: std::map„s extractFunkcja:

#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())));
}

I nie rób tego using namespace std;. :)

Twój kod próbuje modyfikować constobiekty, więc ma niezdefiniowane zachowanie, jak słusznie wskazuje odpowiedź druckermanly .

Niektóre inne odpowiedzi ( Phinza i Deuchiego ) argumentują, że klucz nie może być przechowywany jako constobiekt, ponieważ uchwyt węzła wynikający z wyodrębnienia węzłów z mapy pozwala na brak constdostępu do klucza. Takie wnioskowanie może początkowo wydawać się wiarygodne, ale P0083R3 , dokument wprowadzający extractfunkcje), ma dedykowaną sekcję na ten temat, która unieważnia ten argument:

Obawy

Pojawiło się kilka obaw dotyczących tego projektu. Zajmiemy się nimi tutaj.

Nieokreślone zachowanie

Najtrudniejszą częścią tej propozycji z teoretycznego punktu widzenia jest fakt, że wyodrębniony element zachowuje swój stały typ klucza. Zapobiega to jego przenoszeniu lub zmianie. Aby rozwiązać ten problem, udostępniliśmy funkcję akcesorium klucza , która zapewnia nieograniczony dostęp do klucza w elemencie utrzymywanym przez uchwyt węzła. Ta funkcja wymaga implementacji „magii”, aby upewnić się, że działa poprawnie w obecności optymalizacji kompilatora. Jednym ze sposobów na osiągnięcie tego jest połączenie pair<const key_type, mapped_type> i pair<key_type, mapped_type>. Konwersji między nimi można dokonać bezpiecznie, stosując technikę podobną do tej zastosowanej std::launderprzy ekstrakcji i ponownym włożeniu.

Nie uważamy, że stanowi to problem techniczny lub filozoficzny. Jednym z powodów, dla których biblioteka standardowa istnieje jest pisać non-przenośne i magiczny kod, który klient nie może napisać w przenośnych C ++ (np <atomic>, <typeinfo>, <type_traits>, itd.). To tylko kolejny taki przykład. Wszystko, co jest wymagane od dostawców kompilatorów do wdrożenia tej magii, to to, że nie wykorzystują niezdefiniowanego zachowania w związkach do celów optymalizacji - a obecnie kompilatory już to obiecują (w zakresie, w jakim jest to wykorzystywane).

Nakłada to na klienta ograniczenie, że jeśli te funkcje są używane, std::pairnie można wyspecjalizować się w takim pair<const key_type, mapped_type>układzie, który ma inny układ niż pair<key_type, mapped_type>. Uważamy, że prawdopodobieństwo, że ktoś rzeczywiście tego chce, wynosi zero, a formalne sformułowanie ogranicza specjalizację tych par.

Pamiętaj, że funkcja kluczowego członka jest jedynym miejscem, w którym takie sztuczki są konieczne, i że nie są wymagane żadne zmiany w pojemnikach ani parze.

(moje podkreślenie)

Nie sądzę, że const_castmodyfikacja prowadzi do niezdefiniowanego zachowania w tym przypadku, ale proszę o komentarz, czy ta argumentacja jest poprawna.

Ta odpowiedź twierdzi, że

Innymi słowy, otrzymasz UB, jeśli zmodyfikujesz pierwotnie stały obiekt, a poza tym nie.

Zatem wiersz v.emplace_back(make_pair(std::move(const_cast<string&>(p.first)),p.second));w pytaniu nie prowadzi do UB wtedy i tylko wtedy, gdy stringobiekt p.firstnie został utworzony jako obiekt stały. Zauważ teraz, że odniesienie doextract stanów

Wyodrębnienie węzła unieważnia iteratory wyodrębnionego elementu. Wskaźniki i odniesienia do wyodrębnionego elementu pozostają ważne, ale nie można ich używać, gdy element jest własnością uchwytu węzła: stają się użyteczne, jeśli element zostanie wstawiony do kontenera.

Więc jeśli odpowiadającyextractnode_handlep , pnadal żyje w jego miejscu przechowywania. Ale po ekstrakcji wolno mi usunąćmove zasoby pjak w kodzie odpowiedzi druckermanly'ego . Oznacza to, że pi dlatego też stringobiekt niep.first został pierwotnie utworzony jako obiekt stały.

Dlatego myślę, że modyfikacja mapkluczy nie prowadzi do UB i z odpowiedzi Deuchie wydaje się, że również teraz uszkodzona struktura drzewa (obecnie wiele takich samych pustych kluczy łańcuchowych) mapnie wprowadza problemów w destruktorze. Tak więc kod w pytaniu powinien działać poprawnie przynajmniej w C ++ 17, w którym extractistnieje metoda (a oświadczenie o wskaźnikach pozostało ważne).

Aktualizacja

Jestem teraz zdania, że ​​ta odpowiedź jest błędna. Nie usuwam go, ponieważ odwołują się do niego inne odpowiedzi.

EDYCJA: Ta odpowiedź jest błędna. W miłych komentarzach wskazano na błędy, ale nie usuwam ich, ponieważ przywołano je w innych odpowiedziach.

@druckermanly odpowiedział na twoje pierwsze pytanie, które mówiło, że mapwymuszona zmiana kluczy psuje porządek, na którym mapzbudowana jest wewnętrzna struktura danych (drzewo czerwono-czarne). Ale korzystanie z tej extractmetody jest bezpieczne, ponieważ robi dwie rzeczy: wyjmij klucz z mapy, a następnie usuń go, aby w ogóle nie wpływał na porządek mapy.

Drugie pytanie, które zadałeś, czy spowodowałoby kłopoty podczas dekonstrukcji, nie stanowi problemu. Kiedy mapa dekonstruuje, wywoła dekonstruktor każdego z jej elementów (map_types itp.), A movemetoda zapewnia bezpieczeństwo dekonstrukcji klasy po jej przeniesieniu. Więc nie martw się. Krótko mówiąc, jest to działanie movezapewniające bezpieczne usunięcie lub ponowne przypisanie nowej wartości do klasy „przeniesionej”. W szczególności string, movemetoda może ustawić swój wskaźnik char na nullptr, więc nie usuwa rzeczywistych danych, które zostały przeniesione, gdy wywołano dekonstruktor oryginalnej klasy.

Komentarz przypomniał mi o punkcie, który przeoczyłem, w zasadzie miał rację, ale jest jedna rzecz, z którą całkowicie się nie zgadzam: const_castprawdopodobnie nie jest to UB. constto tylko obietnica między kompilatorem a nami. obiekty oznaczone jako constnadal są obiektami, takimi samymi jak te, które nie są const, pod względem ich typów i reprezentacji w postaci binarnej. Gdy constzostanie odrzucony, powinien zachowywać się tak, jakby był normalną klasą podlegającą modyfikacji. Jeśli chodzi o move: Jeśli chcesz go użyć, musisz przekazać &zamiast zamiast const &, więc, jak widzę, nie jest to UB, po prostu łamie obietnicę consti przenosi dane.

Przeprowadziłem również dwa eksperymenty, używając odpowiednio MSVC 14.24.28314 i Clang 9.0.0, i dały one ten sam wynik.

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';
}

wynik:

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

Widzimy, że ciąg „2” jest teraz pusty, ale oczywiście złamaliśmy porządek mapy, ponieważ pusty ciąg powinien zostać ponownie umieszczony z przodu. Jeśli spróbujemy wstawić, znaleźć lub usunąć niektóre określone węzły mapy, może to spowodować katastrofę.

W każdym razie możemy zgodzić się, że nigdy nie jest dobrym pomysłem manipulowanie wewnętrznymi danymi jakichkolwiek klas z pominięciem ich publicznych interfejsów. find, insert, removeFunkcje i tak dalej polegać ich poprawności na uporządkowanie wewnętrznej struktury danych, i to jest powód, dlaczego powinniśmy się trzymać z dala od myśli o wgląd wnętrza.