Implementing dynamic array without STL

Question

For my game engine that I'm trying to write without using STL I implemented dynamic array class(some kind of std::vector). I would like to know whether this code suits best practices. I'm also not enough knowledged about move semantics and all that stuff, so please tell if I should add them somewhere in my code. My engine does not use C++ exceptions, so noexcept is skipped even in places where it should be.

#pragma once

#include "Core/Engine/Core.h"
#include "Math/MathCommon.h"
#include "Core/Container/Iterator.h"

#include <initializer_list>

namespace Hermes
{
    /**
    * Templated dynamic array
    * Assumes that elements are reallocate-able, e.g. we don't need to call anybody when moving object in memory
    * Basically that means that object MUST NOT have pointers to themselves and/or other elements of array
    * NOTE : currently this implementation will never shrink allocated memory itself,
    * so you have to do it manually for better memory usage
    */
    template<typename ElementType>
    struct TArray
    {
    public:
        FORCEINLINE TArray() : Data(0), ElementCount(0), AllocatedCount(0)
        {

        }

        FORCEINLINE TArray(size_t InitialCount) : Data(0), ElementCount(0), AllocatedCount(0)
        {
            Resize(InitialCount);
        }

        FORCEINLINE TArray(size_t InitialCount, const ElementType& Filler) : Data(0), ElementCount(0), AllocatedCount(0)
        {
            Fill(0, InitialCount, Filler);
        }

        FORCEINLINE TArray(const TArray<ElementType>& Other) : Data(0), ElementCount(0), AllocatedCount(0)
        {
            Copy(0, Other.ElementCount, Other.GetData());
        }

        FORCEINLINE TArray(TArray<ElementType>&& Other) : Data(Other.Data), ElementCount(Other.ElementCount), AllocatedCount(Other.AllocatedCount)
        {
            Other.Data = 0;
            Other.ElementCount = 0;
            Other.AllocatedCount = 0;
        }

        FORCEINLINE TArray(const std::initializer_list<ElementType>& List)
        {
            Copy(0, List.size(), List._First);
        }

        FORCEINLINE TArray(size_t Count, const ElementType* Source)
        {
            Copy(0, Count, Source);
        }

        FORCEINLINE TArray<ElementType>& operator=(const TArray<ElementType>& Other)
        {
            ElementCount = 0;
            Copy(0, Other.ElementCount, Other.Data);
            Resize(Other.ElementCount);
        }

        FORCEINLINE TArray<ElementType>& operator=(TArray<ElementType>&& Other)
        {
            MemoryOperations::Swap(ElementCount, Other.ElementCount);
            MemoryOperations::Swap(AllocatedCount, Other.AllocatedCount);
            MemoryOperations::Swap(Data, Other.Data);
            return *this;
        }

        FORCEINLINE TArray<ElementType>& operator=(const std::initializer_list<ElementType> List)
        {
            Copy(0, List.size(), List._First);
        }

        FORCEINLINE ~TArray()
        {
            Resize(0);
        }

        FORCEINLINE bool RangeCheck(size_t Index) const
        {
            return (Index >= 0) && (Index < ElementCount);
        }

        FORCEINLINE ElementType* GetData()
        {
            return Data;
        }

        FORCEINLINE const ElementType* GetData() const
        {
            return Data;
        }

        FORCEINLINE ElementType& operator[](size_t Index)
        {
            return Data[Index];
        }

        FORCEINLINE const ElementType& operator[](size_t Index) const
        {
            return Data[Index];
        }

        FORCEINLINE size_t Size() const
        {
            return ElementCount;
        }

        FORCEINLINE size_t Capacity() const
        {
            return AllocatedCount;
        }

        FORCEINLINE size_t Slack() const
        {
            return AllocatedCount - ElementCount;
        }

        FORCEINLINE size_t AppendUnitialized(size_t Count)
        {
            size_t StartIndex = ElementCount;
            Resize(ElementCount + Count);
            ElementCount += Count;
            return StartIndex;
        }

        FORCEINLINE size_t AppendDefaulted(size_t Count)
        {
            size_t StartIndex = AppendUnitialized(Count);
            MemoryOperations::ConstructDefaultItems<ElementType>(&Data[StartIndex], Count);
            return StartIndex;
        }

