wstawianie vs umiejscowienie vs operator [] w mapie c ++

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_typelub 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:

1. Jaka jest przewaga każdego z nich nad innymi?

2. Czy zaistniała potrzeba dodania umiejscowienia do normy? Czy jest coś, co wcześniej nie byłoby możliwe bez tego?

W szczególnym przypadku mapy starymi opcjami były tylko dwa: operator[]i insert(różne smaki insert). 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.

insertFunkcja (w pojedynczy element smaku) trwa value_type( std::pair<const Key,Value>), to używa klucza ( firstczłonek) i stara się go wstawić. Ponieważ std::mapnie 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. insertFunkcja nie zmieni stan na mapie, lecz powrót iterację na elemencie (i falsewskazuje, że nie dodaje się).

// assume m is std::map<int,int> already has an element with key 5 and value 0
m[5] = 10;                      // postcondition: m[5] == 10
m.insert(std::make_pair(5,15)); // m[5] is still 10

W przypadku insertargumentu jest przedmiotem value_type, który można utworzyć na różne sposoby. Możesz bezpośrednio skonstruować go odpowiednim typem lub przekazać dowolny obiekt, z którego value_typemożna go skonstruować, czyli tam, gdzie std::make_pairwchodzi w grę, ponieważ pozwala na proste tworzenie std::pairobiektów, chociaż prawdopodobnie nie jest to, czego chcesz ...

Efekt netto następujących połączeń jest podobny :

K t; V u;
std::map<K,V> m;           // std::map<K,V>::value_type is std::pair<const K,V>

m.insert( std::pair<const K,V>(t,u) );      // 1
m.insert( std::map<K,V>::value_type(t,u) ); // 2
m.insert( std::make_pair(t,u) );            // 3

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 do insertfunkcji. insertFunkcja stworzy odpowiedni węzeł w wyszukiwaniu binarnym drzewie i skopiuj value_typeczęść z argumentu do węzła. Zaletą używania value_typejest to, że, no cóż, value_typezawsze pasuje value_type , nie można pomylić typu std::pairargumentów!

Różnica polega na [3]. Ta funkcja std::make_pairjest funkcją szablonu, która utworzy std::pair. Podpis to:

template <typename T, typename U>
std::pair<T,U> make_pair(T const & t, U const & u );

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 przypadku T==K,U==V, więc wywołanie do std::make_pairzwróci a std::pair<K,V>(zwróć uwagę na brak const). Podpis wymaga, value_typeaby był bliski, ale nie taki sam, jak wartość zwrócona z wywołania do std::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:

