C ++ 맵에서 insert vs emplace vs operator []

C ++ 맵에서 insert vs emplace vs operator []

---

처음으로 맵을 사용하고 있으며 요소를 삽입하는 방법이 많이 있음을 깨달았습니다. 당신은 사용할 수 있습니다 emplace(), operator[]또는 insert()플러스 사용과 같은 변형 value_type또는 make_pair. 모든 사례에 대한 많은 정보와 특정 사례에 대한 질문이 있지만 여전히 큰 그림을 이해할 수 없습니다. 그래서 두 가지 질문은 다음과 같습니다.

1. 다른 것보다 그들 각각의 장점은 무엇입니까?

2. 표준에 배치를 추가해야합니까? 그것 없이는 불가능했던 것이 있습니까?

---

:지도의 특정 경우 기존의 옵션은 두 가지였다 operator[]와 insert(의 다른 맛을 insert). 그래서 나는 그것들을 설명하기 시작할 것입니다.

는 operator[]A는 발견 또는-추가 연산자. 지도 안에서 주어진 키를 가진 요소를 찾으려고 시도하고 존재하는 경우 저장된 값에 대한 참조를 반환합니다. 그렇지 않은 경우 기본 초기화로 새 요소가 삽입되어 참조를 반환합니다.

insert(단일 소자 풍미) 함수는 소요 value_type( std::pair<const Key,Value>)는 키 (사용 first부재)와 삽입하려고. 때문에 std::map중복을 허용하지 않는 것도 삽입은하지 않습니다 기존 요소가있는 경우.

이 둘의 첫 번째 차이점은 operator[]기본 초기화 값 을 구성 할 수 있어야한다는 점입니다. 따라서 기본 초기화 할 수없는 값 유형에는 사용할 수 없습니다. 둘 사이의 두 번째 차이점은 주어진 키를 가진 요소가 이미있을 때 발생하는 것입니다. 이 insert함수는 맵의 상태를 수정하지 않고 반복자를 요소 (및 false삽입되지 않았 음을 나타내는)에 반환합니다 .

// 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

insert인수 의 경우의 객체이며 value_type다른 방식으로 만들 수 있습니다. 적절한 유형으로 직접 구성하거나 객체 를 간단하게 생성 할 수 있기 때문에 생성 될 수 value_type있는 곳 에서 객체를 전달할 수 있습니다. 아마도 원하는 것은 아닙니다.std::make_pairstd::pair

다음 호출의 순 효과는 비슷합니다 .

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

그러나 실제로는 같지 않습니다 ... [1]과 [2]는 실제로 동일합니다. 두 경우 모두 코드는 동일한 유형 ( std::pair<const K,V>) 의 임시 객체를 만들어 insert함수에 전달합니다 . 이 insert함수는 이진 검색 트리에 적절한 노드를 만든 다음 value_type인수에서 노드로 부분 을 복사 합니다. 사용의 장점은 항상 일치value_type 한다는 점 입니다. 인수 유형을 잘못 입력 할 수 없습니다 !value_type value_typestd::pair

차이점은 [3]에 있습니다. 함수 std::make_pair는를 생성하는 템플릿 함수입니다 std::pair. 서명은 다음과 같습니다

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

나는 std::make_pair일반적인 사용법이므로 의도적으로 템플릿 인수를 제공하지 않았습니다 . 그리고 의미는 템플릿 인수로이 경우, 호출에서 추론하는 것입니다 T==K,U==V호출 할 수 있도록 std::make_pair반환하며 std::pair<K,V>(누락 참고 const). 서명은 value_type에 가깝지만 호출에서 반환 된 값과 동일하지 않아야합니다 std::make_pair. 충분히 가깝기 때문에 올바른 유형의 임시를 작성하고 복사를 초기화합니다. 그러면 노드에 복사되어 총 2 개의 사본이 생성됩니다.

템플릿 인수를 제공하면이 문제를 해결할 수 있습니다.

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

그러나 [1]의 경우 명시 적으로 유형을 입력하는 것과 같은 방식으로 오류가 발생하기 쉽습니다.

