Boost logo

Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: degski (degski_at_[hidden])
Date: 2017-10-12 09:42:34


On 11 October 2017 at 18:07, Thorsten Ottosen via Boost <
boost_at_[hidden]> wrote:

> Sure, and we have certainly floated various ideas. I leaning towards the
> following principles:
>
> A. insert never allocates if it can avoid it
> B. insert, when allocation is needed, balances the free capacity
> C. a push at either end by default does not balance the free capacity
>

 That is how I would do it as well, relocation should re-balance, though.

D. in certain situations push at either end may choose to balance the free
> capacity, say of the free capacity in the opposite end is larger than
> size() or perhaps larger or equal to size().
>

resize and reserve are also candidates for having such a consideration. One
could imagine resize_back/resize_front/reserve_back/reserve_front and let
resize and reserve always re-balance (when appropriate).

> You can always store extra stuff in the allocated buffer instead of
> directly in the class. I don't if that is what you did. But you don't
> actually same memory that way, you just moved the location.
>

Not necessary, the relevant bits for this point are below:

template<typename T, typename A = std::allocator<T>, typename G =
golden_ratio_growth_policy<2>>
class pod_collection : private A {

    // Other stuff, the rest...

    inline iterator begin ( ) noexcept { return iterator { begin_pointer (
) }; }
    inline iterator end ( ) noexcept { return iterator { m_end }; }

    inline bool empty ( ) const noexcept { return not ( m_size ); }
    inline bool full ( ) const noexcept { return m_size == m_capacity; }

    inline void clear ( ) noexcept { m_end = begin_pointer ( ); m_size = 0;
}

    inline reference operator [ ] ( const size_type i_ ) noexcept { return
*( begin_pointer ( ) + i_ ); }

    private:

    __forceinline pointer begin_pointer ( ) const noexcept { return m_end -
m_size; }
    __forceinline pointer back_pointer ( ) const noexcept { return m_end -
1; }

    size_type m_size, m_capacity; // size_type = std::uint32_t's
    pointer m_end;
};

Needless to say that the whole exercise only makes sense on 64-bit
platforms.

The only pointer is the end pointer, so push_back can be fast. Since one
doesn't need the pointer to the allocated memory all the time, it can be
calculated on the fly, when needed. For iteration there is hardly a penalty
(one subtraction, for begin()), but for indexed access there *is* a penalty
(of one subtraction per access), so to be avoided (with iterators).

degski

-- 
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk