Korzystam z map po raz pierwszy i zdałem sobie sprawę, że istnieje wiele sposobów wstawiania elementu. Możesz użyć emplace()
, operator[]
lub insert()
, oraz wariantów takich jak użycie value_type
lub make_pair
. Chociaż istnieje wiele informacji o nich wszystkich i pytania dotyczące konkretnych przypadków, nadal nie rozumiem całościowego obrazu. Moje dwa pytania to:
Jaka jest przewaga każdego z nich nad innymi?
Czy zaistniała potrzeba dodania umiejscowienia do normy? Czy jest coś, co wcześniej nie byłoby możliwe bez tego?
operator[]
jest oparty natry_emplace
. Warto też wspomniećinsert_or_assign
.Odpowiedzi:
W szczególnym przypadku mapy starymi opcjami były tylko dwa:
operator[]
iinsert
(różne smakiinsert
). Więc zacznę je wyjaśniać.operator[]
To find-or-add operator. Spróbuje znaleźć element z danym kluczem na mapie, a jeśli istnieje, zwróci odwołanie do zapisanej wartości. Jeśli nie, utworzy nowy element wstawiony na miejscu z domyślną inicjalizacją i zwróci do niego odwołanie.insert
Funkcja (w pojedynczy element smaku) trwavalue_type
(std::pair<const Key,Value>
), to używa klucza (first
członek) i stara się go wstawić. Ponieważstd::map
nie zezwala na duplikaty, jeśli istnieje element, nic nie wstawi.Pierwszą różnicą między nimi jest to, że
operator[]
musi być w stanie skonstruować domyślną wartość inicjowaną , a zatem nie można jej użyć w przypadku typów wartości, których nie można zainicjować domyślnie. Druga różnica między nimi polega na tym, że istnieje już element z danym kluczem.insert
Funkcja nie zmieni stan na mapie, lecz powrót iterację na elemencie (ifalse
wskazuje, że nie dodaje się).W przypadku
insert
argumentu jest przedmiotemvalue_type
, który można utworzyć na różne sposoby. Możesz bezpośrednio skonstruować go odpowiednim typem lub przekazać dowolny obiekt, z któregovalue_type
można go skonstruować, czyli tam, gdziestd::make_pair
wchodzi w grę, ponieważ pozwala na proste tworzeniestd::pair
obiektów, chociaż prawdopodobnie nie jest to, czego chcesz ...Efekt netto następujących połączeń jest podobny :
Ale tak naprawdę nie są takie same ... [1] i [2] są w rzeczywistości równoważne. W obu przypadkach kod tworzy tymczasowy obiekt tego samego typu (
std::pair<const K,V>
) i przekazuje go doinsert
funkcji.insert
Funkcja stworzy odpowiedni węzeł w wyszukiwaniu binarnym drzewie i skopiujvalue_type
część z argumentu do węzła. Zaletą używaniavalue_type
jest to, że, no cóż,value_type
zawsze pasujevalue_type
, nie można pomylić typustd::pair
argumentów!Różnica polega na [3]. Ta funkcja
std::make_pair
jest funkcją szablonu, która utworzystd::pair
. Podpis to:Celowo nie podałem argumentów szablonu
std::make_pair
, ponieważ jest to powszechne użycie. I implikacja jest taka, że argumenty szablonu są wywnioskowane z wywołania, w tym przypadkuT==K,U==V
, więc wywołanie dostd::make_pair
zwróci astd::pair<K,V>
(zwróć uwagę na brakconst
). Podpis wymaga,value_type
aby był bliski, ale nie taki sam, jak wartość zwrócona z wywołania dostd::make_pair
. Ponieważ jest wystarczająco blisko, utworzy tymczasową poprawnego typu i zainicjuje kopię. To z kolei zostanie skopiowane do węzła, tworząc w sumie dwie kopie.Można to naprawić, podając argumenty szablonu:
Ale nadal jest to podatne na błędy w taki sam sposób, jak jawne wpisywanie typu w przypadku [1].
Do tego momentu istnieją różne sposoby wywoływania,
insert
które wymagają utworzeniavalue_type
zewnętrznego i kopii tego obiektu do kontenera. Alternatywnie możesz użyć,operator[]
jeśli typ jest domyślnie możliwy do skonstruowania i przypisania (celowe ustawianie ostrości tylko wm[k]=v
) i wymaga domyślnej inicjalizacji jednego obiektu oraz skopiowania wartości do tego obiektu.W C ++ 11, z różnymi szablonami i doskonałym przekazywaniem, istnieje nowy sposób dodawania elementów do kontenera poprzez umieszczanie (tworzenie na miejscu). Te
emplace
funkcje w różnych pojemnikach zrobić w zasadzie to samo: zamiast się źródło , z którego można skopiować do pojemnika, funkcja przyjmuje parametry, które zostaną przekazane do konstruktora obiektu przechowywanego w pojemniku.W [5] obiekt
std::pair<const K, V>
nie jest tworzony i przekazywanyemplace
, ale przekazywane są do niego odniesieniat
iu
obiekt,emplace
które przekazują je konstruktorowivalue_type
podobiektu wewnątrz struktury danych. W tym przypadku niestd::pair<const K,V>
są wykonywane żadne kopie , co jest zaletą wemplace
stosunku do alternatyw C ++ 03. Tak jak w przypadkuinsert
tego, nie zastąpi wartości na mapie.Interesującym pytaniem, o którym nie myślałem, jest to, jak
emplace
można faktycznie zaimplementować mapę, i nie jest to prosty problem w ogólnym przypadku.źródło
mapped_type
kopiowania zdarzenia. To, czego chcemy, to umieszczenie konstrukcjimapped_type
pary i umieszczenie konstrukcji pary na mapie. Dlatego brakuje zarównostd::pair::emplace
funkcji, jak i obsługi przekazywaniamap::emplace
. W obecnej formie nadal musisz podać skonstruowany typ odwzorowany do konstruktora par, który go raz skopiuje. jest lepszy niż dwa razy, ale nadal nie jest dobry.insert_or_assign
itry_emplace
(oba z C ++ 17), które pomagają wypełnić pewne luki w funkcjonalności istniejących metod.Emplace: Wykorzystuje odwołanie do wartości, aby użyć rzeczywistych obiektów, które już utworzyłeś. Oznacza to, że nie jest wywoływany żaden konstruktor kopiowania lub przenoszenia, co jest dobre dla DUŻYCH obiektów! Czas O (log (N)).
Wstaw: Zawiera przeciążenia dla standardowego odniesienia do wartości i odniesienia do wartości, a także iteratory do list elementów do wstawienia oraz „podpowiedzi” do pozycji, do której należy element. Zastosowanie iteratora „podpowiedzi” może sprowadzić czas wstawiania do czasu ciągłego, w przeciwnym razie jest to czas O (log (N)).
Operator []: sprawdza, czy obiekt istnieje, a jeśli tak, modyfikuje odwołanie do tego obiektu, w przeciwnym razie używa dostarczonego klucza i wartości do wywołania make_pair na dwóch obiektach, a następnie wykonuje tę samą pracę, co funkcja wstawiania. To jest czas O (log (N)).
make_pair: robi niewiele więcej niż tworzenie pary.
Nie było „potrzeby” dodawania miejsca pracy do normy. W c ++ 11 uważam, że dodano odniesienie typu &&. Usunęło to konieczność semantyki przenoszenia i umożliwiło optymalizację określonego zarządzania pamięcią. W szczególności odniesienie do wartości. Przeciążony operator insert (value_type &&) nie wykorzystuje semantyki in_place, a zatem jest znacznie mniej wydajny. Chociaż zapewnia możliwość radzenia sobie z referencjami wartości, ignoruje ich główny cel, jakim jest konstruowanie obiektów.
źródło
emplace()
jest po prostu jedynym sposobem na wstawienie elementu, którego nie można skopiować ani przenieść. (i tak, być może, aby najskuteczniej wstawić taki, którego konstruktory kopiujące i przenoszące kosztują znacznie więcej niż konstrukcja, jeśli coś takiego istnieje) Wydaje się również, że pomyliłeś pomysł: nie chodzi o „ [skorzystanie] z odniesienia do wartości używać rzeczywistych obiektów, które już utworzyłeś "; żaden obiekt nie został jeszcze utworzony,map
a argumenty, których potrzebuje, aby go utworzyć, należy przekazać w sobie. Nie tworzysz obiektu.Oprócz możliwości optymalizacji i prostszej składni, istotnym rozróżnieniem między wstawianiem a pozycjonowaniem jest to, że pozwala on na wyraźne konwersje. (Dotyczy to całej standardowej biblioteki, nie tylko map).
Oto przykład do zademonstrowania:
Jest to wprawdzie bardzo specyficzny szczegół, ale jeśli masz do czynienia z łańcuchami konwersji zdefiniowanych przez użytkownika, warto o tym pamiętać.
źródło
v.emplace(v.end(), 10, 10);
... czy teraz musisz użyćv.emplace(v.end(), foo(10, 10) );
:?emplace
wykorzystują klasę, która przyjmuje pojedynczy parametr. IMO sprawiłoby, że charakter składni variadic umiejscowienia byłby o wiele bardziej wyraźny, gdyby w przykładach użyto wielu parametrów.Poniższy kod może pomóc zrozumieć „ideę dużego obrazu” dotyczącą tego, czym się
insert()
różniemplace()
:Otrzymałem wynik:
Zauważ, że:
An
unordered_map
zawsze wewnętrznie przechowujeFoo
obiekty (a nie, powiedzmy,Foo *
s) jak klucze, które są zniszczone, gdyunordered_map
są zniszczone. Tutajunordered_map
kluczami wewnętrznymi były liczby 13, 11, 5, 10, 7 i 9.unordered_map
faktycznie przechowująstd::pair<const Foo, int>
obiekty, które z kolei przechowująFoo
obiekty. Aby jednak zrozumieć „duży obraz” tego, czym sięemplace()
różniinsert()
(patrz podświetlone pole poniżej), można tymczasowo wyobrazić sobie tenstd::pair
obiekt jako całkowicie pasywny. Po zrozumieniu tego „pomysłu na duży obraz” ważne jest, aby wykonać kopię zapasową i zrozumieć, w jaki sposób użycie tegostd::pair
obiektu pośredniegounordered_map
wprowadza subtelne, ale ważne szczegóły techniczne.Wstawienie każdego z
foo0
,foo1
ifoo2
wymagało 2 wywołań do jednego zFoo
konstruktorów kopiowania / przenoszenia oraz 2 wywołań doFoo
destruktora (jak teraz opisuję):za. Wstawienie każdego z nich
foo0
ifoo1
utworzenie obiektu tymczasowego (foo4
ifoo6
odpowiednio), którego destruktor był natychmiast wywoływany po zakończeniu wstawiania. Ponadto wewnętrzneFoo
s Unordered_map (które sąFoo
s 5 i 7) również miały swoje wywoływacze, gdy zniszczono unordered_map.b. Aby wstawić
foo2
, zamiast tego najpierw jawnie utworzyliśmy nie-tymczasowy obiekt pary (o nazwiepair
), który wywołałFoo
konstruktor kopiowania nafoo2
(tworzeniefoo8
jako element wewnętrznypair
). Następnieinsert()
edytujemy tę parę, co spowodowałounordered_map
ponowne wywołanie konstruktora kopiowania (onfoo8
) w celu utworzenia własnej kopii wewnętrznej (foo9
). Podobnie jak w przypadkufoo
s 0 i 1, wynikiem końcowym były dwa wywołania destruktora dla tego wstawienia, z tą jedyną różnicą, żefoo8
destruktor został wywołany dopiero wtedy, gdy osiągnęliśmy koniec,main()
a nie wywołany natychmiast poinsert()
zakończeniu.Wykorzystanie
foo3
skutkowało tylko 1 wywołaniem konstruktora kopiuj / przenieś (tworzącfoo10
wewnętrznie wunordered_map
) i tylko 1 wywołaniemFoo
destruktora. (Wrócę do tego później).Dla
foo11
, my bezpośrednio przeszły całkowitą do 11emplace(11, d)
tak, żeunordered_map
nazwałbymFoo(int)
konstruktora podczas gdy wykonanie jest w jegoemplace()
metodzie. W przeciwieństwie do (2) i (3), nie potrzebowaliśmy nawet jakiegoś wcześniej wychodzącegofoo
obiektu, aby to zrobić. Co ważne, zauważ, żeFoo
wystąpiło tylko 1 wywołanie konstruktora (które zostało utworzonefoo11
).Następnie bezpośrednio przekazaliśmy liczbę całkowitą 12 do
insert({12, d})
. W przeciwieństwie doemplace(11, d)
(które przywołanie spowodowało tylko 1 wywołanieFoo
konstruktora), to wywołanieinsert({12, d})
wywołało dwa wywołania doFoo
konstruktora (tworzeniefoo12
ifoo13
).To pokazuje, jaka jest główna różnica między „dużym obrazem”
insert()
aemplace()
:Uwaga: Powód „ prawie ” w „ prawie zawsze ” powyżej wyjaśniono w I) poniżej.
umap.emplace(foo3, d)
nazwieFoo
non-const jest następujące: Ponieważ używamyemplace()
, kompilator wie, żefoo3
(obiekt non-constFoo
) ma być argumentem dla jakiegośFoo
konstruktora. W tym przypadku najbardziej pasującymFoo
konstruktorem jest konstruktor kopii non-constFoo(Foo& f2)
. Właśnie dlategoumap.emplace(foo3, d)
nazywany konstruktorem kopii, podczas gdyumap.emplace(11, d)
nie.Epilog:
I. Zauważ, że jedno przeciążenie
insert()
jest w rzeczywistości równeemplace()
. Jak opisano na tej stronie cppreference.com , przeciążenietemplate<class P> std::pair<iterator, bool> insert(P&& value)
(które jest przeciążeniem (2)insert()
na tej stronie cppreference.com) jest równoważneemplace(std::forward<P>(value))
.II. Dokąd się udać?
za. Zapoznaj się z powyższym kodem źródłowym i zapoznaj się z dokumentacją
insert()
(np. Tutaj ) iemplace()
(np. Tutaj ), które można znaleźć w Internecie. Jeśli używasz IDE, takiego jak eclipse lub NetBeans, możesz łatwo dostać IDE, aby powiedział ci, które przeciążenieinsert()
lubemplace()
jest wywoływane (w eclipse po prostu trzymaj kursor myszy nieruchomo nad wywołaniem funkcji przez sekundę). Oto jeszcze trochę kodu do wypróbowania:Wkrótce zobaczysz, że które przeciążenie
std::pair
konstruktora (patrz odniesienie ) zostanie użyte,unordered_map
może mieć istotny wpływ na liczbę obiektów kopiowanych, przenoszonych, tworzonych i / lub niszczonych, a także kiedy to nastąpi.b. Zobacz, co się stanie, gdy użyjesz innej klasy kontenera (np.
std::set
Lubstd::unordered_multiset
) zamiaststd::unordered_map
.do. Teraz użyj
Goo
obiektu (tylko kopia o zmienionej nazwieFoo
) zamiastint
jako typu zakresu wunordered_map
(tzn. Użyjunordered_map<Foo, Goo>
zamiastunordered_map<Foo, int>
) i zobacz, ileGoo
wywoływanych jest konstruktorów. (Spoiler: jest efekt, ale nie jest zbyt dramatyczny.)źródło
Pod względem funkcjonalności lub wydajności oba są takie same.
W przypadku obu dużych pamięci umieszczanie obiektów jest zoptymalizowane pod kątem pamięci, które nie używają konstruktorów kopii
Proste, szczegółowe wyjaśnienie https://medium.com/@sandywits/all-about-emplace-in-c-71fd15e06e44
źródło