        FORCEINLINE size_t Append(const ElementType& Item, size_t Count = 1)
        {
            Fill(ElementCount, Count, Item);
            return ElementCount;
        }

        FORCEINLINE size_t Append(const TArray<ElementType>& Other)
        {
            size_t StartIndex = ElementCount;
            Copy(StartIndex, Other.ElementCount, Other.Data);
            return StartIndex;
        }

        FORCEINLINE size_t Append(const std::initializer_list<ElementType>& List)
        {
            size_t StartIndex = ElementCount;
            Copy(StartIndex, List.size(), List.begin());
            return StartIndex;
        }

        FORCEINLINE size_t Append(size_t Count, const ElementType* Source)
        {
            size_t StartIndex = ElementCount;
            Copy(StartIndex, Count, Source);
            return StartIndex;
        }

        FORCEINLINE size_t InsertUninitialized(size_t Index, size_t Count)
        {
            HERMES_ASSERT(Index < ElementCount);
            if (!Count) return -1;
            Resize(ElementCount + Count);
            Memory::Memmove(&Data[Index + Count], &Data[Index], Count * sizeof(ElementType));
            ElementCount += Count;
            return Index;
        }

        FORCEINLINE size_t InsertDefaulted(size_t Index, size_t Count)
        {
            InsertUninitialized(Index, Count);
            MemoryOperations::ConstructDefaultItems<ElementType>(&Data[Index], Count);
            return Index;
        }

        FORCEINLINE size_t Insert(size_t Index, const ElementType& Item, size_t Count = 1)
        {
            InsertUninitialized(Index, Count);
            Fill(Index, Count, Item);
            return Index;
        }

        FORCEINLINE size_t Insert(size_t Index, const TArray<ElementType&> Other)
        {
            InsertUninitialized(Index, Count);
            Copy(Index, Count, Other.Data);
            return Index;
        }

        FORCEINLINE size_t Insert(size_t Index, std::initializer_list<ElementType> Source)
        {
            InsertUninitialized(Index, Count);
            Copy(Index, Source.size(), Source._First);
        }

        FORCEINLINE size_t Insert(size_t Index, size_t Count, const ElementType* Source)
        {
            InsertUninitialized(Index, Count);
            Copy(Index, Count, Source);
            return Index;
        }

        /**
         * Appends elements to the end of array
         */
        FORCEINLINE size_t Push(const ElementType& Item)
        {
            return Append(Item);
        }

        /**
         * Appends element to the end of array constructing it with given args
         */
        template<typename... ArgsType>
        FORCEINLINE void Emplace(ArgsType&&... Args)
        {
            size_t Index = AppendUnitialized(1);
            new (Data + Index) ElementType(MemoryOperations::Forward<ArgsType>(Args)...);
            return Index;
        }

        template<typename... ArgsType>
        FORCEINLINE ElementType& EmplaceAt(size_t Index, ArgsType&&... Args)
        {
            InsertUninitialized(Index, 1);
            new (Data + Index) ElementType(MemoryOperations::Forward<ArgsType>(Args)...);
            return Data[Index];
        }

        /**
         * Returns copy of last element of array and removes it from array
         */
        FORCEINLINE ElementType Pop()
        {
            HERMES_ASSERT(ElementCount > 0)
            auto Result = Data[ElementCount - 1];
            RemoveAt(ElementCount - 1);
            return Result;
        }

        /**
         * Resizes array to at least NewCount elements, but could allocate more to reduce memory fragmentation
         * If NewCount < ElementCount last elements will be properly destroyed
         */
        FORCEINLINE void Resize(size_t NewCount)
        {
            if (NewCount != AllocatedCount)
            {
                if (NewCount < ElementCount)
                {
                    MemoryOperations::DestroyItems(&Data[NewCount], ElementCount - NewCount);
                }
                size_t EstimatedAllocationSize = sizeof(ElementType) * NewCount; //EngineGlobals::GAllocator().GetOptimalAllocationSize(sizeof(ElementType) * NewCount, alignof(ElementType));
                Data = (ElementType*)realloc(Data, EstimatedAllocationSize); //EngineGlobals::GAllocator().Reallocate(Data, EstimatedAllocationSize, alignof(ElementType));
                AllocatedCount = (EstimatedAllocationSize / sizeof(ElementType));
                if (NewCount < ElementCount)
                    ElementCount = NewCount;
            }
        }

