10
\$\begingroup\$

I am an undergraduate currently learning data structures and C++. I am trying to implement some simplified STL containers. Here is my implementation of vector, which does not have the allocator.

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: https://github.com/TohnoYukine/DataStructures

#pragma once
#include <stdexcept>

#define MAX_VECTOR_SIZE 1073741824U     //1GB

namespace DataStructures
{
template<typename T>
class Vector
{
public:
    using value_type        = T;
    using reference         = T&;
    using const_reference   = const T&;
    using pointer           = T*;
    using const_pointer     = const T*;
    using difference_type   = ptrdiff_t;
    using size_type         = size_t;

    using iterator          = T*;
    using const_iterator    = const T*;
    using reverse_iterator          = std::reverse_iterator<iterator>;
    using const_reverse_iterator    = std::reverse_iterator<const_iterator>;

    //Constructor, Destructor and Assignment
    Vector() noexcept;
    explicit Vector(size_type n);
    Vector(size_type n, const T& val);
    Vector(const_iterator first, const_iterator last);

    template<typename InputIterator, typename = typename std::enable_if_t<std::_Is_iterator<InputIterator>::value>>
    Vector(InputIterator first, InputIterator last);

    Vector(std::initializer_list<T> init);
    Vector(const Vector& origin);
    Vector(Vector<T> && origin) noexcept;
    ~Vector();
    Vector<T>& operator=(const Vector<T>& origin);  //Assign will modify reserved_size to origin.reserved_size, which behaves differently from STL vector.
    Vector<T>& operator=(Vector<T>&& origin);
    Vector<T>& operator=(std::initializer_list<T> init);
    void assign(size_type n, const T& val);
    void assign(std::initializer_list<T> init);
    template<typename InputIterator, typename = typename std::enable_if_t<std::_Is_iterator<InputIterator>::value>> 
    void assign(InputIterator first, InputIterator last);

    //Element access
    reference operator[](size_type index);  //No check
    const_reference operator[](size_type index) const;
    reference at(size_type index);          //Check and throw out_of_range exception
    const_reference at(size_type index) const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;
    T* data() noexcept;
    const T* data() const noexcept;

    //Iterators
    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;
    reverse_iterator rbegin() noexcept;
    const_reverse_iterator rbegin() const noexcept;
    const_reverse_iterator crbegin() const noexcept;
    reverse_iterator rend() noexcept;
    const_reverse_iterator rend() const noexcept;
    const_reverse_iterator crend() const noexcept;

    //Capacity
    bool empty() const noexcept;
    size_type size() const noexcept;
    size_type max_size() const noexcept;
    void reserve(size_type n);
    size_type capacity() const noexcept;
    void shrink_to_fit();

    //Modifiers
    void clear() noexcept;
    iterator insert(const_iterator pos, const T& val);
    iterator insert(const_iterator pos, T&& val);
    iterator insert(const_iterator pos, size_type, T& val);
    iterator insert(const_iterator pos, std::initializer_list<T> init);
    template<typename InputIterator> iterator insert(const_iterator pos, InputIterator first, InputIterator last);  //last not included
    template <typename ... Args> iterator emplace(const_iterator pos, Args&& ... args);
    iterator erase(const_iterator pos);
    iterator erase(const_iterator first, const_iterator last);  //last not included
    void push_back(const T& val);
    void push_back(T&& rval);
    template <typename ... Args> reference emplace_back(Args&& ... args);
    void pop_back();
    void resize(size_type n);               //Fill with default initialized element
    void resize(size_type n, const T&val);  //Fill with val
    void swap(Vector<T>& other);

