Simplified Vector Implementation in C++

Question

I have implemented a class Vector to learn about data structures and algorithms and how to implement them using C++. I have yet to implement some std::vector functionalities e.g. custom allocator template parameter, iterator/const_iterator classes.

I'm learning C++ through a C++11 book and trying to learn C++14 and C++17 best practices on the fly. I would appreciate any advice on how to improve or make it more compatible with modern best practices. I'm using g++ compiler with -std=c++17 flag.

One specific issue that I was in doubt was about the move assignment operator. I saw some code around the internet using a unified assignment operator for both copy and move assignment operators using swap, but this link made me think that it wasn't the best way to do it. Any thoughts?

Vector.h

namespace algorithms
{
    template<typename T>
    class Vector
    {
    public:
        using size_type = std::size_t;
        using iterator = T*;
        using const_iterator = const T*;
        using reference = T&;
        using const_reference = const T&;

        // Constructors and Destructor
        Vector();
        Vector(size_type initial_size, const T& value);
        explicit Vector(size_type initial_size);
        Vector(std::initializer_list<T> initializer);
        Vector(const Vector<T>& vector);
        Vector(Vector<T>&& vector) noexcept;
        Vector& operator=(const Vector<T>& vector);
        Vector& operator=(Vector<T>&& vector) noexcept;
        ~Vector();

        // Iterators
        /// TODO: Replace pointers by an iterator class
        iterator begin() noexcept;
        const_iterator begin() const noexcept;
        const_iterator cbegin() const noexcept;
        iterator end() noexcept;
        const_iterator end() const noexcept;
        const_iterator cend() const noexcept;

        // Capacity
        size_type size() const noexcept;
        bool empty() const noexcept;
        size_type capacity() const noexcept;
        void reserve(size_type new_capacity);
        void resize(size_type new_size, const T& value);
        void resize(size_type new_size);
        void shrink_to_fit();

        // Modifiers
        template<typename... Args>
        reference emplace_back(Args&&... args);
        template<typename... Args>
        iterator emplace(iterator position, Args&&... args);
        void push_back(const T& value);
        void push_back(T&& value);
        void pop_back();
        iterator erase(iterator position);
        iterator erase(iterator first, iterator last);
        void clear() noexcept;
        void swap(Vector<T>& vector) noexcept;

        // Accessors
        reference operator[](size_type index);
        const_reference operator[](size_type index) const;
        reference at(size_type index);
        const_reference at(size_type index) const;
        reference back();
        const_reference back() const;
    private:
        using Alloc = std::allocator<T>;
        Alloc allocator;
        T* dynamic_array;
        T* end_position; // points to one past the last constructed element in the array
        T* capacity_limit; // points to one past the end of the array

        void reallocate(size_type new_capacity);
        void reallocate_if_full();
        void deallocate();
        void allocate_and_copy(const_iterator begin, const_iterator end);
    };

    // Non-member swap
    template<typename T>
    void swap(Vector<T>& left, Vector<T>& right);
}

Vector.inl

namespace algorithms
{
    // Constructors
    template<typename T>
    Vector<T>::Vector(): dynamic_array(nullptr), end_position(nullptr), capacity_limit(nullptr)
    {}

    template<typename T>
    Vector<T>::Vector(size_type initial_size, const T& value)
    {
        dynamic_array = allocator.allocate(initial_size);
        end_position = std::uninitialized_fill_n(dynamic_array, initial_size, value);
        capacity_limit = dynamic_array + initial_size;
    }

    template<typename T>
    Vector<T>::Vector(size_type initial_size): Vector<T>(initial_size, T())
    {}

    template<typename T>
    Vector<T>::Vector(std::initializer_list<T> initializer)
    {
        allocate_and_copy(initializer.begin(), initializer.end());
    }

    template<typename T>
    Vector<T>::Vector(const Vector<T>& vector)
    {
        allocate_and_copy(vector.cbegin(), vector.cend());
    }

    template<typename T>
    Vector<T>::Vector(Vector<T>&& vector) noexcept:
        dynamic_array(vector.dynamic_array), end_position(vector.end_position), capacity_limit(vector.capacity_limit)
    {
        vector.dynamic_array = nullptr;
        vector.end_position = nullptr;
        vector.capacity_limit = nullptr;
    }

    template<typename T>
    Vector<T>& Vector<T>::operator=(const Vector<T>& vector)
    {
        Vector<T> temp(vector);

        swap(temp);

        return *this;
    }

    template<typename T>
    Vector<T>& Vector<T>::operator=(Vector<T>&& vector) noexcept
    {
        if (this != &vector) // protection against self-assignment
        {
            deallocate();
            dynamic_array = vector.dynamic_array;
            end_position = vector.end_position;
            capacity_limit = vector.capacity_limit;

            vector.dynamic_array = nullptr;
            vector.end_position = nullptr;
            vector.capacity_limit = nullptr;
        }

        return *this;
    }