        /**
         * Destroys all elements and makes sure that array could fit at least NewCount elements
         */
        FORCEINLINE void Reset(size_t NewCount)
        {
            Resize(NewCount);
            MemoryOperations::DestroyItems(Data, NewCount);
        }

        /**
         * Removes extra slack, although it still may exist to optimize memory allocation
         */
        FORCEINLINE void Trim()
        {
            Resize(ElementCount);
        }

        /**
         * Removes everything from array and leave extra slack as required
         */
        FORCEINLINE void Empty(size_t ExtraSlack = 0)
        {
            // We need to manually destroy items placed at slack memory because Resize won't do that
            MemoryOperations::DestroyItems(Data, ExtraSlack);
            ElementCount = 0;
            Resize(ExtraSlack);
        }

        FORCEINLINE void RemoveAt(size_t Index, size_t Count = 1)
        {
            MemoryOperations::DestroyItems(Data + Index, Count);
            Memory::Memmove(Data + Index, Data + Index + Count, Count * sizeof(ElementType));
            ElementCount -= Count;
        }

        typedef TRangedIterator<ElementType> Iterator;
        typedef TRangedIterator<const ElementType> ConstIterator;

        /**
         * Functions required to allow this container to be used in ranged-for loops
         */
        FORCEINLINE Iterator begin() { return Iterator(Data); }
        FORCEINLINE Iterator end()   { return Iterator(Data + ElementCount); }

        FORCEINLINE ConstIterator cbegin() { return ConstIterator(Data); }
        FORCEINLINE ConstIterator cend()   { return ConstIterator(Data + ElementCount); }

    private:
        /**
         * Fills range from Data[Start] to Data[Start + Count] with Filler using copy constructor
         * This function properly destroys and overrides data stored at [Start; Start + Count] range and resize array if needed
         */
        FORCEINLINE void Fill(size_t Start, size_t Count, const ElementType& Filler)
        {
            if (Start + Count > ElementCount)
                Resize(Start + Count);
            if (Start < ElementCount)
                MemoryOperations::DestroyItems(&Data[Start], max(min(ElementCount - Start, Count), 0));
            MemoryOperations::CopyConstructItem(&Data[Start], Filler, Count);
            ElementCount = Math::Max(Start + Count, ElementCount);
        }

        /**
         * Copies Count elements from Source to Data[Start]
         * This function properly destroys and overrides data stored at [Start; Start + Count] range and resize array if needed
         */
        FORCEINLINE void Copy(size_t Start, size_t Count, const ElementType* Source)
        {
            if (Start + Count > ElementCount)
                Resize(Start + Count);

            if (Start < ElementCount)
                MemoryOperations::DestroyItems(&Data[Start], max(min(ElementCount - Start, Count), 0));
            MemoryOperations::CopyConstructItems(&Data[Start], Source, Count);
            ElementCount = Math::Max(Start + Count, ElementCount);
        }

    private:
        ElementType* Data;

        size_t ElementCount;

        size_t AllocatedCount;
    };
}

EDIT: Here's all header files required. I've also modified source code to use realloc instead of my custom-made allocator to reduce amount of source code. I know that realloc of 0 size and nullptr is implementation-dependent, but my implementation correctly handles it so no problems here. Core/Engine/Core.h

#pragma once

#ifdef HERMES_PLATFORM_WINDOWS
#include <windows.h>

#define DLL_IMPORT __declspec(dllimport)
#define DLL_EXPORT __declspec(dllexport)

#define FORCEINLINE __forceinline

#define HERMES_ASSERT(Expression, ...) if (!(Expression)) DebugBreak();

#endif    

