[boost] GSoC: Enhanced vector and deque containers

Subject: [boost] GSoC: Enhanced vector and deque containers
From: Benedek Thaler (thalerbenedek_at_[hidden])
Date: 2015-02-22 05:09:40

Hi,

I'm looking at the "Enhanced vector and deque containers"[0] item of the
GSoC projects. I have to following interface idea:

boost::devector:
Like std::vector, but the first call to push_back inserts the element to
the middle of the buffer. Likewise, reserve puts the contents to the middle
of the new buffer (if any). This allows a cheap push_front, pop_front,
push_back, pop_back.

boost::deque:
Like std:deque, but segment size can be specified in the constructor. To
make buffer operations easier, a `segment_end` would be provided:

iterator segment_end(iterator begin)

Which returns the end of the largest consecutive range starting at `begin`.

I'm also thinking about the following twist: Assuming this layout:

[a,b,c,d] [e,f,g,_]

Brackets denote segments, letters are elements, underscore is empty space.
Here, inserting `x` after `d` normally results several moves and this
layout:

[a,b,c,d] [x,e,f,g]

But instead, we could allocate a new segment:

[a,b,c,d] [_,x,_,_] [e,f,g,_]

To make the insertion cheaper. This behavior is similar to a segmented
list, i.e: std::list<boost::devector<T>>

Are these similar to the "extra functionality" mentioned in the docs you
were thinking about?

Thanks,
Benedek

[0]:
https://svn.boost.org/trac/boost/wiki/SoC2015#a5.Enhancedvectoranddequecontainers