C++: std::vector with space reserving for both ends

Question

Just some thoughts:

I wanted to erase x elements from the beginning of a std::vector with size n > x. Since a vector uses an array internally, this could be as easy as setting the pointer for vector.begin() to the index of the first element which is kept. But instead, erase shifts all elements in the array to that the first element actually starts at index 0, making the erase operation take much more time than it could.

Furthermore, if the valid 'zone' of the internal array was really controlled by just some start and end indices / pointers of the vector structure, then there would be also the option to reserve space in front of the first element. E.g., a vector is initialized and 20 spaces are reserved at the end and 10 at the beginning. Internally, then an array of space 30 (or 32) is created, where the start index/pointer points to the 11th value of the internal array, allowing to include new elements to the front of the 'vector' in constant speed.

Well, my point is, I think such a data structure would be somewhat useful, at least for my purposes. I'm pretty sure someone already thought of this and already implemented it. So I want to ask: How is the data structure called that I'm describing? If it exists, I'd love to use it. I think this is not a double-linked list, since there, every element is kind of a struct containing the element value and additional pointers to the neighbors (to my knowledge).

EDIT: And yes, such a structure would probably use more memory than necessary, especially when erasing some elements from the beginning, because then, the internal array still has the initial size. But well, memory isn't a big issue anymore for most problems, and there could be a (time-expensive) 'memory-optimize' operation to create a new, smaller array, copying over all old values and deleting the old internal array to use the smallest possible size.

It's not quite a [`std::deque`](http://en.cppreference.com/w/cpp/container/deque), but that's the closest in the Standard Library I think. — BoBTFish, Jan 12 '17 at 11:12
`std::vector` does not really "use an array internally". It allocates via `std::allocate`, which uses placement new to reserve memory. It does not (and cannot) use `new[]`. — Christian Hackl, Jan 12 '17 at 11:15
Any reason you can't use a std::vector ? This would allow you to keep null items at the front. — UKMonkey, Jan 12 '17 at 11:17
Sounds like one of Boost's dynamic ring buffers work the way you describe: they can insert and erase at both ends without moving existing data, and when the buffer is full, it can be reallocated. — Kerrek SB, Jan 12 '17 at 11:17
@UKMonkey Never thought of that. But that does not guarantee that the elements to which the pointers point are contiguous, right? Btw, I usually avoid using pointers as much as possible since I'm worried that they will lead to problems at some time. Also, the environment I'm working in doesn't have c++11 and neither allows the inclusion of boost, afaik. — kushy, Jan 12 '17 at 11:20
@kushy not unless you use placement new - but that's probably not worth the effort. — UKMonkey, Jan 12 '17 at 11:24
What keeps you from writing a wrapper around `vector`? It doesn't sound too difficult to keep track of the beginning (keeping track of the end is done by the vector), and provide methods and ctor for reserving at the beginning. My guess is it's about a day's work, i.e. it cannot be more than 2 weeks ;-). — Peter - Reinstate Monica, Jan 12 '17 at 11:28
I agree with UKMonkey about placement new. It can totally solve the problem with [a lot of effort](http://stackoverflow.com/questions/40605120/how-to-use-void-as-a-single-variable-holder-ex-void-raw-someclass/40605486#40605486). It is worth learning, at least for me. ... By the way, there is a lot of difference between 1 day and 2 weeks, no? :) — javaLover, Jan 12 '17 at 11:32

Nim · Accepted Answer · 2017-01-12T12:59:45.930

Expanding on @Kerrek SB's comment, boost::circular_buffer<> does I think what you need, for example:

#include <iostream>
#include <boost/circular_buffer.hpp>

int main()
{
  boost::circular_buffer<int> cb(3);

  cb.push_back(1);
  cb.push_back(2);
  cb.push_back(3);

  for( auto i : cb) {
      std::cout << i << std::endl;
  }

  // Increase to hold two more items
  cb.set_capacity(5);
  cb.push_back(4);
  cb.push_back(5);

  for( auto i : cb) {
      std::cout << i << std::endl;
  }

  // Increase to hold two more items
  cb.rset_capacity(7);
  cb.push_front(0);
  cb.push_front(-1);

  for( auto i : cb) {
      std::cout << i << std::endl;
  }  
}

TBH - I have not looked at the implementation, so cannot comment on whether it moves data around (I'd be highly surprised.) but if you pull down the source, take a quick peek to satisfy if performance is a concern...

EDIT: Quick look at the code reveals that the push_xxx operations does not indeed move data around, however the xxx_capacity operations do result in a move/copy - to avoid that, ensure the ring has enough capacity at the start and it will work as you wish...

C++: std::vector with space reserving for both ends

1 Answers1