2
\$\begingroup\$

I've just finally finished implementing std::vector. I'm currently re-implementing whatever I can in the hope to learn more of how data structures works.

I tried to respect all requirements, but I probably missed a lot (or made mistakes). At first I thought implementing std::vector would be somewhat easy... but how wrong I was.

Anyway, I've taken some reference from cppreference.com; the template is allocator-aware, I also tried implementing a random access iterator, and tried to add exception guarantees (which I'm very bad at). This is my beginner attempt to std::vector, and I'm open to all criticism and code review.

N.B. I avoided re-creating the specialization of bool since I think it's really ahead of my current level of expertise.

#ifndef VECTOR_CONTAINER
#define VECTOR_CONTAINER

#include <exception>
#include <stdexcept>
#include <algorithm>
#include <cassert>
#include <concepts>
#include <compare>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>

namespace constants {
    inline constexpr std::size_t realloc_factor = 2;
}

namespace random_access {
    template<typename Type>
    class iterator
    {
    private:
        Type* m_iterator;

    public:
        using value_type = Type;
        using reference = value_type&;
        using pointer = value_type*;
        using iterator_category = std::random_access_iterator_tag;
        using difference_type = std::ptrdiff_t;
        //using iterator_concept = std::contiguous_iterator_tag;

        constexpr iterator(Type* iter = nullptr) : m_iterator{ iter } {}

        constexpr auto operator<=>(const iterator&) const = default;
        constexpr reference operator*() const noexcept { 
            return *m_iterator; 
        }
        
        constexpr pointer operator->() const noexcept { 
            return m_iterator; 
        }
        
        constexpr iterator& operator++() noexcept { 
            ++m_iterator; 
            return *this; 
        }
        
        constexpr iterator operator++(int) noexcept { 
            iterator tmp(*this); ++(*this); 
            return tmp; 
        }
        
        constexpr iterator& operator--() noexcept { 
            --m_iterator;
            return *this;
        }
        
        constexpr iterator operator--(int) noexcept { 
            iterator tmp(*this); 
            --(*this); 
            return tmp;
        }
        
        constexpr iterator& operator+=(const difference_type other) noexcept { 
            m_iterator += other; 
            return *this; 
        }
        
        constexpr iterator& operator-=(const difference_type other) noexcept { 
            m_iterator -= other; 
            return *this;
        }
        
        friend constexpr iterator operator+(difference_type first, const iterator& other) noexcept { 
            return other.m_iterator + first;
        }
        
        friend constexpr iterator operator+(const iterator& first, difference_type other) noexcept { 
            return first.m_iterator + other; 
        }
        
        friend constexpr iterator operator-(const iterator& first, const difference_type other) noexcept { 
            return first.m_iterator - other; 
        }
        
        constexpr difference_type operator-(const iterator& other) const noexcept { 
            return std::distance(m_iterator, other.m_iterator); 
        }
        
        constexpr reference operator[](std::size_t index) const { 
            return m_iterator[index]; 
        }
        
        constexpr friend bool operator== (const iterator& first, const iterator& second) { 
            return first.m_iterator == second.m_iterator; 
        }
    };
}

namespace container {

    template<typename Type, typename Allocator = std::allocator<Type>>
    class vector {
    private:
        Type* m_vector;
        std::size_t m_capacity{};
        std::size_t m_size{};
        Allocator m_allocator;

        constexpr void reset(vector& other) noexcept {
            other.m_vector = nullptr;
            other.m_capacity = 0;
            other.m_size = 0;
        }

        constexpr void allocate(std::size_t capacity) {
            m_capacity = capacity;
            m_vector = std::allocator_traits<allocator_type>::allocate(m_allocator, capacity);
        }

        constexpr void deallocate(std::size_t capacity) {
            std::allocator_traits<allocator_type>::deallocate(m_allocator, m_vector, capacity);
            m_capacity = 0;
            m_size = 0;
        }

        constexpr void reallocate(std::size_t old_cap, std::size_t new_cap) {
            deallocate(old_cap);
            allocate(new_cap);
        }

        constexpr void construct(std::size_t size, const Type& value) {
            m_size = size;
            for (std::size_t index{ 0 }; index < size; ++index)
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index, value);
        }

