Custom vector that uses less memory than std::vector

Question

I'm using vectors to create matrix and the vector itself is consuming a large space. So I implemented a version that would use less memory and, if possible, be as fast or faster than std::vector.

How can I improve the performance and is there anything that should be changed?

#ifndef __DATAARRAY_H__
#define __DATAARRAY_H__
#include <memory>
#include "core/Exceptions/ArgumentException.h"

template <size_t S> class Sizer { };
    namespace Core
    {
#pragma pack(1)
        template <class DataType, class MaxSizeType>
        class DataArray
        {
        public:
            DataArray() :m_iDataSize(0), m_aData(nullptr), m_iDataCapacity(0){
            }
            DataArray(MaxSizeType size) :m_iDataSize(0){
                _Reserve(size);
            }

            DataArray(const DataArray& dArray)
            {
                _Reserve(dArray.m_iDataCapacity);
                _CopyData(dArray);
            }
            void reserve(MaxSizeType size){
            }

            void resize(MaxSizeType size){
                if (size < m_iDataSize)
                {
                    _Delete_Data(m_aData + size, m_aData + m_iDataSize);
                    m_iDataSize = size;
                }
                else if (m_iDataSize < size){
                    _Reserve(size);
                    DataType* pData = (m_aData + m_iDataSize);
                    for (; pData < m_aData + size; ++pData) {
                        new (pData)DataType;
                    }
                    m_iDataSize = size;
                }
            }

            void push_back(DataType element){
                if (m_iDataCapacity <= m_iDataSize)
                {
                    _Reserve(m_iDataCapacity + 1);
                }
                new (m_aData + m_iDataSize)DataType(element);
                m_iDataSize++;
            }

            DataType& operator[](MaxSizeType id)
            {
                if (id < 0 || id >= size()) 
                   throw std::invalid_argument("Not enought memory");
                return m_aData[id];
            }

            DataType& operator=(const DataArray& dArray)
            {
                if (this == &dArray)
                    return *this;
                _Delete_m_aData();
                _Reserve(dArray.m_iDataCapacity);
                _CopyData(dArray);
                return *this;
            }

            MaxSizeType size(){
                return m_iDataSize;
            }

            MaxSizeType Capacity(){
                return m_iDataCapacity;
            }

            ~DataArray(){
                _Delete_m_aData();
            }
        protected:
            inline void _Reserve(MaxSizeType size){
                if (size > m_iDataCapacity){
                    DataType* new_Data = (DataType*)std::realloc(m_aData, sizeof(DataType)*size);
                    if (new_Data != NULL){
                        m_aData = new_Data;
                        m_iDataCapacity = size;
                    }
                    else{
                        _Delete_m_aData();
                        throw std::invalid_argument("Not enought memory");
                    }
                }
            }
            inline void _CopyData(const DataArray& dArray){
                DataType* pOrig = dArray.m_aData;
                DataType* pDest = m_aData;
                DataType* pOriEnd = pOrig + dArray.m_iDataSize;
                for (; pOrig < pOriEnd; ++pDest, ++pOrig)
                {
                    new (pDest)DataType(*pOrig);
                }
                m_iDataSize = dArray.m_iDataSize;
            }

            inline void _Delete_m_aData()
            {
                _Delete_Data(m_aData, m_aData + m_iDataSize);
                m_iDataSize = 0;
                m_iDataCapacity = 0;
                free(m_aData);
            }

            inline void _Delete_Data(DataType* begin, DataType* end)
            {
                DataType* pData = begin;
                for (; pData < end; ++pData) {
                    ((DataType*)pData)->~DataType();
                }
            }
            MaxSizeType m_iDataCapacity;
            MaxSizeType m_iDataSize;
            DataType* m_aData;
        };
#pragma pack()
}
#endif

Answer 1

Size Requirements

You talk about wanting to "use less memory" than std::vector. But std::vector doesn't use that much memory. It's three pointers. I guess if you set your MaxSizeType to int instead of size_t, you can have a vector of 16 bytes instead of 24, but I would really have to see what you're doing that that difference should matter.

Performance

There's two glaring issues that jump out at me as far as performance goes. I suspect this would be substantially slower than std::vector.

First one is on push_back:

void push_back(DataType element){
    if (m_iDataCapacity <= m_iDataSize)
    {
        _Reserve(m_iDataCapacity + 1);
    }
    new (m_aData + m_iDataSize)DataType(element);
    m_iDataSize++;
}

First, you're taking your DataType by value. That's incurring an extra copy, which you don't want to do. Secondly, your resize policy is increasing capacity by one. This means that your push_back() is expected \$O(n)\$. There's an easy explanation for this too: once we reach our capacity, we will have to _Reserve() on every subsequent push_back(), which means we're copying \$n\$ elements every time. The right thing to do is to increase capacity by a constant factor.

The next issue comes from indexing:

DataType& operator[](MaxSizeType id)
{
    if (id < 0 || id >= size()) 
       throw std::invalid_argument("Not enought memory");
    return m_aData[id];
}

First, the exception is misleading. A better exception type would be std::out_of_range, and a message indicating this - since the issue isn't that we ran out of memory. That's an error that we would throw if allocation fails (in _Reserve, you do the same thing - there you should throw std::bad_alloc).

