SmallVector.h

Go to the documentation of this file.

 
#ifndef GUL17_SMALLVECTOR_H_
#define GUL17_SMALLVECTOR_H_
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <stdexcept>
#include <type_traits>
#include <utility>
 
#include "gul17/cat.h"
#include "gul17/finalizer.h"
#include "gul17/internal.h"
 
namespace gul17 {
 
template <typename ElementT, size_t in_capacity>
class SmallVector
{
public:
    using ValueType = ElementT;
    using value_type = ValueType;
    using SizeType = std::uint32_t;
    using size_type = SizeType;
    using DifferenceType = std::ptrdiff_t;
    using difference_type = DifferenceType;
    using Reference = ValueType&;
    using reference = Reference;
    using ConstReference = const ValueType&;
    using const_reference = ConstReference;
    using Iterator = ValueType*;
    using iterator = Iterator;
    using ConstIterator = const ValueType*;
    using const_iterator = ConstIterator;
    using ReverseIterator = std::reverse_iterator<Iterator>;
    using reverse_iterator = ReverseIterator;
    using ConstReverseIterator = std::reverse_iterator<ConstIterator>;
    using const_reverse_iterator = ConstReverseIterator;
 
    SmallVector() noexcept = default;
 
    explicit SmallVector(SizeType num_elements)
    {
        static_assert(std::is_default_constructible<ValueType>::value,
            "SmallVector: Element type is not default-constructible");
 
        reserve(num_elements);
        for (SizeType i = 0u; i != num_elements; ++i)
            ::new(static_cast<void*>(data() + i)) ValueType{};
        size_ = num_elements;
    }
 
    SmallVector(SizeType num_elements, const ValueType& value)
    {
        fill_empty_vector_with_copied_value(num_elements, value);
    }
 
    template<class InputIterator,
             typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
    SmallVector(InputIterator first, InputIterator last)
    {
        fill_empty_vector_with_copied_range(first, last);
    }
 
    SmallVector(const SmallVector& other)
        noexcept(std::is_nothrow_copy_constructible<ValueType>::value)
    {
        static_assert(std::is_copy_constructible<ValueType>::value == true,
            "SmallVector: Element type is not copy-constructible");
        fill_empty_vector_with_copied_range(other.cbegin(), other.cend());
    }
 
    SmallVector(SmallVector&& other)
        noexcept(std::is_nothrow_move_constructible<ValueType>::value)
    {
        move_or_copy_all_elements_from(std::move(other));
    }
 
    SmallVector(std::initializer_list<ValueType> init)
    {
        fill_empty_vector_with_copied_range(init.begin(), init.end());
    }
 
    ~SmallVector()
    {
        clear();
        if (is_storage_allocated())
            deallocate_space_for_elements(data_ptr_);
    }
 
    void assign(SizeType num_elements, const ValueType& value)
    {
        clear();
        fill_empty_vector_with_copied_value(num_elements, value);
    }
 
    template<class InputIterator,
        typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
    void assign(InputIterator first, InputIterator last)
    {
        clear();
        fill_empty_vector_with_copied_range(first, last);
    }
 
    void assign(std::initializer_list<ValueType> init)
    {
        const auto num_elements = static_cast<SizeType>(init.size());
 
        clear();
        reserve(num_elements);
        std::uninitialized_copy(init.begin(), init.end(), data());
        size_ = num_elements;
    }
 
    constexpr Reference at(SizeType idx)
    {
        if (idx >= size_)
            throw std::out_of_range(cat("Index out of range: ", idx, " >= ", size_));
        return *(data() + idx);
    }
 
    constexpr ConstReference at(SizeType idx) const
    {
        if (idx >= size_)
            throw std::out_of_range(cat("Index out of range: ", idx, " >= ", size_));
        return *(data() + idx);
    }
 
    constexpr Reference back() noexcept
    {
        return *(data_end() - 1);
    }
 
