C++ Vector The basics

Question

Following on from my two previous posts.

• An alternative vector
• An Alternative Vector (Copy Assignment Operator)

I have written a detailed blog about how to write a minimal vector like class. This set of articles has been inspired by multiple posts here on http://codereview.stackexchange.com (See Sources).

• Index
  1. Resource Management: Allocation
  2. Resource Management: Copy and Swap
  3. Resource Management: Resize
  4. Resource Management: Simple Optimization
  5. The Other Stuff

The final result is below.
But now it is my turn for some review to make sure I did not screw up too much. :-)

Head:

#ifndef THORSANVIL_CONTAINER_VECTOR
#define THORSANVIL_CONTAINER_VECTOR

#include <type_traits>
#include <memory>
#include <algorithm>
#include <stdexcept>
#include <iterator>
#include <cmath>

namespace ThorsAnvil
{
    namespace Container
    {

Types:

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

    private:
        size_type       capacity;
        size_type       length;
        T*              buffer;

        struct Deleter
        {
            void operator()(T* buffer) const
            {
                ::operator delete(buffer);
            }
        };

Constructors:

    public:
        Vector(int capacity = 10)
            : capacity(capacity)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {}
        template<typename I>
        Vector(I begin, I end)
            : capacity(std::distance(begin, end))
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            for(auto loop = begin;loop != end; ++loop)
            {
                pushBackInternal(*loop);
            }
        }
        Vector(std::initializer_list<T> const& list)
            : Vector(std::begin(list), std::end(list))
        {}
        ~Vector()
        {
            // Make sure the buffer is deleted even with exceptions
            // This will be called to release the pointer at the end
            // of scope.
            std::unique_ptr<T, Deleter>     deleter(buffer, Deleter());

            clearElements<T>();
        }
        Vector(Vector const& copy)
            : capacity(copy.length)
            , length(0)
            , buffer(static_cast<T*>(::operator new(sizeof(T) * capacity)))
        {
            try
            {
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    push_back(copy.buffer[loop]);
                }
            }
            catch(...)
            {
                clearElements<T>();
                ::operator delete(buffer);

                // Make sure the exceptions continue propagating after
                // the cleanup has completed.
                throw;
            }
        }
        Vector& operator=(Vector const& copy)
        {
            copyAssign<T>(copy);
            return *this;
        }
        Vector(Vector&& move) noexcept
            : capacity(0)
            , length(0)
            , buffer(nullptr)
        {
            move.swap(*this);
        }
        Vector& operator=(Vector&& move) noexcept
        {
            move.swap(*this);
            return *this;
        }
        void swap(Vector& other) noexcept
        {
            using std::swap;
            swap(capacity,      other.capacity);
            swap(length,        other.length);
            swap(buffer,        other.buffer);
        }

Access:

        reference           operator[](size_type index)         {return buffer[index];}
        const_reference     operator[](size_type index) const   {return buffer[index];}
        reference           at(size_type index)                 {validateIndex(index);return buffer[index];}
        const_reference     at(size_type index) const           {validateIndex(index);return buffer[index];}
        reference           front()                             {return buffer[0];}
        const_reference     front() const                       {return buffer[0];}
        reference           back()                              {return buffer[length - 1];}
        const_reference     back() const                        {return buffer[length - 1];}

Comparison:

        bool operator!=(Vector const& rhs) const {return !(*this == rhs);}
        bool operator==(Vector const& rhs) const
        {
            return (size() == rhs.size())
                ?  std::equal(begin(), end(), rhs.begin())
                :  false;
        }

Iterators:

        iterator            begin()                             {return buffer;}
        iterator            rbegin()                            {return std::reverse_iterator<iterator>(end());}
        const_iterator      begin() const                       {return buffer;}
        const_iterator      rbegin() const                      {return std::reverse_iterator<iterator>(end());}

        iterator            end()                               {return buffer + length;}
        iterator            rend()                              {return std::reverse_iterator<iterator>(begin());}
        const_iterator      end() const                         {return buffer + length;}
        const_iterator      rend() const                        {return std::reverse_iterator<iterator>(begin());}

        const_iterator      cbegin() const                      {return begin();}
        const_iterator      crbegin() const                     {return rbegin();}
        const_iterator      cend() const                        {return end();}
        const_iterator      crend() const                       {return rend();}

Non-Mutating Functions:

        size_type           size() const                        {return length;}
        bool                empty() const                       {return length == 0;}

Mutating Functions:

        void push_back(T const& value)
        {
            resizeIfRequire();
            pushBackInternal(value);
        }
        void push_back(T&& value)
        {
            resizeIfRequire();
            moveBackInternal(std::forward<T>(value));
        }
        template<typename... Args>
        void emplace_back(Args&&... args)
        {
            resizeIfRequire();
            constructBackInternal(std::forward<T>(args)...);
        }
        void pop_back()
        {
            --length;
            buffer[length].~T();
        }
        void reserve(size_type capacityUpperBound)
        {
            if (capacityUpperBound > capacity)
            {
                reserveCapacity(capacityUpperBound);
            }
        }

