2
\$\begingroup\$

I rolled a little container class (just for couriosity) which was meant to be able as a vector replacement in some cases.

(Whoever wonders about the lack of move semantic etc, I just left it out due to lazyness.)

#ifndef GUARD_HEADER_vector_h
#define GUARD_HEADER_vector_h

#include <iterator>

/*Custom-Container implementation which can replace std::vector in some cases.
  The Container has an interface close to the std::vector interface with some little changes.
  The goal was to improve the insertion and erasure performance of array containers while still providing
  compatability with regular array functions and standard algorithms*/

namespace custom
{
    typedef unsigned int size_a;
    typedef char         byte;

    //Minimal allocator interface to unify allocators for later tests
    class iallocator
    {
    public:
        virtual void*       allocate(size_a)  = 0;
        virtual void        deallocate(void*) = 0;
        virtual iallocator* copy()            = 0;
    };

    //Minimalistic default allocator
    class allocator : public iallocator
    {
    public:
        void* allocate(size_a n)
        {
            return new byte[n];
        }

        void deallocate(void* memory)
        {
            delete[] (byte*)memory;
        }

        iallocator* copy()
        {
            return new allocator;
        }

    private:
    };

    //A STL-vector !LIKE! container which provides faster insert and erase operatons by the costs of a higher memory demand. If used with C-Libraries it's recommended to call shrink before the interaction!
    template <class T> class container
    {
    public:
        typedef T                    value_type;
        typedef T*                   pointer;
        typedef T&                   reference;
        typedef pointer*             access;

        //Minimal iterator implementation to interact with algorithms
        class iterator
        {
        public:
            typedef T                         value_type;
            typedef T&                        reference;
            typedef T*                        pointer;
            typedef unsigned int              difference_type;
            typedef std::forward_iterator_tag iterator_category;

            iterator(access ptr)
                : m_Content(ptr)
            {}

            T& operator *() const
            {
                return **m_Content;
            }

            pointer operator->() const
            {
                return *m_Content;
            }

            iterator& operator++()
            {
                ++m_Content;

                return *this;
            }

            iterator& operator--()
            {
                --m_Content;

                return *this;
            }

            iterator& operator++(int)
            {
                ++m_Content;

                return *this;
            }

            iterator& operator--(int)
            {
                --m_Content;

                return *this;
            }

            bool operator == (const iterator& it) const
            {
                return it.m_Content == m_Content;
            }

            bool operator != (const iterator& it) const
            {
                return it.m_Content != m_Content;
            }

            int operator - (const iterator& it) const
            {
                return m_Content - it.m_Content;
            }

            iterator operator + (int n) const
            {
                return iterator(m_Content + n);
            }

            iterator operator - (int n) const
            {
                return iterator(m_Content - n);
            }

            bool operator < (const iterator& it) const
            {
                return it.m_Content < m_Content;
            }

            bool operator > (const iterator& it) const
            {
                return it.m_Content > m_Content;
            }

        private:
            access m_Content;
        };

        container(int n = 30, iallocator* alloc = new allocator)
            : m_Allocator(alloc), m_Size(0), m_NumArrays(1), m_ArrayCapacity(n)
        {
            m_Memory  = (access )alloc->allocate(sizeof(pointer));
            *m_Memory = (pointer)alloc->allocate(sizeof(T) * n);

            m_Access  = (access )alloc->allocate(sizeof(pointer) * n);

            for (int currentAccess = 0; n > currentAccess; ++currentAccess)
            {
                m_Access[currentAccess] = &m_Memory[0][currentAccess];
            }
        }

        container(const container& mv)
            : m_Allocator(mv.m_Allocator->copy()), m_Size(0), m_NumArrays(1), m_ArrayCapacity(mv.capacity())
        {
            m_Memory  = (access )alloc->allocate(sizeof(pointer));
            *m_Memory = (pointer)alloc->allocate(sizeof(T) * mv.capacity());

            m_Access  = (access )alloc->allocate(sizeof(pointer) * mv.capacity());

            for (int element = 0; mv.size() > element; ++element)
            {
                push_back(mv[element]);
            }
        }

        ~container()
        {
            clear();

            for (int index = 0; m_NumArrays > index; ++index)
            {
                m_Allocator->deallocate(m_Memory[index]);
            }

            m_Allocator->deallocate(m_Memory);
            m_Allocator->deallocate(m_Access);

            delete m_Allocator;

            m_Memory    = nullptr;
            m_Access    = nullptr;
            m_Allocator = nullptr;
        }

        container& operator = (const container& mv)
        {
            clear();

            for (int element = 0; mv.size() > element; ++element)
            {
                push_back(mv[element]);
            }

            return *const_cast<container<T>*>(this);
        }

        //Reserve memory for n elements (No instances are created)
        void reserve(int n)
        {
            resize(n);
        }

        //Add element to the end of the container
        void push_back(const T& value)
        {
            if (m_Size == m_ArrayCapacity * m_NumArrays)
            {
                resize();
            }

            int memoryIndex = m_Size / m_ArrayCapacity;
            int arrayIndex  = m_Size - (memoryIndex * m_ArrayCapacity);

            new(&m_Memory[memoryIndex][arrayIndex])T(value);

            ++m_Size;
        }

        //Erase last element on container
        void pop_back()
        {
            pointer last = m_Access[m_Size - 1];

            last->~T();

            --m_Size;
        }

        //Insert element to container[pos]
        void insert(int pos, const T& value)
        {
            if (pos < 0 || pos >= m_Size && m_Size != 0)
            {
                return; //No exception planned
            }

            if (m_Size == m_ArrayCapacity * m_NumArrays)
            {
                resize();
            }

            pointer acc = m_Access[m_Size];

            memmove(m_Access + pos + 1, m_Access + pos, (m_Size - pos) * sizeof(pointer));

            m_Access[pos] = acc;
            new(acc)T(value);

            ++m_Size;
        }

        //Insert element to container[it]
        void insert(iterator it, const T& value)
        {
            int pos = it - begin();

            if (pos < 0 || pos >= m_Size && m_Size != 0)
            {
                return; //No exception planned
            }

            if (m_Size == m_ArrayCapacity * m_NumArrays)
            {
                resize();
            }

            pointer acc = m_Access[m_Size];

            memmove(m_Access + pos + 1, m_Access + pos, (m_Size - pos) * sizeof(pointer));

            m_Access[pos] = acc;
            new(acc)T(value);

            ++m_Size;
        }

        //Erase container element [n]
        void erase(int pos)
        {
            if (pos < 0 || pos >= m_Size && m_Size != 0)
            {
                return; //No exception planned
            }

            --m_Size;

            pointer acc = m_Access[pos];

            memmove(m_Access + pos, m_Access + pos + 1, (m_Size - pos) * sizeof(pointer));

            m_Access[m_Size] = acc;
            acc->~T();
        }

        //Erase container element at iterator it
        void erase(iterator it)
        {
            int pos = it - begin();

            if (pos < 0 || pos >= m_Size && m_Size != 0)
            {
                return; //No exception planned
            }

            --m_Size;

            pointer acc = m_Access[pos];

            memmove(m_Access + pos, m_Access + pos + 1, (m_Size - pos) * sizeof(pointer));

            m_Access[m_Size] = acc;
            acc->~T();
        }

        //Acess to array[n]
        T& operator[](int n)
        {
            return *m_Access[n];
        }

        //Acess to array[n]
        T& at(int n) const
        {
            //No boundry-check planned

            return *m_Access[n];
        }

        //Returns container size
        int size() const
        {
            return m_Size;
        }

        //Returns container capacity
        int capacity() const
        {
            return m_ArrayCapacity * m_NumArrays;
        }

        //Check if container is empty
        bool empty() const
        {
            return m_Size == 0;
        }

        //Pack container content into single memory chunk of container::size()
        void shrink()
        {
            pointer  array  = (pointer)m_Allocator->allocate(sizeof(T) * m_Size);
            access   memory = (access )m_Allocator->allocate(sizeof(pointer));

            *memory = array;

            access acc      = (access )m_Allocator->allocate(sizeof(pointer) * m_Size);

            for (int index = 0; m_Size > index; ++index)
            {
                new(&array[index])T(*m_Access[index]);
                acc[index] = &array[index];
            }

            for (int index = 0; m_NumArrays > index; ++index)
            {
                m_Allocator->deallocate(m_Memory[index]);
            }

            m_Allocator->deallocate(m_Memory);
            m_Allocator->deallocate(m_Access);

            m_NumArrays = 1;
            m_ArrayCapacity = m_Size;

            m_Memory = memory;
            m_Access = acc;
        }

        //Swaps content with another custom::container
        void swap(container<T>& mv)
        {
            access      memory        = m_Memory;
            access      access        = m_Access;

            iallocator* allocator     = m_Allocator;

            int         size          = m_Size;
            int         numArrays     = m_NumArrays;
            int         arrayCapacity = m_ArrayCapacity;

            m_Memory                  = mv.m_Memory;
            m_Access                  = mv.m_Access;

            m_Allocator               = mv.m_Allocator;

            m_Size                    = mv.m_Size;
            m_NumArrays               = mv.m_NumArrays;
            m_ArrayCapacity           = mv.m_ArrayCapacity;

            mv.m_Memory               = memory;
            mv.m_Access               = access;

            mv.m_Allocator            = allocator;

            mv.m_Size                 = size;
            mv.m_NumArrays            = numArrays;
            mv.m_ArrayCapacity        = arrayCapacity;
        }

        //Returns first element
        T& front() const
        {
            return at(0);
        }

        //Returns last element
        T& back() const
        {
            return at(m_Size - 1);
        }

        //Clears container (no memory is freed!)
        void clear()
        {
            for (int counter = 0; m_Size > counter; ++counter)
            {
                pop_back();
            }
        }

        //Returns iterator to the container begin
        iterator begin() const
        {
            return iterator(m_Access);
        }

        //Returns iterator to the container end
        iterator end() const
        {
            return iterator(m_Access + m_Size);
        }

        //Returns pointer to the first memory block in the container
        pointer data() const
        {
            return m_Memory[0];
        }

    private:
        void resize()
        {
            access tmp  = (access)m_Allocator->allocate(sizeof(pointer) * (m_NumArrays + 1));
            access acc  = (access)m_Allocator->allocate(sizeof(pointer) * (m_NumArrays + 1) * m_ArrayCapacity);

            for (int current = 0; m_NumArrays > current; ++current)
            {
                tmp[current] = m_Memory[current];
            }

            for (int current = 0; m_Size > current; ++current)
            {
                acc[current] = m_Access[current];
            }

            tmp[m_NumArrays] = (pointer)m_Allocator->allocate(sizeof(T) * m_ArrayCapacity);

            for (int current = 0; m_ArrayCapacity > current; ++current)
            {
                acc[current + m_Size] = &tmp[m_NumArrays][current];
            }

            m_Allocator->deallocate(m_Memory);
            m_Memory = tmp;

            m_Allocator->deallocate(m_Access);
            m_Access = acc;

            ++m_NumArrays;
        }

        void resize(int n)
        {
            if (n < m_Size)
            {
                return; //No exception planned
            }

            pointer  array  = (pointer)m_Allocator->allocate(sizeof(T) * n);
            access   memory = (access )m_Allocator->allocate(sizeof(pointer));

            *memory = array;

            access acc      = (access )m_Allocator->allocate(sizeof(pointer) * n);

            for (int index  = 0; n > index; ++index)
            {              
                acc[index]  = &array[index];
            }              

            for (int index  = 0; m_Size > index; ++index)
            {
                new(&array[index])T(*m_Access[index]);
            }

            for (int index = 0; m_NumArrays > index; ++index)
            {
                m_Allocator->deallocate(m_Memory[index]);
            }

            m_Allocator->deallocate(m_Memory);
            m_Allocator->deallocate(m_Access);

            m_NumArrays = 1;
            m_ArrayCapacity = n;

            m_Memory = memory;
            m_Access = acc;
        }

        access m_Memory;
        access m_Access;

        iallocator* m_Allocator;

        int m_Size;
        int m_NumArrays;
        int m_ArrayCapacity;
    };
}