지금까지 외부 insert에서 생성 value_type하고 해당 객체를 컨테이너에 복사 해야하는 다른 호출 방법 이 있습니다. 또는 operator[]유형이 기본 구성 가능 하고 할당 가능한 경우 (의도적으로 만 초점을 맞추고 m[k]=v) 한 객체의 기본 초기화와 해당 객체 에 대한 값 의 사본 이 필요한 경우 사용할 수 있습니다.

11 C ++에서, 가변 템플릿 완벽한 전송로를 이용하여 용기에 요소를 추가하는 새로운 방법이 emplacing (장소에서 생성). emplace다른 컨테이너 의 함수는 기본적으로 동일한 작업 을 수행합니다. 컨테이너 에 복사 할 소스 를 가져 오는 대신 컨테이너에 저장된 객체의 생성자로 전달되는 매개 변수를 사용합니다.

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

[5]에서는로 std::pair<const K, V>작성되어 전달 emplace되지 않고 t및 u오브젝트에 대한 참조 가 전달되어 데이터 구조 내부의 하위 오브젝트 emplace생성자로 전달됩니다 value_type. 이 경우의 사본 이 전혀std::pair<const K,V> 수행 되지 않으므로emplace C ++ 03 대안 에 비해 이점이 있습니다. 의 경우와 마찬가지로 insert맵의 값을 무시하지 않습니다.

---

내가 생각하지 않은 흥미로운 질문 emplace은 실제로지도를 구현 하는 방법 이며, 일반적인 경우에는 간단한 문제가 아닙니다.

---

Emplace : rvalue 참조를 활용하여 이미 생성 한 실제 객체를 사용합니다. 즉, 복사 또는 이동 생성자가 호출되지 않으며 LARGE 객체에 적합합니다! O (로그 (N)) 시간

삽입 : 표준 lvalue 참조 및 rvalue 참조에 대한 오버로드와 삽입 할 요소 목록에 대한 반복자 및 요소가 속한 위치에 대한 "힌트"가 있습니다. "힌트"반복자를 사용하면 삽입 시간이 일정한 시간으로 줄어 듭니다. 그렇지 않으면 O (log (N)) 시간입니다.

Operator [] : 객체가 존재하는지 확인하고 존재하는 경우이 객체에 대한 참조를 수정하고, 그렇지 않으면 제공된 키와 값을 사용하여 두 객체에 대해 make_pair를 호출 한 다음 삽입 기능과 동일한 작업을 수행합니다. 이것은 O (log (N)) 시간입니다.

make_pair : 쌍을 만드는 것 이상을 수행하지 않습니다.

표준에 배치를 추가 할 필요가 없습니다. c ++ 11에서는 && 유형의 참조가 추가되었다고 생각합니다. 이것은 이동 의미론의 필요성을 제거하고 특정 유형의 메모리 관리를 최적화 할 수있게했습니다. 특히 rvalue 참조입니다. 오버로드 된 insert (value_type &&) 연산자는 in_place 시맨틱을 이용하지 않으므로 훨씬 덜 효율적입니다. rvalue 참조를 처리 할 수있는 기능을 제공하지만 객체의 구성에 대한 주요 목적은 무시합니다.

---

최적화 기회와 간단한 구문 외에도 삽입과 배치 사이의 중요한 차이점은 후자가 명시 적 변환을 허용한다는 것 입니다. (이것은지도뿐만 아니라 전체 표준 라이브러리에 있습니다.)

다음은 시연하는 예입니다.

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

이것은 매우 구체적인 세부 사항이지만, 사용자 정의 전환 체인을 다루는 경우이를 염두에 두어야합니다.

---

다음 코드는 insert()차이점에 대한 "큰 그림 아이디어"를 이해하는 데 도움이 될 수 있습니다 emplace().

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

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;

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

내가 얻은 결과는 다음과 같습니다.

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

그것을주의해라:

1. 는 unordered_map항상 내부적으로 Foo객체 ( Foo *s가 아닌 s)를 키로 저장하며, 키는 파괴 될 때 모두 파괴됩니다 unordered_map. 여기서 unordered_map의 내부 키는 foos 13, 11, 5, 10, 7, 9입니다.

   • So technically, our unordered_map actually stores std::pair<const Foo, int> objects, which in turn store the Foo objects. But to understand the "big picture idea" of how emplace() differs from insert() (see highlighted box below), it's okay to temporarily imagine this std::pair object as being entirely passive. Once you understand this "big picture idea," it's important to then back up and understand how the use of this intermediary std::pair object by unordered_map introduces subtle, but important, technicalities.

