Re: [container] Contributing 'stationary_vector' to Boost

From: Mehrdad Niknami (mniknami_at_[hidden])
Date: 2021-01-04 18:45:37

Hi,

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.

Thanks,
Mehrdad

On Mon, Jan 4, 2021 at 6:17 AM Hans Dembinski <hans.dembinski_at_[hidden]>
wrote:

> Hi,
>
> > On 4. Jan 2021, at 13:17, Mehrdad Niknami via Boost <
> boost_at_[hidden]> wrote:
> >
> > Hi all,
> >
> > Happy new year! New mailing list member here.
> >
> > I've developed an STL-style stationary_vector class that retains elements
> > in-place when growing.
> > Very briefly, it is effectively a piecewise-contiguous vector, with the
> > following advantages over vector:
> >
> >   - Appending has O(1) overhead in the *worst* case (e.g., push_back()
> does
> >   not move elements)
> >   - Insertion and random-access can be done in parallel, as prior
> >   iterators & references remain valid
> >
> > This has a variety of benefits, including better UX (no "hiccups" due to
> > reallocations), and the ability to simplify parallel processing of
> > streaming data.
> > It occurred to me the larger C++ community might find this useful.
> >
> > I was wondering if there would be interest in incorporating it into
> > Boost.Container, and if so, what steps I could take to make that happen?
>
> It sounds like you reinvented a deque?
> https://en.cppreference.com/w/cpp/container/deque
>
> Best regards,
> Hans