3
\$\begingroup\$

To train my skills in C++, I decided to implement the well-known "Dynamic array" data structure on my own. I realized early on that using pointers or smart pointers is wrong, as it leads to calling default constructor on reallocation. A naive approach for the push_back function would include: T* new_buf = new T[n]this is what will call the default constructor of type T. This is the main problem that caused me to start learning allocators.

In the past, I didn't pay much attention to allocators and the probability of throwing an exception (and also noexcept specifier). This is my first project that takes these details into account. When programming in C++, it is important for me to follow the best practices and the latest standards.

Next, I will provide my incomplete implementation of the Dynamic array:

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>
#include <ratio>
#include <tuple>
#include <type_traits>
#include <utility>

namespace alloc_ext
{
template <class Alloc>
constexpr void destroy(Alloc& alloc, typename std::allocator_traits<Alloc>::pointer first, const decltype(first) last)
{
    for(; first != last; ++first) {
        std::allocator_traits<Alloc>::destroy(alloc, first);
    }
}

template <class Alloc, class InputIt>
constexpr void initialized_rewrite(Alloc& alloc,
    InputIt first,
    InputIt last,
    const typename std::allocator_traits<Alloc>::pointer d_first)
{
    auto current = d_first;
    try {
        for(; first != last; ++first, (void)++current) {
            std::allocator_traits<Alloc>::destroy(alloc, current);
            std::allocator_traits<Alloc>::construct(alloc, current, *first);
        }
    } catch(...) {
        destroy(alloc, d_first, current);
        throw;
    }
}

template <class Alloc, class InputIt, class Size>
constexpr void initialized_first_destroy_and_copy(Alloc& alloc,
    InputIt first,
    InputIt last,
    Size destroy_count,
    const typename std::allocator_traits<Alloc>::pointer d_first)
{
    auto current = d_first;
    try {
        for(; first != last; ++first, (void)++current) {
            if(destroy_count > 0) {
                std::allocator_traits<Alloc>::destroy(alloc, current);
                --destroy_count;
            }
            std::allocator_traits<Alloc>::construct(alloc, current, *first);
        }
    } catch(...) {
        destroy(alloc, d_first, current);
        throw;
    }
}

template <class Alloc>
constexpr void uninitialized_destroy_move(Alloc& alloc,
    typename std::allocator_traits<Alloc>::pointer first,
    decltype(first) last,
    const decltype(first) d_first)
{
    auto current = d_first;
    try {
        for(; first != last; ++first, (void)++current) {
            std::allocator_traits<Alloc>::construct(alloc, current, std::move(*first));
            std::allocator_traits<Alloc>::destroy(alloc, first);
        }
    } catch(...) {
        destroy(alloc, d_first, current);
        throw;
    }
}

template <class Alloc, class InputIt>
constexpr void uninitialized_copy(Alloc& alloc,
    InputIt first,
    InputIt last,
    const typename std::allocator_traits<Alloc>::pointer d_first)
{
    auto current = d_first;
    try {
        for(; first != last; ++first, (void)++current) {
            std::allocator_traits<Alloc>::construct(alloc, current, *first);
        }
    } catch(...) {
        destroy(alloc, d_first, current);
        throw;
    }
}

template <class Alloc>
constexpr void uninitialized_default_construct(Alloc& alloc,
    const typename std::allocator_traits<Alloc>::pointer first,
    const decltype(first) last)
{
    auto current = first;
    try {
        for(; current != last; ++current) {
            std::allocator_traits<Alloc>::construct(alloc, current);
        }
    } catch(...) {
        destroy(alloc, first, current);
        throw;
    }
}

template <class Alloc>
constexpr void uninitialized_fill(Alloc& alloc,
    const typename std::allocator_traits<Alloc>::pointer first,
    const decltype(first) last,
    const typename std::allocator_traits<Alloc>::value_type& value)
{
    auto current = first;
    try {
        for(; current != last; ++current) {
            std::allocator_traits<Alloc>::construct(alloc, current, value);
        }
    } catch(...) {
        destroy(alloc, first, current);
        throw;
    }
}

template <class Alloc>
constexpr void safe_deallocate(Alloc& alloc,
    typename std::allocator_traits<Alloc>::pointer buf,
    typename std::allocator_traits<Alloc>::size_type size)
{
    if(size > 0)
        std::allocator_traits<Alloc>::deallocate(alloc, buf, size);
}
}

