double ended vector?

[Gamer2015]

Hey there

std::vector is known to be contiguous in memory but it's interface only provides a poor way to insert elements at the beginning, right?

Did any of you once need a container that manages contiguous memory where the performance is not that bad when you have to insert at the beginning (and the end?)

If yes, did you write your own vector class?
- If no, did you just use std::vector and inserted at the beginning?

[Hippogriff]

Any time I needed fairly good performance and insertion at both ends I used a deque. It is -mostly- continuous.
http://www.cplusplus.com/reference/deque/deque/

If you "had" to have contiguous memory I guess I would just deal with inserting at the beginning of the vector. I can't think of an easy way to keep continuous memory and make inserting any better in terms of performance than a vector does.

[htirwin]

You could just allocate more memory for extra space at the beginning, and let the middle of the allocated space be the starting point... Just like with vector, you would have to reallocate when you hit either the beginning or end of the allocated space. It would have about twice the memory overhead of a vector.

[Cubbi]

Is http://www.boost.org/doc/libs/1_58_0/doc/html/boost/circular_buffe_idp26654784.html what you need?

[Gamer2015]

Is http://www.boost.org/doc/libs/1_58_0/doc/html/boost/circular_buffe_idp26654784.html what you need?

Nah, I think circular buffer is not what I'd go for

You could just allocate more memory for extra space at the beginning, and let the middle of the allocated space be the starting point... Just like with vector, you would have to reallocate when you hit either the beginning or end of the allocated space. It would have about twice the memory overhead of a vector.

This seems like a good approach.
If you want to clear the space overhead you could allocate the needed space, move the elements and then delete the old space.

[ne555]

> allocate the needed space, move the elements and then delete the old space.
so every time that you put one more element you reallocate the whole array.
If you mean to do that after you are done with the reading and would start with the processing, then it matters not the container that you use, you could simply transform it in a std::vector at the end.


you mention that you need contiguous memory, but don't specify why. If you can manage to work with two chunks then the circular buffer approach would be quite similar, except that you will be consuming the memory overhead on each insertion

[IWishIKnew]

std::vector<int> whatever;

whatever.insert(whatever.begin(), 1);  //EZ 

For good insert/removal performace, consider using a linked list. It really only matters if you are going to be swapping a lot, though... linked lists have poor random access performace, so you have to decide which one you want.

[naraku9333]

Linked lists do not provide any random access or use the contiguous memory OP stated as a requirement (though I guess a custom allocator could possibly solve that).

[Gamer2015]

I ended up using a std::vector and whenever I need to insert (let's say 100 elements) at the beginning (I know how many elements I have to insert) I use reserve, move the elements in the vector by needed_space and then assign the first elements to the new value.

vec.reserve(vec.size() + needed_space);
std::move(vec.begin(), vec.end(), vec.begin() + needed_space);
for(int i = 0; i < needed_space; ++i) {
    // move-assign elements
}