Vector-like custom container with improved insert performance

Question

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.

• Loki Astari: If you want to insert at the beginning use std::deque
• Mango: @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).
• Martin R: 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 .
• Mango: Does adding to a seperate area count as change? -.-
• Martin R: @Mango: Yes, as explained in the linked-to meta post: "You also should not append your revised code to the question."

Answer 1

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;
 };
}

• Loki Astari: Good recommendations
• Mango: 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
• Mango: 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.
• user128454: @Mango, If you link the updated code (ideally on gcc.godbolt.org), I might be able to help you identify what's going on.
• Mango: codereview.stackexchange.com/questions/179796/vector-replacer