1

I am trying to figure out the fastest way to keep constant number of elements in vector (or maybe there is some ready-made structure that do it automatically).

In my app I am adding multiple elements to the vector and I need to do it fast. Because of vector's self resizing at some point it is significantly decreasing overall application speed. What I was thinking about is to do something like this:

if(my_vector.size() < 300)
    my_vector.push_back(new_element);
else
{
    my_vector.pop_front();
    my_vector.push_back(new_element);
}

but after first few tests I've realized that it might not be the best solution, because I am not sure if pop_front() and later push_back() doesn't still need to resize at some point.

Is there any other solution for this?

sebap123
  • 2,541
  • 6
  • 45
  • 81
  • IIRC it resizes when the count goes over a power of 2. – Carlos May 11 '16 at 14:58
  • 3
    You can use `std::array` if you know the size of elements you want. Or even better use and `std::deque` which is optimized for front/back insertion/removal and always check the `size()` before anything you do. – george_ptr May 11 '16 at 15:00
  • @Carlos Because in my case I have 100s of those vectors even if half is resizing it is taking significant number of time. – sebap123 May 11 '16 at 15:01
  • @GeorgeAl `std::array` is not best here, because I know how many elements I want to have, but not how many I'll have. As for `std::deque` I might try this, now when I think about it. If I remember it correctly if I'll remove first element it will start next time reading from second - is that correct? – sebap123 May 11 '16 at 15:05
  • You can keep your vector a constant size and when you reach your size limit just swap the value for that position e.g.: `my_vector[299] = new_element` you wouldn't need to `pop`, also `pop`ing doesn't cause a reallocation – EdChum May 11 '16 at 15:07
  • @EdChum in this case I am swapping n-th element, but when I am reading it in order, then I have mess, so I cannot do it like that. – sebap123 May 11 '16 at 15:09
  • 2
    Take a look at [boost::circular](http://www.boost.org/doc/libs/1_60_0/doc/html/circular_buffer.html) – user4581301 May 11 '16 at 15:30
  • Reopened. This question is **not** about FIFO, but about **fixed size**. That's a completely different animal. – Pete Becker May 11 '16 at 15:53

3 Answers3

2

Use a std::queue. Its underlying container is a std::deque, but like a stack a queue's interface is specifically for FIFO operations (push_back, pop_front), which is exactly what you're doing in your situation. Here's why a deque is better for this situation:

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location.

The complexity (efficiency) of common operations on deques is as follows:

  • Random access - constant O(1)
  • Insertion or removal of elements at the end or beginning - constant O(1)
user6321193
  • 21
  • 1
  • It's worth emphasizing that `pop_front` is the really slow operation in a `vector`. We need a structure with good `pop_front()` performance. – Aaron McDaid May 11 '16 at 16:04
1

To implement a fixed-size container with push_back and pop_front and minimal memory shuffling, use a std::array of the appropriate size. To keep track of things you'll need a front index for pushing elements and a back index for popping things. To push, store the element at the location given by front_index, then increment front_index and take the remainder modulo the container size. To pop, read the element at the location given by back_index, and adjust that index the same way you did front_index. With that in place, the code in the question will do what you need.

Pete Becker
  • 74,985
  • 8
  • 76
  • 165
0

You just need to reserve the capacity to a reasonable number. The vector will not automatically shrink. So it only will grow and, possibly, stop at some point.

You might be also interested in the resize policies. For example Facebook made a substantial research and created own implementation of the vector - folly::fbvector which has better performance than std::vector

Community
  • 1
  • 1
Teivaz
  • 5,462
  • 4
  • 37
  • 75