insert vs emplace vs operator [] w C++ Mapa

Emplace: wykorzystuje odniesienie rvalue do użycia rzeczywistych obiektów, które już utworzyłeś. Oznacza to, że nie jest wywoływany konstruktor kopiowania lub przenoszenia, dobry dla dużych obiektów! O(log (N)) czas.

Insert: posiada przeciążenia dla standardowych referencji lvalue i rvalue, a także Iteratory do list elementów do wstawienia oraz "podpowiedzi"co do pozycji elementu. Użycie iteratora "podpowiedzi" może sprowadzić czas wstawiania do czasu kontantowego, w przeciwnym razie jest O(log (N)) czas.

Operator []: sprawdza, czy obiekt istnieje, a jeśli tak, modyfikuje odniesienie do tego obiektu, w przeciwnym razie używa podanego klucza i wartości do wywołania make_pair na obu obiektach, a następnie wykonuje tę samą pracę, co funkcja insert. To jest czas o(log(N)).

Make_pair: robi niewiele więcej niż tworzy parę.

Nie było "potrzeby" dodawania emplace do standardu. W c++11 uważam, że dodano & & Typ odniesienia. To usunęło konieczność semantyki ruchu i umożliwiła optymalizację pewnego określonego rodzaju zarządzania pamięcią. W szczególności odniesienie rvalue. Przeciążony operator insert (value_type &&) nie wykorzystuje semantyki in_place i dlatego jest znacznie mniej wydajny. Chociaż zapewnia możliwość radzenia sobie z referencjami rvalue, ignoruje ich kluczowy cel, jakim jest budowa obiektów.

Oprócz możliwości optymalizacji i prostszej składni, ważną różnicą między wstawianiem i umieszczaniem jest to, że ta ostatnia pozwala na konwersje jawne . (Dotyczy to całej biblioteki standardowej, 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 konkretny szczegół, ale kiedy masz do czynienia z łańcuchami konwersji zdefiniowanych przez użytkownika, warto o tym pamiętać.

Poniższy kod może pomóc ci zrozumieć "big picture idea" czym insert() różni się od emplace():

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

struct Foo {
  static int foo_counter;
  int val;

  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;

    std::cout << "\numap.insert(std::pair<Foo, int>(foo0, d))\n";
    umap.insert(std::pair<Foo, int>(foo0, d));
    //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)));
    //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();
}

Wyjście, które dostałem było:

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_map zawsze wewnętrznie przechowuje Foo obiekty (a nie, powiedzmy, Foo *s) jako klucze, które są niszczone, gdy unordered_map jest niszczone. Tutaj, klucze wewnętrzne unordered_map były foos 13, 11, 5, 10, 7, i 9.

   • więc technicznie, nasz unordered_map faktycznie przechowuje std::pair<const Foo, int> obiekty, które z kolei przechowuje Foo obiekty. Aby jednak zrozumieć, czym emplace() różni się od insert() (patrz podświetlona ramka poniżej), w porządku jest tymczasowo wyobrazić sobie ten std::pair obiekt jako całkowicie pasywny. Kiedy już zrozumiesz tę "ideę big picture", ważne jest, aby wykonać kopię zapasową i zrozumieć, w jaki sposób użycie tego pośredniego obiektu std::pair przez unordered_map wprowadza subtelne, ale ważne szczegóły techniczne.

2. Wstawianie każdego z foo0, foo1, oraz foo2 wymagane 2 wywołania do jednego z konstruktorów Foo i 2 wywołania do destruktora Foo (Jak teraz opisuję):

   A. wstawienie każdego z foo0 i foo1 utworzyło obiekt tymczasowy (odpowiedniofoo4 i foo6), którego Destruktor został wywołany natychmiast po zakończeniu wstawiania. Dodatkowo, wewnętrzne Foounordered_map (które są foos 5 i 7) również miały wywoływane destruktory, gdy unordered_map został zniszczony.

   B. Aby wstawić foo2, my zamiast tego najpierw utworzono nie-tymczasową parę (foo8), która wywołała Konstruktor kopiujący Foo, a następnie wstawiono go, co spowodowało, że unordered_map ponownie wywołał Konstruktor kopiujący, aby utworzyć wewnętrzną kopię (foo9). Podobnie jak w przypadku foos 0 i 1, efektem końcowym były dwa wywołania destruktora dla tego Wstawienia, z tą tylko różnicą, że Destruktor foo8 został wywołany dopiero, gdy osiągnęliśmy koniec main().

3. Emplacing foo3 spowodował tylko 1 wywołanie konstruktora Kopiuj/przenieś (tworzenie foo10 wewnętrznie) i tylko 1 wywołanie destruktora Foo. (Wrócę do tego później).

4. Dla foo11, przekazaliśmy bezpośrednio liczbę całkowitą 11 tak, że unordered_map wywoła konstruktor Foo(int). W przeciwieństwie do funkcji w (3), nie potrzebowaliśmy nawet jakiegoś wcześniej wychodzącego obiektu foo, aby to zrobić.

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

insert() prawie zawsze wymaga budowy lub istnienie jakiegoś Foo obiektu w zakresie main() (po którym następuje kopiowanie lub przenoszenie), jeśli używa się emplace(), to każde wywołanie konstruktora jest wykonywane całkowicie wewnętrznie w zakresie unordered_map (tzn. wewnątrz zakresu definicji metody emplace()). Argument(y) dla klucza, który przekazujesz emplace(), jest bezpośrednio przekazywany do wywołania konstruktora Foo wewnątrz unordered_map (Opcjonalne dodatkowe szczegóły: jeśli nowo zbudowany obiekt jest natychmiast wbudowany w jedną ze zmiennych składowych unordered_map, tak aby żaden Destruktor nie został wywołane, gdy wykonanie opuszcza emplace() i nie są wywoływane konstruktory move lub copy).

Uwaga: przyczyna prawie w prawie zawsze jest wyjaśniona w I) poniżej.