namespace darray_ns
{
// Implementation of dynamic array. Created by PavelPI 09.12.2021
// Throwing an exception of type std::allocator_traits<allocator_type>::value_type
// from the destructor leads to undefined behavior
template <class Allocator, class Ratio = std::ratio<3, 2>> class darray
{
    static_assert(Ratio::num > 0 && Ratio::den > 0 && Ratio::num > Ratio::den);

public:
    using allocator_type = Allocator;

private:
    using alloc_tr = std::allocator_traits<allocator_type>;
    using pointer = typename alloc_tr::pointer;

public:
    using ratio = Ratio;
    using value_type = typename alloc_tr::value_type;
    using reference = value_type&;
    using rvalue_reference = value_type&&;
    using const_reference = const value_type&;
    using iterator = typename alloc_tr::pointer;
    using const_iterator = typename alloc_tr::const_pointer;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
    using difference_type = std::iter_difference_t<iterator>;
    using size_type = typename alloc_tr::size_type;

private:
    static constexpr const char* at_out_err = "darray::at(pos) - Attempt to access a non-existent index";

    size_type mcap;
    size_type msize;
    Allocator malloc;
    pointer mbuf;

    [[nodiscard]] constexpr pointer hint_allocate(size_type n)
    {
        if(mcap > 0)
            return alloc_tr::allocate(malloc, n, mbuf + mcap - 1);
        else
            return alloc_tr::allocate(malloc, n);
    }

    constexpr void grow_alloc(size_type new_cap)
    {
        assert(new_cap > 0 && new_cap >= size());
        pointer new_buf = hint_allocate(new_cap);
        constexpr bool is_copyable = std::is_copy_constructible<value_type>::value;
        if constexpr(!std::is_nothrow_move_constructible<value_type>::value && is_copyable) {
            try {
                alloc_ext::uninitialized_copy(malloc, mbuf, mbuf + size(), new_buf);
            } catch(...) {
                alloc_tr::deallocate(malloc, new_buf, new_cap);
                throw;
            }
            alloc_ext::destroy(malloc, mbuf, mbuf + size());
        } else {
            try {
                alloc_ext::uninitialized_destroy_move(malloc, mbuf, mbuf + size(), new_buf);
            } catch(...) {
                alloc_tr::deallocate(malloc, new_buf, new_cap);
                throw;
            }
        }
        alloc_ext::safe_deallocate(malloc, mbuf, capacity());
        mbuf = new_buf;
        mcap = new_cap;
    }

    template <bool OtherFill>
    constexpr void internal_resize(size_type new_size,
        std::conditional_t<OtherFill, const_reference, std::tuple<>> value)
    {
        if(size() == new_size)
            return;
        const bool need_grow = new_size > capacity();
        if(need_grow || new_size > size()) {
            if(need_grow)
                grow_alloc(new_size);
            if constexpr(OtherFill)
                alloc_ext::uninitialized_fill(malloc, mbuf + size(), mbuf + new_size, value);
            else
                alloc_ext::uninitialized_default_construct(malloc, mbuf + size(), mbuf + new_size);
        } else
            alloc_ext::destroy(malloc, mbuf + new_size, mbuf + msize);
        msize = new_size;
    }

    template <bool Init, class InputIt> constexpr void internal_assign(InputIt first, InputIt last)
    {
        using tag = typename std::iterator_traits<InputIt>::iterator_category;
        static_assert(!std::is_same<tag, std::output_iterator_tag>::value);
        if constexpr(std::is_same<tag, std::input_iterator_tag>::value) {
            if constexpr(!Init)
                clear_and_free();
            std::copy(first, last, std::back_inserter(*this));
        } else {
            const size_type new_cap = static_cast<size_type>(std::distance(first, last));
            if(new_cap > capacity() || Init) {
                pointer new_buf = hint_allocate(new_cap);
                try {
                    alloc_ext::uninitialized_copy(malloc, first, last, new_buf);
                } catch(...) {
                    alloc_tr::deallocate(malloc, new_buf, new_cap);
                    throw;
                }
                if constexpr(!Init)
                    destroy_and_dealloc();
                mcap = msize = new_cap;
                mbuf = new_buf;
            } else {
                // new_cap<=capacity && !Init
                if(new_cap <= msize) {
                    alloc_ext::initialized_rewrite(malloc, first, last, mbuf);
                    alloc_ext::destroy(malloc, mbuf + new_cap, mbuf + msize);
                } else
                    alloc_ext::initialized_first_destroy_and_copy(malloc, first, last, msize, mbuf);

                msize = new_cap;
            }
        }
    }

    constexpr void clear_and_free()
    {
        clear();
        alloc_ext::safe_deallocate(malloc, mbuf, capacity());
        mcap = 0;
    }

    constexpr void destroy_and_dealloc()
    {
        alloc_ext::destroy(malloc, mbuf, mbuf + size());
        alloc_ext::safe_deallocate(malloc, mbuf, capacity());
    }

    constexpr size_type next_cap() const
    {
        if(mcap != 0) {
            if constexpr(ratio::den != 1) {
                return static_cast<size_type>((static_cast<std::uintmax_t>(mcap) * ratio::num + ratio::den - 1) /
                    ratio::den); // We are wary of overflow and rounding up
            } else
                return capacity() * ratio::num;
        }
        return 1;
    }

    constexpr static int private_call = 0;
    constexpr darray(size_type init, const Allocator& alloc, int) noexcept
        : mcap(init)
        , msize(init)
        , malloc(alloc)
        , mbuf(alloc_tr::allocate(malloc, init))
    {
    }

public:
    //------------------------------
    //-----CONSTRUCTORS SECTION-----
    //------------------------------
    constexpr explicit darray(const Allocator& alloc) noexcept
        : mcap(0)
        , msize(0)
        , malloc(alloc)
    //, mbuf(nullptr)
    {
    }

    constexpr darray() noexcept(noexcept(Allocator()))
        : darray(Allocator())
    {
    }

    constexpr explicit darray(size_type count, const Allocator& alloc = Allocator())
        : darray(count, alloc, private_call)
    {
        alloc_ext::uninitialized_default_construct(alloc, mbuf, mbuf + size());
    }

    constexpr darray(size_type count, const value_type& value, const Allocator& alloc = Allocator())
        : darray(count, alloc, private_call)
    {
        alloc_ext::uninitialized_fill(alloc, mbuf, mbuf + size(), value);
    }

    template <class InputIt>
    constexpr darray(InputIt first, InputIt last, const Allocator& alloc = Allocator())
        : darray(alloc)
    {
        internal_assign<true>(first, last);
    }

    constexpr darray(const darray& o, const Allocator& alloc)
        : darray(o.begin(), o.end(), alloc)
    {
    }
    constexpr darray(const darray& o)
        : darray(o, alloc_tr::select_on_container_copy_construction(o.malloc))
    {
    }

    constexpr darray(darray&& o) noexcept
        : mcap(std::exchange(o.mcap, 0))
        , msize(std::exchange(o.msize, 0))
        , malloc(std::move(o.malloc))
        , mbuf(std::move(o.mbuf)) // vs std::exchange(o.mbuf, nullptr)
    {
    }
    constexpr darray(darray&& o, const Allocator& alloc) noexcept
        : malloc(alloc)
    {
        if(o.get_allocator() != get_allocator()) {
            msize = mcap = 0;
            // vs mbuf=nullptr;
            internal_assign<true>(std::make_move_iterator(o.first), std::make_move_iterator(o.last));
            o.msize = o.mcap = 0;
            // vs o.mbbuf=nullptr
        } else {
            mcap = std::exchange(o.mcap, 0);
            msize = std::exchange(o.msize, 0);
            mbuf = std::move(o.mbuf); // vs std::exchange(o.mbuf, nullptr);
        }
    }

    constexpr darray(std::initializer_list<value_type> il, const Allocator& alloc = Allocator())
        : darray(il.begin(), il.end(), alloc)
    {
    }

    constexpr ~darray()
    {
        destroy_and_dealloc();
    }
    //------------------------------
    //-----EDN OF CONSTRUCTORS------
    //------------------------------
    //------------------------------
    //----ELEMENT ACCESS SECTION----
    //------------------------------
    constexpr reference operator[](size_type pos)
    {
        return mbuf[pos];
    }
    constexpr const_reference operator[](size_type pos) const
    {
        return mbuf[pos];
    }
    constexpr reference at(size_type pos)
    {
        if(pos < size()) {
            return operator[](pos);
        } else
            throw std::out_of_range(at_out_err);
    }
    constexpr const_reference at(size_type pos) const
    {
        // TODO Duplicate
        if(pos < size()) {
            return operator[](pos);
        } else
            throw std::out_of_range(at_out_err);
    }
    constexpr reference front()
    {
        return *begin();
    }
    constexpr const_reference front() const
    {
        return *cbegin();
    }
    constexpr reference back()
    {
        return *std::prev(end());
    }
    constexpr const_reference back() const
    {
        return *std::prev(cend());
    }
    constexpr pointer data() noexcept
    {
        return mbuf;
    }
    constexpr const pointer data() const noexcept
    {
        return mbuf;
    }
    //------------------------------
    //----END OF ELEMENT ACCESS-----
    //------------------------------

    //------------------------------
    //------ITERATORS SECTION-------
    //------------------------------
    constexpr iterator begin() noexcept
    {
        return mbuf;
    }
    constexpr const_iterator begin() const noexcept
    {
        return mbuf;
    }
    constexpr const_iterator cbegin() const noexcept
    {
        return const_cast<const darray&>(*this).begin();
    }
    constexpr iterator end() noexcept
    {
        return mbuf + size();
    }
    constexpr const_iterator end() const noexcept
    {
        return mbuf + size();
    }
    constexpr const_iterator cend() const noexcept
    {
        return const_cast<const darray&>(*this).end();
    }
    // reverse
    constexpr reverse_iterator rbegin() noexcept
    {
        return reverse_iterator(end());
    }
    constexpr const_reverse_iterator rbegin() const noexcept
    {
        return reverse_iterator(end());
    }
    constexpr const_reverse_iterator crbegin() const noexcept
    {
        return const_cast<const darray&>(*this).rbegin();
    }

    constexpr reverse_iterator rend() noexcept
    {
        return reverse_iterator(begin());
    }
    constexpr const_reverse_iterator rend() const noexcept
    {
        return reverse_iterator(begin());
    }
    constexpr const_reverse_iterator crend() const noexcept
    {
        return const_cast<const darray&>(*this).rend();
    }
    //------------------------------
    //------END OF ITERATORS--------
    //------------------------------
    //------------------------------
    //------CAPACITY SECTION--------
    //------------------------------
    [[nodiscard]] constexpr bool empty() const noexcept
    {
        return size() == 0;
    }
    constexpr size_type size() const noexcept
    {
        return msize;
    }
    constexpr size_type max_size() const noexcept
    {
        return alloc_tr::max_size(malloc);
    }
    constexpr void reserve(size_type new_cap)
    {
        if(new_cap > mcap) {
            grow_alloc(new_cap);
        }
    }
    constexpr size_type capacity() const noexcept
    {
        return mcap;
    }

    constexpr void shrink_to_fit()
    {
        if(size() == capacity())
            return;
        if(size() != 0)
            grow_alloc(size());
        else
            alloc_ext::safe_deallocate(malloc, mbuf, capacity());
    }
    //------------------------------
    //------END OF CAPACITY --------
    //------------------------------
    //------------------------------
    //-----MODIFIERS SECTION--------
    //------------------------------
    constexpr void clear() noexcept
    {
        alloc_ext::destroy(malloc, mbuf, mbuf + msize); // TODO reverse order is better?
        msize = 0;
    }

    template <class... Args> constexpr reference emplace_back(Args&&... args)
    {
        if(msize >= mcap) {
            grow_alloc(next_cap());
        }
        alloc_tr::construct(malloc, mbuf + msize, std::forward<Args>(args)...);
        ++msize;
        return back();
    }

    constexpr void push_back(const value_type& val)
    {
        emplace_back(val);
    }

    constexpr void push_back(value_type&& val)
    {
        emplace_back(std::move(val));
    }

    constexpr void pop_back() noexcept
    {
        --msize;
        alloc_tr::destroy(malloc, mbuf + msize);
    }

    constexpr void resize(size_type new_size)
    {
        internal_resize<false>(new_size, std::tuple<>());
    }
    constexpr void resize(size_type new_size, const_reference value)
    {
        internal_resize<true>(new_size, value);
    }

    constexpr void swap(darray& o) noexcept(
        alloc_tr::propagate_on_container_swap::value || alloc_tr::is_always_equal::value)
    {
        using std::swap;
        if constexpr(alloc_tr::propagate_on_container_swap::value)
            swap(malloc, o.malloc);
        else {
            if constexpr(!alloc_tr::is_always_equal::value)
                assert(malloc == o.malloc);
        }
        swap(mcap, o.mcap);
        swap(msize, o.msize);
        swap(mbuf, o.mbuf);
    }
    //------------------------------
    //------END OF MODIFIERS--------
    //------------------------------

    //------------------------------
    //---MEMBER FUNCTIONS SECTION---
    //------------------------------
    template <class InputIt> constexpr void assign(InputIt first, InputIt last)
    {
        internal_assign<false>(first, last);
    }
    constexpr void assign(std::initializer_list<value_type> il)
    {
        assign(il.begin(), il.end());
    }

    constexpr allocator_type get_allocator() const noexcept
    {
        return malloc;
    }

    darray& operator=(const darray& o)
    {
        if(this != &o) {
            if constexpr(alloc_tr::propagate_on_container_copy_assignment::value) {
                if(malloc != o.malloc) {
                    clear_and_free();
                    malloc = o.malloc;
                }
            }
            assign(o.begin(), o.end());
        }
        return *this;
    }

    constexpr darray& operator=(darray&& o) noexcept(
        alloc_tr::propagate_on_container_move_assignment::value || alloc_tr::is_always_equal::value)
    {
        if(this != &o) {
            const auto updater = [&]() {
                destroy_and_dealloc();
                msize = std::exchange(o.msize, 0);
                mcap = std::exchange(o.mcap, 0);
                mbuf = std::move(o.mbuf); // TODO vs std::exchange(o.mbuf,nullptr)
            };
            if constexpr(alloc_tr::propagate_on_container_move_assignment::value) {
                updater();
                malloc = std::move(o.malloc); // TODO with move vs without move
            } else {
                if(malloc != o.malloc)
                    assign(std::make_move_iterator(o.begin()), std::make_move_iterator(o.end()));
                else
                    updater();
            }
        }
        return *this;
    }

    constexpr darray& operator=(std::initializer_list<value_type> il)
    {
        assign(il.begin(), il.end());
    }
    //------------------------------
    //---END OF MEMBER FUNCTIONS----
    //------------------------------
};
template <class Alloc, class Ratio>
void swap(darray<Alloc, Ratio>& l, darray<Alloc, Ratio>& r) noexcept(noexcept(l.swap(r)))
{
    l.swap(r);
}

template <class Alloc, class Ratio>
constexpr bool operator==(const darray<Alloc, Ratio>& l, const darray<Alloc, Ratio>& r)
{
    if(l.size() != r.size())
        return false;
    return std::equal(l.begin(), l.end(), r.begin());
}

template <class Alloc, class Ratio>
constexpr auto operator<=>(const darray<Alloc, Ratio>& l, const darray<Alloc, Ratio>& r)
{
    return std::lexicographical_compare_three_way(l.begin(), l.end(), r.begin(), r.end());
}
}
template <class T, class Ratio = std::ratio<3, 2>> using darray = darray_ns::darray<std::allocator<T>, Ratio>;

int main()
{
    //Your code
    //darray<int> d{1,2,3,4,5};
    return 0;
}

Be careful, in this implementation, the insert/remove methods are not implemented yet. Also, I will provide a link to the playground where darray is used.

Any constructive criticism is welcome.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.