Private:

    private:
        void validateIndex(size_type index)
        {
            if (index >= length)
            {
                throw std::out_of_range("Out of Range");
            }
        }

        void resizeIfRequire()
        {
            if (length == capacity)
            {
                size_type     newCapacity  = std::max(2.0, capacity * 1.62);
                reserveCapacity(newCapacity);
            }
        }
        void reserveCapacity(size_type newCapacity)
        {
            Vector<T>  tmpBuffer(newCapacity);

            simpleCopy<T>(tmpBuffer);

            tmpBuffer.swap(*this);
        }
        void pushBackInternal(T const& value)
        {
            new (buffer + length) T(value);
            ++length;
        }
        void moveBackInternal(T&& value)
        {
            new (buffer + length) T(std::forward<T>(value));
            ++length;
        }
        template<typename... Args>
        void constructBackInternal(Args&&... args)
        {
            new (buffer + length) T(std::forward<Args>(args)...);
            ++length;
        }
        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == false>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T const& v){dst.pushBackInternal(v);}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_nothrow_move_constructible<X>::value == true>::type
        simpleCopy(Vector<T>& dst)
        {
            std::for_each(buffer, buffer + length,
                          [&dst](T& v){dst.moveBackInternal(std::move(v));}
                         );
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == false>::type
        clearElements()
        {
            // Call the destructor on all the members in reverse order
            for(int loop = 0; loop < length; ++loop)
            {
                // Note we destroy the elements in reverse order.
                buffer[length - 1 - loop].~T();
            }
        }

        template<typename X>
        typename std::enable_if<std::is_trivially_destructible<X>::value == true>::type
        clearElements()
        {
            // Trivially destructible objects can be re-used without using the destructor.
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                            &&  std::is_nothrow_destructible<X>::value) == true>::type
        copyAssign(Vector<X>& copy)
        {
            if (this == &copy)
            {
                return;
            }

            if (capacity <= copy.length)
            {
                clearElements<T>();
                length = 0;
                for(int loop = 0; loop < copy.length; ++loop)
                {
                    pushBackInternal(copy[loop]);
                }
            }
            else
            {
                // Copy and Swap idiom
                Vector<T>  tmp(copy);
                tmp.swap(*this);
            }
        }

        template<typename X>
        typename std::enable_if<(std::is_nothrow_copy_constructible<X>::value
                             &&  std::is_nothrow_destructible<X>::value) == false>::type
        copyAssign(Vector<X>& copy)
        {
            // Copy and Swap idiom
            Vector<T>  tmp(copy);
            tmp.swap(*this);
        }
};

Tail:

    }
}
#endif

Answer 1

I've only had a chance to glance at things so far, but this almost jumped out at me:

    bool operator==(Vector const& rhs) const
    {
        return (size() == rhs.size())
            ?  std::equal(begin(), end(), rhs.begin())
            :  false;
    }

This seems rather convoluted, at least to me. I'd prefer:

bool operator==(Vector const& rhs) const
{
    return (size() == rhs.size()) && std::equal(begin(), end(), rhs.begin());             
}

I believe this shows the intent much more directly, and (thanks to short-circuit evaluation) still avoids evaluating std::equal if the sizes aren't equal.

Some of the names also seem somewhat misleading. For example, I'd rename resizeIfRequire to something like reallocIfRequired, since it can only affect the capacity, not the size.

Oh, looking at the multiplier you've used: 1.62 is a poor choice. The point of using the golden mean is that it's the largest multiplier you can use that guarantees that (if they're contiguous) the discarded pieces will eventually add together to be large enough to fulfill the next larger request size. Note that wording carefully though: the golden mean is the largest multiplier you can use and still get this result. By rounding up from the golden mean (1.618...) to 1.62, you've basically assured this can't happen.

To get the desired behavior, you need to use a multiplier that's less than or equal to the golden mean. In most cases, the memory manager will add a little overhead to the block size you use, so if you use exactly the golden mean, it'll never happen either. I'd recommend a multiplier no greater than 1.6. In many cases, it's easiest to use 1.5, which makes integer math easy, and still gets roughly the same effects (and a fair amount of empirical testing indicates works well in general).

Answer 2

My 5 cents:

This does not seems legal to use std::forward, unless it is not universal reference.

Change it to std::move or add template<class UT>.

    void push_back(T&& value)
    {
        resizeIfRequire();
        moveBackInternal(std::forward<T>(value));
    }

You did this everywhere.

Answer 3

Reverse iterator don't compile.

for (auto k = b.rbegin(); k != b.rend(); ++k)
{ std::cout << k; }

Give: error: no viable conversion from 'std::reverse_iterator' to 'iterator' (aka 'int *')

You shouldn't use a pointer as reverse iterator, the ++ on a reverse iterator should decrement the position.

---

The move operator should invalidate the moved object.

Vector& operator=(Vector&& move) noexcept
{
    move.swap(*this);
    // move should be deallocated and invalidated
    return *this;
}

---

Apart from that I didn't spot any other obvious mistake. And Valgrind didn't spot any leaks. Also I like the format and the use of enable_if to optimize the copy of POD.