1. continued: powód, dla którego wywołanie umap.emplace(foo3, d) wywołało Foo's non-const copy constructor jest następujący: ponieważ używamy emplace(), kompilator wie, że foo3 (obiekt non-const {6]}) ma być argumentem do jakiegoś konstruktora Foo. W tym przypadku najbardziej pasuje Foo konstruktor jest konstrukcją non-const copy Foo(Foo& f2). To dlatego umap.emplace(foo3, d) nazywa Konstruktor kopiujący, podczas gdy umap.emplace(11, d) Nie.

Epilog:

I. zauważ, że jedno przeciążenie insert() jest w rzeczywistości równoważne emplace(). Jak opisano w tym cppreference.com strona , przeciążenie template<class P> std::pair<iterator, bool> insert(P&& value) (czyli przeciążenie (2) z insert() na tej cppreference.com strona) jest odpowiednikiem emplace(std::forward<P>(value)).

II. dokąd się stąd udać?

A. Pobaw się z powyższym źródłem kod i dokumentacja badań dla insert() (np. tutaj) i emplace() (np. tutaj), które można znaleźć online. Jeśli używasz IDE, takiego jak eclipse lub NetBeans, możesz łatwo uzyskać IDE, aby powiedzieć, które przeciążenie insert() lub emplace() jest wywoływane(w eclipse, po prostu trzymaj kursor myszy na stałym wywołaniu funkcji przez sekundę). Oto kilka kodów 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 to 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 cals
// 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 przeciążenie std::pair konstruktora (zobacz Referencja ) może mieć istotny wpływ na to, ile obiektów zostanie skopiowanych, przeniesionych, utworzonych i/lub zniszczonych oraz kiedy to nastąpi.

B. Zobacz, co się dzieje, gdy używasz innej klasy kontenera (np. std::set lub std::unordered_multiset) zamiast std::unordered_map.

C. Teraz użyj Goo obiektu (tylko zmienioną kopię Foo) zamiast int jako typu zakresu w unordered_map (tzn. użyj unordered_map<Foo, Goo> zamiast unordered_map<Foo, int>) i zobacz, ile i które konstruktory Goo są dzwoniłem. (Spoiler: jest efekt, ale nie jest zbyt dramatyczny.)