GSoC: Enhanced vector and deque containers
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.Enhancedvectoranddequeconta...
participants (1)
-
Benedek Thaler