Vector implementation

Question

This is a C++ Vector that I've made for the pleasure of it. It was made on a whim and is not related any school assignment or anything alike this.

This Vector does not aim to be compliant with the standard library, and does not aim to replace std::vector. However, its goal is to be very efficient while being simple and easy to use. It also takes into account POD types to optimize for them, but this has to be specified by the Vector user.

1. Would you please take a look and let me know your impressions?
2. Does it do anything in a wrong way? Do you see any issues with it?

I am also wondering if I should use C++11 type support such as std::is_pod and remove the manual control of POD optimization.

I would also like "for each" to work with my vector, but I dislike the all-lower-case syntax of the required begin() and end() functions. Is there's a non-compiler specific way to specify which functions to use instead of the default begin() and end()?

Here is the header file and .cpp file which is included in the header. There are unit tests at ../CoreSpecimen/DataStruct/Vector.cpp but posting them here would surpass the character limits. I'm not looking for a review of the tests but feel free to do so if you would like.

Header:

/* Vector.hpp */

#pragma once
#include "../Types.hpp"
#include "../Memory/Memory.hpp"
#include "VectorAssert.hpp"

//Placement New
#ifdef CoreTargetWin32
    inline void* operator new(Core::UInt, void* address){return address;}
    inline void operator delete(void*, void*){}
#elif CoreTargetLinux
    #ifdef CoreTarget64Bits
        inline void* operator new(long unsigned int, void* address){return address;}
    #else
        inline void* operator new(unsigned int, void* address){return address;}
    #endif
    inline void operator delete(void*, void*){}
#endif

namespace Core
{
    namespace DataStruct
    {
        template<class T> class Vector
        {
            public:
            enum CtorModeEnum{Always, Once, Pod};
            typedef T Element;
            typedef T const ConstElement;

            //DefaultMode is private except for UnitTest
            #ifndef VectorUnitTest
                private:
            #endif
            static CtorModeEnum DefaultMode;

            private:
            CtorModeEnum _ctorMode;
            Element* _origin; //Array Start
            Element* _last; //Sequence End
            Element* _end; //Array End

            /* Private Functions */
            void Deallocate();
            void Allocate(UInt capacity);
            void AutoAllocate();
            void Construct(ConstElement* target, ConstElement* source) const;
            void Move(ConstElement* target, Element *source) const;
            void Destroy(ConstElement* target) const;
            void Destroy(ConstElement* begin, ConstElement* end) const;
            void MoveRange(Element* target, Element* begin, Element* end) const;
            void CopyToSelf(Vector const & source);
            void MoveToSelf(Vector & source);

            public:
            /* Constructors && Destructor */
            Vector(CtorModeEnum ctorMode = DefaultMode);
            Vector(UInt capacity, CtorModeEnum ctorMode = DefaultMode);
            Vector(ConstElement* begin, ConstElement* end, CtorModeEnum ctorMode = DefaultMode);
            Vector(Vector const & source);
            Vector(Vector&& Source);
            virtual ~Vector();

            /* Operators */
            Vector& operator=(Vector const & source);
            Vector& operator=(Vector&& source);
            Vector& operator+=(Vector const & source);
            Element& operator[](UInt offset);
            ConstElement& operator[](UInt offset) const;

            /* Accesors */
            CtorModeEnum CtorMode() const;
            Bool IsEmpty() const;
            UInt Capacity() const;
            UInt Length() const;

            /* Iterators */
            Element* Begin();
            Element* End();
            Element* RBegin();
            Element* REnd();
            ConstElement* Begin() const;
            ConstElement* End() const;
            ConstElement* RBegin() const;
            ConstElement* REnd() const;

            /* Public Functions */
            void Reserve(UInt capacity);
            void Shrink();
            void Clear();
            void Free();
            void Add(ConstElement& value);
            void AddRange(ConstElement* begin, ConstElement* end);
            void Insert(Element& at, ConstElement& value);
            void Insert(UInt offset, ConstElement& value);
            void Remove(Element& item);
            void Remove(UInt position);
            Element* DrivePointer(UInt future_length);
        };

        #include "Vector.cpp"
    }
}

