On Mon, 15 Jun 2020 at 11:32, Peter Dimov via Boost
Andrey Semashev wrote:
I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".
Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...
Erasing/inserting at begin()+k for small k will be considerably more efficient than vector.
Another approach worth exploring in my opinion is *to change 'the allocator' from being a std-node-allocator to being a node=allocator that 'dispenses' from a std::vector.* Such an 'allocator' exists, i.e. 'plf::colony'. Now our LL (the ring) has vector-allocation-patterns behind it [see docs plf::colcony], with an added benefit: the nodes are like with std::allocator never moved. The latter is currently (due to implementation details, which will change) not strictly true, notably reserve() moves objects (reserve() is not usable with non-movable objects), but plf::colony is otherwise well usable for non-movable-non-copyable types (contrary to what is said in the docs). I have written a PoC https://github.com/degski/this_local/blob/b6305194e14de6c6678cea6a847d1aee00... . degski