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.