c++ container very efficient at adding elements to the end

Question

I have been running a c++ program for scientific purpose and I am now looking at optimizing it.

The bottleneck seems to be a function where I need to stack pairs of integers. Their number is impossible to know from the start, and I have been using a std::vector of a custom struct holding two ints. Is there a more efficient data container for repetitively adding elements at the end? Should I use it with two ints instead of a pair or custom structure?

edit: After timing and profiling my program, I can say that, for my use, vector is slightly faster than deque (by only 3%). My layman conclusion is that the CPU makes a good use of the contiguity of the data. Optimization is more than ever a sorcery for me! And to those it may help: I actually improved significantly my running time by switching from the STL C++ 11 random number generator to the BOOST one.

Answer 1

The cost of the logarithmic number of reallocations you have to do is arguably irrelevant. However, you may consider using a std::deque that guarantees O(1) insertion at the front and at the end. You would lose contiguity, but some cache friendliness is kept. A deque is usually a decent trade-off, especially if you need to pop from the front.

Consider also estimating the number of elements the vector will store, and using reserve. Be careful however not to waste too much memory or you'll get the opposite effect.

Answer 2

As already mentioned by gd1, a std::deque (double-ended queue) allows fast insertion and deletion at both ends. Additionally, insertion and deletion at either end of a deque never invalidates pointers or references.

In your case you could for example use std::deque with std::pair (defined in <utility>) to suit your needs:

// Small example:
deque<pair<int, int>> deq;
deq.push_back({1234, 4321});
cout << deq.at(0).first << " " << deq.at(0).second;

// using 'at' above, should normally be inside a try block as it may throw 
// out_of_range exception