    constexpr ConstReference back() const noexcept
    {
        return *(data_end() - 1);
    }
 
    constexpr Iterator begin() noexcept
    {
        return data();
    }
 
    constexpr ConstIterator begin() const noexcept
    {
        return data();
    }
 
    constexpr SizeType capacity() const noexcept { return capacity_; }
 
    constexpr ConstIterator cbegin() const noexcept
    {
        return begin();
    }
 
    constexpr ConstIterator cend() const noexcept
    {
        return end();
    }
 
    void clear() noexcept
    {
        destroy_range(data(), data_end());
        size_ = 0;
    }
 
    ConstReverseIterator crbegin() noexcept
    {
        return std::make_reverse_iterator(end());
    }
 
    ConstReverseIterator crend() noexcept
    {
        return std::make_reverse_iterator(begin());
    }
 
    constexpr ValueType* data() noexcept
    {
        return data_ptr_;
    }
 
    constexpr const ValueType* data() const noexcept
    {
        return data_ptr_;
    }
 
    template <typename... ArgumentTypes>
    Iterator emplace(ConstIterator pos, ArgumentTypes&&... arguments)
    {
        if (pos == cend())
        {
            emplace_back(std::forward<ArgumentTypes>(arguments)...);
            return data_end() - 1;
        }
 
        ValueType v(std::forward<ArgumentTypes>(arguments)...);
 
        return insert_single_value(pos, std::move(v));
    }
 
    template <typename... ArgumentTypes>
    Reference emplace_back(ArgumentTypes&&... arguments)
    {
        if (size_ == capacity_)
            grow();
 
        ::new(static_cast<void*>(data_end()))
            ValueType(std::forward<ArgumentTypes>(arguments)...);
 
        ++size_;
 
        return back();
    }
 
    constexpr bool empty() const noexcept { return size_ == 0u; }
 
    constexpr Iterator end() noexcept
    {
        return data_end();
    }
 
    constexpr ConstIterator end() const noexcept
    {
        return data_end();
    }
 
    Iterator erase(ConstIterator pos)
    {
        return erase(pos, pos + 1);
    }
 
    Iterator erase(ConstIterator first, ConstIterator last)
    {
        auto range_begin = const_cast<Iterator>(first);
        auto range_end = const_cast<Iterator>(last);
        auto num_elements = range_end - range_begin;
 
        std::move(range_end, end(), range_begin);
        destroy_range(end() - num_elements, end());
 
        size_ -= static_cast<SizeType>(num_elements);
 
        return range_begin;
    }
 
    constexpr Reference front() noexcept
    {
        return *data();
    }
 
    constexpr ConstReference front() const noexcept
    {
        return *data();
    }
 
    constexpr SizeType inner_capacity() const noexcept { return in_capacity; }
 
    Iterator insert(ConstIterator pos, const ValueType& value)
    {
        return insert_single_value(pos, value);
    }
 
    Iterator insert(ConstIterator pos, ValueType&& value)
    {
        return insert_single_value(pos, std::move(value));
    }
 
    Iterator insert(ConstIterator pos, SizeType num_elements, const ValueType& value)
    {
        const auto idx = static_cast<SizeType>(pos - begin());
        if (num_elements < 1)
            return begin() + idx;
 
        const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
        Iterator insert_pos = begin() + idx;
 
        // Copy-assign to moved-from elements
        std::fill_n(insert_pos, num_assignable, value);
 
        // Copy the remaining values into uninitialized cells
        copy_value_into_uninitialized_cells(size_, num_elements - num_assignable, value);
 
        size_ += num_elements;
 
        return insert_pos;
    }
 