    //Non-Member Functions
    template<typename T> friend bool operator==(const Vector<T>& lhs, const Vector<T>& rhs);
    template<typename T> friend bool operator!=(const Vector<T>& lhs, const Vector<T>& rhs);
    template<typename T> friend bool operator<(const Vector<T>& lhs, const Vector<T>& rhs);
    template<typename T> friend bool operator<=(const Vector<T>& lhs, const Vector<T>& rhs);
    template<typename T> friend bool operator>(const Vector<T>& lhs, const Vector<T>& rhs);
    template<typename T> friend bool operator>=(const Vector<T>& lhs, const Vector<T>& rhs);
    template<typename T> friend void swap(Vector<T>& lhs, Vector<T>& rhs);

private:
    size_type reserved_size = 4;
    size_type vector_size = 0;
    T* storage = nullptr;
    inline void reallocate();
    inline void move_storage(T* dest, T* from, size_type n);
};

/* Dividing Line (っ °Д °;)っ (っ °Д °;)っ (っ °Д °;)っ  */

template<typename T>
inline Vector<T>::Vector() noexcept
{
    storage = new T[reserved_size];
}

template<typename T>
inline Vector<T>::Vector(size_type n)
{
    vector_size = n;
    reserved_size = n + n / 2 + 1;
    storage = new T[reserved_size];
    for (size_type i = 0; i < n; i++)
        storage[i] = T();   //Is this necessary?
}

template<typename T>
inline Vector<T>::Vector(size_type n, const T & val)
{
    vector_size = n;
    reserved_size = n + n / 2 + 1;
    storage = new T[reserved_size];
    for (size_type i = 0; i < n; i++)
        storage[i] = val;
}

template<typename T>
inline Vector<T>::Vector(const_iterator first, const_iterator last)
{
    size_type count = last - first;
    vector_size = count;
    reserved_size = count + count / 2 + 1;
    storage = new T[reserved_size];
    for (size_type i = 0; i < count; i++)
        storage[i] = *first++;
}

template<typename T>
inline Vector<T>::Vector(std::initializer_list<T> init)
{
    size_type count = init.size();
    vector_size = 0;
    reserved_size = count + count / 2 + 1;
    storage = new T[reserved_size];
    for (const T& elem : init)          //Why do I have to use const T& instead of T&
        storage[vector_size++] = elem;  //Can I use std::move?
}

template<typename T>
inline Vector<T>::Vector(const Vector &origin)
{
    vector_size = origin.vector_size;
    reserved_size = origin.reserved_size;
    storage = new T[reserved_size];
    for (size_t i = 0; i < vector_size; i++)
        storage[i] = origin.storage[i];
}

template<typename T>
inline Vector<T>::Vector(Vector<T>&& origin) noexcept
{
    swap(origin);
}

template<typename T>
inline Vector<T>::~Vector()
{
    if (storage != nullptr)
        delete[] storage;
}

template<typename T>
inline Vector<T>& Vector<T>::operator=(const Vector<T>& origin)
{
    swap(Vector<T>(origin));
    return *this;
}

template<typename T>
inline Vector<T>& Vector<T>::operator=(Vector<T>&& origin)
{
    swap(origin);
    return *this;
}

template<typename T>
inline Vector<T>& Vector<T>::operator=(std::initializer_list<T> init)
{
    swap(Vector<T>(init));
    return *this;
}

template<typename T>
inline void Vector<T>::assign(size_type n, const T & val)
{
    swap(Vector<T>(n, val));
}

template<typename T>
inline void Vector<T>::assign(std::initializer_list<T> init)
{
    swap(Vector<T>(init));
}

template<typename T>
template<typename InputIterator, typename SFINAE_MAGIC>
inline Vector<T>::Vector(InputIterator first, InputIterator last)
{
    size_type count = 0;
    for (InputIterator curr = first; curr != last; ++curr) ++count;
    vector_size = count;
    reserved_size = count + count / 2 + 1;
    storage = new T[reserved_size];
    for (size_type i = 0; i < count; i++)
        storage[i] = *first++;
}

template<typename T>
template<typename InputIterator, typename SFINAE_MAGIC>
inline void Vector<T>::assign(InputIterator first, InputIterator last)
{
    swap(Vector<T>(first, last));
}

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

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

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

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

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

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

template<typename T>
inline typename Vector<T>::reverse_iterator Vector<T>::rbegin() noexcept
{
    return reverse_iterator(storage + vector_size);
}

template<typename T>
inline typename Vector<T>::const_reverse_iterator Vector<T>::rbegin() const noexcept
{
    return reverse_iterator(storage + vector_size);
}

template<typename T>
inline typename Vector<T>::const_reverse_iterator Vector<T>::crbegin() const noexcept
{
    return rbegin();
}

template<typename T>
inline typename Vector<T>::reverse_iterator Vector<T>::rend() noexcept
{
    return reverse_iterator(storage);
}

template<typename T>
inline typename Vector<T>::const_reverse_iterator Vector<T>::rend() const noexcept
{
    return reverse_iterator(storage);
}

template<typename T>
inline typename Vector<T>::const_reverse_iterator Vector<T>::crend() const noexcept
{
    return rend();
}

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

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

template<typename T>
inline typename Vector<T>::size_type Vector<T>::max_size() const noexcept
{
    return MAX_VECTOR_SIZE;
}

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

template<typename T>
inline void Vector<T>::resize(size_type n)
{
    if (n > vector_size)
    {
        if (n > reserved_size)
        {
            reserved_size = n;
            reallocate();
        }
    }
    else
    {
        for (size_t i = n; i < vector_size; i++)
            storage[i].~T();
    }
    vector_size = n;
}

template<typename T>
inline void Vector<T>::resize(size_type n, const T& val)
{
    if (n > vector_size)
    {
        if (n > reserved_size)
        {
            reserved_size = n + n / 2 + 1;
            reallocate();
        }
        for (size_t i = vector_size; i < n; i++)
            storage[i] = val;
    }
    else
    {
        for (size_t i = n; i < vector_size; i++)
            storage[i].~T();
    }
    vector_size = n;
}

template<typename T>
inline void Vector<T>::reserve(size_type n)
{
    if (n > reserved_size)
    {
        reserved_size = n;
        reallocate();
    }
}

template<typename T>
inline void Vector<T>::shrink_to_fit()
{
    reserved_size = vector_size;
    reallocate();
}

template<typename T>
inline typename Vector<T>::reference Vector<T>::operator[](size_type index)
{
    return storage[index];
}

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

template<typename T>
inline typename Vector<T>::reference Vector<T>::at(size_type pos)
{
    if (pos < vector_size)
        return storage[pos];
    throw std::out_of_range{ "Accessed position is out of range!" };
}

template<typename T>
inline typename Vector<T>::const_reference Vector<T>::at(size_type pos) const
{
    if (pos < vector_size)
        return storage[pos];
    throw std::out_of_range{ "Accessed position is out of range!" };
}

template<typename T>
inline typename Vector<T>::reference Vector<T>::front()
{
    return storage[0];
}

template<typename T>
inline typename Vector<T>::const_reference Vector<T>::front() const
{
    return storage[0];
}

template<typename T>
inline typename Vector<T>::reference Vector<T>::back()
{
    return storage[vector_size - 1];
}

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

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

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

template<typename T>
template<typename ...Args>
inline typename Vector<T>::reference Vector<T>::emplace_back(Args && ...args)
{
    if (vector_size == reserved_size)
    {
        reserved_size += reserved_size / 2 + 1;
        reallocate();
    }
    return storage[vector_size++] = std::move(T(std::forward<Args>(args) ...));
}

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

template<typename T>
inline void Vector<T>::push_back(T &&rval)
{
    emplace_back(std::forward<T>(rval));    //Is this okay?
}

template<typename T>
inline void Vector<T>::pop_back()
{
    storage[--vector_size].~T();
}

template<typename T>
template<typename ...Args>
inline typename Vector<T>::iterator Vector<T>::emplace(const_iterator iter, Args && ...args)
{
    size_type pos = iter - storage;
    iterator _iter = &storage[pos]; //Check for range validity
    if (vector_size == reserved_size)
    {
        reserved_size += reserved_size / 2 + 1;
        reallocate();
    }
    _iter = &storage[pos];
    //memmove(_iter + 1, _iter, (vector_size - (_iter - storage)) * sizeof(T));
    move_storage(_iter + 1, _iter, vector_size - (_iter - storage));
    ++vector_size;
    *_iter = std::move(T(std::forward<Args>(args) ...));
    return _iter;
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator iter, const T& lval)
{
    return emplace(iter, lval);
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator iter, T&& rval)
{
    return emplace(iter, std::forward<T>(rval));
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator iter, size_type n, T &val)
{
    size_type pos = iter - storage;
    iterator _iter = &storage[pos];
    if (n == 0) return _iter;
    if (vector_size + n > reserved_size)
    {
        reserved_size += n;
        reallocate();
    }
    _iter = &storage[pos];
    //memmove(_iter + n, _iter, (vector_size - (_iter - storage)) * sizeof(T));
    move_storage(_iter + n, _iter, vector_size - (_iter - storage));
    vector_size += n;
    for (size_t i = 0; i < n; i++)
        *iter++ = val;
    return &storage[pos];
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator iter, std::initializer_list<T> init)
{
    size_type pos = iter - storage;
    iterator _iter = &storage[pos];
    size_type n = init.size();
    if (n == 0) return _iter;
    if (vector_size + n > reserved_size)
    {
        reserved_size += n;
        reallocate();
    }
    _iter = &storage[pos];
    //memmove(_iter + n, _iter, (vector_size - (_iter - storage)) * sizeof(T));
    move_storage(_iter + n, _iter, vector_size - (_iter - storage));
    vector_size += n;
    for (const T& elem : init)
        *_iter++ = elem;
    return &storage[pos];
}

template<typename T>
template<typename InputIterator>
inline typename Vector<T>::iterator Vector<T>::insert(const_iterator iter, InputIterator first, InputIterator last)
{
    size_type pos = iter - storage;
    iterator _iter = &storage[pos];

    size_type n = 0;
    for (InputIterator curr = first; curr != last; ++curr) ++n;

    if (n == 0) return _iter;
    if (vector_size + n > reserved_size)
    {
        reserved_size += n;
        reallocate();
    }
    _iter = &storage[pos];  //Must refresh _iter after reallocation
    //memmove(_iter + n, _iter, (vector_size - (_iter - storage)) * sizeof(T));
    move_storage(_iter + n, _iter, vector_size - (_iter - storage));
    vector_size += n;
    for (size_t i = 0; i < n; i++)
        *_iter++ = *first++;
    return &storage[pos];
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::erase(const_iterator iter)
{
    iterator _iter = &storage[iter - storage];
    _iter->~T();
    //memmove(_iter, _iter + 1, (vector_size - (_iter - storage)) * sizeof(T));
    move_storage(_iter, _iter + 1, vector_size - (_iter - storage));
    vector_size -= 1;
    return _iter;
}

template<typename T>
inline typename Vector<T>::iterator Vector<T>::erase(const_iterator first, const_iterator last)
{
    size_type n = last - first;
    iterator _iter = &storage[first - storage];
    iterator _last = _iter + n;
    if (n == 0) return _iter;
    for (size_t i = 0; i < n; i++)
        first++->~T();
    //memmove(_iter, last, (vector_size - (last - storage)) * sizeof(T));
    move_storage(_iter, _last, vector_size - (_last - storage));
    vector_size -= n;
    return _iter;
}

template<typename T>
inline void Vector<T>::swap(Vector<T>& rhs)
{
    std::swap(vector_size, rhs.vector_size);
    std::swap(reserved_size, rhs.reserved_size);
    std::swap(storage, rhs.storage);
}

template<typename T>
inline void Vector<T>::clear() noexcept
{
    vector_size = 0;
    for (size_t i = 0; i < vector_size; i++)
        storage[i].~T();
}

template<typename T>
inline bool operator==(const Vector<T>& lhs, const Vector<T>& rhs)
{
    if (lhs.vector_size != rhs.vector_size)
        return false;
    for (size_t i = 0; i < lhs.vector_size; i++)
        if (lhs.storage[i] != rhs.storage[i])
            return false;
    return true;
}

template<typename T>
inline bool operator!=(const Vector<T>& lhs, const Vector<T>& rhs)
{
    return !(lhs == rhs);
}

template<typename T>
inline bool operator<(const Vector<T>& lhs, const Vector<T>& rhs)
{
    typename Vector<T>::size_type n = (lhs.vector_size < rhs.vector_size) ? lhs.vector_size : rhs.vector_size;
    for (size_t i = 0; i < n; i++)
        if (lhs.storage[i] != rhs.storage[i])
            return lhs.storage[i] < rhs.storage[i];
    return lhs.vector_size < rhs.vector_size;
}

template<typename T>
inline bool operator>(const Vector<T>& lhs, const Vector<T>& rhs)
{
    typename Vector<T>::size_type n = lhs.vector_size < rhs.vector_size ? lhs.vector_size : rhs.vector_size;
    for (size_t i = 0; i < n; i++)
        if (lhs.storage[i] != rhs.storage[i])
            return lhs.storage[i] > rhs.storage[i];
    return lhs.vector_size > rhs.vector_size;
}

template<typename T>
inline bool operator<=(const Vector<T>& lhs, const Vector<T>& rhs)
{
    return !(lhs > rhs);
}

template<typename T>
inline bool operator>=(const Vector<T>& lhs, const Vector<T>& rhs)
{
    return !(lhs < rhs);
}

template<typename T>
inline void swap(Vector<T>& lhs, Vector<T>& rhs)
{
    lhs.swap(rhs);
}

template<typename T>
inline void Vector<T>::reallocate()
{
    T* new_storage = new T[reserved_size];
    //memcpy(new_storage, storage, vector_size * sizeof(T));
    move_storage(new_storage, storage, vector_size);
    delete[] storage;
    storage = new_storage;
}

template<typename T>
inline void Vector<T>::move_storage(T * dest, T * from, size_type n)
{
    if (dest < from)
    {
        T *_dest = dest, *_from = from;
        for (size_t i = 0; i < n; i++)
            *_dest++ = std::move(*_from++);
    }
    else if (dest > from)
    {
        T *_dest = dest + n - 1, *_from = from + n - 1;
        for (size_t i = n; i > 0; i--)
            *_dest-- = std::move(*_from--);
    }
    else
        return;
}
}
\$\endgroup\$
22
\$\begingroup\$

Design

The main thing about a vector is not constructing its members until they are put into the container. The vector you have constructs all the members immediately which can be very expensive if your type T has an expensive constructor (or you never use any of the members).

T* storage = nullptr;

As a result you don't want to use T* as your storage type (you can but that's something we can cover later). You want to use char* and allocate enough storage for the reserved elements but not actually construct any of these elements.

