11
\$\begingroup\$

Following on from my two previous posts.

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).

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
\$\endgroup\$
  • \$\begingroup\$ Not a full answer, but three bug reports: Your rbegin() function needs to return reverse_iterator, not iterator. Your moveBackInternal function needs to call std::move(value), not std::forward<T>(value). I suspect that Vector<int>(1).push_back(2) will corrupt memory. \$\endgroup\$ – Quuxplusone Mar 21 '16 at 2:51
  • \$\begingroup\$ @Quuxplusone: Thanks. rbegin()/rend() oops mistake added unit tests for that. Now fixed. std::forward Vs std::move still working on move semantics; so I get that wrong sometimes. Will have to write an article about the subject. I doubt that there is memory corruption with that. But while adding some unit tests to test the theory; I did find another error. Need std::max() to make sure capacity of 0/1 scales up correctly. \$\endgroup\$ – Martin York Mar 21 '16 at 5:52
  • \$\begingroup\$ For the record, your "another bug" was indeed the bug I was referring to with that third sentence. :) \$\endgroup\$ – Quuxplusone Mar 21 '16 at 6:02
  • 1
    \$\begingroup\$ That must be some new meaning of 'minimal' that I wasn't previously aware of... I'm glad that we can usually get away with #include <vector>. \$\endgroup\$ – DarthGizka Mar 21 '16 at 6:13
  • \$\begingroup\$ @DarthGizka: Yes this is minimal. That is why other examples on codereview get so many comments when they try and implement their own vector. But also note I wrote this as an exploration of why std::vector is written the way it is. This is the result of five blog posts (so you can see the reason for each feature in the blog). But even my code needs a review. :-) \$\endgroup\$ – Martin York Mar 21 '16 at 6:34
6
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Thanks. Need to read more on that topic. Here i was trying to be clever and kicking myself in the butt. \$\endgroup\$ – Martin York Mar 21 '16 at 19:51
  • \$\begingroup\$ Golden ratio will still likely cause rounding errors. If you want to do it right, precompute the first few (dozen... or hundred?) fibonacci numbers and use them as multipliers. This way you'll have actual integer multipliers and you can set the initial value to something sane. So all the values after will be sane*fib(n). \$\endgroup\$ – Dmitry Rubanovich Jun 8 '17 at 9:04
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I notice now that they spotted the iterator bug in a comment of the original post.. >_> \$\endgroup\$ – ilmale Mar 23 '16 at 21:42
  • \$\begingroup\$ Thanks for the review. All input gratefully received. There is no need to invalidate the moved object though (after a move the object just needs to be valid). And you should definitely not deallocate the memory. The move objects destructor will handle this until then it could be potentially re-used. \$\endgroup\$ – Martin York Mar 23 '16 at 22:09
  • \$\begingroup\$ I think you are right, but the expected behaviour is that a moved object is not the owner of the resource. From cppreference "Move assignment operators typically "steal" the resources held by the argument (e.g. pointers to dynamically-allocated objects, file descriptors, TCP sockets, I/O streams, running threads, etc.), rather than make copies of them, and leave the argument in some valid but otherwise indeterminate state. For example, move-assigning from a std::string or from a std::vector may result in the argument being left empty. However, this behaviour should not be relied upon." \$\endgroup\$ – ilmale Mar 23 '16 at 22:55
  • 1
    \$\begingroup\$ Yes. After you have moved an object what is left behind is unspeciied as long as the object is valid. But you can still re-use it if you set it to a known state before use. std::string a = "X";std::string b = "Y";a = std::move(b); /* b can still be used. But you need to set it to a known state before you can do anything useful */ b.clear();. If I had deallocate the memory associated with b then you would have had lots of unnessacery work in resource management. But simply setting its state to empty it becomes re-usable with no memory allocation required. \$\endgroup\$ – Martin York Mar 23 '16 at 23:06

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.