    template<class InputIterator,
             typename = std::enable_if_t<not std::is_integral<InputIterator>::value>>
    Iterator insert(ConstIterator pos, InputIterator first, InputIterator last)
    {
        const auto idx = static_cast<SizeType>(pos - begin());
        const auto num_elements = static_cast<SizeType>(std::distance(first, last));
        if (num_elements < 1)
            return begin() + idx;
 
        const SizeType num_assignable = make_space_at_idx_for_n_elements(idx, num_elements);
        Iterator insert_pos = begin() + idx;
 
        // Copy-assign to moved-from elements
        std::copy_n(first, num_assignable, insert_pos);
 
        // Copy the remaining values into uninitialized cells
        copy_range_into_uninitialized_cells(size_, first + num_assignable, last);
 
        size_ += num_elements;
 
        return insert_pos;
    }
 
    Iterator insert(ConstIterator pos, std::initializer_list<ValueType> init)
    {
        return insert(pos, init.begin(), init.end());
    }
 
    constexpr SizeType max_size() const noexcept
    {
        return std::numeric_limits<SizeType>::max();
    }
 
    SmallVector& operator=(const SmallVector& other)
        noexcept(std::is_nothrow_copy_assignable<ValueType>::value)
    {
        if (&other != this)
        {
            clear();
            reserve(other.size());
            std::uninitialized_copy(other.cbegin(), other.cend(), data());
            size_ = other.size();
        }
 
        return *this;
    }
 
    SmallVector& operator=(SmallVector&& other)
        noexcept(std::is_nothrow_move_constructible<ValueType>::value)
    {
        if (&other != this)
        {
            clear();
            if (is_storage_allocated())
                deallocate_space_for_elements(data_ptr_);
            move_or_copy_all_elements_from(std::move(other));
        }
 
        return *this;
    }
 
    SmallVector& operator=(std::initializer_list<ValueType> init)
    {
        assign(init);
        return *this;
    }
 
    friend bool operator==(const SmallVector& lhs, const SmallVector& rhs)
    {
        return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
    }
 
    friend bool operator!=(const SmallVector& lhs, const SmallVector& rhs)
    {
        return not (lhs == rhs);
    }
 
    constexpr Reference operator[](SizeType idx)
    {
        return *(data() + idx);
    }
 
    constexpr ConstReference operator[](SizeType idx) const
    {
        return *(data() + idx);
    }
 
    void pop_back()
    {
        --size_;
        auto p = data_end();
        p->~ValueType();
    }
 
    void push_back(const ValueType& value)
    {
        if (size_ == capacity_)
            grow();
 
        ::new(static_cast<void*>(data_end())) ValueType(value);
 
        ++size_;
    }
 
    void push_back(ValueType&& value)
    {
        if (size_ == capacity_)
            grow();
 
        ::new(static_cast<void*>(data_end())) ValueType(std::move(value));
 
        ++size_;
    }
 
    ReverseIterator rbegin() noexcept
    {
        return std::make_reverse_iterator(end());
    }
 
    ReverseIterator rend() noexcept
    {
        return std::make_reverse_iterator(begin());
    }
 
    void reserve(SizeType new_capacity)
    {
        if (new_capacity <= capacity_)
            return;
 
        // Allocate aligned memory for the new "outer" capacity.
        auto* new_data = allocate_space_for_elements(new_capacity);
        auto _ = finally([&new_data]() { deallocate_space_for_elements(new_data); });
 
        auto* d_end = data_end();
        uninitialized_move_or_copy(data(), d_end, new_data);
        destroy_range(data(), d_end);
 
        if (is_storage_allocated())
            deallocate_space_for_elements(data_ptr_);
 
        data_ptr_ = new_data;
        new_data = nullptr;
        capacity_ = new_capacity;
    }
 
    void resize(SizeType num_elements)
    {
        static_assert(std::is_default_constructible<ValueType>::value,
            "SmallVector: For using resize(), element type must be default-constructible");
 
        if (num_elements < size_)
        {
            destroy_range(data() + num_elements, data_end());
        }
        else if (num_elements > size_)
        {
            reserve(num_elements);
            fill_uninitialized_cells_with_default_constructed_elements(size_,
                num_elements - size_);
        }
 
        size_ = num_elements;
    }
 
