YAVI (Yet another vector implementation)

Question

I am a C# game developer currently learning C++. I am trying to implement some simplified STL containers. Here is my implementation of vector, which does not have the allocator (because std::allocator is to Allocation what std::vector is to Vexation).

My objective is to understand the mechanics how the vector works behind the scenes as well as practice modern C++ techniques.

I have also published code under GitHub. Here is the link.

Thank you in advance for taking the time to read my code.

#pragma once

#include <algorithm>
#include <type_traits>

template<typename T>
class Vector
{
public:
    typedef                T* iterator;
    typedef const          T* const_iterator;

    typedef                T& reference;
    typedef const          T& const_reference;

    typedef                T* pointer;
    typedef const          T* const_pointer;

public:
    Vector();
    explicit Vector(const size_t size);
    Vector(const Vector<T>& other);
    Vector(Vector<T>&& other) noexcept (std::is_nothrow_move_constructible_v<T>);
    ~Vector();
    Vector<T>& operator=(const Vector<T>& other);
    Vector<T>& operator=(Vector<T>&& other) noexcept(std::is_nothrow_move_assignable_v<T>);

public:
    template<class... Args>
    reference emplace_back(Args&& ... args);

    void push_back(const T& element);
    void push_back(T&& element);

    iterator insert(iterator pos, const T& value);
    iterator insert(iterator pos, T&& value);

    iterator erase(iterator pos);
    const_iterator erase(const_iterator pos);
    iterator erase(iterator pos, iterator last);

    reference operator[](const size_t n) noexcept;
    const_reference operator[](const size_t n) const noexcept;

    reference at(const size_t n);
    const_reference at(const size_t n) const;

public:
    bool validate() const noexcept;
    bool empty() const noexcept;
    size_t size() const noexcept;
    size_t capacity() const noexcept;
    void reserve(const size_t newCapacity);

public:
    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;

    reference                  front();
    const_reference            front() const;

    reference                  back();
    const_reference            back() const;

    pointer                    data() noexcept;
    const_pointer              data() const noexcept;

private:
    void cleanup();
    void reallocate(const size_t desiredCapacity);
    void resize();
    void swap(Vector<T>& other) noexcept;
    void memcopy_trivially(T* src, T* dest, const size_t size);
    template<class... Args>
    void emplace_back_internal(Args&& ... element);
    template<class... U>
    void emplace_internal(iterator pos, U&& ... value);

private:
    size_t _size;
    size_t _capacity;
    T* _container;
};

template<typename T>
Vector<T>::Vector()
    :
    _size(0),
    _capacity(0),
    _container(nullptr)
{
}

template<typename T>
Vector<T>::Vector(const size_t size)
    :
    _size(size),
    _capacity(size),
    _container(static_cast<T*>(_aligned_malloc(sizeof(T)* size, alignof(T))))
{
    try
    {
        for (size_t i = 0; i < size; i += 1)
        {
            new (_container + i) T();
        }
    }
    catch (...)
    {
        cleanup();
        throw;
    }
}

template<typename T>
Vector<T>::Vector(const Vector<T>& other)
    :
    _size(0),
    _capacity(other._size),
    _container(static_cast<T*>(_aligned_malloc(sizeof(T)* other._size, alignof(T))))
{
    if constexpr (std::is_trivially_copyable_v<T>)
    {
        memcopy_trivially(_container, other._container, other._size);
    }
    else
    {
        try
        {
            for (_size = 0; _size < other._size; _size += 1)
            {
                emplace_back_internal(std::forward<T>(other._container[_size]));
            }
        }
        catch (...)
        {
            cleanup();
            throw;
        }
    }
}

template<typename T>
Vector<T>::Vector(Vector<T>&& other) noexcept (std::is_nothrow_move_constructible_v<T>)
    :
    _size(other._size),
    _capacity(other._capacity),
    _container(other._container)
{
    other._size = 0;
    other._container = nullptr;
}

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

template<typename T>
Vector<T>& Vector<T>::operator=(const Vector<T>& other)
{
    if (&other != this)
    {
        Vector<T> tmp(other);
        tmp.swap(*this);
    }
    return *this;
}

template<typename T>
Vector<T>& Vector<T>::operator=(Vector<T>&& other) noexcept(std::is_nothrow_move_assignable_v<T>)
{
    if (&other != this)
    {
        other.swap(*this);
    }
    return *this;
}

template<typename T>
void Vector<T>::push_back(const T& element)
{
    if (_size == _capacity)
    {
        resize();
    }

    emplace_back_internal(element);
    _size += 1;
}