#ifdef HERMES_BUILD_ENGINE
#define HERMES_API DLL_EXPORT
#define GAME_API DLL_IMPORT
#elif defined HERMES_BUILD_GAME
#define HERMES_API DLL_IMPORT
#define GAME_API DLL_EXPORT
#else
#error "Either HERMES_BUILD_ENGINE or HERMES_BUILD_GAME need to be specified"
#endif

#define CREATE_APP_INSTANCE_FUNCTION_NAME "CreateApplicationInstance"

#ifdef HERMES_PLATFORM_WINDOWS
typedef char               int8  ;
typedef unsigned char      uint8 ;
typedef short int          int16 ;
typedef unsigned short int uint16;
typedef int                int32 ;
typedef unsigned int       uint32;
typedef long long          int64 ;
typedef unsigned long long uint64;
typedef uint64             size_t; // We compile only 64 bit builds on Windows
#endif

Math/MathCommon.h

#pragma once

#include "Core/Engine/Core.h"

namespace Hermes
{
    namespace Math
    {
        // TODO : intrinsic versions
        /**
         * log2 for 32-bit numbers
         */
        FORCEINLINE uint8 FloorLog2(uint32 Number)
        {
            uint32 Result = 0;
            if (Number >= 1ull << 16) { Number >>= 16; Result += 16; }
            if (Number >= 1ull << 8) { Number >>= 8; Result += 8; }
            if (Number >= 1ull << 4) { Number >>= 4; Result += 4; }
            if (Number >= 1ull << 2) { Number >>= 2; Result += 2; }
            if (Number >= 1ull << 1) { Result += 1; }
            return (Number == 0) ? 0 : Result;
        }

        /**
         * log2 for 64-bit numbers
         */
        FORCEINLINE uint8 FloorLog2_64(uint64 Number)
        {
            uint32 Result = 0;
            if (Number >= 1ull << 32) { Number >>= 32; Result += 32; }
            if (Number >= 1ull << 16) { Number >>= 16; Result += 16; }
            if (Number >= 1ull << 8) { Number >>= 8; Result += 8; }
            if (Number >= 1ull << 4) { Number >>= 4; Result += 4; }
            if (Number >= 1ull << 2) { Number >>= 2; Result += 2; }
            if (Number >= 1ull << 1) { Result += 1; }
            return (Number == 0) ? 0 : Result;
        }

        FORCEINLINE bool IsPowerOf2(uint64 Number)
        {
            return !(Number & (Number - 1));
        }

        FORCEINLINE int64 CeilIntegerDivide(int64 Dividend, int64 Divisor)
        {
            return ((Dividend + Divisor - 1) / Divisor);
        }

        template<typename T>
        FORCEINLINE T Max(T A, T B)
        {
            return (A > B ? A : B);
        }

        template<typename T>
        FORCEINLINE T Min(T A, T B)
        {
            return (A < B ? A : B);
        }
    }
}

Core/Container/Iterator.h

#pragma once

#include "Core/Engine/Core.h"

namespace Hermes
{
    /**
     * Very simple iterator that only defines functions required by ranged-for loop
     */
    template<typename ElementType>
    struct TRangedIterator
    {
    public:
        FORCEINLINE TRangedIterator(ElementType* InPtr) : Ptr(InPtr) {}

        FORCEINLINE bool operator!=(const TRangedIterator<ElementType>& Other) const { return Ptr != Other.Ptr; }

        FORCEINLINE TRangedIterator<ElementType>& operator++() { Ptr++; return *this; }

        FORCEINLINE ElementType& operator*() const { return *Ptr; }
    private:
        ElementType* Ptr;
    };
}

Answer 1

Overview

Couple of small bugs.

You don't always seem to initialize the appropriate objects correctly. Overall I find it a bit confusing when objects are initialized and when they are not.

The major missing part is that a lot of important functionality is another library and it I can check it is correct.

A lot of functionality you use pass a pointer and a size. In the standard they normal use two iterators to specify ranges. I would change the functionality to match this more normal C++ patern.

Code Review

The Resize() is the center of this implementation so we need to look at that first to compare against where it is used.

