On 11 October 2017 at 00:23, Ion Gaztañaga via Boost <boost@lists.boost.org> wrote:
I think the following is coherent, maybe not optimal in moves if only push_back is used:
-----xxxxxxxxxxxxx---------
^^^^^---------------------- front free capacity ^^^^^^^^^^^^^^^^^^--------- front capacity -----^^^^^^^^^^^^^--------- size ------------------^^^^^^^^^ back free capacity -----^^^^^^^^^^^^^^^^^^^^^^ back capacity ^^^^^^^^^^^^^^^^^^^^^^^^^^^ capacity
front/back_free_capacity indicates the number of push_front/backs until data movement (and maybe allocation) is needed.
front/back_capacity is front/back_free_capacity + size. If size == front/back_capacity, then data movement (and maybe allocation) will happen
capacity == size means that any insertion will lead to reallocation.
I've tested a toy implementation doing exactly this. template<typename T, typename P = allocation_policy<1, 1>, typename A = std::allocator<T>, typename G = vs_growth_policy<2>> class veque : private A { // Stuff... inline size_type size ( ) const noexcept { return ( size_type ) ( m_end - m_begin ); } inline size_type capacity ( ) const noexcept { return m_free_capacity_begin + size ( ) + m_free_capacity_end; } size_type m_free_capacity_begin = 0, m_free_capacity_end = 0; pointer m_begin = nullptr, m_end = nullptr; }; With a size_type std::uint32_t, the foot print is 24 bytes on 64 bit (like de::devector). The idea with the allocation policy is to re-balance the total free space on relocation between front and back free space (1 to 1 in the default case, but could obviously be anything). This leads to lower memory usage on random growth (push_front/push_back) over a std::vector of veque(s) (de::devector). This approach is speedwise on par with de:devector for push_front/push_back, and doesn't give surprises in the the free capacity department. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798