template<typename T>
void Vector<T>::push_back(T&& element)
{
    if (_size == _capacity)
    {
        resize();
    }

    emplace_back_internal(std::move(element));
    _size += 1;
}

template<typename T>
typename Vector<T>::iterator
Vector<T>::insert(iterator pos, const T& value)
{
    emplace_internal(pos, value);

    _size += 1;

    return pos;
}

template<typename T>
typename Vector<T>::iterator
Vector<T>::insert(iterator pos, T&& value)
{
    emplace_internal(pos, std::move(value));

    _size += 1;

    return pos;
}

template<typename T>
typename Vector<T>::iterator
Vector<T>::erase(iterator position)
{
    if (position < begin() || position >= end())
    {
        throw std::out_of_range("Vector::erase -- out of range");
    }

    std::move(position + 1, end(), position);

    back().~T();
    _size -= 1;

    return position;
}

template<typename T>
typename Vector<T>::const_iterator
Vector<T>::erase(const_iterator position)
{
    if (position < begin() || position >= end())
    {
        throw std::out_of_range("Vector::erase -- out of range");
    }

    auto destPositon = const_cast<iterator>(position);

    return erase(destPositon);
}

template<typename T>
typename Vector<T>::iterator
Vector<T>::erase(iterator first, iterator last)
{
    if (first > last || first < begin() || first > end() || last < begin() || last > end())
    {
        throw std::out_of_range("Vector::erase(first, last) -- out of range");
    }

    if (first == last)
    {
        return begin();
    }

    size_t elementsToRemoveCnt = std::distance(first, last);

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

    std::destroy(position, end());

    _size -= elementsToRemoveCnt;

    return first;
}

template<typename T>
template<class... Args>
inline typename Vector<T>::reference
Vector<T>::emplace_back(Args&& ... args)
{
    if (_size == _capacity)
    {
        resize();
    }

    emplace_back_internal(std::move(args)...);
    _size += 1;

    return back();
}

template<typename T>
void Vector<T>::cleanup()
{
    if constexpr (!std::is_trivially_destructible_v<T>)
    {
        std::destroy(begin(), end());
    }

    _aligned_free(_container);
}

template<typename T>
std::enable_if_t<std::is_nothrow_move_constructible_v<T>> uninitialized_move_or_copy(T* first, T* last, T* dest)
{
    std::uninitialized_move(first, last, dest);
}

template<typename T>
std::enable_if_t<std::is_copy_constructible_v<T> && !std::is_nothrow_move_constructible_v<T>> uninitialized_move_or_copy(T* first, T* last, T* dest)
{
    try
    {
        std::uninitialized_copy(first, last, dest);
    }
    catch (...)
    {
        _aligned_free(dest);
        throw;
    }
}

template<typename T>
inline void Vector<T>::reallocate(const size_t desiredCapacity)
{
    _capacity = desiredCapacity;

    if (void* try_alloc_mem = _aligned_malloc(sizeof(T) * _capacity, alignof(T)))
    {
        try
        {
            auto alloced_mem = static_cast<T*>(try_alloc_mem);

            if constexpr (std::is_trivially_copyable_v<T>)
            {
                memcopy_trivially(alloced_mem, _container, _size);
            }
            else
            {
                uninitialized_move_or_copy<T>(begin(), end(), alloced_mem);
            }

            cleanup();

            _container = alloced_mem;
        }
        catch (...)
        {
            _aligned_free(try_alloc_mem);
            throw;
        }
    }
    else
    {
        throw std::bad_alloc();
    }
}

template<typename T>
void Vector<T>::resize()
{
    reallocate(std::max(static_cast<size_t>(2), _capacity * 2));
}

template<typename T>
inline void Vector<T>::swap(Vector<T>& other) noexcept
{
    std::swap(_size, other._size);
    std::swap(_capacity, other._capacity);
    std::swap(_container, other._container);
}

template<typename T>
void Vector<T>::memcopy_trivially(T* dest, T* src, const size_t size)
{
    std::memcpy(dest, src, size * sizeof(T));
    _size = size;
}

