On 11 October 2017 at 00:23, Ion Gaztañaga via Boost
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 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
