Re: [container] Proposal for ring queues

From: degski (degski_at_[hidden])
Date: 2020-06-17 10:01:53

On Mon, 15 Jun 2020 at 11:32, Peter Dimov via Boost <boost_at_[hidden]>
wrote:

> 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/b6305194e14de6c6678cea6a847d1aee0021d2b1/include/this_local/this_local/detail/this_local/detail.hpp#L503>
.

degski