template<typename T>
template<class... U>
void Vector<T>::emplace_internal(iterator pos, U&& ... value)
{
    if (pos < begin() || pos > end())
    {
        throw std::out_of_range("Vector::insert -- out of range");
    }

    if (pos == end())
    {
        if (_size == _capacity)
        {
            resize();
        }

        emplace_back_internal(value...);

        return;
    }

    const size_t positionIndex = std::distance(begin(), pos);

    if (_size == _capacity)
    {
        resize();
    }

    emplace_back_internal(back());

    if constexpr (std::is_nothrow_move_assignable_v<T>)
    {
        std::move_backward(begin() + positionIndex, end() - 1, end());
    }
    else
    {
        Vector<T> tmp(*this);
        try
        {
            std::copy_backward(begin() + positionIndex, end() - 1, end()); // does mempcy for trivial objects
        }
        catch (...)
        {
            cleanup();
            swap(tmp);
            throw;
        }
    }

    new(begin() + positionIndex) T(std::forward<U>(value)...);
}

template<typename T>
template<class... Args>
inline void Vector<T>::emplace_back_internal(Args&& ... element)
{
    new(_container + _size) T(std::forward<Args>(element)...);
}

template<typename T>
inline bool operator==(const Vector<T>& a, const Vector<T>& b)
{
    return ((a.size() == b.size()) && std::equal(a.begin(), a.end(), b.begin()));
}

template<typename T>
typename Vector<T>::reference
Vector<T>::operator[](const size_t index) noexcept
{
    return *(begin() + index);
}

template<typename T>
typename Vector<T>::const_reference
Vector<T>::operator[](const size_t index) const noexcept
{
    return *(begin() + index);
}

template<typename T>
typename Vector<T>::reference
Vector<T>::at(const size_t index)
{
    if (index >= size())
    {
        throw std::out_of_range("Vector::at -- out of range");
    }

    return _container[index];
}

template<typename T>
typename Vector<T>::const_reference
Vector<T>::at(const size_t index) const
{
    if (index >= size())
    {
        throw std::out_of_range("Vector::at -- out of range");
    }

    return _container[index];
}

template<typename T>
inline bool Vector<T>::validate() const noexcept
{
    return (_capacity >= _size);
}

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

template<typename T>
inline size_t Vector<T>::size() const noexcept
{
    return _size;
}

template<typename T>
inline size_t Vector<T>::capacity() const noexcept
{
    return _capacity;
}

template<typename T>
inline void Vector<T>::reserve(const size_t newCapacity)
{
    if (newCapacity <= _capacity)
    {
        return;
    }

    if (!empty())
    {
        reallocate(newCapacity);
    }
    else if (empty() && _capacity > 0)
    {
        _aligned_free(_container);

        _container = static_cast<T*>(_aligned_malloc(sizeof(T) * newCapacity, alignof(T)));
    }
    else if (empty() && _capacity == 0)
    {
        _container = static_cast<T*>(_aligned_malloc(sizeof(T) * newCapacity, alignof(T)));
    }
    else
    {
        // ?
        throw;
    }

    _capacity = newCapacity;
}

template<typename T>
inline typename Vector<T>::iterator
Vector<T>::begin() noexcept
{
    return _container;
}

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

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

template<typename T>
inline typename Vector<T>::iterator
Vector<T>::end() noexcept
{
    return _container + _size;
}

template<typename T>
inline typename Vector<T>::const_iterator
Vector<T>::end() const noexcept
{
    return _container + _size;
}

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

template<typename T>
inline typename Vector<T>::reference
Vector<T>::front()
{
    return const_cast<reference>(std::as_const(*this).front());
}

template<typename T>
inline typename Vector<T>::const_reference
Vector<T>::front() const
{
    if (empty())
    {
        throw std::range_error("vector::front -- empty vector");
    }

    return *begin();
}

template<typename T>
inline typename Vector<T>::reference
Vector<T>::back()
{
    return const_cast<reference>(std::as_const(*this).back());
}

template<typename T>
inline typename Vector<T>::const_reference
Vector<T>::back() const
{
    if (empty())
    {
        throw std::range_error("vector::back -- empty vector");
    }

    return *std::prev(end());
}

template<typename T>
inline typename Vector<T>::const_pointer
Vector<T>::data() const noexcept
{
    return _container;
}

template<typename T>
inline typename Vector<T>::pointer
Vector<T>::data() noexcept
{
    return _container;
}

L. F. · Accepted Answer · 2019-09-11 09:52:52Z

As a learner, I think you have done a great job. Here's some suggestions:

General

Don't use multiple public: labels. It seems your intent is to split the declarations into groups, but that can be achieved better with // iterator, // element access, etc.
Some member types are missing: size_type, difference_type, value_type.
Reverse iterator support is missing.
Try to avoid nonstandard functions like _aligned_malloc. Use portable features — ::operator new, for example. It would be beneficial for you to wrap the allocation and deallocation into functions, so you can have an easier time transitioning when you add allocator support in the future.

