Boost logo

Boost :

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


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

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.

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

[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?



Boost list run by bdawes at, gregod at, cpdaniel at, john at