Implementation:

/* Vector.cpp */

/******************************************************************************/
/* Static *********************************************************************/
/******************************************************************************/

template<class T> typename Vector<T>::CtorModeEnum Vector<T>::DefaultMode = Vector<T>::CtorModeEnum::Always;

/******************************************************************************/
/* Private Functions **********************************************************/
/******************************************************************************/

template<class T> void Vector<T>::Deallocate()
{
    if(_origin)
    {
        if(_ctorMode != CtorModeEnum::Pod)
            Destroy(_origin, _last);

        Memory::Free(_origin);

        _origin = NULL;
        _last = NULL;
        _end = NULL;
    }
}

template<class T> void Vector<T>::Allocate(UInt capacity)
{
    Element* newOrigin;

    if(capacity == 0)
    {
        Deallocate();
        return;
    }

    newOrigin = (Element*)Memory::Alloc(sizeof(Element) * capacity);

    if(!IsEmpty())
    {
        if(_ctorMode != CtorModeEnum::Always)
            Memory::Copy(_origin, newOrigin, sizeof(Element) * Length());
        else
        {
            MoveRange(newOrigin, _origin, _last);
            Destroy(_origin, _last); //2013-04-19 is Destroy really needed since Move was just used? What if C++11 is not enabled?
        }
        Memory::Free(_origin);
    }

    _last = newOrigin + (_last - _origin);
    _end = newOrigin + capacity;
    _origin = newOrigin;
}

template <class T> void Vector<T>::AutoAllocate()
{
    if(_origin == NULL)
        Allocate(2U);
    else if(_last == _end)
        Allocate(Capacity() << 1U);
}

template <class T> void Vector<T>::Construct(ConstElement* target, ConstElement *source) const
{
    AssertSourceTarget((VoidPtr)source, (VoidPtr)target);
    new((VoidPtr)target) Element(*source);
}

template <class T> void Vector<T>::Move(ConstElement* target, Element *source) const
{
    AssertSourceTarget((VoidPtr)source, (VoidPtr)target);
    new((VoidPtr)target) Element((Element&&)(*source));
}

template <class T> void Vector<T>::Destroy(ConstElement* target) const
{
    AssertTarget((VoidPtr)target);
    target->~Element();
}

template <class T> void Vector<T>::Destroy(ConstElement* begin, ConstElement* end) const
{
    AssertBeginEnd((VoidPtr)begin, (VoidPtr)end);

    while(begin != end)
        Destroy(begin++);
}

template <class T> void Vector<T>::MoveRange(Element* target, Element* begin, Element* end) const
{
    AssertTarget(target);
    AssertBeginEnd(begin, end);

    if(_ctorMode != CtorModeEnum::Always)
        Memory::Move((VoidPtr)begin, (VoidPtr)target, sizeof(Element) * (end - begin));
    else
    {
        if(target < begin)
            while(begin != end)
                Move(target++, begin++);
        else
        {
            target += end - begin - 1;
            while(begin != end)
                Move(target--, --end);
        }
    }
}

template <class T> void Vector<T>::CopyToSelf(Vector const & source)
{
    UInt length;
    ConstElement *it, *source_it, *source_end;

    Deallocate();
    _ctorMode = source._ctorMode;

    if(!source.IsEmpty())
    {
        length = source.Length();
        Allocate(length);

        it = _origin;
        source_it = source.Begin();
        source_end = source.End();

        if(_ctorMode != CtorModeEnum::Always)
        {
            Memory::Move((VoidPtr)source_it, (VoidPtr)it, sizeof(Element) * length);
            _last += length;
        }
        else
            while(source_it != source_end)
            {
                Construct(it++, source_it++);
                ++_last;
            }
    }
}

template <class T> void Vector<T>::MoveToSelf(Vector & source)
{
    Deallocate();
    _ctorMode = source._ctorMode;

    if(!source.IsEmpty())
    {
        _origin = source._origin;
        _last = source._last;
        _end = source._end;
        source._origin = NULL;
        source._last = NULL;
        source._end = NULL;
    }
}

