End of array points to newly allocated array C++

Question

Using C++, I am trying to create an array that holds pointers to objects I'm storing. But when the array is full, I want to expand the array.

the easy option is to allocate a new array with bigger size, then copy the elements to it, this is quite inefficient, and I thought of another way I want to try to do it:

create array of fixed size X
When full, create a new array, and make the end of the first array point to the start of the first element
Repeat as long as needed

What methods can I use to do that? I thought of one way to do it, but it seems very hacky:

declare all my new array as pointers to object pointer, then reinterprit_cast the filled elements to object pointer.

Note: I know I can use Vector, but I am instructed not to use std library.

Kind Regards,

What you're describing in step two is how [`std::deque`](http://en.cppreference.com/w/cpp/container/deque) is implemented, as a *list* of smaller arrays. — Some programmer dude, Dec 08 '15 at 07:28
You could define a simple structure to do this: `struct Chunk { T *ptr; size_t count; Chunk *next; };`. The memory would, however, not be exactly the same as you describe i.e. the array's end wouldn't've a pointer but this structure would've it. — legends2k, Dec 08 '15 at 07:29
What you're describing is quite similar to a linked list. Another way which is quite common, but only if you can make some estimations about the number of elements and if memory is not severely limited, is just to create an array big enough to hold all future elements. — flowit, Dec 08 '15 at 07:29
"the easy option is to allocate a new array with bigger size, then copy the elements to it, this is quite inefficient" - It depends on how you will access the elements. If after allocation and copying there will be sequential access to all the elements, then allocation+copy (i.e. continous memory area) will be more efficient in future (because of no cache-missing). — vladon, Dec 08 '15 at 07:31
@legends2k and flowit, thank you, a structure linked-list-like seems appropriate, I was trying to keep minimum information, but this seems to be a good solution actually. — Salah Alshaal, Dec 08 '15 at 07:36
@vladon I use binary trees to store the elements, I'm assuming this is sequential, thus my implementation will be slow. — Salah Alshaal, Dec 08 '15 at 07:38
If you really want it the way you describe, perhaps you could go completely low and do a `new char [length]` of required length = `n * sizeof(T) + sizeof(void*)`. Then take a pointer to the beginning of this memory chunk and hand it over as an array and take another pointer to the end of the array where you've the `void*` which you can point to the next chunk. However, this requires mucking around with low-level, so be warned. You may tread on [UB](http://stackoverflow.com/q/2397984/183120) here. — legends2k, Dec 08 '15 at 07:38
Note that if you're using a linked list, you can't use the `[]` operator to access the elements without some work. — Some programmer dude, Dec 08 '15 at 07:39
@JoachimPileborg True; for anything of the `deque` sorts, without overloading `operator[]` using the subscript notation is out of question due to the discontinuity in memory. — legends2k, Dec 08 '15 at 07:41

Alexander V · Answer 1 · 2015-12-08T07:57:01.743

Using C++, I am trying to create an array that holds pointers to objects I'm storing. But when the array is full, I want to expand the array.

With C++ templates and C primitives we can improvise a simple vector like below. And the grow buffer strategy is to double the size when the threshold is met.

#include <iostream>
#include <stdlib.h>

template <typename T>
class MyVector
{
   public:
      MyVector() : m_count(0), m_size(0), m_buffer(0)
      {
          m_size = bufInitSize;
          m_buffer = (T*)malloc(sizeof(T) * bufInitSize);
      }
      ~MyVector()
      {
         if (m_buffer)
            free(m_buffer);
      }
      void add(const T& p)
      {
         if (m_count + 1 >= m_size)
         {
             m_size *= 2;
             m_buffer = (T*)realloc(m_buffer, sizeof(T) * m_size);
         }
         m_buffer[m_count ++ ] = p;

      }
      T& operator[](int idx)
      {
         return m_buffer[idx];
      }

   private:
      static const int bufInitSize = 1024;
      T*  m_buffer;
      int m_count;
      int m_size;
};

void main()
{
   // using MyVector
   MyVector<int*> vctOfIntPtr;
   int n = 100;
   vctOfIntPtr.add(&n);
   int* pN = vctOfIntPtr[0];
   std::cout << *pN;
}

Lucien · Accepted Answer · 2015-12-16T02:41:25.767

There are some good answers in the comments already. I just want to provide a way to achieve exactly the behavior you described.

Since the elements of the array are pointers as well, you can define a union as the element of your array like this:

template<typename T>
union Cell
{
    T* pElm;
    Cell* pNext;//A fixed size array of Cells
}

And then build your array on top of it. For example:

template<typename T>
class SpecialArray
{
public:
    //the next pointer is included
    static const size_t ARRAY_LEN = 1000;// For example
    using Pointer = T*;
    using Segment = Cell<T>[ARRAY_LEN];

protected:
    Segment* pFirst;
    size_t mSize;

public:
    SpecialArray()
        :pFirst(nullptr),mSize(0){}
    SpecialArray(SpecialArray&&){}
    ~SpecialArray(){}

    Pointer& operator[](size_t index)
    {
        Segment* seg = pFirst;
        size_t offest = 0;
        //Search logic...

        return seg[offest]->pElm;
    }
    const Pointer& operator[](size_t index) const;
};

End of array points to newly allocated array C++

2 Answers2