        constexpr void destruct(std::size_t size) {
            for (std::size_t index{ 0 }; index < size; ++index)
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + index);
            m_size = 0;
        }

        constexpr void allocate_and_copy_construct(std::size_t capacity, std::size_t size, const Type& value = Type()) {
            allocate(capacity);
            construct(size, value);
        }

        constexpr void construct_init_list(std::initializer_list<Type> values) {
            m_size = values.size();
            for (size_type index{ 0 }; const auto & currentValue : values)
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + (index++), currentValue);
        }

        constexpr void deallocate_and_destruct(std::size_t capacity, std::size_t size) {
            destruct(size);
            deallocate(capacity);

        }

        constexpr void deallocate_destruct_keep_size_and_capacity(std::size_t size, std::size_t capacity) {
            for (std::size_t index{ 0 }; index < m_size; ++index)
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + index);
            std::allocator_traits<allocator_type>::deallocate(m_allocator, m_vector, m_capacity);

            m_capacity = capacity;
            m_size = size;
        }

        constexpr void uninitialized_alloc_copy(const vector& other) {
            m_size = other.m_size;
            for (size_type index{ 0 }; index < m_size; ++index) {
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index, *(other.m_vector + index));
            }
        }

        constexpr void uninitialized_alloc_move(vector&& other) noexcept {
            m_size = other.m_size;
            m_capacity = other.m_capacity;
            for (size_type index{ 0 }; index < m_size; ++index)
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index, std::move(*(other.m_vector + index)));
            reset(other);
        }

        constexpr void copy(const vector& other) {
            if (other.m_vector) {
                allocate(other.m_size);
                uninitialized_alloc_copy(other);
            }
            else
                m_vector = nullptr;
        }

        constexpr void reallocate_strong_guarantee(std::size_t capacity) {
            Type* tempVect = std::allocator_traits<allocator_type>::allocate(m_allocator, capacity);
            if (std::is_nothrow_move_constructible<Type>::value || !std::is_nothrow_move_constructible<Type>::value && !std::is_copy_constructible<Type>::value) {
                for (size_type index{ 0 }; index < m_size; ++index)
                    std::allocator_traits<allocator_type>::construct(m_allocator, tempVect + index, std::move(m_vector[index]));
            }

            else {
                size_type copiesMade{ 0 };
                try {
                    for (size_type index{ 0 }; index < m_size; ++index) {
                        std::allocator_traits<allocator_type>::construct(m_allocator, tempVect + index, *(m_vector + index));
                        ++copiesMade;
                    }
                }

                catch (...) {
                    for (std::size_t index{ 0 }; index < copiesMade; ++index)
                        std::allocator_traits<allocator_type>::destroy(m_allocator, tempVect + index);
                    std::allocator_traits<allocator_type>::deallocate(m_allocator, tempVect, capacity);

                    throw;
                }
            }
            size_type temp_cap = capacity;
            deallocate_destruct_keep_size_and_capacity(m_size, temp_cap);
            m_vector = tempVect;
            tempVect = nullptr;
        }

        constexpr void shift_and_construct(std::size_t index_pos, const Type& value, std::size_t count = 1) {
            // Should provide strong exception guarantee.

            size_type copies_made{ 0 };
            size_type copies_made1{ 0 };
            size_type copies_made2{ 0 };
            auto count_after_last_element = m_vector + size() + count;
            auto last_element = m_vector + size();
            auto current_pos = m_vector + index_pos;

            try {
                for (std::size_t index{ 0 }; index < count; ++index) {
                    std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + size() + index, m_vector[size() + index]);
                    ++copies_made;
                }
            }
            catch (...) {
                for (std::size_t index{ 0 }; index < copies_made; ++index)
                    std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + size() + index);
                throw;
            }

            try {
                while (current_pos++ != m_vector + size()) {
                    *(--(count_after_last_element)) = *(--(last_element));
                    ++copies_made1;
                }
            }
            catch (...) {
                while (copies_made1 != 0) {
                    std::allocator_traits<Allocator>::destroy(m_allocator, m_vector + size() + 1 + copies_made1);
                    --copies_made1;
                }
                throw;
            }

            //std::copy_backward(m_vector + index_pos, m_vector + size(), m_vector + size() + count);
            for (std::size_t index{ 0 }; index < count; ++index) {
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + index_pos + index);
            }

            try {
                for (std::size_t index{ 0 }; index < count; ++index) {
                    std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index_pos + index, value);
                    ++copies_made2;
                }
            }
            catch (...) {
                for (std::size_t index{ 0 }; index < copies_made2; ++index) {
                    std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + size() + index);
                }
                throw;
            }
            m_size += count;
        }

        constexpr void shift_and_construct_init(std::size_t pos_index_position, std::initializer_list<Type> list) {
            for (size_type index{ 0 }; auto value : list) {
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + size() + index, m_vector[size() + index]);
                ++index;
            }

            std::copy_backward(m_vector + pos_index_position, m_vector + size(), m_vector + size() + list.size());

            for (size_type index{ 0 }; auto value : list) {
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + pos_index_position + index);
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + pos_index_position + index, value);
                ++index;
            }
            m_size += list.size();
        }

        constexpr void shift_and_construct(std::size_t index_pos, Type&& value) {
            if (std::is_nothrow_move_constructible<Type>::value || !std::is_nothrow_move_constructible<Type>::value && !std::is_copy_constructible<Type>::value) {
                auto one_after_last_element = m_vector + size() + 1;
                auto last_element = m_vector + size();
                auto current_pos = m_vector + index_pos;

                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + size(), std::move(*(m_vector+size())));
                std::move_backward(m_vector + index_pos, m_vector + size(), m_vector + size() + 1);
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index_pos, std::move(value));
                m_size += 1;
            }
            else shift_and_construct(index_pos, value);
        }

        constexpr void insert_end_strong_guarantee(const Type& value) {
            try {
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + m_size, value);
            }
            catch (...) {
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + m_size);
                throw;
            }
            m_size += 1;
        }

        constexpr void  insert_end_strong_guarantee(Type&& value) {
            if constexpr (std::is_nothrow_move_constructible<Type>::value)
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + m_size, std::move(value));
            else
                insert_end_strong_guarantee(value);
            m_size += 1;
        }


    public:
        // Aliases  
        using value_type = Type;
        using reference = value_type&;
        using const_reference = const value_type&;
        using pointer = Type*;
        using const_pointer = const pointer;
        using allocator_type = Allocator;
        using const_alloc_reference = const allocator_type&;
        using size_type = std::size_t;
        using init_list_type = std::initializer_list<Type>;
        using iterator = random_access::iterator<Type>;
        using const_iterator = random_access::iterator<const Type>;
        using reverse_iterator = std::reverse_iterator<iterator>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;
        using difference_type = std::ptrdiff_t;


        // Constructors
        constexpr vector() noexcept : m_vector{ nullptr } {}

        constexpr explicit vector(const_alloc_reference allocator) noexcept
            : m_allocator{ allocator }, m_vector{ nullptr } {}

        constexpr explicit vector(size_type length, const_alloc_reference allocator = Allocator())
            : m_allocator{ allocator } {
            allocate_and_copy_construct(length, length);
        }

        constexpr explicit vector(size_type length, const_reference value, const_alloc_reference allocator = Allocator())
            : m_allocator{ allocator } {
            allocate_and_copy_construct(length, length, value);
        }

        constexpr explicit vector(init_list_type values, const_alloc_reference allocator = Allocator())
            : m_allocator{ allocator } {
            allocate(values.size());
            construct_init_list(values);
        }

        template<typename input_iter>
        constexpr vector(input_iter first, input_iter last, const_alloc_reference allocator = Allocator()) {
            size_type size = std::distance(last, first);
            allocate(size);
            for (size_type index{ 0 }; index < size; ++index) {
                std::allocator_traits<Allocator>::construct(m_allocator, m_vector + index, *(first + index));
                ++m_size;
            }
        }

        // Copy semantics
        constexpr vector(const vector& other) {
            m_allocator = std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.get_allocator());
            copy(other);
        }

        constexpr vector(const vector& other, const_alloc_reference allocator)
            : m_allocator{ allocator } {
            copy(other);
        }

        constexpr vector& operator=(const vector& other) {
            if (this == &other) { return *this; }
            destruct(size());
            if (other.m_vector)
            {
                if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value) {
                    m_allocator = other.get_allocator();
                }
                if (other.size() > capacity()) {
                    reallocate(capacity(), other.size());
                }
                uninitialized_alloc_copy(other);
            }
            else {
                m_vector = nullptr;
                m_size = 0;
            }
            return *this;
        }


        // Move semantics
        constexpr vector(vector&& other) noexcept
            : m_vector{ other.m_vector }, m_size{ other.m_size }, m_capacity{ other.m_capacity }, m_allocator{ std::move(other.m_allocator) } {
            reset(other);
        }

        constexpr vector(vector&& other, const_alloc_reference allocator) noexcept
            : m_size{ other.m_size }, m_capacity{ other.m_capacity }, m_allocator{ std::move(allocator) } {
            if (allocator != other.get_allocator()) {
                uninitialized_alloc_move(std::move(other));
            }
            else
                m_vector = other.m_vector;

            reset(other);
        }

        constexpr vector& operator=(vector&& other) noexcept {
            if (this == &other) { return *this; }

            if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value) {
                deallocate_and_destruct(capacity(), size());
                m_allocator = other.get_allocator();
                m_vector = other.m_vector;
                reset(other);
            }
            else if (m_allocator == other.m_allocator) {
                deallocate_and_destruct(capacity(), size());
                m_vector = other.m_vector;
                reset(other);
            }
            else {
                destruct(size());
                reallocate(capacity(), other.capacity());
                uninitialized_alloc_move(std::move(other));
            }
            m_size = other.m_size;
            m_capacity = other.m_capacity;

            return *this;
        }

        ~vector() noexcept { deallocate_and_destruct(m_capacity, m_size); }

        // Overloaded operators
        constexpr vector& operator=(init_list_type values) {
            destruct(m_size);
            if (values.size() > capacity()) {
                reallocate(capacity(), values.size());
            }

            construct_init_list(values);
            return *this;
        }

        // Operator<=> doesn't seem to work this way...
        //constexpr auto operator<=>(const vector&) = default;
        constexpr friend bool operator== (const vector& first, const vector& second) {
            return (first.m_size == second.m_size &&
                std::equal(first.m_vector, first.m_vector + first.size(), second.m_vector, second.m_vector + second.size()));
        }
        constexpr bool operator!= (const vector& other) const {
            return !(*this == other);
        }
        constexpr bool operator< (const vector& other) const {
            return std::lexicographical_compare(m_vector, m_vector+size(), other.begin(), other.end());
        }
        constexpr bool operator> (const vector& other) const {
            return !(*this < other);
        }

        constexpr bool operator<=(const vector& other) const {
            return !(other < *this);
        }

        constexpr bool operator>=(const vector& other) const {
            return !(*this < other);
        }


        // Member functions
        constexpr void assign(size_type size, const_reference value) {
            destruct(m_size);
            if (size > capacity()) {
                reallocate(capacity(), size);
            }
            construct(size, value);
        }

        constexpr void assign(init_list_type values) {
            destruct(m_size);
            if (values.size() > capacity())
            {
                reallocate(capacity(), values.size());
            }
            construct_init_list(values);
        }

        template<typename input_iter>
        constexpr void assign(input_iter first, input_iter last) {
            size_type size = std::distance(last, first);
            destruct(size);
            if (size > capacity()) {
                reallocate(capacity(), size);
            }
            for (size_type index{ 0 }; index < size; ++index) {
                std::allocator_traits<Allocator>::construct(m_allocator, m_vector + index, *(first + index));
                ++m_size;
            }
        }

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

        // Access functions
        constexpr reference at(size_type index) { 
            return index < size() ? m_vector[index] : throw std::out_of_range("Index out of range"); 
        }
        constexpr const_reference at(size_type index) const { 
            return index < size() ? m_vector[index] : throw std::out_of_range("Index out of range"); 
        }
        constexpr reference operator[](size_type index) { 
            assert(index < size() && "Index out of range"); return m_vector[index]; 
        }
        constexpr const_reference operator[](size_type index) const { 
            assert(index < size() && "Index out of range"); return m_vector[index]; 
        }
        constexpr pointer data() noexcept {
            return (size() != 0) ? m_vector : nullptr; 
        }
        constexpr const_pointer data() const noexcept { 
            return (size() != 0) ? m_vector : nullptr; 
        }
        constexpr reference back() { 
            return *(end() - 1); 
        }
        constexpr const_reference back() const { 
            return *(end() - 1); 
        }
        constexpr reference front() { 
            return *(begin()); 
        }
        constexpr const_reference front() const {
            return *(begin()); 
        }

        // Iterators
        constexpr iterator begin() noexcept { 
            return m_vector; 
        }
        constexpr const_iterator begin() const noexcept { 
            return m_vector; 
        }
        constexpr const_iterator cbegin() const noexcept { 
            return m_vector; 
        }
        constexpr reverse_iterator rbegin() noexcept {
            return reverse_iterator(m_vector + size()); 
        }
        constexpr const_reverse_iterator crbegin() const noexcept { 
            return const_reverse_iterator(m_vector + size()); 
        }
        constexpr iterator end() noexcept { 
            return m_vector + size(); 
        }
        constexpr const_iterator end() const noexcept { 
            return m_vector + size();
        }
        constexpr const_iterator cend() const noexcept {
            return m_vector + size(); 
        }
        constexpr reverse_iterator rend() noexcept { 
            return reverse_iterator(m_vector); 
        }
        constexpr const_reverse_iterator rend() const noexcept { 
            return reverse_iterator(m_vector); 
        }

        // Capacity  related    
        constexpr size_type size() const noexcept { 
            return m_size; 
        }
        constexpr size_type max_size() const noexcept { 
            return std::numeric_limits<difference_type>::max(); 
        }
        constexpr size_type capacity() const noexcept { 
            return m_capacity; 
        }
        constexpr bool empty() const noexcept { 
            return m_size == 0; 
        }
        constexpr bool is_null() const noexcept { 
            return m_vector == nullptr; 
        }

        constexpr void reserve(size_type capacity) {
            if (capacity > max_size())
                throw std::length_error("Capacity allocated exceeds max_size()");

            else if (capacity > m_capacity)
                reallocate_strong_guarantee(capacity);
        }

        constexpr void shrink_to_fit() { 
            if (m_capacity != m_size) { 
                reallocate_strong_guarantee(m_size); 
            } 
        }

        // Modifier functions
        constexpr void clear() noexcept { 
            destruct(m_size); 
        }

        constexpr iterator insert(const iterator pos, const_reference value) {
            return emplace(pos, value);
        }

        constexpr iterator insert(const iterator pos, value_type&& value) {
            return emplace(pos, std::move(value));
        }

        constexpr iterator insert(const iterator pos, init_list_type values) {
            size_type pos_index_position = std::distance(pos, begin());
            if (size() + values.size() < capacity()) {
                shift_and_construct_init(pos_index_position, values);
            }

            else {
                do {
                    if (m_capacity == 0) m_capacity = 1;
                    m_capacity *= constants::realloc_factor;
                } while (m_capacity < values.size() + m_size);

                reallocate_strong_guarantee(m_capacity);
                shift_and_construct_init(pos_index_position, values);
            }
            return values.size() == 0 ? pos : iterator(m_vector + pos_index_position);
        }

        constexpr iterator insert(const iterator pos, size_type count, const_reference value) {
            size_type pos_index_position = std::distance(pos, begin());
            if (size() + count < capacity()) {
                if (pos == end()) {
                    insert_end_strong_guarantee(value);
                }
                else
                    shift_and_construct(pos_index_position, value, count);
            }
            else {
                do {
                    if (m_capacity == 0) m_capacity = 1;
                    m_capacity *= constants::realloc_factor;
                } while (m_capacity < m_size);

                reallocate_strong_guarantee(m_capacity);
                shift_and_construct(pos_index_position, value, count);
            }
            return count == 0 ? pos : iterator(m_vector + pos_index_position);
        }

        constexpr iterator erase(const iterator pos) {
            assert(pos <= end() && "Vector subscript out of range");
            size_type pos_index_position = std::distance(pos, begin());
            std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + pos_index_position);
            if constexpr (std::is_nothrow_move_constructible<Type>::value) {
                std::move(m_vector + pos_index_position + 1, m_vector + size(), m_vector + pos_index_position);
            }

            else
                std::copy(m_vector + pos_index_position + 1, m_vector + size(), m_vector + pos_index_position);
            --m_size;
            return (end() == pos) ? end() : iterator(m_vector + pos_index_position);
        }

        constexpr iterator erase(const iterator first, const iterator last) {
            bool last_equals_end = (last == end());
            assert(first <= end() && "Vector's first argument out of range");
            assert(last <= end() && "Vector's second argument out of range");
            assert(first <= last && "Vector's first argument smaller than second argument");
            size_type first_position = std::distance(first, begin());
            size_type last_position = std::distance(last, begin());
            size_type difference{ last_position - first_position };
            for (size_type index{ first_position }; index < last_position; ++index) {
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + index);
            }
            if constexpr (std::is_nothrow_move_constructible<Type>::value) {
                std::move(m_vector + last_position, m_vector + size(), m_vector + first_position);
            }
            else
                std::copy(m_vector + last_position, m_vector + size(), m_vector + first_position);
            m_size -= difference;
            return (last_equals_end) ? iterator(m_vector + last_position) : iterator(m_vector + first_position);
        }

        constexpr void pop_back() noexcept {
            std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + size() - 1);
            m_size -= 1;
        }

        constexpr void resize(size_type count, const_reference value = value_type()) {
            auto temp_size = size();
            if (count < size()) {
                for (size_type index{ count }; index < temp_size; ++index)
                    pop_back();
            }
            else {
                if (count > capacity())
                    reallocate_strong_guarantee(count);
                for (size_type index{ temp_size }; index < count; ++index)
                    insert_end_strong_guarantee(value);
            }
        }

        template<typename...Args>
        constexpr iterator emplace(const iterator pos, Args&&...args) { // Provide strong guarantee
            assert(pos <= end() && "Vector's argument out of range");
            size_type pos_index_position = std::distance(pos, begin());

            if (size() + 1 < capacity()) {
                if (pos == end()) {
                    try {
                        std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + size(), std::forward<Args>(args)...);
                    }
                    catch (...) {
                        std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + size());
                        throw;
                    }
                    ++m_size;
                }
                else {
                    shift_and_construct(pos_index_position, std::forward<Args>(args)...);
                }
            }
            else {
                do {
                    if (m_capacity == 0) m_capacity = 1;
                    m_capacity *= constants::realloc_factor;
                } while (m_capacity < 1 + size());
                reallocate_strong_guarantee(m_capacity);
                shift_and_construct(pos_index_position, std::forward<Args>(args)...); // Checks if move constructor is noexcept. Otherwise does copy
            }
            
            return iterator(m_vector + pos_index_position);
        }

        template<typename...Args>
        constexpr reference emplace_back(Args...args) {
            emplace(end(), std::forward<Args>(args)...);
            return *(m_vector + size() - 1);
        }

        constexpr void push_back(const Type& value) {
            emplace_back(value);
        }

        constexpr void push_back(Type&& value) {
            emplace_back(std::move(value));
        }

        constexpr void swap(vector& other) noexcept { 
            if (this == &other) { return; }
            if (std::allocator_traits<allocator_type>::propagate_on_container_swap::value
                || std::allocator_traits<allocator_type>::is_always_equal::value) {
                std::swap(m_allocator, other.m_allocator);
            }
            std::swap(m_vector, other.m_vector); 
            std::swap(m_capacity, other.m_capacity);
            std::swap(m_size, other.m_size);
        }
    };

    // Erase, erase_if
    template<typename Type, typename Allocator, typename Val>
    constexpr auto erase(container::vector<Type, Allocator>& vec, const Val& value) {
        auto iter = std::remove(vec.begin(), vec.end(), value);
        auto dist = std::distance(iter, vec.end());
        vec.erase(iter, vec.end());
        return dist;
    }

    template<typename Type, typename Allocator, typename Predicate>
    constexpr auto erase_if(container::vector<Type, Allocator>& vec, Predicate predicate) {
        auto iter = std::remove_if(vec.begin(), vec.end(), predicate);
        auto dist = std::distance(iter, vec.end());
        c.erase(iter, vec.end());
        return dist;
    }
    

    namespace pmr {
        template <class T>
        using vector = container::vector<T, std::pmr::polymorphic_allocator<T>>;
    }
}