When you insert values into the vector you can use Placement New to construct the objects in a particular location in memory.

void push_back(T const& item)
{
    // Up here check you have enough reserved space (cover that later).

    // Placement new.
    // Its like new but you provide the memory location that the object
    // will be constructed (so no memory is allocated) and the object of
    // type T is constructed in place at that location.
    new (reinterpret_cast<T*>(storage + size) T(item);   // exact expression here will depend on type of storage (just make it point at the correct location)

    // increment the size after you have created the object.
    ++size;
}

Code Review

Initializer list

Sure you can initialize the elements in place in the class declaration. But personally I think this makes maintenance harder. When I look at your code I have to go back and check the declaration is good to make sure all members are initialized. I prefer to put all members in the initializer list. But saying that your way is fine:

But the members that are not initialized in the class should be initialized in the initializer list.

template<typename T>
inline Vector<T>::Vector() noexcept
    : storage(new T[reserved_size])
{}

Its not that it matter for POD types like pointers. But it can make a difference for other types. So it is a good idea to be consistent and always use the initializer list.

template<typename T>
inline Vector<T>::Vector(size_type n)
    : vector_size(n)
    , reserved_size(n + n / 2 + 1)
    , storage(new T[reserved_size])
{
    // No this is not necessary in your implementation.
    // But if you change it to the one I describe in the design section
    // then yes it becomes necessary
    for (size_type i = 0; i < n; i++)
        storage[i] = T();
}

Always bracket sub blocks:

Yes this looks safe.

    for (size_type i = 0; i < n; i++)
        storage[i] = T();

But one day this will bite you in the butt. Not all function calls are actually function calls. Sometimes people hide macros as function look alikes. Sometimes these macros are multiple statements and not wrapped correctly this will not show up here and your code will not work as expected. So always add the braces.

    for (size_type i = 0; i < n; i++) {
        storage[i] = T();
    }

Default values

Here you are creating a set of objects of type T with the default constructor.

    for (size_type i = 0; i < n; i++) {
        storage[i] = T();
    }

Not all types have a default constructor. So this function will not work if the T can not be default constructed. This is why the std::vector has a slightly different signature for vector:

template<typename T>
inline Vector<T>::Vector(size_type n, T const& value = T{})

Then the loop will copy value into each member of the vector. If T does not have a default constructor this method will not compile but it does allow the user to provide an alternative inline.

Vector<MyObj>  data(15, MyObj{1,2,3});

This method also allows you to comprise your two size based constructors into a single method.

Iterators

Your iterator based constructor, only allows the use of iterators from other Vector objects.

template<typename T>
inline Vector<T>::Vector(const_iterator first, const_iterator last)

This is a bit constraining. Normally a container should be constructible from iterators from any type of other container (anything you want to copy into a vector).

template<typename T>
template<typename I>
inline Vector<T>::Vector<I>(I b, I e)

You should be careful subtracting iterators. Doing so does not always give you what you want (the distance between them). But there is a built in function that does just that:

    size_type count = std::distance(first, last);

Pass by const reference

Prefer to pass by const reference when you can to avoid a copy.

template<typename T>
inline Vector<T>::Vector(std::initializer_list<T> const& init)
                                                  ^^^^^^^

DRY Code

DRY stands for "Don't Repeat Yourself". If you have the same piece of code spread around your class. Then one day you find a mistake in that code you have to find all the repatitions and fix every one individually. This is both cumbersome and error prone. So prefer to do it in a single place (one function) and call this function from all the places you need to do it.

This piece of code keeps popping up:

    vector_size = <Some Value>;
    reserved_size = <Some Value: usally size + size / 2 + 1>
    storage = new T[reserved_size];
    for (<Some Type of loop>)
        Copy element into sorage.

Deleting a nullptr is not an error.

template<typename T>
inline Vector<T>::~Vector()
{
    // There is no need for this check.
    // delete works perfectly well for nullptr.
    if (storage != nullptr)
        delete[] storage;
}

Manually calling destructor

You are allowed to manually call the destructor.

    {
        for (size_t i = n; i < vector_size; i++)
            storage[i].~T();
    }

But when you do you must make sure that the destructor is never called for that object again (or you make sure it is reconstructed before the next call to the destructor).

This means you should only call the destructor on objects that have been created with placement new as these are the only objects that will not have there destructors called automatically.

In your case when the destructor is called, this wall call delete on the storage pointer, which will call the destructor for each member. These members have already been destroyed so now you have undefined behavior.

R-Values

An unnamed object is already an r-value ref.

    return storage[vector_size++] = std::move(T(std::forward<Args>(args) ...));

So there is no need to call move on it.

    return storage[vector_size++] = T(std::forward<Args>(args) ...);

using std::swap

Normally you don't fully specify std::swap. This is because not all types come from the std namespace and they may have their own optimized version of swap in their own namespace. If you specify std::swap it has to use the one in standard any you miss out on the customized swap.

template<typename T>
inline void Vector<T>::swap(Vector<T>& rhs)
{
    std::swap(vector_size, rhs.vector_size);
    std::swap(reserved_size, rhs.reserved_size);
    std::swap(storage, rhs.storage);
}

So write like this:

template<typename T>
inline void Vector<T>::swap(Vector<T>& rhs)
{
    using std::swap;
    swap(vector_size, rhs.vector_size);
    swap(reserved_size, rhs.reserved_size);
    swap(storage, rhs.storage);
}

So if the member is using a type with a specialized swap then Koenig lookup will find the specialized swap. Otherwise you have brought std::swap into the current scope and that can be used.

Check out:

Vector - Resource Management Allocation
Vector - Resource Management Copy Swap
Vector - Resize
Vector - Simple Optimizations
Vector - the Other Stuff
Memory Resizing

\$\endgroup\$
  • 1
    \$\begingroup\$ instead of using char[] as your storage class, you might want to use std::aligned_storage<sizeof(T), alignof(T)>::type \$\endgroup\$ – WorldSEnder Nov 10 '17 at 8:55
  • \$\begingroup\$ std::initializer_list never copies elements, it is meant to be passed by value. \$\endgroup\$ – Incomputable Nov 10 '17 at 10:59
  • 1
    \$\begingroup\$ @WorldSEnder char* can point at any location. Also if you ask for (dynamically allocate with new) a block larger than size T then it is automatically aligned for objects of type T. Note: if memory is aligned for objects of size 2^n then it is also aligned for objects of size 2^(n+1) and all alignment is done on 2^m boundaries. The use of std::aligned_storage is when you are allocating the memory locally (ie automatic storage duration) or inside another object (ie automatic storage duration). \$\endgroup\$ – Martin York Nov 10 '17 at 16:32
  • \$\begingroup\$ @Incomputable: What about std::initializer_list<int> data{1,2,3,4};std::vector v(data); As far as I can tell std::initializer_list has no intrinsic magic properties that make it work differently (apart from syntax helping). Its just that normal use case is highly optimized. \$\endgroup\$ – Martin York Nov 10 '17 at 16:33
  • \$\begingroup\$ @LokiAstari where I was getting at was to separate size and capacity which is, I realize now, something you have not put explicitly in your answer. Constructing objects in advance as in new T[reserved_size] is not allowed if the constructor of T has side effects. \$\endgroup\$ – WorldSEnder Nov 10 '17 at 16:52
9
\$\begingroup\$

Implementation

  • There is a lot of code duplication. Maybe introduce helper functions (in an internal namespace if you don't want to pollute the outer one)?
  • Vector::Vector() might throw even though it is marked noexcept, because new can throw if it is unable to acquire memory. Since Vector::Vector() is marked noexcept, this would crash the program.
  • Vector::Vector(size_type n) allocates more memory than needed for n elements. If I specify how many elements are (very likely) going to be in the Vector initially (because I know how many there are going to be), I'd expect it not to waste 50% more memory. (Think of it: If I know there will be 1 billion int32_t in the Vector<int32_t>, the extra reserved memory would amount to 2 GiB!).
  • Same argument for some of the other constructors with explicit or implied number of initial elements.
  • The copy assignment operator doesn't work. It tries to swap a const Vector& - which is const, i.e. not writable. This won't compile (if it were needed)!
  • Vector<T>::operator=(std::initializer_list<T> init) could probably be more efficient if it were done in-place if the current reserved_size is greater than or equal to init.size().
  • The whole for loop in Vector<T>::Vector(InputIterator first, InputIterator last) can simply be replaced by auto count = std::distance(first, last);.
  • All the end()/cend()/rbegin()/crbegin() method invoke undefined behavior if storage == nullptr.
  • MAX_VECTOR_SIZE is the maximum in name only. One can easily create a larger Vector<T> by giving a larger size in one of the constructors taking a size.
  • Vector<T>::reserve(size_type) and Vector<T>::reserve(size_type, const T&) are inconsistent regarding the allocation of new memory. The latter one reserves extra, the first one doesn't.
  • Vector<T>::front() might invoke undefined behavior if storage == nullptr, and returns an invalid result if vector_size == 0.
  • Vector<T>::back() might invoke undefined behavior if storage == nullptr or vector_size == 0.
  • Vector<T>::emplace might invoke undefined behavior if iter is not in [storage, storage + reserved_size). Also, _iter gets assigned twice, possibly with the same value.
  • Technically, it isn't legal to compare pointers that do not point into the same allocation (like it's done in Vector<T>::move_storage). You can however compare them using std::less<T*> or similar.
  • Every std::forward<T> can be replaced with std::move - since T doesn't get deduce by the method calls, it's always a rvalue reference.

Comments

  • //Is this necessary?: No. They already get construted by new[].
  • //Why do I have to use const T& instead of T&: std::initializer_list.begin() returns a const T* - which is const and cannot be assigned to a non-const reference.
  • //Can I use std::move?: You can, but it wouldn't change anything, it would still make a copy since the object is const.
  • //Check for range validity: No, this doesn't check for range validity. It might however invoke undefined behavior.
  • MAX_VECTOR_SIZE (isn't a comment, but could as well be): It doesn't restrict the size of Vector<T> in any way: It's not checked in any of the constructors or when resizing. (Also, 1 GiB seems a bit low for modern 64 bit machines).
\$\endgroup\$
5
\$\begingroup\$

Don't use new T[] or delete[]. They will call the constructor and destructors on the contained objects. In the context of vector this will lead to double construct and double destruct of the objects which is undefined behavior.

Instead use ::operator new(std::size_t) for allocation and ::operator delete(void*) for deallocation or an allocator such as std::allocator<T> with a.allocate(n) and a.deallocate(ptr, n). Those will not construct or deconstruct the objects.

This means of course that in your deconstructor you will need to destruct the objects explicitly.


On default construct don't allocate. Allocations may fail and it's not uncommon for someone to create a empty vector and move something into it later or first reserve with something larger than 4. If you eagerly allocate on default construct then you pay for stuff you won't use.


You can make use of type traits to avoid looping over the vector when you don't need to. For example if a type is std::is_trivially_moveable then you can do a memcpy instead of loop and move construct + destruct in move_storage. If the type is std::is_trivially_destructible then you don't need to call the destructor on any T at all. There are various traits you can make use of that way.

\$\endgroup\$
4
\$\begingroup\$

The code looks great to me. It's visually pleasing, well-structured, uses clear variable names. Though I am not an experienced C++ programmer.

From your GitHub repository, you should delete the ReadMe.txt files after reading them once.

Your test code needs some improvements. Currently it does run all the code (at least I hope so; I haven't checked whether the code coverage is really 100%), but if the operator[] would return something wrong, your test would not detect that. To improve the code, use a unit testing framework. I have heard of CppUnit, but I have no idea whether that is state of the art, since I don't program in C++ on a daily basis.

\$\endgroup\$
  • \$\begingroup\$ Catch library is trending now. Also people combine it with some logging framework, which I forgot the name of. \$\endgroup\$ – Incomputable Nov 10 '17 at 7:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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