CODEWITHSUNDEEP
c++vectorsize
madshov
madshov

Reputation: 693

c++ inserting elements at the end of a vector

I am experiencing a problem with the vector container. I am trying to improve the performance of inserting a lot of elements into one vector.

Basically I am using vector::reserve to expand my vector _children if needed:

if (_children.capacity() == _children.size())
{
     _children.reserve(_children.size() * 2);
}

and using vector::at() to insert a new element at the end of _children instead of vector::push_back():

_children.at(_children.size()) = child;

_children has already one element in it, so the first element should be inserted at position 1, and the capacity at this time is 2.

Despite this, an out_of_range error is thrown. Can someone explain to me, what I misunderstood here? Is it not possible to just insert an extra element even though the chosen position is less than the vector capacity? I can post some more code if needed.

Thanks in advance.

/mads

Upvotes: 1

Views: 1363

Answers (7)

NPE
NPE

Reputation: 500277

Neither at nor reserve increase the size of the vector (the latter increases the capacity but not the size).

Also, your attempted optimization is almost certainly redundant; you should simply push_back the elements into the array and rely on std::vector to expand its capacity in an intelligent manner.

Upvotes: 1

jdm
jdm

Reputation: 10030

The capacity of a vector is not the number of elements it has, but the number of elements it can hold without allocating more memory. The capacity is equal to or larger than the number of elements in the vector.

In your example, _children.size() is 1, but there is no element at position 1. You can only use assignment to replace existing elements, not for adding new ones. Per definition, the last element is at _children.at(_children.size()-1).

The correct way is just to use push_back(), which is highly optimized, and faster than inserting at an index. If you know beforehand how many elements you want to add, you can of course use reserve() as an optimization.

It's not necessary to call reserve manually, as the vector will automatically resize the internal storage if neccessary. Actually I believe what you do in your example is similar what the vector does internally anyway - when it reaches the capacity, reserve twice the current size.

See also http://www.cplusplus.com/reference/stl/vector/capacity/

Upvotes: 0

Marcelo Cantos
Marcelo Cantos

Reputation: 185852

Increasing the capacity doesn't increase the number of elements in the vector. It simply ensures that the vector has capacity to grow up to the required size without having to reallocate memory. I.e., you still need to call push_back().

Mind you, calling reserve() to increase capacity geometrically is a waste of effort. std::vector already does this.

Upvotes: 8

pmr
pmr

Reputation: 59811

vector::reserve is only internally reserving space but is not constructing objects and is not changing the external size of the vector. If you use reserve you need to use push_back. Additionally vector::at does range checking, which makes it a lot slower compared to vector::operator[].

What you are doing is trying to mimic part of the behaviour vector already implements internally. It is going to expand by its size by a certain factor (usually around 1.5 or 2) every time it runs out of space. If you know that you are pushing back many objects and only want one reallocation use:

vec.reserve(vec.size() + nbElementsToAdd);

If you are not adding enough elements this is potentially worse than the default behaviour of vector.

Upvotes: 0

Kerrek SB
Kerrek SB

Reputation: 476990

That's not what at() is for. at() is a checked version of [], i.e. accessing an element. But reserve() does not change the number of elements.

You should just use reserve() followed by push_back or emplace_back or insert (at the end); all those will be efficient, since they will not cause reallocations if you stay under the capacity limit.

Note that the vector already behaves exactly like you do manually: When it reaches capacity, it resizes the allocated memory to a multiple of the current size. This is mandated by the requirement that adding elements have amortized constant time complexity.

Upvotes: 1

Douglas Leeder
Douglas Leeder

Reputation: 53310

You have to differentiate between the capacity and the size. You can only assign within size, and reserve only affects the capacity.

Upvotes: 0

visitor
visitor

Reputation: 1801

This causes accesses out of bounds. Reserving memory does not affect the size of the vector.

Basically, you are doing manually what push_back does internally. Why do you think it would be any more efficient?

Upvotes: 1

Related Questions