Implementing incremental array in C++

Question

I want to implement an array that can increment as new values are added. Just like in Java. I don't have any idea of how to do this. Can anyone give me a way ?

This is done for learning purposes, thus I cannot use std::vector.

Answer 1

I would like to take the opportunity to interest you in an interesting but somewhat difficult topic: exceptions.

• If you start allocating memory yourself and subsequently playing with raw pointers, you will find yourself in the difficult position of avoiding memory leaks.
• Even if you are entrusting the book-keeping of the memory to a right class (say std::unique_ptr<char[]>), you still have to ensure that operations that change the object leave it in a consistent state should they fail.

For example, here is a simple class with an incorrect resize method (which is at the heart of most code):

template <typename T>
class DynamicArray {
public:
  // Constructor
  DynamicArray(): size(0), capacity(0), buffer(0) {}

  // Destructor
  ~DynamicArray() {
    if (buffer == 0) { return; }

    for(size_t i = 0; i != size; ++i) {
      T* t = buffer + i;
      t->~T();
    }

    free(buffer); // using delete[] would require all objects to be built
  }

private:
  size_t size;
  size_t capacity;
  T* buffer;
};

Okay, so that's the easy part (although already a bit tricky).

Now, how do you push a new element at the end ?

template <typename T>
void DynamicArray<T>::resize(size_t n) {
  // The *easy* case
  if (n <= size) {
    for (; n < size; ++n) {
      (buffer + n)->~T();
    }
    size = n;
    return;
  }

  // The *hard* case

  // new size
  size_t const oldsize = size;
  size = n;

  // new capacity
  if (capacity == 0) { capacity = 1; }
  while (capacity < n) { capacity *= 2; }

  // new buffer (copied)
  try {

    T* newbuffer = (T*)malloc(capacity*sizeof(T));

    // copy
    for (size_t i = 0; i != oldsize; ++i) {
      new (newbuffer + i) T(*(buffer + i));
    }

    free(buffer)
    buffer = newbuffer;

  } catch(...) {
    free(newbuffer);
    throw;
  }
}

Feels right no ?

I mean, we even take care of a possible exception raised by T's copy constructor! yeah!

Do note the subtle issue we have though: if an exception is thrown, we have changed the size and capacity members but still have the old buffer.

The fix is obvious, of course: we should first change the buffer, and then the size and capacity. Of course...

But it is "difficult" to get it right.

---

I would recommend using an alternative approach: create an immutable array class (the capacity should be immutable, not the rest), and implement an exception-less swap method.

Then, you'll be able to implement the "transaction-like" semantics much more easily.

Answer 2

An array which grows dynamically as we add elements are called dynamic array, growable array, and here is a complete implementation of a dynamic array .

Answer 3

Here's a starting point: you only need three variables, nelems, capacity and a pointer to the actual array. So, your class would start off as

class dyn_array
{
    T *data;
    size_t nelems, capacity;
};

where T is the type of data you want to store; for extra credit, make this a template class. Now implement the algorithms discussed in your textbook or on the Wikipedia page on dynamic arrays.

Note that the new/delete allocation mechanism does not support growing an array like C's realloc does, so you'll actually be moving data's contents around when growing the capacity.

Answer 4

In C and C++ array notation is basically just short hand pointer maths. So in this example.

    int fib [] = { 1, 1, 2, 3, 5, 8, 13};

This:

    int position5 = fib[5];

Is the same thing as saying this:

    int position5 = int(char*(fib)) + (5 * sizeof(int));

So basically arrays are just pointers.

So if you want to auto allocate you will need to write some wrapper functions to call malloc() or new, ( C and C++ respectively).

Although you might find vectors are what you are looking for...