2. Inserting each of foo0, foo1, and foo2 required 2 calls to one of Foo's copy/move constructors and 2 calls to Foo's destructor (as I now describe):

   a. Inserting each of foo0 and foo1 created a temporary object (foo4 and foo6, respectively) whose destructor was then immediately called after the insertion completed. In addition, the unordered_map's internal Foos (which are foos 5 and 7) also had their destructors called when the unordered_map was destroyed.

   b. To insert foo2, we instead first explicitly created a non-temporary pair object (called pair), which called Foo's copy constructor on foo2 (creating foo8 as an internal member of pair). We then insert()ed this pair, which resulted in unordered_map calling the copy constructor again (on foo8) to create its own internal copy (foo9). As with foos 0 and 1, the end result was two destructor calls for this insertion with the only difference being that foo8's destructor was called only when we reached the end of main() rather than being called immediately after insert() finished.

3. Emplacing foo3 resulted in only 1 copy/move constructor call (creating foo10 internally in the unordered_map ) and only 1 call to Foo's destructor. (I'll get back to this later).

4. For foo11, we directly passed the integer 11 to emplace(11, d) so that unordered_map would call the Foo(int) constructor while execution is within its emplace() method. Unlike in (2) and (3), we didn't even need some pre-exiting foo object to do this. Importantly, notice that only 1 call to a Foo constructor occurred.

5. We then directly passed the integer 12 to insert({12, d}). Unlike with emplace(11, d), this call to insert({12, d}) resulted in two calls to Foo's constructor.

This shows what the main "big picture" difference between insert() and emplace() is:

Whereas using insert() almost always requires the construction or existence of some Foo object in main()'s scope (followed by a copy or move), if using emplace() then any call to a Foo constructor is done entirely internally in the unordered_map (i.e. inside the scope of the emplace() method's definition). The argument(s) for the key that you pass to emplace() are directly forwarded to a Foo constructor call within unordered_map (optional additional details: where this newly constructed object is immediately incorporated into one of unordered_map's member variables so that no destructor is called when execution leaves emplace() and no move or copy constructors are called).

Note: The reason for the almost in almost always is explained in I) below.

3. continued: The reason why calling umap.emplace(foo3, d) called Foo's non-const copy constructor is the following: Since we're using emplace(), the compiler knows that foo3 (a non-const Foo object) is meant to be an argument to some Foo constructor. In this case, the most fitting Foo constructor is the non-const copy construct Foo(Foo& f2). This is why umap.emplace(foo3, d) called a copy constructor while umap.emplace(11, d) did not.

Epilogue:

I. Note that one overload of insert() is actually equivalent to emplace(). As described in this cppreference.com page, the overload template<class P> std::pair<iterator, bool> insert(P&& value) (which is overload (2) of insert() on this cppreference.com page) is equivalent to emplace(std::forward<P>(value)).

II. Where to go from here?

a. Play around with the above source code and study documentation for insert() (e.g. here) and emplace() (e.g. here) that's found online. If you're using an IDE such as eclipse or NetBeans then you can easily get your IDE to tell you which overload of insert() or emplace() is being called (in eclipse, just keep your mouse's cursor steady over the function call for a second). Here's some more code to try out:

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

You'll soon see that which overload of the std::pair constructor (see reference) ends up being used by unordered_map can have an important effect on how many objects are copied, moved, created, and/or destroyed and when this occurs.

b. See what happens when you use some other container class (e.g. std::set or std::unordered_multiset) instead of std::unordered_map.

c. Now use a Goo object (just a renamed copy of Foo) instead of an int as the range type in an unordered_map (i.e. use unordered_map<Foo, Goo> instead of unordered_map<Foo, int>) and see how many and which Goo constructors are called. (Spoiler: there is an effect but it isn't very dramatic.)

참고URL : https://stackoverflow.com/questions/17172080/insert-vs-emplace-vs-operator-in-c-map