Constructors, assignment operators, and the destructor

Instead of writing the default constructor, it may be better to use in-class member initializers to ensure that the data members aren't left uninitialized accidentally. And it can (and should) be made noexcept:
```
Vector() noexcept = default;
```
(Note: = default default-initializes the data members by default, which means data members of type, say, int, will be left uninitialized. There's no problem if you use in-class member initializes as I said above.)
size_t should be std::size_t or (properly defined) size_type. It's not common practice in C++ to make parameters const — at least not in the declaration. So instead of
```
explicit Vector(const size_t size);
```
go with
```
explicit Vector(size_type count);
```
(you may noticed that I used count instead of size to avoid name shadowing.)
There's the (count, value) constructor and the (iterator, iterator) constructor. Where are they? :) And the std::initializer_list constructor.
The move constructor and assignment operator should be unconditionally noexcept because they don't actually move elements.
This is usually phrased as reinterpret_cast:
```
_container(static_cast<T*>(_aligned_malloc(sizeof(T)* size, alignof(T))))
```
and by the way, I like to put nontrivial code (like memory allocation) in the function body to avoid order dependency problems, but that is purely a matter of taste.

Don't reimplement the library:

try
{
    for (size_t i = 0; i < size; i += 1)
    {
        new (_container + i) T();
    }
}
catch (...)
{
    cleanup();
    throw;
}

can be written as

std::uninitialized_value_construct_n(_container, size);

which is simple to understand and much less error prone. The try block can be removed because the standard library takes care of exception safety.

Similarly,

if constexpr (std::is_trivially_copyable_v<T>)
{
    memcopy_trivially(_container, other._container, other._size);
}
else
{
    try
    {
        for (_size = 0; _size < other._size; _size += 1)
        {
            emplace_back_internal(std::forward<T>(other._container[_size]));
        }
    }
    catch (...)
    {
        cleanup();
        throw;
    }
}

can be rewritten as

std::uninitialized_copy_n(other.begin(), other.end(), _container);

the trivial copy optimization should be handled by any decent implementation, so you don't need to worry about it yourself—:)

Use the copy and swap idiom. This saves you a lot of boilerplate. The move constructor can be simplified:
```
template <typename T>
Vector<T>::Vector(Vector&& other) noexcept
    :Vector{}
{
    swap(other);
}
```
The copy and move assignment operators can be unified:
```
template <typename T>
auto Vector<T>::operator=(Vector other) noexcept -> Vector&
{
    swap(other);
    return *this;
}
```
(the effect of the noexcept here is that move assignment is noexcept while copy assignment is not. Think of it.)
std::initializer_list assignment operator :)

This function

template<typename T>
void Vector<T>::cleanup()
{
    if constexpr (!std::is_trivially_destructible_v<T>)
    {
        std::destroy(begin(), end());
    }

    _aligned_free(_container);
}

is a standard facility — it should be named clear, made public, and made noexcept. (Did you just "accidentally" implement a feature?)

Any decent implementation should implement the trivial optimization for std::destroy. Don't do it yourself. If your implementation doesn't, you should complain to them ;) In general, if you are calling a library function, you can be 95% sure that all (relatively) trivial optimizations are implemented.

And you can delegate to erase if you want.

The `assign` functions

Oops, they are missing.

The member access functions

operator[] should not be made noexcept. noexcept doesn't just mean "no exceptions" — it actually means "this function won't fail".

Also, you probably need std::launder at some point.

Capacity

validate is not a standard function and thus should preferably be private.

The logic of the reserve function can be simplified. I am pretty sure you can avoids the if else if else if else chain by refactoring the code somehow. And

else
{
    // ?
    throw;
}

That's dead code, isn't it? The comment that consists of a single question mark confuses me even more.

Oh, and shrink_to_fit.

Thank you so much for your review. I use validate just for testing purposes. the ` else { // ? throw;}` mess was there just to make sure I didn't get to that stage. I should remove it. Thanks for pointing out that some of the code can be replaced with STD methods. I am trying to use as much STD as possible. — Marius T
– Marius T, Commented Sep 10, 2019 at 12:49
@MariusT You are welcome, good job. You can just remove the final else clause and replace the last else if with else. — L. F.
– L. F., Commented Sep 10, 2019 at 13:40
For the reserve I replaced everything with an if/else and in the else I _aligned_free and _algined_malloc() . much easier to read and it's the same functionality — Marius T
– Marius T, Commented Sep 10, 2019 at 14:05
Making the default constructor = default; is probably not a good idea. As the default initialization will not initialize the members (as they are POD types with no initializer). — Loki Astari
– Loki Astari, Commented Sep 10, 2019 at 19:06
@MartinYork I said "use in-class member initializers" before giving the = default code. Anyway, I'll clarify — L. F.
– L. F., Commented Sep 11, 2019 at 9:51

