CODEWITHSUNDEEP
c++intstdmovestdvector
Andrei Baskakov
Andrei Baskakov

Reputation: 11

How to efficiently insert a pair in std::vector?

I have a std::vector<std::pair<...>> and want to efficiently modify them:

vector<pair<int, int>> vec;
vec.emplace_back(4, 5);
vec.emplace_back(6, 7);

// Now I want to set the first pair in the vector.
vec[0] = make_pair(10, 10);

As I understand we have

  1. Temporary pair is constructed by make_pair. This takes 2 copies of ints.
  2. Next pair<int,int>& operator=( pair<int,int>&& other ) is called which calls std::move on two ints in the pair. This takes 2 copies of ints.

As a result we 4 copies of ints!

But modification of a pair in a Vector should take 2 copies of ints. emplace_back seems to be what I need, but it makes an in-place construction only in the end of the vector, not at any other index.

For sure I can do

vec[0].first = 10;
vec[0].second = 10;

But this takes into account the internals of pair, which I want to omit.

How can I write the code more efficiently (without redundant copies of ints)?

Upvotes: 1

Views: 995

Answers (1)

John Zwinck
John Zwinck

Reputation: 249424

Enable compiler optimization and behold, they are exactly the same: https://godbolt.org/z/Nwb_y0

The assembly generated by GCC 8 is:

    mov     rax, QWORD PTR [rdi]
    mov     DWORD PTR [rax], esi
    mov     DWORD PTR [rax+4], edx

As you can see, the integers are stored just once, there is no extra copy.

If you compile with -O1 instead of -O2 or -O3, the code is actually worse for the "simpler" version without make_pair: it loads the address from the vector twice. So the make_pair version is better at -O1 and identical at higher levels of optimization.

Upvotes: 1

Related Questions