A vecor<> that grows by doubling its capacity for MSVC

Bonita Montero

2024-08-10 11:32:02 UTC

Sorry, wrong group.

Post by Bonita Montero
I didn't understand why Microsoft decided to grow the capacity of
a vector only by 50% when needed. libstdc++ and libc++ increase
the capacity by 100%. And C#'s ArrayList is also implemented with
100%-growing.
So I modified VC++'s vector<> to multiply it's capacity by 2^N
according to the destination capcacity. Take a look at the function
complexReCap, which does the ticky part without looping to calculate
the final capacity.
#pragma once
#include <vector>
#include <iterator>
#include <type_traits>
#include <utility>
#include <bit>
#include <cassert>
#include <ranges>
#if defined(_MSC_VER)
template<typename Range, typename T>
concept d_vector_range = std::forward_iterator<decltype(Range().begin())>
    && requires( Range rg ) { { rg.begin() != rg.end() } ->
std::convertible_to<bool>; }
    && std::convertible_to<decltype(*Range().begin()), T>;
template<typename T, typename Alloc = std::allocator<T>>
struct d_vector : public std::vector<T, Alloc>
{
    using super = std::vector<T, Alloc>;
    using iterator = super::iterator;
    using value_type = super::value_type;
    using reference = super::reference;
    using size_type = super::size_type;
    using const_iterator = super::const_iterator;
    using super::vector;
    constexpr iterator insert( const_iterator pos, value_type const
&value );
    constexpr iterator insert( const_iterator pos, value_type &&value );
    constexpr iterator insert( const_iterator pos, size_type count,
value_type const &value );
    template<std::input_iterator InputIt>
    constexpr iterator insert( const_iterator pos, InputIt first,
InputIt last )
        requires std::convertible_to<std::iter_value_t<InputIt>,
value_type>;
    constexpr iterator insert( const_iterator pos,
std::initializer_list<T> ilist );
    template<typename ... Args>
        requires std::is_constructible_v<T, Args ...>
    constexpr iterator emplace( const_iterator pos, Args &&... args );
    constexpr void push_back( T const &value );
    constexpr void push_back( T &&value );
    template<typename ... Args>
        requires std::is_constructible_v<T, Args ...>
    constexpr reference emplace_back( Args &&... args );
#if defined(__cpp_lib_containers_ranges)
    template<typename Range>
        requires d_vector_range<Range, T>
    constexpr void assign_range( Range &&rg );
    template<typename Range>
        requires d_vector_range<Range, T>
    constexpr iterator insert_range( const_iterator pos, Range &&rg );
    template<typename Range>
        requires d_vector_range<Range, T>
    constexpr void append_range( Range &&rg );
#endif
    void incr( size_t n );
    void reCap( size_t required );
    void complexReCap( size_t required, size_t cap );
};
template<typename T, typename Alloc>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::insert( const_iterator pos, value_type const &value )
{
    incr( 1 );
    return super::insert( pos, value );
}
template<typename T, typename Alloc>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::insert( const_iterator pos, value_type &&value )
{
    incr( 1 );
    return super::insert( pos, std::move( value ) );
}
template<typename T, typename Alloc>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::insert( const_iterator pos, size_type count, value_type const
&value )
{
    incr( count );
    return super::insert( pos, count, value );
}
template<typename T, typename Alloc>
template<std::input_iterator InputIt>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::insert( const_iterator pos, InputIt first, InputIt last )
    requires std::convertible_to<std::iter_value_t<InputIt>, value_type>
{
    incr( distance( first, last ) );
    super::insert( pos, first, last );
}
template<typename T, typename Alloc>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::insert( const_iterator pos, std::initializer_list<T> ilist )
{
    incr( ilist.size() );
    super::insert( pos, ilist );
}
template<typename T, typename Alloc>
template<typename ... Args>
    requires std::is_constructible_v<T, Args ...>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::emplace( const_iterator pos, Args &&... args )
{
    incr( 1 );
    return super::emplace( pos, std::forward<Args>( args ) ... );
}
template<typename T, typename Alloc>
constexpr void d_vector<T, Alloc>::push_back( T const &value )
{
    incr( 1 );
    return super::push_back( value );
}
template<typename T, typename Alloc>
constexpr void d_vector<T, Alloc>::push_back( T &&value )
{
    incr( 1 );
    return super::push_back( std::move( value ) );
}
template<typename T, typename Alloc>
template<typename ... Args>
    requires std::is_constructible_v<T, Args ...>
constexpr typename d_vector<T, Alloc>::reference d_vector<T,
Alloc>::emplace_back( Args &&... args )
{
    incr( 1 );
    return super::emplace_back( std::forward<Args>( args ) ... );
}
#if defined(__cpp_lib_containers_ranges)
template<typename T, typename Alloc>
template<typename Range>
    requires d_vector_range<Range, T>
constexpr void d_vector<T, Alloc>::assign_range( Range &&rg )
{
    reCap( std::ranges::size( rg ) );
    super::assign_range( rg );
}
template<typename T, typename Alloc>
template<typename Range>
    requires d_vector_range<Range, T>
constexpr typename d_vector<T, Alloc>::iterator d_vector<T,
Alloc>::insert_range( const_iterator pos, Range &&rg )
{
    incr( std::ranges::size( rg ) );
    return super::insert_range( pos, rg );
}
template<typename T, typename Alloc>
template<typename Range>
    requires d_vector_range<Range, T>
constexpr void d_vector<T, Alloc>::append_range( Range &&rg )
{
    incr( std::ranges::size( rg ) );
    super::append_range( rg );
}
#endif
template<typename T, typename Alloc>
inline void d_vector<T, Alloc>::incr( size_t n )
{
    reCap( super::size() + n );
}
template<typename T, typename Alloc>
inline void d_vector<T, Alloc>::reCap( size_t required )
{
    if( size_t cap = super::capacity(); required > cap ) [[unlikely]]
        complexReCap( required, cap );
}
template<typename T, typename Alloc>
__declspec(noinline)
void d_vector<T, Alloc>::complexReCap( size_t required, size_t cap )
{
    using namespace std;
    assert(required > cap);
    // if capacity is zero increment it to one
    cap += (size_t)!cap;
    // make cap the same magnitude like required
    cap <<= countl_zero( cap ) - countl_zero( required );
    // required still larger than cap ?
    // the branch is likely because cap is usually a power of two
    if( required > cap ) [[likely]]
        // yes: cap woudln't oveflow ?
        if( (ptrdiff_t)cap >= 0 ) [[likely]]
            // yes: double it
            cap *= 2;
        else
            // no: throw bad_alloc
            throw bad_alloc();
    // reserve cap elements, which is >= required
    try
    {
        // optimistically try to reseve new capacity
        super::reserve( cap );
    }
    catch( bad_alloc const & )
    {
        // didn't work: try to reserve required capacity
        super::reserve( required );
    }
}
#else
template<typename T, typename Alloc = std::allocator<T>>
using d_vector = std::vector<T, Alloc>;
#endif