    template<typename T>
    Vector<T>::~Vector()
    {
        deallocate();
    }

    // Iterators
    template<typename T>
    typename Vector<T>::iterator Vector<T>::begin() noexcept
    {
        return dynamic_array;
    }

    template<typename T>
    typename Vector<T>::const_iterator Vector<T>::begin() const noexcept
    {
        return dynamic_array;
    }

    template<typename T>
    typename Vector<T>::const_iterator Vector<T>::cbegin() const noexcept
    {
        return dynamic_array;
    }

    template<typename T>
    typename Vector<T>::iterator Vector<T>::end() noexcept
    {
        return end_position;
    }

    template<typename T>
    typename Vector<T>::const_iterator Vector<T>::end() const noexcept
    {
        return end_position;
    }

    template<typename T>
    typename Vector<T>::const_iterator Vector<T>::cend() const noexcept
    {
        return end_position;
    }

    // Capacity
    template<typename T>
    typename Vector<T>::size_type Vector<T>::size() const noexcept
    {
        return static_cast<size_type>(end_position - dynamic_array);
    }

    template<typename T>
    bool Vector<T>::empty() const noexcept
    {
        return size() == 0;
    }

    template<typename T>
    typename Vector<T>::size_type Vector<T>::capacity() const noexcept
    {
        return static_cast<size_type>(capacity_limit - dynamic_array);
    }

    template<typename T>
    void Vector<T>::reserve(size_type new_capacity)
    {
        if (new_capacity <= capacity())
        {
            return;
        }

        reallocate(new_capacity);
    }

    template<typename T>
    void Vector<T>::resize(size_type new_size, const T& value)
    {
        if (new_size > capacity())
        {
            reallocate(2 * new_size);
            end_position = std::uninitialized_fill_n(end_position, new_size - size(), value);
        }
        else if (new_size > size())
        {
            end_position = std::uninitialized_fill_n(end_position, new_size - size(), value);
        }
        else if (new_size < size())
        {
            for (size_type i = 0; i < size() - new_size; ++i)
            {
                --end_position;
                std::allocator_traits<Alloc>::destroy(allocator, end_position);
            }
        }
    }

    template<typename T>
    void Vector<T>::resize(size_type new_size)
    {
        resize(new_size, T());
    }

    template<typename T>
    void Vector<T>::shrink_to_fit()
    {
        reallocate(size());
    }

    // Modifiers
    template<typename T>
    template<typename... Args>
    typename Vector<T>::reference Vector<T>::emplace_back(Args&&... args)
    {
        reallocate_if_full();

        std::allocator_traits<Alloc>::construct(allocator, end_position, std::forward<Args>(args)...);
        ++end_position;
    }

    template<typename T>
    template<typename... Args>
    typename Vector<T>::iterator Vector<T>::emplace(iterator position, Args&&... args)
    {
        const size_type distance = std::distance(begin(), position);

        if (position == end_position)
        {
            emplace_back(std::forward<Args>(args)...);
        }
        else 
        {
            reallocate_if_full();

            std::move_backward(begin() + distance, end_position, end_position + 1);
            std::allocator_traits<Alloc>::construct(allocator, begin() + distance, std::forward<Args>(args)...);
            ++end_position;
        }

        return begin() + distance;
    }

    template<typename T>
    void Vector<T>::push_back(const T& value)
    {
        emplace_back(value);
    }

    template<typename T>
    void Vector<T>::push_back(T&& value)
    {
        emplace_back(std::move(value));
    }

    template<typename T>
    void Vector<T>::pop_back()
    {
        --end_position;
        std::allocator_traits<Alloc>::destroy(allocator, end_position);
    }

    template<typename T>
    typename Vector<T>::iterator Vector<T>::erase(iterator position)
    {
        std::move(position + 1, end(), position);
        --end_position;
        std::allocator_traits<Alloc>::destroy(allocator, end_position);
        return position;
    }

    template<typename T>
    typename Vector<T>::iterator Vector<T>::erase(iterator first, iterator last)
    {
        if (first == last)
        {
            return begin();
        }

        auto new_end_position = std::move(last, end(), first);

        for (auto iterator = new_end_position; iterator != end_position; ++iterator)
        {
            std::allocator_traits<Alloc>::destroy(allocator, iterator);
        }

        end_position = new_end_position;

        return first;
    }

    template<typename T>
    void Vector<T>::clear() noexcept
    {
        deallocate();
        dynamic_array = nullptr;
        end_position = nullptr;
        capacity_limit = nullptr;
    }

    template<typename T>
    void Vector<T>::swap(Vector<T>& vector) noexcept
    {
        using std::swap;

        swap(this->dynamic_array, vector.dynamic_array);
        swap(this->end_position, vector.end_position);
        swap(this->capacity_limit, vector.capacity_limit);
    }