#endif
```
\$\endgroup\$
2
  • \$\begingroup\$ That's a lot of code for a beginner! \$\endgroup\$ Jan 23, 2021 at 18:14
  • 1
    \$\begingroup\$ @MartinYork This made me laugh actually haha. Well, remember, length and code correctness are two different things... :S \$\endgroup\$ Jan 23, 2021 at 18:17

1 Answer 1

4
\$\begingroup\$

Overview

One of the good implementations of vector I have seen. Still a couple of bugs.


You make an attempt at strong exception gurantees but I don't think you get there. The standard pattern for achieving this will make you much more successful.

  1. Create Temporary.
    Copy/Move data into Temporary.
  2. Swap (Exception safe)
  3. Destroy old state.

Note: You can use the constructor/destructor to achieve steps 1 and 3 which just means you need to implement the swap semantics.

Have a read of this article I wrote: https://lokiastari.com/posts/Vector-Resize


You should add a swap method and swap function. It will make several standard pattern easier.


Questions

Why are you using three different namespaces? constants, random_access and container. Seems like they are all part of the same namespace to me.

Common Patterns

I see a lot of this pattern:

for (size_type index{ 0 }; index < m_size; ++index)
    std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index, std::move(*(other.m_vector + index)));

Where you don't use braces around the code inside a for() loop. This is a bad habit and going to burn you one day. Best practice is to always add the braces to make sure that you never accidentally only execute one statement. Your gellow coders will appreciate it.

Code Review

First time I have seen the space ship operator used by somebody in code.

        constexpr auto operator<=>(const iterator&) const = default;

You seem to have missed a new line.
You have the newline in the --operator

        constexpr iterator operator++(int) noexcept { 
            iterator tmp(*this); ++(*this); 
            return tmp; 
        }

Never seen this in user defined iterator before.

        friend constexpr iterator operator+(difference_type first, const iterator& other) noexcept { 
            return other.m_iterator + first;
        }

It will lead to this:

        iterator y = con.begin();
        iterator x = 5 + y; 

But it is supported by the standard iterators (though I had to write code to check std::vector). So It seems to fit logically.


Normally when you override the operator== you symmetrically also provide the operator!= version.

        constexpr friend bool operator== (const iterator& first, const iterator& second) { 
            return first.m_iterator == second.m_iterator; 
        }
    };

To match C-Array (which is what std::vector also does) you should destroy the objects in reverse order of creation.

        constexpr void destruct(std::size_t size) {
            for (std::size_t index{ 0 }; index < size; ++index)
                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + index);
            m_size = 0;
        }

You learn something new every day:

for (size_type index{ 0 }; const auto & currentValue : values)

I have never seen that for() loop construct before. That is actually quite usefull.


Again I would destroy in reverse order of creation.

constexpr void deallocate_destruct_keep_size_and_capacity(std::size_t size, std::size_t capacity);

I believe there is a bug here:

        constexpr void uninitialized_alloc_move(vector&& other) noexcept {
            m_size = other.m_size;
            m_capacity = other.m_capacity;
            for (size_type index{ 0 }; index < m_size; ++index)
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + index, std::move(*(other.m_vector + index)));


            // This call to reset sets all the members of `other` to 0/nullptr
            // I believe you just leaked all the memory from `other.
            reset(other);

            // Note: Simply deallocating other is not enough either.
            //       The members of the `other` container are still valid
            //       objects so they need to be destroyed.
            //
            // I think this needs:
            // other.deallocate_and_destruct();

        }

