4
\$\begingroup\$

This is intended to be a simpler replacement of std::vector, written for entertainment. It should be as fast or faster than std::vector, but does not need to have as many features.

It should also be simple to use.

I am looking for a review on the following:

  • Bugs
  • Performance
  • Class/Functions/Variables Naming
  • Useful features to add
  • Code structure
  • Anything else

Here is the header file Vector.hpp

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

namespace Core
{
    namespace DataStruct
    {
        template<class ItemType> class Vector
        {
            ItemType* VecPtr;
            UInt Capacity;
            UInt Length;

            void AllocSpace();
            void DestroyAll();

            public:
            typedef ItemType* Iterator;
            typedef ItemType const * ConstIterator;

            Vector();
            ~Vector();

            void Reserve(UInt Capacity);

            void Add(ItemType const & Value);
            void Insert(UInt Position, ItemType const & Value);
            void Remove(UInt Position);

            void Clear();
            void Free();

            UInt GetCapacity() const;
            UInt GetLength() const;

            ItemType operator[](UInt Position) const;

            Iterator Begin();
            Iterator End();
            ConstIterator Begin() const;
            ConstIterator End() const;
            ConstIterator CBegin() const;
            ConstIterator CEnd() const;
        };

        #include "Vector.cpp"
    }
}

And the implementation Vector.cpp, excluded from the build and included from Vector.hpp since it is a template.

template <class ItemType> void Vector<ItemType>::AllocSpace()
{
    if(Capacity == 0U)
        Reserve(2U);
    else if(Capacity == Length)
        Reserve(Capacity << 1U);
}

template <class ItemType> void Vector<ItemType>::DestroyAll()
{
    Iterator it = Begin();
    Iterator end = End();
    while(it < end)
        it++->~ItemType();
}

template<class ItemType> Vector<ItemType>::Vector() : VecPtr(NULL), Capacity(0U), Length(0U) {}

template<class ItemType> Vector<ItemType>::~Vector()
{
    Free();
}

template<class ItemType> void Vector<ItemType>::Reserve(UInt Capacity)
{
    ItemType* ptr;

    if(Capacity > this->Capacity)
    {
        ptr = (ItemType*)System::Memory::Alloc(sizeof(ItemType) * Capacity);
        if(VecPtr)
        {
            System::Memory::Copy(VecPtr, ptr, sizeof(ItemType) * this->Capacity);
            System::Memory::Free(VecPtr);
        }
        VecPtr = ptr;
        this->Capacity = Capacity;
    }
}

template<class ItemType> void Vector<ItemType>::Add(ItemType const & Value)
{
    Insert(Length, Value);
}

template<class ItemType> void Vector<ItemType>::Insert(UInt Position, ItemType const & Value)
{
    ItemType* ptr;
    Bool insert;

    AllocSpace();

    //If Position is beyond the end then insert at end.
    insert = Position < Length;
    ptr = insert ? VecPtr + Position : VecPtr + Length;

    if(insert)
        System::Memory::Move(ptr, ptr + 1, sizeof(ItemType) * (Length - Position));

    new((VoidPtr)ptr) ItemType(Value);
    ++Length;
}

template<class ItemType> void Vector<ItemType>::Remove(UInt Position)
{
    ItemType* ptr;

    if(Position < Length)
    {
        --Length;
        ptr = VecPtr + Position;
        ptr->~ItemType();
        if(Position < Length)
            System::Memory::Move(ptr + 1, ptr, sizeof(ItemType) * (Length - Position));
    }
}

template<class ItemType> void Vector<ItemType>::Clear()
{
    DestroyAll();
    Length = 0U;
}

template<class ItemType> void Vector<ItemType>::Free()
{
    if(VecPtr)
    {
        DestroyAll();
        System::Memory::Free(VecPtr);
        VecPtr = NULL;
        Capacity = 0U;
        Length = 0U;
    }
}

template<class ItemType> UInt Vector<ItemType>::GetCapacity() const
{
    return Capacity;
}

template<class ItemType> UInt Vector<ItemType>::GetLength() const
{
    return Length;
}

template<class ItemType> ItemType Vector<ItemType>::operator[](UInt Position) const
{
    return *(VecPtr + Position);
}

template<class ItemType> typename Vector<ItemType>::Iterator Vector<ItemType>::Begin()
{
    return VecPtr;
}