    // Accessors
    template<typename T>
    typename Vector<T>::reference Vector<T>::operator[](size_type index)
    {
        return dynamic_array[index];
    }

    template<typename T>
    typename Vector<T>::const_reference Vector<T>::operator[](size_type index) const
    {
        return dynamic_array[index];
    }

    template<typename T>
    typename Vector<T>::reference Vector<T>::at(size_type index)
    {
        if (index < 0 || index >= size())
        {
            throw std::out_of_range("Invalid index");
        }

        return dynamic_array[index];
    }

    template<typename T>
    typename Vector<T>::const_reference Vector<T>::at(size_type index) const
    {
        if (index < 0 || index >= size())
        {
            throw std::out_of_range("Invalid index");
        }

        return dynamic_array[index];
    }

    template<typename T>
    typename Vector<T>::reference Vector<T>::back()
    {
        return dynamic_array[size() - 1];
    }

    template<typename T>
    typename Vector<T>::const_reference Vector<T>::back() const
    {
        return dynamic_array[size() - 1];
    }

    // Private
    template<typename T>
    void Vector<T>::reallocate(size_type new_capacity)
    {
        auto new_array = allocator.allocate(new_capacity);

        auto new_end_position = std::uninitialized_copy(std::make_move_iterator(begin()), std::make_move_iterator(end()), new_array);

        deallocate();

        dynamic_array = new_array;
        end_position = new_end_position;
        capacity_limit = dynamic_array + new_capacity;
    }

    template<typename T>
    void Vector<T>::reallocate_if_full()
    {
        if (size() == capacity())
        {
            size_type new_capacity = (size() != 0) ? 2 * size() : 1;
            reallocate(new_capacity);
        }
    }

    template<typename T>
    void Vector<T>::deallocate()
    {
        if (dynamic_array)
        {
            std::for_each(dynamic_array, end_position,
                            [&allocator = allocator](T& value) { std::allocator_traits<Alloc>::destroy(allocator, &value); });
            allocator.deallocate(dynamic_array, capacity_limit - dynamic_array);
        }
    }

    template<typename T>
    void Vector<T>::allocate_and_copy(const_iterator begin, const_iterator end)
    {
        size_type new_capacity = end - begin;
        dynamic_array = allocator.allocate(new_capacity);
        end_position = std::uninitialized_copy(begin, end, dynamic_array);
        capacity_limit = end_position;
    }

    // Non-member swap function
    template<typename T>
    void swap(Vector<T>& left, Vector<T>& right)
    {
        left.swap(right);
    }
}

Answer 1

Good effort. Still, there are many points even without going into allocator-support:

1. You are missing a very important ctor (and the corresponding deduction guide):

   template <class InputIt, SFINAE_here>
   vector(InputIt first, InputIt last);
   

   Not only is it very useful in its own right, but copy-ctor and initializer_list-ctor can be trivially implemented in terms of it.

2. You are missing .assign(). The version using an iterator-range would be the preferred building-block for construction from an iterator-range which has to be counted for getting the size.

3. You are missing assignment from initializer_list, .insert(), .data(), and reverse-iterator-support.

4. Members should accept const_iterators as inputs and return iterators.

5. You can use the injected class-name (Vector) instead of specifying the template-parameters (Vector<T>). As a bonus, that is future-proof in case you later decide to add the allocator-support.

6. std::allocator<T> is a trivial empty class. As such, any space it uses is wasted. Either use empty base optimization or just create it on-demand.

7. You are missing comparison operators.

8. Using in-class-initializers allows you to simplify your ctors. The default ctor can then even be made trivial by = default;-ing it in-class.

9. Vector<T>::Vector(size_type initial_size, const T& value) is unsafe. If an exception gets thrown when allocating, all pointer-members are still indeterminate on entrance to the dtor. If one gets thrown later, all but .dynamic_array will be indeterminate, with equally bad results.

10. Vector<T>::Vector(size_type initial_size) creates an ephemeral T and then copy-constructs all members using the previous ctor. While that works for many types, for some it is silently wrong, inefficient, or won't even compile.

11. Don't pessimize the common case by checking for self-assignment. Simply swap everything.

12. void Vector<T>::resize(size_type new_size, const T& value) really should go for just enough if it has to reallocate.

13. Point 10 also applies to void Vector<T>::resize(size_type new_size).

14. .insert(), .push_back(), and .resize() from a const& must work right even if passed an element of the container!

15. .erase(Iter, Iter) should return the passed iterator if the range is empty, not anything else.

16. std::uninitialized_move() was introduced in C++17, no need for std::uninitialized_copy() + move-iterators.

17. There is a good reason to avoid doubling capacity on reallocation: If you stay below that, re-use of returned memory becomes possible.

18. Non-member swap() should also be nowxcept.