/******************************************************************************/
/* Constructors && Destructor *************************************************/
/******************************************************************************/

template<class T> Vector<T>::Vector(CtorModeEnum ctorMode) :
    _ctorMode(ctorMode),
    _origin(NULL),
    _last(NULL),
    _end(NULL)
{}

template<class T> Vector<T>::Vector(UInt capacity, CtorModeEnum ctorMode) :
    _ctorMode(ctorMode),
    _origin(NULL),
    _last(NULL),
    _end(NULL)
{
    Allocate(capacity);
}

template<class T> Vector<T>::Vector(Vector const & source) :
    _origin(NULL),
    _last(NULL),
    _end(NULL)
{
    CopyToSelf(source);
}

template<class T> Vector<T>::Vector(Vector&& source) :
    _origin(NULL),
    _last(NULL),
    _end(NULL)
{
    MoveToSelf(source);
}

template<class T> Vector<T>::Vector(ConstElement* begin, ConstElement* end, CtorModeEnum ctorMode) :
    _ctorMode(ctorMode),
    _origin(NULL),
    _last(NULL),
    _end(NULL)
{
    AddRange(begin, end);
}

template<class T> Vector<T>::~Vector()
{
    Deallocate();
}

/******************************************************************************/
/* Operators ******************************************************************/
/******************************************************************************/

template<class T> Vector<T>& Vector<T>::operator=(Vector const & source)
{
    if(this != &source)
        CopyToSelf(source);

    return *this;
}

template<class T> Vector<T>& Vector<T>::operator=(Vector&& source)
{
    if(this != &source)
        MoveToSelf(source);

    return *this;
}

template<class T> Vector<T>& Vector<T>::operator+=(Vector const & source)
{
    if(!source.IsEmpty())
        AddRange(source.Begin(), source.End());

    return *this;
}

template<class T> typename Vector<T>::Element& Vector<T>::operator[](UInt offset)
{
    AssertVectorIsEmpty(_origin);
    AssertRange(offset, Length());
    return *(_origin + offset);
}

template<class T> typename Vector<T>::ConstElement& Vector<T>::operator[](UInt offset) const
{
    AssertVectorIsEmpty(_origin);
    AssertRange(offset, Length());
    return *(_origin + offset);
}

/******************************************************************************/
/* Accesors *******************************************************************/
/******************************************************************************/

template<class T> typename Vector<T>::CtorModeEnum Vector<T>::CtorMode() const
{
    return _ctorMode;
}

template<class T> Bool Vector<T>::IsEmpty() const
{
    return _last == _origin;
}

template<class T> UInt Vector<T>::Capacity() const
{
    return _end - _origin;
}

template<class T> UInt Vector<T>::Length() const
{
    return _last - _origin;
}

/******************************************************************************/
/* Iterators ******************************************************************/
/******************************************************************************/

template<class T> typename Vector<T>::Element* Vector<T>::Begin()
{
    return _origin;
}

template<class T> typename Vector<T>::Element* Vector<T>::End()
{
    return _last;
}

template<class T> typename Vector<T>::Element* Vector<T>::RBegin()
{
    return _last - 1;
}

template<class T> typename Vector<T>::Element* Vector<T>::REnd()
{
    return _origin - 1;
}

template<class T> typename Vector<T>::ConstElement* Vector<T>::Begin() const
{
    return _origin;
}

template<class T> typename Vector<T>::ConstElement* Vector<T>::End() const
{
    return _last;
}

template<class T> typename Vector<T>::ConstElement* Vector<T>::RBegin() const
{
    return _last - 1;
}

template<class T> typename Vector<T>::ConstElement* Vector<T>::REnd() const
{
    return _origin - 1;
}

/******************************************************************************/
/* Public Functions ***********************************************************/
/******************************************************************************/

template<class T> void Vector<T>::Reserve(UInt capacity)
{
    if(capacity > Capacity())
        Allocate(capacity);
}

template<class T> void Vector<T>::Shrink()
{
    if(_end > _last)
        Allocate(Length());
}

template<class T> void Vector<T>::Clear()
{
    if(!IsEmpty())
    {
        if(_ctorMode != CtorModeEnum::Pod)
            Destroy(_origin, _last);

        _last = _origin;
    }
}