    void resize(SizeType num_elements, const ValueType& element)
    {
        if (num_elements < size_)
        {
            destroy_range(data() + num_elements, data_end());
        }
        else if (num_elements > size_)
        {
            reserve(num_elements);
            copy_value_into_uninitialized_cells(size_, num_elements - size_, element);
        }
 
        size_ = num_elements;
    }
 
    void shrink_to_fit()
    {
        const SizeType new_capacity = std::max(inner_capacity(), size_);
 
        // No shrinking required?
        if (new_capacity == capacity_)
            return;
 
        ValueType* new_data{};
        ValueType* allocation{};
        auto _ = finally([&allocation]() { deallocate_space_for_elements(allocation); });
 
        if (new_capacity == inner_capacity())
        {
            new_data = get_internal_array_pointer();
        }
        else
        {
            allocation = allocate_space_for_elements(new_capacity);
            new_data = allocation;
        }
 
        auto* d_end = data_end();
        uninitialized_move_or_copy(data(), d_end, new_data);
        destroy_range(data(), d_end);
 
        if (is_storage_allocated())
            deallocate_space_for_elements(data_ptr_);
 
        data_ptr_ = new_data;
        capacity_ = new_capacity;
        allocation = nullptr; // Avoid deallocation by the "finally" guard
    }
 
    constexpr SizeType size() const noexcept { return size_; }
 
    void swap(SmallVector& other)
    {
        if (is_storage_allocated())
        {
            if (other.is_storage_allocated())
                swap_heap_with_heap(*this, other);
            else
                swap_heap_with_internal(*this, other);
        }
        else
        {
            if (other.is_storage_allocated())
                swap_heap_with_internal(other, *this);
            else
                swap_internal_with_internal(*this, other);
        }
    }
 
private:
    alignas(ValueType)
    std::array<std::byte, in_capacity * sizeof(ValueType)> internal_array_;
 
    ValueType* data_ptr_{ get_internal_array_pointer() };
 
    SizeType capacity_{ in_capacity };
    SizeType size_{ 0u };
 
    static ValueType* allocate_space_for_elements(std::size_t num_elements)
    {
        return static_cast<ValueType*>(
            ::operator new[](num_elements * sizeof(ValueType),
                             std::align_val_t{ alignof(ValueType) }));
    }
 
    template<class InputIterator>
    void copy_range_into_uninitialized_cells(SizeType pos, InputIterator first,
                                             InputIterator last)
    {
        auto data_ptr = data() + pos;
 
        try
        {
            for (auto it = first; it != last; ++it)
            {
                ::new(static_cast<void*>(data_ptr)) ValueType{ *it };
                ++data_ptr;
            }
        }
        catch (...)
        {
            for (auto p = data() + pos; p != data_ptr; ++p)
                p->~ValueType();
 
            throw;
        }
    }
 
    void copy_value_into_uninitialized_cells(SizeType pos, SizeType num_elements,
                                             const ValueType& value)
    {
        const auto start_ptr = data() + pos;
        const auto end_ptr = start_ptr + num_elements;
        for (auto p = start_ptr; p != end_ptr; ++p)
            ::new(static_cast<void*>(p)) ValueType(value);
    }
 
    constexpr ValueType* data_end() noexcept
    {
        return data_ptr_ + size_;
    }
 
    constexpr const ValueType* data_end() const noexcept
    {
        return data_ptr_ + size_;
    }
 
    static void deallocate_space_for_elements(ValueType* ptr) noexcept
    {
        ::operator delete[](ptr, std::align_val_t{ alignof(ValueType) });
    }
 
    static void destroy_range(Iterator it_start, Iterator it_end) noexcept
    {
        for (auto it = it_start; it != it_end; ++it)
            it->~ValueType();
    }
 
    template<typename InputIterator>
    void fill_empty_vector_with_copied_range(InputIterator first, InputIterator last)
    {
        const auto num_elements = static_cast<SizeType>(std::distance(first, last));
 
        reserve(num_elements);
        copy_range_into_uninitialized_cells(0u, first, last);
        size_ = num_elements;
    }
 