This does work. But you made me look it up.

if (std::is_nothrow_move_constructible<Type>::value || 
    !std::is_nothrow_move_constructible<Type>::value && 
    !std::is_copy_constructible<Type>::value)

Better to make clear your intention to the reader using braces.


This does not provide the strong gurantee.

        constexpr void reallocate_strong_guarantee(std::size_t capacity) {
            Type* tempVect = std::allocator_traits<allocator_type>::allocate(m_allocator, capacity);

            // This is known at compile time.
            // You should use the `constepxr if` or SFINE to make sure
            // only one piece of code is actually planted by the compiler.
            if (/*MOVABLE NOTHROW*/) {
                // STUFF
            }    
            else {
                size_type copiesMade{ 0 };
                try {
                    // STUFF
                }

                catch (...) {
                    // Don't forget reverse order of destruction.
                    for (std::size_t index{ 0 }; index < copiesMade; ++index)
                        // Note this can also potentially throw.
                        // You don't know what the destructor of T will do.
                        std::allocator_traits<allocator_type>::destroy(m_allocator, tempVect + index);
                    
                    // If the `destroy()` above throws for any member
                    // you are goint to leak the `tempVect` object here.
                    // A simple solution is to place the `tempVect` inside `std::unique_ptr`
                    // while you are working on it (and release it when you assign to `m_vector`.
                      std::allocator_traits<allocator_type>::deallocate(m_allocator, tempVect, capacity);

                    throw;
                }
            }
            size_type temp_cap = capacity;

            // Again you have a issue with destruction of the members
            // If anything goes wrong during this function call and
            // an exception escapes this object is now in a bad state
            // (some members are in a bad state and tempVect is leaked.
            deallocate_destruct_keep_size_and_capacity(m_size, temp_cap);
            m_vector = tempVect;
            tempVect = nullptr;
        }