template<class T> void Vector<T>::Free()
{
    Deallocate();
}

template<class T> void Vector<T>::Add(ConstElement& value)
{
    AutoAllocate();

    if(_ctorMode != CtorModeEnum::Pod)
        Construct(_last, &value);
    else
        *_last = value;

    ++_last;
}

template<class T> void Vector<T>::AddRange(ConstElement* begin, ConstElement* end)
{
    UInt length;

    AssertBeginEnd((VoidPtr)begin, (VoidPtr)end);

    length = end - begin;
    Reserve(Length() + length);

    if(_ctorMode == CtorModeEnum::Pod)
    {
        Memory::Move((VoidPtr)begin, (VoidPtr)_last, sizeof(Element) * length);
        _last += length;
    }
    else
        while(begin != end)
            Construct(_last++, begin++);
}

template<class T> void Vector<T>::Insert(Element& at, ConstElement& value)
{
    Int offset;
    Element* element;

    offset = &at - _origin;
    AutoAllocate();
    element = _origin + offset;

    MoveRange(element + 1, element, _last);
    ++_last;

    if(_ctorMode == CtorModeEnum::Pod)
        *element = value;
    else
        Construct(element, &value);
}

template<class T> void Vector<T>::Insert(UInt offset, ConstElement& value)
{
    UInt length = Length();
    Element* element;

    //If the offset is past the end, insert at end
    if(offset > length)
        offset = length;

    AutoAllocate();
    element = _origin + offset;

    MoveRange(element + 1, element, _last);
    ++_last;

    if(_ctorMode == CtorModeEnum::Pod)
        *element = value;
    else
        Construct(element, &value);
}

template<class T> void Vector<T>::Remove(Element& element)
{
    if(!IsEmpty() && &element)
    {
        if(_ctorMode != CtorModeEnum::Pod)
            Destroy(&element);

        if(&element != _last - 1)
        {
            MoveRange(&element, &element + 1, _last);
            if(_ctorMode == CtorModeEnum::Always)
                Destroy(_last - 1);
        }

        --_last;
    }
}

template<class T> void Vector<T>::Remove(UInt offset)
{
    UInt length;
    Element* element;

    if(!IsEmpty())
    {
        length = Length();

        //If the offset is past the end, delete last
        if(offset >= length)
            offset = length - 1;

        element = _origin + offset;

        if(_ctorMode != CtorModeEnum::Pod)
            Destroy(element);

        if(element != _last - 1)
        {
            MoveRange(element, element + 1, _last);
            if(_ctorMode == CtorModeEnum::Always)
                Destroy(_last - 1);
        }

        --_last;
    }
}

template<class T> typename Vector<T>::Element* Vector<T>::DrivePointer(UInt future_length)
{
    _last = _origin + future_length;
    return _origin;
}

Answer 1

When you include source from a header file its best to name the file differently:

#include "Vector.cpp"

// Normally when including template source name the file tpp

#include "Vector.tpp"

Your reverse iterators are not going to work as epected:

template<class T> typename Vector<T>::ConstElement* Vector<T>::RBegin() const
{
    return _last - 1;
}

template<class T> typename Vector<T>::ConstElement* Vector<T>::REnd() const
{
    return _origin - 1;
}

When you increment the reverse iterator it should head in the reverse direction to the normal iterator (so it needs some wrapper to do that). Luckily there is such a wrapper in the standard library

At first glance a lot of your manual movement/copying of stuff around are covered by standard algorithms. Though the standard algorithms don't use run time checks they do it at compile time so would be much more efficient to use the standard algorithms.

    if(_ctorMode != CtorModeEnum::Always)
        Memory::Copy(_origin, newOrigin, sizeof(Element) * Length());
    else
    {
        MoveRange(newOrigin, _origin, _last);
    }

I would have written this as:

    // The compiler decides if it is movable at compile time.
    // If not it will copy it. If it is a POD type it will just use
    // a memmov() otherwise it has to invoke the constructor appropriately.
    std::move(_origin, _last, newOrigin);