    void fill_empty_vector_with_copied_value(SizeType num_elements, const ValueType& value)
    {
        reserve(num_elements);
        copy_value_into_uninitialized_cells(0u, num_elements, value);
        size_ = num_elements;
    }
 
    void fill_uninitialized_cells_with_default_constructed_elements(SizeType pos,
        SizeType num_elements)
    {
        const auto start_ptr = data() + pos;
        const auto end_ptr = start_ptr + num_elements;
        auto ptr = start_ptr;
 
        try
        {
            for (; ptr != end_ptr; ++ptr)
                ::new(static_cast<void*>(ptr)) ValueType{};
        }
        catch (...)
        {
            destroy_range(start_ptr, ptr);
            throw;
        }
    }
 
    const ValueType* get_internal_array_pointer() const noexcept
    {
        return reinterpret_cast<const ValueType*>(internal_array_.data());
    }
 
    ValueType* get_internal_array_pointer() noexcept
    {
        return reinterpret_cast<ValueType*>(internal_array_.data());
    }
 
    void grow()
    {
        const auto remaining_space = std::numeric_limits<SizeType>::max() - capacity_;
 
        if (remaining_space == 0u)
            throw std::length_error("Max. capacity reached");
 
        SizeType increase = capacity_ / 2u;
        if (increase > remaining_space)
            increase = remaining_space;
        else if (increase == 0u)
            increase = 1u;
 
        reserve(capacity_ + increase);
    }
 
    template <typename T>
    Iterator insert_single_value(ConstIterator pos, T&& value)
    {
        if (pos == end())
        {
            push_back(std::forward<T>(value));
            return begin() + size_ - 1;
        }
 
        const auto idx = static_cast<SizeType>(pos - begin());
 
        if (size_ == capacity_)
            grow();
 
        Iterator insert_pos = begin() + idx;
 
        auto data_ptr = data();
 
        // Construct new back() element by moving from the old back()
        ::new(static_cast<void*>(data_ptr + size_)) ValueType(std::move(*(data_ptr + size_ - 1)));
 
        std::move_backward(insert_pos, data_ptr + size_ - 1, data_ptr + size_);
        ++size_;
 
        *insert_pos = std::forward<T>(value);
 
        return insert_pos;
    }
 
    bool is_storage_allocated() const noexcept
    {
        return data_ptr_ != get_internal_array_pointer();
    }
 
    SizeType make_space_at_idx_for_n_elements(SizeType idx, SizeType num_elements)
    {
        const auto new_size = size_ + num_elements;
 
        if (new_size > capacity_)
            reserve(new_size);
 
        auto data_ptr = data();
 
        // We have a total number of elements that need to be shifted backwards,
        // of which some need to be move-initialized at the end of the vector
        // and some simply need to be moved from one element to another.
        const SizeType num_shifted = size_ - idx;
        const SizeType num_move_initialized = std::min(num_shifted, num_elements);
        const SizeType num_moved = num_shifted - num_move_initialized;
 
        // Move-initialize elements in uninitialized space at the back of the container
        const auto from_ptr = data_ptr + size_ - num_move_initialized;
        const auto to_ptr = from_ptr + num_elements;
        for (SizeType i = 0; i != num_move_initialized; ++i)
            ::new(static_cast<void*>(to_ptr + i)) ValueType(std::move(*(from_ptr + i)));
 
        // Move elements backwards within old vector size
        std::move_backward(data_ptr + idx, data_ptr + idx + num_moved, to_ptr);
 
        return num_move_initialized;
    }
 
