std::vector push_back() semantics

Question

I understand that push_back in an std::vector places a copy of the object passed as argument at the end.

Let's consider this simple example

class Foo
{
public:
  Foo(int i=-1) :i_(i) {std::cout << "Foo:" << i_ << std::endl;}

  Foo(const Foo& rhs) 
  {
    i_ = rhs.i_;
    std::cout << "Foo copy CTOR:" << i_ <<  std::endl;
  }

  ~Foo() {std::cout << "~Foo:" << i_ << std::endl;}

private:
  int i_;
};

And this fragment of code

void testObjects()
{
  std::vector<Foo> vFoo;

  for (int i=0; i < 3; i++)
  {
    std::cout << std::endl;
    Foo aFoo(i+100);
    vFoo.push_back(aFoo);
    std::cout << "i=" << i << " vector size=" << vFoo.size() 
              << std::endl;
  }
  std::cout << "end of loop - vector size=" << vFoo.size() 
            << std::endl << std::endl;
}

The result that I am getting is:

Foo:100
Foo copy CTOR:100
i=0 vector size=1
~Foo:100

Foo:101
Foo copy CTOR:100
Foo copy CTOR:101
~Foo:100
i=1 vector size=2
~Foo:101

Foo:102
Foo copy CTOR:100
Foo copy CTOR:101
Foo copy CTOR:102
~Foo:100
~Foo:101
i=2 vector size=3
~Foo:102
end of loop - vector size=3

~Foo:100
~Foo:101
~Foo:102

I've got the impression the the vector increases its size by one (as expected) and its content is shifted (down ?), causing extra (??) copy-construction. Am I right?

I thank you in advance for your time.

Regards

Yes, you are right. If you want proof, add a reserve call and see what changes. — David Schwartz
– David Schwartz, Commented Oct 8, 2013 at 10:09

Krzysztof Kosiński · Accepted Answer · 2013-10-08 18:48:20Z

3

The contents of the vector are not shifted, otherwise push_back() could not be amortized constant time.

Based on the output, I think your implementation of std::vector starts with a capacity of 0 or 1, and doubles the capacity whenever it's exceeded. What you're seeing is not the shifting of the contents of the vector, but a reallocation of the internal memory buffer.

To verify, add this line after the declaration of vFoo:

vFoo.reserve(16);

You should not see the extra copy constructor calls after that.

Alternatively, you could run the test code up to higher sizes of the vector (at least up to 4), and verify that the copy constructions of all elements happen less and less often. In the long run, there should be at most O(log N) reallocations for N insertions.

If the above is not the case, it indicates that you are using a broken implementation of std::vector which does not conform to the C++ standard.

edited Oct 8, 2013 at 18:48

answered Oct 8, 2013 at 10:10

Krzysztof Kosiński

4,3652 gold badges21 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user2857891 Over a year ago

Krzysztof: you are perfectly right. Calling "reserve" makes the printout statements behave as expected. So, is it always good practice to pre-serve capacity before inserting? Especially when I have an estimate of how many elements I'm going to push (e.g. reserve to the smallest power^2 larger that the expected size...)

Stack Overflow is garbage Over a year ago

@user2857891 not always. If you don't know in advance how many elements you're going to insert, then you can't meaningfully call reserve. It doesn't need to be a power of two either. If you know how many elements you want, reserve that many. Otherwise, just let the vector reallocate as it grows, and it will try to do so efficiently.

Theo Belaire Over a year ago

It's better to call reserve with a guess though, (lower bounds are always safe). It's not asymptotically any more efficient, but if you guess close it can save about a factor of two.

Collectives™ on Stack Overflow

std::vector push_back() semantics

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related