Re: [container] Contributing 'stationary_vector' to Boost

From: Jeff Hajewski (jeff.hajewski_at_[hidden])
Date: 2021-01-05 19:06:23

On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost <
boost_at_[hidden]> wrote:

> Not quite - my container is single-ended.
>
I assume this is because you grow your block size as you extend the vector.
Without looking at the implementation of deque, could you not use your
approach when appending on the left side as well?
Both sides of the deque would allocate geometrically increasing block sizes
independently, which would maintain algorithmic complexity.

Jeff

Mehrdad
>
> On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <hans.dembinski_at_[hidden]>
> wrote:
>
> >
> > > On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami_at_[hidden]>
> wrote:
> > >
> > > It's similar, but not quite. std::deque uses fixed-size blocks and
> tends
> > to be slow in my experience (at least in some implementations).
> > > stationary_vector on the other hand uses variably-sized blocks (with
> > geometrically increasing sizes).
> > > Its capacity at least doubles every round; in fact, it reduces to a
> > single array when the entire size is reserved beforehand.
> > > This allows it to perform much more competitively with (and similarly
> > to) std::vector.
> > > It may be what std::deque should have been, but isn't currently.
> >
> > Ok, that sounds like your container offers the same basic guarantees as a
> > std::deque with a more efficient implementation. If it is indeed more
> > efficient due to the use of variable-sized blocks than
> > boost::container::deque, then could you include your improvements into
> > boost::container::deque?
> >
> >
> >
> https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>