template<class ItemType> typename Vector<ItemType>::Iterator Vector<ItemType>::End()
{
    return VecPtr + Length;
}

template<class ItemType> typename Vector<ItemType>::ConstIterator Vector<ItemType>::Begin() const
{
    return VecPtr;
}

template<class ItemType> typename Vector<ItemType>::ConstIterator Vector<ItemType>::End() const
{
    return VecPtr + Length;
}

template<class ItemType> typename Vector<ItemType>::ConstIterator Vector<ItemType>::CBegin() const
{
    return VecPtr;
}

template<class ItemType> typename Vector<ItemType>::ConstIterator Vector<ItemType>::CEnd() const
{
    return VecPtr + Length;
}

The functions in the Memory namespace calls the following:

  • Memory::Alloc -> malloc
  • Memory::Copy -> memcpy
  • Memory::Move -> memmove
  • Memory::Free -> free
\$\endgroup\$
3
  • 1
    \$\begingroup\$ For being C++ it looks a lot like C#... it even has some conceptual errors from thinking in reference semantics instead of value semantics \$\endgroup\$
    – K-ballo
    Jan 7, 2013 at 20:18
  • \$\begingroup\$ memcpy()/memmove is not sufficient for the general case in C++ (though you can specialize it to work for certain types). Anything that is not POD type (or standard-layout types as K-ballo more accurately calls them) will have to be copied/moved using the copy/move constructors of the type. \$\endgroup\$ Jan 7, 2013 at 22:39
  • 2
    \$\begingroup\$ Even getting things as fast as std::vector will be a struggle. It is very efficient. \$\endgroup\$ Jan 7, 2013 at 22:39

1 Answer 1

3
\$\begingroup\$

The first and most obvious disadvantage of your Vector is that it does not satisfy the standard requirements for a Sequence. That means that your Vector cannot be used with any of the standard algorithms nor with 3rd party algorithms designed to work with Sequences. It is only useful to store elements, and nothing else.

The lack of proper constructors/destructor and assignment operator will cause crashes and leaks every time your Vector is used. There is a lot to say on that subject, please search for a basic C++ rule known as The Rule of Three which will let you know how you should write those special member functions to achieve the proper semantics.

The next obvious drawback of your implementation is that one can only get copies of the elements stored in the Vector. This not only inconvenient, its also really inefficient. One has to make a copy of the element just to read it; and in order to write it one has to make a copy, modify said copy, remove the element from the Vector and then insert the modified copy. As said, this is both inconvenient and really inefficient. This would be a better approach for your subscript operator:

ItemType& operator[](UInt Position){ ... };
ItemType const& operator[](UInt Position) const{ ... };

This returns a reference to the stored element instead, so its possible to modify it in place if we have a non-const Vector.

Another important drawback is that the Vector as implemented will only work with standard-layout types. Simply moving or copying the underlying memory for any other kind of type may result in garbled internal values, broken invariants, or even crashes and undefined behavior.

The naming convention is strange to C++, it seems like something brought from a different language, perhaps C#. But the semantics are not the same, so as a result this Vector will look odd for a C++ coder, and it will seem familiar to a C# coder which would be inclined to think the semantics are the ones from C#.

You said that This is intended to be a simpler replacement of std::vector. But if I were to replace std::vector with Vector the code would not even compile, and even if it would then the observed behavior would greatly differ. As a general rule, when you code in C++ you should stick to C++ conventions. The same applies for any other language as well.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the detailed review. I fixed the operator[] to return a reference and also added a const version. I did not intend for this class to be able to replace existing use of std::vector, so I am fine with it not qualifying as a sequence. I will look further into the Rule of Three, did you imply among other things that the constructor should be virtual? How does this Vector not work with storing custom class? It does not simply copy the memory but also call the copy constructor on the added elements, and then their destructor when removing them. Again thanks for your review. \$\endgroup\$
    – Valrandir
    Jan 7, 2013 at 21:22
  • \$\begingroup\$ Ok so because there is no copy constructor defined, and no operator=, the compiler provides their default implementation. If either of those are used, ItemType* VecPtr; will simply be copied and point to the same memory as the source vector. I will be fixing that, thank you. \$\endgroup\$
    – Valrandir
    Jan 7, 2013 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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