The classic way to provide the strong exception gurantee is to do this in three distinct phases.

        1: Allocate Temporary state.
           Copy/Move all data into the Temporary state.
        2: SWAP the temporary state and the current state.
        3: Deallocate and release the Temporary state.

If something goes wrong in phase 1 or 3 the current state of the object is not affected. Unfortunately because you attempt to deallocate before swapping the state you potentially are left with an object in an inconsistent state.


Interesting attempt!

        constexpr void shift_and_construct(std::size_t index_pos, const Type& value, std::size_t count = 1) {

I don't think you can provide this gurantee.

            // Should provide strong exception guarantee.

You can only provide as much of a guarantee as the T type provides. This is because you are copying over elements. If something goes wrong one way it can go just as bad trying to put it back.


Declare variables as close to their place of use as possible.

            size_type copies_made{ 0 };
            size_type copies_made1{ 0 };
            size_type copies_made2{ 0 };

            try {
                while (current_pos++ != m_vector + size()) {
                    *(--(count_after_last_element)) = *(--(last_element));
                    ++copies_made1;
                }
            }
            catch (...) {
                while (copies_made1 != 0) {

                    // If you destroy objects then they are not in a valid state.

                    // The best you can do is copy them back.
                    // But I would not even try and do that as copying them
                    // back could also result in an exception.
                    //
                    // Your move is only as good as the guarantees that are provided by T

                    std::allocator_traits<Allocator>::destroy(m_allocator, m_vector + size() + 1 + copies_made1);
                    --copies_made1;
                }
                throw;
            }

BUG: You can not destroy an object that does not exist.

        constexpr void insert_end_strong_guarantee(const Type& value) {
            try {
                std::allocator_traits<allocator_type>::construct(m_allocator, m_vector + m_size, value);
            }
            catch (...) {
                // You can not call the destructor on an object that has
                // failed in construction.
                //
                // The constructor either works or it fails.
                // If it fails the object does not exist and thus can
                // can nto be destoryed.

                std::allocator_traits<allocator_type>::destroy(m_allocator, m_vector + m_size);
                throw;
            }

Personally I dislike when you initialize half the variables in the declaration and half in the initializer list. As a maintainer I need to keep flicking back to check what was done in the variable list above.

        constexpr vector() noexcept : m_vector{ nullptr } {}

Here you are assuming that input_iter is actually a Random Accesses Iterator.

        template<typename input_iter>
        constexpr vector(input_iter first, input_iter last, const_alloc_reference allocator = Allocator()) {
            size_type size = std::distance(last, first);
            allocate(size);
            for (size_type index{ 0 }; index < size; ++index) {

                // Note: first + index is not always valid on all iterator
                //       types.
                std::allocator_traits<Allocator>::construct(m_allocator, m_vector + index, *(first + index));
                ++m_size;
            }
        }

This does not provide the strong exception guarantee. You destroy the current object before you even attempt to make a copy. Thus if the copy fails your object is in an invalid state.

Also the use of self assignment is code pesimization for the normal (expect) assignment situations (yes you should account for self assignment but it is rare in real code so explicitly optimizing for it actually makes normal code worse).

        constexpr vector& operator=(const vector& other) {
            if (this == &other) { return *this; }
            destruct(size());
            if (other.m_vector)
            {
                if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value) {
                    m_allocator = other.get_allocator();
                }
                if (other.size() > capacity()) {
                    reallocate(capacity(), other.size());
                }
                uninitialized_alloc_copy(other);
            }
            else {
                m_vector = nullptr;
                m_size = 0;
            }
            return *this;
        }

The standard way fo doing the assignemnt operator copes with both situations:

        constexpr vector& operator=(vector const& other)
        {
            vector tmp(other);   // Copy
            other.swap(*this);   // Swap current and other state.
            return *this;
        }                        // Tmp state cleaned up.

Strong exception guarantee. Does not have pesimizzing self assignment check.


Sure this works:

        constexpr vector(vector&& other) noexcept
            : m_vector{ other.m_vector }, m_size{ other.m_size }, m_capacity{ other.m_capacity }, m_allocator{ std::move(other.m_allocator) } {
 
            reset(other);
        }

But the standard implementation is easier to read:

        constexpr vector(vector&& other) noexcept
            : m_vector(nullptr)
            , m_size(0)
            , m_capacity(0)
        {
            other.swap(*this);
        }

Again this does not provide the strong exception guarantee. Because you destroy the state of this object before swapping. This leaves your object in a an invalid state if something goes wrong during the destruction of the members.

        constexpr vector& operator=(vector&& other) noexcept {
            if (this == &other) { return *this; }

            if constexpr (std::allocator_traits<allocator_type>::propagate_on_container_move_assignment::value) {
                deallocate_and_destruct(capacity(), size());
                m_allocator = other.get_allocator();
                m_vector = other.m_vector;
                reset(other);
            }
            else if (m_allocator == other.m_allocator) {
                deallocate_and_destruct(capacity(), size());
                m_vector = other.m_vector;
                reset(other);
            }
            else {
                destruct(size());
                reallocate(capacity(), other.capacity());
                uninitialized_alloc_move(std::move(other));
            }
            m_size = other.m_size;
            m_capacity = other.m_capacity;

            return *this;
        }

The standard pattern for this:

        constexpr vector& operator=(vector&& other) noexcept
        {
            other.swap(*this);
            // If you feel inclined you can now reset the state of other.
            other.clear();   // This destroys all the objects.
                             // But should leave the capacity in place.
                             // The other object can potentially be re-used
                             // without having to reallocate space.
                             // And if it is not re-used its destructor
                             // will clean up capacity.
            return *this;
        }

Again not exception safe and thus does not provide the strong gurantee.

        // Overloaded operators
        constexpr vector& operator=(init_list_type values) {
            destruct(m_size);
            if (values.size() > capacity()) {
                reallocate(capacity(), values.size());
            }

            construct_init_list(values);
            return *this;
        }

Do it like this:

        constexpr vector& operator=(init_list_type values) {
            vector tmp(values);
            tmp.swap(*this);
            return *this;
        }

Sure:

        constexpr pointer data() noexcept {
            return (size() != 0) ? m_vector : nullptr; 
        }

BUT that seems like an over complex way of saying:

       constexpr pointer data() noexcept {return m_vector;}

Why does it have to be nullptr if the size is zero?


Is this true:

        constexpr size_type max_size() const noexcept { 
            return std::numeric_limits<difference_type>::max(); 
        }

You can really allocate this amount of memory?


Is this a way of asking if capacity == 0 ?

        constexpr bool is_null() const noexcept { 
            return m_vector == nullptr; 
        }

Why do you want to be able to do this. Personally I think you have overcomplicated your code by using nullptr to represent a zero capacity vector. I would have always allocated space (I assume if you declare it will be used).


In your case can this ever fail (capacity > max_size())?

        constexpr void reserve(size_type capacity) {
            if (capacity > max_size())
                throw std::length_error("Capacity allocated exceeds max_size()");

            else if (capacity > m_capacity)
                reallocate_strong_guarantee(capacity);
        }

\$\endgroup\$
2
  • 1
    \$\begingroup\$ “Normally when you override the operator== you symmetrically also provide the operator!= version.” Not anymore. In fact, since operator<=> is defaulted in iterator, even operator== is unnecessary. In the vector class, you could also get away with just operator<=> and operator== (you need operator== in vector because operator<=> can’t be defaulted, due to the allocator member). \$\endgroup\$
    – indi
    Jan 23, 2021 at 20:59
  • \$\begingroup\$ Woah, thanks a lot for the review! I'll have to read this carefully and fix whatever has to be fixed. Regarding the last question (capacity > max_size()), I implemented that according to Cppreference - although it's true that hardly ever can that happen, especially in a custom implementation. Once again, thanks a lot for the feedback & review, it's really helpful and appreciated. \$\endgroup\$ Jan 23, 2021 at 21:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.