But the main problem is this kills performance because on every lookup, we have a branch. Every time. And branches are slow. That's why on std::vector, operator[] is defined simply as:

reference
operator[](size_type __n) 
{    
    return *(this->_M_impl._M_start + __n);
}  

If you want bounds checking, you can provide a separate member function called at().

Other Issues

You're missing a lot of other nice features that std::vector provides:

• Missing iterators, begin(), and end().
• Missing const overloads of member functions

• This cast is unnecessary, since pData is already a DataType.

  ((DataType*)pData)->~DataType();
  

Answer 2

• There's an issue with your naming convention. Names starting with an underscore, followed by a capital letter (e.g.: _Reserve) and double underscore (e.g.: __DATAARRAY_H__), are using a notation reserved for future expansion of the Standard Library and compiler extensions. To avoid name clashes, prefer not using the underscore prefix on your own names. You can find more details about the naming rules of C++ in here: What are the rules about using an underscore in a C++ identifier?

• None of your class methods are const, which means I can't, for instance, call operator[] on a const DataArray instance. Methods that don't change member data should always be declared as const. More about const member functions in here.

• Consider adding a move constructor and operator. It might optimize your class quite a bit by allowing the compiler to avoid unnecessary copies.

Answer 3

realloc essentially does a memcpy to the newly allocated buffer. This will create issues if the move construction is non-trivial and/or the moved-from object still needs proper destruction.

If this is the case for the DataType then you should allocate a new buffer and placement-move-construct into the new buffer, destruct the objects in the old buffer and finally free the old buffer.

Answer 4

Reserved Identifiers:

An identifier with a leading underscore followed by a capital letter is reserved for use by the system in all scopes.

Thus the following are bad:

            inline void _Reserve(MaxSizeType size)
            inline void _CopyData(const DataArray& dArray)
            inline void _Delete_m_aData()    
            inline void _Delete_Data(DataType* begin, DataType* end)

Use constructors to initialize all members

            DataArray(MaxSizeType size) :m_iDataSize(0){
                _Reserve(size);
            }

Looks good. But _Reserve() does not always initialize all the remaining members!! (If size == 0) the two remaining members are left undefined.

Also doing this is bad practice because you are assuming that somebody that modifies _Reserve() knows the contract it has with the constructor (ie that it must initialize those two members). The contract is not specified anywhere...

Dead code should be removed

            void reserve(MaxSizeType size){
            }

Pass values by reference.

            void push_back(DataType element){
                         ///     ^^^   parameter copied

Resizing for more than you need.

                if (m_iDataCapacity <= m_iDataSize)
                {
                    _Reserve(m_iDataCapacity + 1);
                }

This is very inefficient if you add lots of elements in a row. Once you reach the initial size every time you push back you are reserving more capacity. When you hit the limit reserve more than you need so that you don't have to reserve every time.

Provide const versions of some methods:

            DataType& operator[](MaxSizeType id)

There should be two version of this method. This will allow your object to use in const contexts (thus allowing you to build const correct code).

            DataType&       operator[](MaxSizeType id);
            DataType const& operator[](MaxSizeType id) const;

Operator [] is non checking

                if (id < 0 || id >= size()) 
                   throw std::invalid_argument("Not enought memory");

For efficiency operator[] does not check bounds (as after testing you have fixed all those bugs). For code where the index is calculated at run time and needs to be validated you usually provide the method at(MaxSizeType id).

That's not the correct exception:

                if (id < 0 || id >= size()) 
                   throw std::invalid_argument("Not enought memory");

This is an out of range access. There is already an exception specifically for this. Alos it has nothing to do with "enought" memory.

Prefer to use the copy and swap idiom

This assignment constructor is not exception safe.

If _Reserve throws an exception then the objects data is not in a consistent state. Because you have called the destructor on all the members (but not reset the size of the array and not copied new values into their place).

You should never destroy old data if there is a possibility of failure.

            DataType& operator=(const DataArray& dArray)
            {
                if (this == &dArray)
                    return *this;
                _Delete_m_aData();
                _Reserve(dArray.m_iDataCapacity);  // If this throws your out of luck.
                _CopyData(dArray);                 // Because this is not called
                return *this;                      // to set the correct members.
            }

These look like it should be const methods.

            MaxSizeType size(){
                return m_iDataSize;
            }

            MaxSizeType Capacity(){
                return m_iDataCapacity;
            }

There is a bug in _Reserve.

If this is called from the assignment operator after all the elements have been deleted. Now if there is a realoc failure. The you are calling _Delete_m_aData() which calls _Delete_Data() which calls the destructor on the objects again. Even though they have previously been destroyed.

                    else{
                        _Delete_m_aData();
                        throw std::invalid_argument("Not enought memory");
                    }

Different types of brace style

Be consistent.

        DataArray(const DataArray& dArray)
        {
            _Reserve(dArray.m_iDataCapacity);
            _CopyData(dArray);
        }
        void reserve(MaxSizeType size){
        }

Move Semantics not supported.

Your class does not provide move semantics. Supporting them would make your class a whole bunch more efficient it a lot of situations.