Community · Accepted Answer · 2020-06-10 13:24:26Z

Issue with Default construction

try
{
    for (size_t i = 0; i < size; i += 1)
    {
        new (_container + i) T();
    }
}
catch (...)
{
    cleanup();  // This will call the destructor on all members of
                // _container. But if you throw an exception here
                // then not all members will have been constructed.
                //
                // A simple fix.
                // Initializer list sets "_size" to zero 
                // Initializer list sets "_capacity" to size.
                // Then in the loop above simple go
                // for (;_size < _capacity; ++size)
    throw;
}

Weird Look with Copy Construction

The copy constructor uses:

emplace_back_internal(std::forward<T>(other._container[_size]));

This looks like a move operation (std::forward()). The thing that is saving you is that other is const so it does not bind to the rvalue reference. But this makes it look really weird.

I would simply expect:

emplace_back_internal(other._container[_size]);

Issue with Move construction

other._size = 0;
other._container = nullptr;

What about the other capacity?
Is the capacity also now zero?

I normally write this as a swap operation.

Vector<T>::Vector(Vector<T>&& other) noexcept (std::is_nothrow_move_constructible_v<T>)
    :
    _size(0),
    _capacity(0),
    _container(nullptr)
{
    other.swap(*this);
}

Copy Assignment is old style

Vector<T>& Vector<T>::operator=(const Vector<T>& other)
{
    if (&other != this)
    {
        Vector<T> tmp(other);
        tmp.swap(*this);
    }
    return *this;
}

You are pessimizing the normal operation by checking for assignment to self. Your code works with assignment to self. Yes it will be much more expensive for assignment to self BUT it is safe and practically never happens in real code. So you are saving time on an operation that basically never happens at the extra cost for an operation that happens all the time (you risk branch predication failure here) plus the cost of actually doing the branch test.

Vector<T>& Vector<T>::operator=(const Vector<T>& other)
{
    Vector<T> tmp(other);
    tmp.swap(*this);
    return *this;
}

Same with your move operation.

Style Oddities.

Increment

You keep using +=1

 _size += 1

Where I would expect:

 ++_size;

Thank you for the review! Issue with Default construction I actually do that exact thing in my copy constructor but I missed doing it in my explicit constructor. Issue with Move construction: Do I have to care that much about the other in the move constructor? Standard states that I have to leave other in a valid, yet unspecified state as nobody is allowed to touch it. I just make sure the destructor is not called and I think I should be done. I avoid swap because it creates unnecessary TMP objects. P.S: I am yet to find my incrementation style. I know it's weird :( — Marius T
– Marius T, Commented Sep 9, 2019 at 19:28
P.P.S: I just now realized you're the Loki Astari. Just wanted to say that your vector blog post was a great source of information while implementing my own version. Thanks again! — Marius T
– Marius T, Commented Sep 9, 2019 at 19:38
Valid yet unspecified. This means that functions that have no preconditions will work. Things like push_back() has no pre-conditions (as the vector should re-size if it is too small). So if I call push_back() after the vector has been moved away I still expect it to work correctly as it is a valid state (though I could not make any assumptions about what was inside the vector it could be full or empty that's unspecified). But in your case a call to push_back() will result in a crash (as you use the nullptr as part of an emplace back). — Loki Astari
– Loki Astari, Commented Sep 9, 2019 at 22:32
If you set the capacity to zero (as well as the size) then your vector will correctly allocate the needed space and continue to work. — Loki Astari
– Loki Astari, Commented Sep 9, 2019 at 22:33

Stack Exchange Network

YAVI (Yet another vector implementation)

2 Answers 2

General

Constructors, assignment operators, and the destructor

The `assign` functions

The member access functions

Capacity

Issue with Default construction

Weird Look with Copy Construction

Issue with Move construction

Copy Assignment is old style

Style Oddities.

Increment

You must log in to answer this question.

Linked

Hot Network Questions

YAVI (Yet another vector implementation)

2 Answers 2

General

Constructors, assignment operators, and the destructor

The assign functions

The member access functions

Capacity

Issue with Default construction

Weird Look with Copy Construction

Issue with Move construction

Copy Assignment is old style

Style Oddities.

Increment

You must log in to answer this question.

Linked

Related

Hot Network Questions

The `assign` functions