On filling a vector

In C++11, what is the cheapest way to create a std::vector<T> with a bunch of statically known T elements (in terms of the number of special member functions of T invoked)?

In other words, which of the blocks in the below program produces the fewest lines of output:

#include <iostream>
#include <vector>
struct S {
    S() { std::cout << " default ctor\n"; }
    S(int) { std::cout << " int ctor\n"; }
    S(S const &) { std::cout << " copy ctor\n"; }
    S(S &&) { std::cout << " move ctor\n"; }
    ~S() { std::cout << " dtor\n"; }
    void operator =(S const &) { std::cout << " copy assignment\n"; }
    void operator =(S &&) { std::cout << " move assignment\n"; }
};
int main() {
    {
        std::cout << "A1:\n";
        std::vector<S> s { S(), S(), S() };
    }
    {
        std::cout << "A2:\n";
        std::vector<S> s { {}, {}, {} };
    }
    {
        std::cout << "A3:\n";
        std::vector<S> s { 0, 0, 0 };
    }
    {
        std::cout << "B1:\n";
        std::vector<S> s;
        s.reserve(3);
        s.push_back(S());
        s.push_back(S());
        s.push_back(S());
    }
    {
        std::cout << "B2:\n";
        std::vector<S> s;
        s.reserve(3);
        s.push_back({});
        s.push_back({});
        s.push_back({});
    }
    {
        std::cout << "B3:\n";
        std::vector<S> s;
        s.reserve(3);
        s.push_back(0);
        s.push_back(0);
        s.push_back(0);
    }
    {
        std::cout << "C1:\n";
        std::vector<S> s;
        s.reserve(3);
        s.emplace_back(S());
        s.emplace_back(S());
        s.emplace_back(S());
    }
    // {
    //  std::cout << "C2:\n";
    //  std::vector<S> s;
    //  s.reserve(3);
    //  s.emplace_back({});
    //  s.emplace_back({});
    //  s.emplace_back({});
    // }
    {
        std::cout << "C3:\n";
        std::vector<S> s;
        s.reserve(3);
        s.emplace_back(0);
        s.emplace_back(0);
        s.emplace_back(0);
    }
}

(Of course, each block needs at least three “dtor” lines when its s goes out of scope, so keep those out of the count.)

What might come as a surprise is that the A variants using an initializer list, though short and sweet, are rather heavy: Each one needs three constructors for the three elements of the initializer list (“default ctor” for A1 and A2, “int ctor” for A3), three copy constructors to copy the elements from the initializer list into the vector, and three destructors when destroying the initializer list. Nine calls to special member functions overall.

That is just as expensive as the B variants. (The difference being the order in which the special member functions are called for the individual elements.) However, the advantage of all three B variants is that they use the move constructor instead of the copy constructor to pass the temporary S instances into the vector.

(If you had hoped that the A variants would use the move constructors instead of the copy constructors, too: that does not work, as initializer lists only offer const access to their members.)

Variant C1 is not any different from variant B1. Still nine calls overall (employing the move constructor).

Variant C3, finally, is better: Although it looks more expensive to pass “wrong” int arguments that first need to be converted into proper S instances, the big benefit here is that those “int ctor” calls can directly instantiate the vector elements—no construction of temporary S instances, no copy or move constructors, no destruction of temporaries. Just three constructor calls overall.

(And variant C2 is commented out for good reason; there is just no way to tell emplace_back to instantiate an element directly into the vector through a default constructor call. But then again, most of the time what you want to put into the vector are not default-constructed elements, anyway.)

Advertisements

5 thoughts on “On filling a vector

  1. Bill Jobs

    {
    std::cout << "D1:\n";
    std::vector s (3);
    }

    D1:
    default ctor
    default ctor
    default ctor
    dtor
    dtor
    dtor

    //—————————-
    {
    std::cout << "D2:\n";
    std::vector s (3, 0);
    }

    D2:
    int ctor
    copy ctor
    copy ctor
    copy ctor
    dtor
    dtor
    dtor
    dtor

    Reply
    1. stbergmann Post author

      Yeah, if all elements happen to have the same value. (I should have made the original code more interesting to stress that what I wanted to talk about is if the elements have arbitrary, and in general different, values.)

      Reply
  2. bmichaelsen

    I created myself a struct Data { int m_a; Data() : m_a(4711) {}; Data(a) : m_a(a+4711) {}; }; and benchmarked filling a three element vector. Here are the results from three runs in walltime:

    A1/A2/A3/B1/B2/B3/C1/C2/C3
    72.0/72.0/72.0/87.5/89.6/87.5/87.4/-/90.0
    71.9/72.1/72.1/87.5/89.6/87.5/87.4/-/90.0
    72.0/72.0/72.0/87.5/89.6/87.5/87.4/-/90.0

    … which suggests the conclusion of “C3, finally, is better”, to be misleading at least as a general advise. And indeed the A1/A2/A3 calls seem to not only being the most readable, but also the best performing — at least in my test runs.

    Done with gcc 4.8.3 and -std=c++11 -O2 on a Intel i5-4200U@1.6GHz (which is not an uncommon piece of hardware).

    Reply
  3. Pingback: 50 ways to fill your vector … | You can't take the sky from me.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s