#endif//GUARD_HEADER_vector_h

Test methology: I decided to try the worst case example (insert(begin(), xyz) to look how the performance can differ between the stl-vector and my custom-container.

#include "customcontainer.h"
#include <archive.h> //custom utility header, not included! contains timer

int main()
{
    custom::container<std::string> vc;

    vc.reserve(1000000);

    custom::delta_timer timer;

    timer.start();

    for (int i = 0; 50000 > i; ++i)
    {
        vc.insert(vc.begin(), mango::to_string(i));
    }

    vc.shrink(); //Shrink reorders both arrays of the container that the access pointer and the elements are in the right order. 
                 //Basically only needed if the container is used with c-libraries but included to bring up a fair end result.

    timer.stop();

    std::cout << timer.totalTime() << " " << vc.size();

    std::for_each(vc.begin(), vc.end(), [](std::string& str)->void {std::cout << str; mango::mgetch();  });

    return 0;
}

The 50000 insert(begin(), xyz) call are taking 0,25 seconds (avg.) on the custom::container and 18.5 seconds (avg.) on the std::vector.

The push_back(xyz) performance of both containers is pretty similar. (0.05 seconds avg.)

My system: I7-6600U @2,6 GHz, 8GB RAM, windows 7 64 bit.

The compiler I use: MSVC2015

With smaller types like int and characters, the difference becomes much smaller since shifting ints is nearly as fast as shifting pointers. The lager the elements are, the bigger get's the difference between the custom::container and the std::vector. The insert performance is still worlds apart from a std::list, but in my opinion, the custom::container does perform very well.

I left out exceptions on purpose since the container isn't meant to go productive and I see no reason to implement them on a "curiousity project".

I am open for any constructive ideas to improve the general container design or possibilities to improve the performance even further.

\$\endgroup\$
  • \$\begingroup\$ If you want to insert at the beginning use std::deque \$\endgroup\$ – Martin York Nov 4 '17 at 3:28
  • \$\begingroup\$ @Loki Astari deque can't interact with c-libraries due to the lack of continous memory. Deque can't fully interact with graohics api's since they also require that quite often (sending vertices to the gpu for instance). \$\endgroup\$ – Mango Nov 4 '17 at 9:11
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Martin R Nov 4 '17 at 9:35
  • \$\begingroup\$ Does adding to a seperate area count as change? -.- \$\endgroup\$ – Mango Nov 4 '17 at 9:41
  • \$\begingroup\$ @Mango: Yes, as explained in the linked-to meta post: "You also should not append your revised code to the question." \$\endgroup\$ – Martin R Nov 4 '17 at 9:43
4
\$\begingroup\$

Instead of going through every little improvement one-by-one, I'm going to make two big sweeping recommendations:

  1. The fact that you are making a std::vector<> alternative does not mean that you shouldn't implement your logic using stl containers. Expressing your code using the STL containers is going to give you safety, move semantics, and all that good stuff while maintaining your lazyness!

  2. On top of that, if you use actual indices instead of double pointers for the index table, you can greatly simplify the resizing process, and maintain sane invariants with a lot less pain.

Check this out, so much nicer:

namespace custom {
  template<typename T, typename Alloc=std::allocator<T>>
  class container {
  public:

    T& operator[](std::size_t id) {
      return objects[indices[id]];
    }
  //etc...
  private:
    std::vector<std::size_t> indices;
    std::vector<T, Alloc> objects;
  };
}
\$\endgroup\$
  • \$\begingroup\$ Good recommendations \$\endgroup\$ – Martin York Nov 4 '17 at 5:21
  • \$\begingroup\$ Since I appreciate your feedback, I implemented your approach for the container (at least the baseline of it). It's a good approach to the solution. I tested it very few but from what I've got from my first tests, I am very satisfied \$\endgroup\$ – Mango Nov 4 '17 at 9:02
  • \$\begingroup\$ Ok, I tested your implementation under some different systems which lead to very different results. If I use the vector implementation on my Ryzen 5 system, you idea performs nearly identical to my implementation (0.3s to 0.33s, which should be measurment failure). Under my I7 system on the other hand, you idea is a lot slower than my implementation. (0.25 to 0.9) I am still try to figgure out why exactly that happens, but I will tell if I got something new. \$\endgroup\$ – Mango Nov 7 '17 at 6:57
  • \$\begingroup\$ @Mango, If you link the updated code (ideally on gcc.godbolt.org), I might be able to help you identify what's going on. \$\endgroup\$ – Frank Nov 7 '17 at 7:26
  • \$\begingroup\$ codereview.stackexchange.com/questions/179796/vector-replacer \$\endgroup\$ – Mango Nov 7 '17 at 7:31

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.