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


15

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.


3
Jaki jest cel tego „kradzieży”? Aby usunąć element z mapy? Dlaczego więc po prostu tego nie zrobić (usunąć element z mapy)? Również modyfikowanie constwartości jest zawsze UB.
Jakiś programista koleś

najwyraźniej doprowadzi to do poważnych błędów!
rezaebrh

1
Nie bezpośrednia odpowiedź na twoje pytanie, ale: Co jeśli nie zwrócisz wektora, ale zakres lub parę iteratorów? Pozwoli to uniknąć całkowitego kopiowania. W każdym razie potrzebne są testy porównawcze do śledzenia postępu optymalizacji oraz profiler do wyszukiwania punktów aktywnych.
Ulrich Eckhardt

1
@ ALX23z Czy masz jakieś źródło tego oświadczenia. Nie mogę sobie wyobrazić, jak kopiowanie wskaźnika jest droższe niż kopiowanie całego regionu pamięci.
Sebastian Hoffmann

1
@SebastianHoffmann został wspomniany w ostatnim CppCon, nie jestem pewien, o której rozmowie, tho. Chodzi o to, że std::stringma krótką optymalizację. Oznacza to, że istnieje pewna nietrywialna logika przy kopiowaniu i przenoszeniu, a nie tylko wymiana wskaźnika, a ponadto większość ruchu polega na kopiowaniu - aby nie radzić sobie z dość długimi łańcuchami. Różnica statystyczna i tak była niewielka i na ogół różni się w zależności od rodzaju wykonywanego przetwarzania łańcucha.
ALX23z

Odpowiedzi:


18

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;. :)


Dzięki, spróbuję tego! Ale czy jesteś pewien, że nie mogę zrobić tak jak ja? Mam na myśli, że mapnie będę narzekał, jeśli nie wywołam jego metod (czego nie robię), a może wewnętrzne porządkowanie nie jest ważne w jego destruktorze?
phinz

2
Klucze mapy są tworzone const. Mutowanie constobiektu jest natychmiastowym UB, niezależnie od tego, czy cokolwiek faktycznie uzyskuje do niego dostęp później.
HTNW

Ta metoda ma dwa problemy: (1) Ponieważ chcę wyodrębnić wszystkie elementy, nie chcę wyodrębniać według klucza (nieefektywne wyszukiwanie), ale przez iterator. Widziałem, że jest to również możliwe, więc jest w porządku. (2) Popraw mnie, jeśli się mylę, ale do wyodrębnienia wszystkich elementów będzie ogromne obciążenie (dla ponownego zrównoważenia wewnętrznej struktury drzewa przy każdym wyodrębnianiu)?
phinz

2
@phinz Jak widać na cppreferencji extract podczas używania iteratorów jako argumentu zamortyzowano stałą złożoność. Niektóre koszty ogólne są nieuniknione, ale prawdopodobnie nie będą na tyle znaczące, aby miały znaczenie. Jeśli masz specjalne wymagania nieobjęte tym, musisz wdrożyć własne mapspełniające te wymagania. Te stdpojemniki są przeznaczone do wspólnego celu ogólnego application.They nie są zoptymalizowane pod kątem konkretnych zastosowań.
orzech

@HTNW Czy jesteś pewien, że klucze zostały utworzone const? W takim przypadku proszę wskazać, gdzie moja argumentacja jest błędna.
phinz

4

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)


To właściwie część odpowiedzi na pierwotne pytanie, ale mogę zaakceptować tylko jedno.
phinz

0

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.


1
Przepraszamy, Twoja odpowiedź jest zła. Napiszę odpowiedź, aby to wyjaśnić - ma to coś wspólnego ze związkami zawodowymi i std::launder.
LF

-1

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.


2
„to, czy spowodowałoby kłopoty podczas dekonstrukcji, nie stanowi problemu”. Technicznie poprawne, ponieważ niezdefiniowane zachowanie (zmiana constwartości) miało miejsce wcześniej. Jednak argument „ move[funkcja] zapewnia, że ​​można bezpiecznie zdekonstruować [obiekt] klasy po jej przeniesieniu” nie ma zastosowania: nie można bezpiecznie przejść z constobiektu / odwołania, ponieważ wymaga to modyfikacji, która constzapobiega. Możesz spróbować obejść to ograniczenie, używając const_cast, ale w tym momencie w najlepszym razie wchodzisz głęboko w zachowanie specyficzne dla implementacji, jeśli nie UB.
hoffmale

@hoffmale Dzięki, przeoczyłem i popełniłem duży błąd. Jeśli to nie ty to wskazałeś, moja odpowiedź tutaj może wprowadzić kogoś w błąd. Właściwie powinienem powiedzieć, że movefunkcja przyjmuje &zamiast a const&, więc jeśli ktoś nalega, aby wyprowadził klucz z mapy, musi go użyć const_cast.
Deuchie

1
„obiekty oznaczone jako const są nadal obiektami, takimi jak te, które nie są oznaczone const, pod względem ich typów i reprezentacji w postaci binarnej”. Nie. Obiekty const można umieścić w pamięci tylko do odczytu. Ponadto const umożliwia kompilatorowi rozumowanie kodu i buforowanie wartości zamiast generowania kodu dla wielu odczytów (co może mieć duże znaczenie pod względem wydajności). Więc spowodowane przez UB const_castbędzie nieznośne. Może to działać przez większość czasu, ale łam kod w subtelny sposób.
LF

Ale tutaj myślę, że możemy być pewni, że obiekty nie są umieszczane w pamięci tylko do odczytu, ponieważ później extractmożemy przesuwać się z tego samego obiektu, prawda? (patrz moja odpowiedź)
phinz

1
Przepraszamy, analiza w twojej odpowiedzi jest nieprawidłowa. Napiszę odpowiedź, aby to wyjaśnić - ma to coś wspólnego ze związkami zawodowymi istd::launder
LF
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.