I assuming MemoryOperations::DestroyItems() calls the destructor on the elements in the range provided. I would note that normal arrays they will be destroyed in reverse order (you may want to implement the same way but I don't have the source to check). This reverse order of destruction will match normal object creation in that they are destroyed in reverse order of construction.

I would also note this function does not resize (ElementCount does not expand) the array but rather expands the allocated size (ie the size available for the array to expand into (AllocatedCount grows). So this should really be called Reserve() rather than Resize().

We have bug in the use of realloc(). The standard pattern is:

   ElementType* tmp = realloc(Data, newSize);
   if (tmp != nullptr) {
       Data = tmp;
   }

The reason to do this is because if the realloc() fails it will return nullptr and your statement above would override Data thus leaking the original value.

        void Resize(size_t NewCount)
        {
            // I would do less (<) than rather than not euqal (!=)
            // That way if the allocation is smaller than the current size
            // you don't waste time making the size smaller.
            //
            // Though you use this for the destructor and need this feature.
            // I would change this behavior (to avoid smaller resizes) and
            // have an explicit function to deallocate that can be used by
            // the destructor.
            if (NewCount != AllocatedCount)
            {
                if (NewCount < ElementCount)
                {
                    // Assume this calls the destructor.
                    MemoryOperations::DestroyItems(&Data[NewCount], ElementCount - NewCount);
                }
                size_t EstimatedAllocationSize = sizeof(ElementType) * NewCount; //EngineGlobals::GAllocator().GetOptimalAllocationSize(sizeof(ElementType) * NewCount, alignof(ElementType));

                // This is a BUG see above.
                Data = (ElementType*)realloc(Data, EstimatedAllocationSize); //EngineGlobals::GAllocator().Reallocate(Data, EstimatedAllocationSize, alignof(ElementType));
                AllocatedCount = (EstimatedAllocationSize / sizeof(ElementType));
                if (NewCount < ElementCount)
                    ElementCount = NewCount;
            }
        }

---

This is a BUG:

This Allocates the space for InitialCount values. But none of these values are initialized. So anything that uses a constructor now has UB.

        FORCEINLINE TArray(size_t InitialCount) : Data(0), ElementCount(0), AllocatedCount(0)
        {
            Resize(InitialCount);
            // Maybe this should be:
            Fill(0, InitialCount, ElementType{}); // Fill with a default value.
        }

---

This constructor is basically the same as the one above. The difference is that you provide a default value to fill the array with. You can collapse the two constructors by defaulting the Filler parameter`.

        FORCEINLINE TArray(size_t InitialCount, const ElementType& Filler) : Data(0), ElementCount(0), AllocatedCount(0)
        {
            Fill(0, InitialCount, Filler);
        }

---

This is usually implemented by simply calling swap. But this works as well.

        FORCEINLINE TArray(TArray<ElementType>&& Other) : Data(Other.Data), ElementCount(Other.ElementCount), AllocatedCount(Other.AllocatedCount)
        {
            Other.Data = 0;
            Other.ElementCount = 0;
            Other.AllocatedCount = 0;
        }

---

The type initializer_list does not have a member _First. If this compiles you must be using a non-standard implementation of the standard library.

        FORCEINLINE TArray(const std::initializer_list<ElementType>& List)
        {
            Copy(0, List.size(), List._First);
        }

---

The previous constructor and this constructor could be collapsed into a single constructor that takes iterators (which is the standard pattern in C++, rather than pointer to first and length).

        FORCEINLINE TArray(size_t Count, const ElementType* Source)
        {
            Copy(0, Count, Source);
        }

---

I would note that Index can never be smaller than zero (its unsigned).

        FORCEINLINE bool RangeCheck(size_t Index) const
        {
            return (Index >= 0) && (Index < ElementCount);
        }

This sort of suggests you are not checking the warnings (or you don't have warnings set high enough). You should fix all warnings they are errors in your logical thinking.

---

Don't like this.
You are exposing the internal data.

        FORCEINLINE ElementType* GetData()
        FORCEINLINE const ElementType* GetData() const

---

Interesting Name :-)

        FORCEINLINE size_t Slack() const

---

Can't tell if this works.
I am assuming you know how placement new works.

        FORCEINLINE size_t AppendDefaulted(size_t Count)
        {
            size_t StartIndex = AppendUnitialized(Count);
            //
            // I assumes this uses the placement new to construct
            // the elements into uninitialized memory.
            MemoryOperations::ConstructDefaultItems<ElementType>(&Data[StartIndex], Count);
            return StartIndex;
        }

---

Probable Bug.

I can't tell if this works because the interesting part is in Memory::Memmove()!

But you can't do a simple move on objects that have constructors/destructors. You must make sure that the appropriate methods are called. Things that use resources will potential break if you simply copy them.

        FORCEINLINE size_t InsertUninitialized(size_t Index, size_t Count)
        {
            HERMES_ASSERT(Index < ElementCount);
            if (!Count) return -1;
            Resize(ElementCount + Count);
            Memory::Memmove(&Data[Index + Count], &Data[Index], Count * sizeof(ElementType));
            ElementCount += Count;
            return Index;
        }

---

Not sure I understand this:

Do you just add a bunch of uninitalized elements then only initialize one?

        template<typename... ArgsType>
        FORCEINLINE ElementType& EmplaceAt(size_t Index, ArgsType&&... Args)
        {
            InsertUninitialized(Index, 1);
            new (Data + Index) ElementType(MemoryOperations::Forward<ArgsType>(Args)...);
            return Data[Index];
        }

---

The standard library splits this function into two parts. A top() which returns a reference to the last value and a pop() which removes the top value (but does not return anything).

This is because it is more efficient. Your causes multiple copies.

        FORCEINLINE ElementType Pop()
        {
            HERMES_ASSERT(ElementCount > 0)
            auto Result = Data[ElementCount - 1];
            RemoveAt(ElementCount - 1);
            return Result;
        }

---

This is normally called clear().

        FORCEINLINE void Empty(size_t ExtraSlack = 0)

---

Can't use move on objects that have constructors.

        FORCEINLINE void RemoveAt(size_t Index, size_t Count = 1)
        {
            MemoryOperations::DestroyItems(Data + Index, Count);
            Memory::Memmove(Data + Index, Data + Index + Count, Count * sizeof(ElementType));
            ElementCount -= Count;
        }

---

Good.
But what about a const version of the object.

        FORCEINLINE Iterator begin() { return Iterator(Data); }
        FORCEINLINE Iterator end()   { return Iterator(Data + ElementCount); }

        FORCEINLINE ConstIterator cbegin() { return ConstIterator(Data); }
        FORCEINLINE ConstIterator cend()   { return ConstIterator(Data + ElementCount); }

I would add this:

        FORCEINLINE ConstIterator begin() const { return ConstIterator(Data); }
        FORCEINLINE ConstIterator end()   const { return ConstIterator(Data + ElementCount); }

---

Self Plug: I wrote a lot about this here:

https://lokiastari.com/series/

Answer 2

There's absolutely no reason to make this code platform-specific.

Instead of guessing the size of the fundamental types, just use the standard types from the compiler-provided <cstdint> (we should only need std::size_t, I think). The whole reason that this header is provided is so we have a portable means of using information that the compiler knows much better than the programmer.

The ugly dllspec stuff that sensible platforms don't need should all be conditional on a platform-provided macro (I think it's #ifdef _WIN32, but double-check that as I've never written any Windows-specific code).

If you can't trust your compiler to decide when it should inline functions, then switch to a better one.

Even if you want to implement your own log₂ function, don't do this:

    FORCEINLINE uint8 FloorLog2(uint32 Number)
    FORCEINLINE uint8 FloorLog2_64(uint64 Number)

C++ has function overloading so that we don't have to change every function call when we change the type of a variable. And there are much faster and simpler implementations of this function.

Not that any of this is used anywhere, so simpler just to remove it until/unless there's a need. It seems that the only thing used from the MathCommon header is Max(), which is so trivial that it could be added (with static linkage) directly into the Vector header, and not drag all of MathCommon into every program that uses Vector. I'd still recommend using std::max() unless you've done something so terrible in your life that you need a penance.

The naming style looks alien - in C++, we normally use lower case for namespace and function names, Title Case for aggregate type names and template parameters, and UPPER CASE for macros (only).