m.insert( std::make_pair<const K,V>(t,u) );  // 4

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, insertktóre wymagają utworzenia value_typezewnę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 w m[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 emplacefunkcje 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.

m.emplace(t,u);               // 5

W [5] obiekt std::pair<const K, V>nie jest tworzony i przekazywany emplace, ale przekazywane są do niego odniesienia ti uobiekt, emplacektóre przekazują je konstruktorowi value_typepodobiektu wewnątrz struktury danych. W tym przypadku niestd::pair<const K,V> są wykonywane żadne kopie , co jest zaletą w emplacestosunku do alternatyw C ++ 03. Tak jak w przypadku inserttego, nie zastąpi wartości na mapie.

Interesującym pytaniem, o którym nie myślałem, jest to, jak emplacemożna faktycznie zaimplementować mapę, i nie jest to prosty problem w ogólnym przypadku.

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.

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:

#include <vector>

struct foo
{
    explicit foo(int);
};

int main()
{
    std::vector<foo> v;

    v.emplace(v.end(), 10);      // Works
    //v.insert(v.end(), 10);     // Error, not explicit
    v.insert(v.end(), foo(10));  // Also works
}

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ć.

Poniższy kod może pomóc zrozumieć „ideę dużego obrazu” dotyczącą tego, czym się insert()różni emplace():

#include <iostream>
#include <unordered_map>
#include <utility>

//Foo simply outputs what constructor is called with what value.
struct Foo {
  static int foo_counter; //Track how many Foo objects have been created.
  int val; //This Foo object was the val-th Foo object to be created.

  Foo() { val = foo_counter++;
    std::cout << "Foo() with val:                " << val << '\n';
  }
  Foo(int value) : val(value) { foo_counter++;
    std::cout << "Foo(int) with val:             " << val << '\n';
  }
  Foo(Foo& f2) { val = foo_counter++;
    std::cout << "Foo(Foo &) with val:           " << val
              << " \tcreated from:      \t" << f2.val << '\n';
  }
  Foo(const Foo& f2) { val = foo_counter++;
    std::cout << "Foo(const Foo &) with val:     " << val
              << " \tcreated from:      \t" << f2.val << '\n';
  }
  Foo(Foo&& f2) { val = foo_counter++;
    std::cout << "Foo(Foo&&) moving:             " << f2.val
              << " \tand changing it to:\t" << val << '\n';
  }
  ~Foo() { std::cout << "~Foo() destroying:             " << val << '\n'; }

  Foo& operator=(const Foo& rhs) {
    std::cout << "Foo& operator=(const Foo& rhs) with rhs.val: " << rhs.val
              << " \tcalled with lhs.val = \t" << val
              << " \tChanging lhs.val to: \t" << rhs.val << '\n';
    val = rhs.val;
    return *this;
  }

  bool operator==(const Foo &rhs) const { return val == rhs.val; }
  bool operator<(const Foo &rhs)  const { return val < rhs.val;  }
};

int Foo::foo_counter = 0;

//Create a hash function for Foo in order to use Foo with unordered_map
namespace std {
   template<> struct hash<Foo> {
       std::size_t operator()(const Foo &f) const {
           return std::hash<int>{}(f.val);
       }
   };
}

int main()
{
    std::unordered_map<Foo, int> umap;  
    Foo foo0, foo1, foo2, foo3;
    int d;

    //Print the statement to be executed and then execute it.

    std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
    umap.insert(std::pair<Foo, int>(foo0, d));
    //Side note: equiv. to: umap.insert(std::make_pair(foo0, d));

    std::cout << "\numap.insert(std::move(std::pair<Foo, int>(foo1, d)))\n";
    umap.insert(std::move(std::pair<Foo, int>(foo1, d)));
    //Side note: equiv. to: umap.insert(std::make_pair(foo1, d));

    std::cout << "\nstd::pair<Foo, int> pair(foo2, d)\n";
    std::pair<Foo, int> pair(foo2, d);

    std::cout << "\numap.insert(pair)\n";
    umap.insert(pair);

    std::cout << "\numap.emplace(foo3, d)\n";
    umap.emplace(foo3, d);

    std::cout << "\numap.emplace(11, d)\n";
    umap.emplace(11, d);

    std::cout << "\numap.insert({12, d})\n";
    umap.insert({12, d});

    std::cout.flush();
}

Otrzymałem wynik:

Foo() with val:                0
Foo() with val:                1
Foo() with val:                2
Foo() with val:                3

umap.insert(std::pair<Foo, int>(foo0, d))
Foo(Foo &) with val:           4    created from:       0
Foo(Foo&&) moving:             4    and changing it to: 5
~Foo() destroying:             4

umap.insert(std::move(std::pair<Foo, int>(foo1, d)))
Foo(Foo &) with val:           6    created from:       1
Foo(Foo&&) moving:             6    and changing it to: 7
~Foo() destroying:             6

std::pair<Foo, int> pair(foo2, d)
Foo(Foo &) with val:           8    created from:       2

umap.insert(pair)
Foo(const Foo &) with val:     9    created from:       8

umap.emplace(foo3, d)
Foo(Foo &) with val:           10   created from:       3

umap.emplace(11, d)
Foo(int) with val:             11

umap.insert({12, d})
Foo(int) with val:             12
Foo(const Foo &) with val:     13   created from:       12
~Foo() destroying:             12

~Foo() destroying:             8
~Foo() destroying:             3
~Foo() destroying:             2
~Foo() destroying:             1
~Foo() destroying:             0
~Foo() destroying:             13
~Foo() destroying:             11
~Foo() destroying:             5
~Foo() destroying:             10
~Foo() destroying:             7
~Foo() destroying:             9

Zauważ, że:

1. An unordered_mapzawsze wewnętrznie przechowuje Fooobiekty (a nie, powiedzmy, Foo *s) jak klucze, które są zniszczone, gdy unordered_mapsą zniszczone. Tutaj unordered_mapkluczami wewnętrznymi były liczby 13, 11, 5, 10, 7 i 9.

   • Tak więc technicznie nasze unordered_mapfaktycznie przechowują std::pair<const Foo, int>obiekty, które z kolei przechowują Fooobiekty. Aby jednak zrozumieć „duży obraz” tego, czym się emplace()różni insert()(patrz podświetlone pole poniżej), można tymczasowo wyobrazić sobie ten std::pairobiekt 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 tego std::pairobiektu pośredniego unordered_mapwprowadza subtelne, ale ważne szczegóły techniczne.

2. Wstawienie każdego z foo0, foo1i foo2wymagało 2 wywołań do jednego z Fookonstruktorów kopiowania / przenoszenia oraz 2 wywołań do Foodestruktora (jak teraz opisuję):

   za. Wstawienie każdego z nich foo0i foo1utworzenie obiektu tymczasowego ( foo4i foo6odpowiednio), którego destruktor był natychmiast wywoływany po zakończeniu wstawiania. Ponadto wewnętrzne Foos Unordered_map (które są Foos 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 nazwie pair), który wywołał Fookonstruktor kopiowania na foo2(tworzenie foo8jako element wewnętrzny pair). Następnie insert()edytujemy tę parę, co spowodowało unordered_mapponowne wywołanie konstruktora kopiowania (on foo8) w celu utworzenia własnej kopii wewnętrznej ( foo9). Podobnie jak w przypadku foos 0 i 1, wynikiem końcowym były dwa wywołania destruktora dla tego wstawienia, z tą jedyną różnicą, że foo8destruktor został wywołany dopiero wtedy, gdy osiągnęliśmy koniec, main()a nie wywołany natychmiast po insert()zakończeniu.

3. Wykorzystanie foo3skutkowało tylko 1 wywołaniem konstruktora kopiuj / przenieś (tworząc foo10wewnętrznie w unordered_map) i tylko 1 wywołaniem Foodestruktora. (Wrócę do tego później).

4. Dla foo11, my bezpośrednio przeszły całkowitą do 11 emplace(11, d)tak, że unordered_mapnazwałbym Foo(int)konstruktora podczas gdy wykonanie jest w jego emplace()metodzie. W przeciwieństwie do (2) i (3), nie potrzebowaliśmy nawet jakiegoś wcześniej wychodzącego fooobiektu, aby to zrobić. Co ważne, zauważ, że Foowystąpiło tylko 1 wywołanie konstruktora (które zostało utworzone foo11).

5. Następnie bezpośrednio przekazaliśmy liczbę całkowitą 12 do insert({12, d}). W przeciwieństwie do emplace(11, d)(które przywołanie spowodowało tylko 1 wywołanie Fookonstruktora), to wywołanie insert({12, d})wywołało dwa wywołania do Fookonstruktora (tworzenie foo12i foo13).

To pokazuje, jaka jest główna różnica między „dużym obrazem” insert()a emplace():

Podczas gdy używanie insert() prawie zawsze wymaga budowy lub istnienia jakiegoś Fooobiektu w main()zasięgu (po którym następuje kopia lub przeniesienie), jeśli użycie emplace()to wtedy każde wywołanie Fookonstruktora odbywa się całkowicie wewnętrznie w unordered_map(tj. W zakresie emplace()definicji metody). Argument (-y) dla klucza, który przekazujesz, emplace()jest bezpośrednio przekazywany do Foowywołania konstruktora w ramach unordered_map::emplace()definicji (opcjonalnie dodatkowe szczegóły: gdzie ten nowo zbudowany obiekt jest natychmiast włączany do jednej ze unordered_mapzmiennych składowych, tak że nie wywołuje się destruktora, gdy wykonanie pozostawia emplace()i nie są wywoływane żadne konstruktory przenoszenia ani kopiowania).

Uwaga: Powód „ prawie ” w „ prawie zawsze ” powyżej wyjaśniono w I) poniżej.

