Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Benedek Thaler (thalerbenedek_at_[hidden])
Date: 2017-09-26 21:06:33

On Tue, Sep 26, 2017 at 2:43 AM, Tim Song via Boost <boost_at_[hidden]>
wrote:

> Just some comments on devector for now, based on a quick read of the
> documentation and implementation.
>
>
Thanks for your time, really good points below.

> [snip]
>
> > typedef pointer iterator;
> > typedef const_pointer const_iterator;
>
> Why are pointers being used as iterator types directly?
>

To keep simple things simple. What's wrong with pointers?

> Implementation:
>
> > class devector
> >    : Allocator
>
> Even private derivation can interfere with overload resolution in
> unexpected and undesirable ways. You have enough data members around
> to leverage EBO without having to make devector itself derive from the
> allocator.
>

Noted.

> https://github.com/erenon/double_ended/blob/master/
> include/boost/double_ended/devector.hpp#L403
> incorrectly calls push_back rather than emplace_back.
>

Bug, noted.

> Insofar as I can determine, your clear() doesn't deallocate storage,
> so https://github.com/erenon/double_ended/blob/master/
> include/boost/double_ended/devector.hpp#L570
> just overwrites the only allocator capable of deallocating the storage
> you are currently holding - without deallocating it first.
>

Bug again, noted.

> More generally, implementation of allocator support requires
> substantial improvement. An allocator that doesn't propagate on X is
> not required to support X at all, but there's no handling for that in
> your code.  Another example: construct takes raw pointers, not
> possibly fancy `pointer` like what you did here:
> https://github.com/erenon/double_ended/blob/master/
> include/boost/double_ended/devector.hpp#L2086
>
>
`pointer` is defined by allocator_traits. Couldn't that be a fancy pointer,
if the Allocator defines it so?

> The fast path for range-insert-at-front
> (https://github.com/erenon/double_ended/blob/master/
> include/boost/double_ended/devector.hpp#L2496)
> is broken based on a cursory inspection:
>
> vector<int> x = {1, 2, 3};
> devector<int> y = {4, 5, 6};
> y.reserve_front(10);
> y.insert(y.begin(), x.begin(), x.end()); // {3, 2, 1, 4, 5, 6} (!)
>

Good catch, ugly bug. Noted.

> Documentation:
>
> Does your push_back etc. really have "amortized linear" complexity?
> And doesn't that depend on the growth policy?
>

It should be amortized constant, and it does depend on the growth policy.

> How can clear() have the postcondition "empty() &&
> front_free_capacity() == 0 && back_free_capacity() == small buffer
> size" yet not deallocate memory?
>

This is a typo. should be  `back_free_capacity() == old capacity.`

> The default growth policy is:
>
> > static size_type new_capacity(size_type capacity);
> > Returns: 4 times the old capacity or 16 if it's 0.
>
> Why those numbers? Were they arbitrarily chosen or based on some sort
> of benchmark? If so, what?
>

The numbers are arbitrarily chosen - probably need to be changed.

Thanks for all the good spots.

Benedek