    void move_or_copy_all_elements_from(SmallVector&& other)
        noexcept(std::is_nothrow_move_constructible<ValueType>::value)
    {
        // Can we simply steal the complete allocated storage?
        if (other.is_storage_allocated())
        {
            data_ptr_ = std::exchange(other.data_ptr_, other.get_internal_array_pointer());
            capacity_ = std::exchange(other.capacity_, other.inner_capacity());
            size_ = std::exchange(other.size_, 0u);
        }
        else // otherwise fall back to moving (or at least copying) all elements
        {
            data_ptr_ = get_internal_array_pointer();
            capacity_ = in_capacity;
            uninitialized_move_or_copy(other.begin(), other.end(), data());
            size_ = other.size();
            other.clear();
        }
    }
 
    static void swap_heap_with_heap(SmallVector &a, SmallVector &b) noexcept
    {
        std::swap(a.data_ptr_, b.data_ptr_);
        std::swap(a.capacity_, b.capacity_);
        std::swap(a.size_, b.size_);
    }
 
    static void swap_heap_with_internal(SmallVector &a, SmallVector &b)
    {
        uninitialized_move_or_copy(b.begin(), b.end(), a.get_internal_array_pointer());
        destroy_range(b.begin(), b.end());
 
        b.data_ptr_ = std::exchange(a.data_ptr_, a.get_internal_array_pointer());
 
        std::swap(a.capacity_, b.capacity_);
        std::swap(a.size_, b.size_);
    }
 
    static void swap_internal_with_internal(SmallVector &a, SmallVector &b)
    {
        if (a.size_ <= b.size_)
        {
            for (SmallVector::SizeType i = 0; i != a.size_; ++i)
                std::swap(a.data()[i], b.data()[i]);
 
            uninitialized_move_or_copy(b.begin() + a.size_, b.end(), a.begin() + a.size_);
            destroy_range(b.begin() + a.size_, b.end());
        }
        else
        {
            for (SizeType i = 0; i != b.size_; ++i)
                std::swap(a.data()[i], b.data()[i]);
 
            uninitialized_move_or_copy(a.begin() + b.size_, a.end(), b.begin() + b.size_);
            destroy_range(a.begin() + b.size_, a.end());
        }
 
        std::swap(a.size_, b.size_);
    }
 
    template <typename T>
    static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value>
    uninitialized_move(T* src_begin, T* src_end, T* dest_begin)
    {
        auto src = src_begin;
        auto dest = dest_begin;
 
        try
        {
            while (src != src_end)
            {
                ::new (static_cast<void*>(dest)) ValueType(std::move(*src));
                ++src;
                ++dest;
            }
        }
        catch (...)
        {
            for (auto p = dest_begin; p != dest; ++p)
                p->~ValueType();
 
            throw;
        }
    }
 
    template <typename T>
    static typename std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
    uninitialized_move(T* src_begin, T* src_end, T* dest_begin) noexcept
    {
        auto src = src_begin;
        auto dest = dest_begin;
 
        while (src != src_end)
        {
            ::new (static_cast<void*>(dest)) ValueType(std::move(*src));
            ++src;
            ++dest;
        }
    }
 
    template <typename T>
    static typename std::enable_if_t<std::is_nothrow_move_constructible<T>::value>
    uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin) noexcept
    {
        uninitialized_move(src_begin, src_end, dest_begin);
    }
 
    template <typename T>
    static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value and
                                     std::is_copy_constructible<T>::value>
    uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin)
    {
        std::uninitialized_copy(src_begin, src_end, dest_begin);
    }
 
    template <typename T>
    static typename std::enable_if_t<not std::is_nothrow_move_constructible<T>::value
                                     and not std::is_copy_constructible<T>::value>
    uninitialized_move_or_copy(T* src_begin, T* src_end, T* dest_begin)
    {
        uninitialized_move(src_begin, src_end, dest_begin);
    }
};
 
 
template<typename ElementT, size_t in_capacity>
void swap(SmallVector<ElementT,in_capacity>& a, SmallVector<ElementT, in_capacity>& b)
{
    a.swap(b);
}
 
 
} // namespace gul17
 
#endif
 
// vi:ts=4:sw=4:sts=4:et