3. ciąg dalszy: Wywołanie konstruktora kopiującego o umap.emplace(foo3, d)nazwie Foonon-const jest następujące: Ponieważ używamy emplace(), kompilator wie, że foo3(obiekt non-const Foo) ma być argumentem dla jakiegoś Fookonstruktora. W tym przypadku najbardziej pasującym Fookonstruktorem jest konstruktor kopii non-const Foo(Foo& f2). Właśnie dlatego umap.emplace(foo3, d)nazywany konstruktorem kopii, podczas gdy umap.emplace(11, d)nie.

Epilog:

I. Zauważ, że jedno przeciążenie insert()jest w rzeczywistości równe emplace() . Jak opisano na tej stronie cppreference.com , przeciążenie template<class P> std::pair<iterator, bool> insert(P&& value)(które jest przeciążeniem (2) insert()na tej stronie cppreference.com) jest równoważne emplace(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 ) i emplace()(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ążenie insert()lub emplace()jest wywoływane (w eclipse po prostu trzymaj kursor myszy nieruchomo nad wywołaniem funkcji przez sekundę). Oto jeszcze trochę kodu do wypróbowania:

std::cout << "\numap.insert({{" << Foo::foo_counter << ", d}})\n";
umap.insert({{Foo::foo_counter, d}});
//but umap.emplace({{Foo::foo_counter, d}}); results in a compile error!

std::cout << "\numap.insert(std::pair<const Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<const Foo, int>({Foo::foo_counter, d}));
//The above uses Foo(int) and then Foo(const Foo &), as expected. but the
// below call uses Foo(int) and the move constructor Foo(Foo&&). 
//Do you see why?
std::cout << "\numap.insert(std::pair<Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(std::pair<Foo, int>({Foo::foo_counter, d}));
//Not only that, but even more interesting is how the call below uses all 
// three of Foo(int) and the Foo(Foo&&) move and Foo(const Foo &) copy 
// constructors, despite the below call's only difference from the call above 
// being the additional { }.
std::cout << "\numap.insert({std::pair<Foo, int>({" << Foo::foo_counter << ", d})})\n";
umap.insert({std::pair<Foo, int>({Foo::foo_counter, d})});


//Pay close attention to the subtle difference in the effects of the next 
// two calls.
int cur_foo_counter = Foo::foo_counter;
std::cout << "\numap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}}) where " 
  << "cur_foo_counter = " << cur_foo_counter << "\n";
umap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}});

std::cout << "\numap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}}) where "
  << "Foo::foo_counter = " << Foo::foo_counter << "\n";
umap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}});


//umap.insert(std::initializer_list<std::pair<Foo, int>>({{Foo::foo_counter, d}}));
//The call below works fine, but the commented out line above gives a 
// compiler error. It's instructive to find out why. The two calls
// differ by a "const".
std::cout << "\numap.insert(std::initializer_list<std::pair<const Foo, int>>({{" << Foo::foo_counter << ", d}}))\n";
umap.insert(std::initializer_list<std::pair<const Foo, int>>({{Foo::foo_counter, d}}));

Wkrótce zobaczysz, że które przeciążenie std::pairkonstruktora (patrz odniesienie ) zostanie użyte, unordered_mapmoż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::setLub std::unordered_multiset) zamiast std::unordered_map.

do. Teraz użyj Gooobiektu (tylko kopia o zmienionej nazwie Foo) zamiast intjako typu zakresu w unordered_map(tzn. Użyj unordered_map<Foo, Goo>zamiast unordered_map<Foo, int>) i zobacz, ile Goowywoływanych jest konstruktorów. (Spoiler: jest efekt, ale nie jest zbyt dramatyczny.)

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