Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

push_back is more efficient than emplace_back?

Tags:

c++

c++11

vector

I wanted to see the difference between push_back and emplace_back, as in several places I read recommendation as now it's better to use emplace_back as "it can do all push_back can do and more", so I expect ti to be more efficient. But to my surprise

#include <iostream>     
#include <vector>    

class A
{
    public:
    A() {std::cout << "A const" << std::endl;}
    ~A() {std::cout << "A dest" << std::endl;}
    A(const A& a) {std::cout << "A copy const" << std::endl;}
    A(A&& a) {std::cout << "A move const" << std::endl;}
    A& operator=(const A& a) {std::cout << "A copy operator=" << std::endl; return *this; }
    A& operator=(A&& a) {std::cout << "A move operator=" << std::endl;  return *this; }
};

int main () {
    std::vector<A> va;
    std::cout <<"push:" << std::endl;
    va.push_back(A());
    std::cout <<std::endl<< "emplace:" << std::endl;
    va.emplace_back(A());

    std::cout <<std::endl<< "end:" << std::endl;

    return 0;
}

Output is

push:
A const
A move const
A dest

emplace:
A const
A move const
A copy const
A dest
A dest

end:
A dest
A dest

emplace_back calls move constructor and then copy one when push_back calls only one move const. I checked with g++ (Ubuntu 7.4.0-1ubuntu1~16.04~ppa1) 7.4.0 and online C++ shell. Am I missing something?

like image 360
DoehJohn Avatar asked May 25 '20 21:05

DoehJohn


People also ask

Why Emplace_back is faster than Push_back?

because emplace_back would construct the object immediately in the vector, while push_back , would first construct an anonymous object and then would copy it to the vector.

What is the time complexity of Push_back?

push_back( ): It adds a new element at the end of the list, after its current last element. Its time complexity is O(1).

Is vector Push_back slow?

In short, push_back is doing more than what operator[] is doing - which is why it is slower (and more accurate).


1 Answers

push_back is not more efficient, and the results you observe are due to the vector resizing itself.

When you call emplace after push_back, the vector has to resize itself to make room for the second element. This means that it has to move the A that was originally inside the vector, making emplace appear more complex.

If you reserve enough space in the vector beforehand, this doesn't happen. Notice the call to va.reserve(2) after va's creation:

#include <iostream>     
#include <vector>    

class A
{
    public:
    A() {std::cout << "A const" << std::endl;}
    ~A() {std::cout << "A dest" << std::endl;}
    A(const A& a) {std::cout << "A copy const" << std::endl;}
    A(A&& a) {std::cout << "A move const" << std::endl;}
    A& operator=(const A& a) {std::cout << "A copy operator=" << std::endl; return *this; }
    A& operator=(A&& a) {std::cout << "A move operator=" << std::endl;  return *this; }
};

int main () {
    std::vector<A> va;
    // Now there's enough room for two elements
    va.reserve(2);
    std::cout <<"push:" << std::endl;
    va.push_back(A());
    std::cout <<std::endl<< "emplace:" << std::endl;
    va.emplace_back(A());

    std::cout <<std::endl<< "end:" << std::endl;

    return 0;
}

The corresponding output is:

push:
A const
A move const
A dest

emplace:
A const
A move const
A dest

end:
A dest
A dest

Can we make things even more efficient? Yes! emplace_back takes whatever arguments you provide it, and forwards them to A's constructor. Because A has a constructor that takes no arguments, you can also use emplace_back with no arguments! In other words, we change

va.emplace_back(A());

to

va.emplace_back(); // No arguments necessary since A is default-constructed

This results in no copy, and no move:

push:
A const
A move const
A dest

emplace:
A const

end:
A dest
A dest

A note on vectors resizing: It's important to note that the implementation of std::vector is smart. If A had been a trivially copyable type, std::vector might have been able resize in-place without additional copying using a system function similar to realloc. However because As constructors and destruction contain code, realloc can't be used here.

like image 123
Alecto Irene Perez Avatar answered Oct 08 '22 02:10

Alecto Irene Perez