C++ reference_array2011-02-17

One thing C++ programmers quickly find is that it is not possible to create a container of references. The usual answer is to use a container of pointers. Usually, it is recommended to use std::vector, which is a terrible choice for POD; but C++0x will at least have std::array, even though that has the downside of being a static size.

However, regardless of container choice, an array of pointers is annoying to work with. Adding items requires & before each object, and accessing items requires * before each object (in most cases, -> after will also work.)

But this is C++. If we wanted to poke at pointers, we could use C89. Surely there's a better way? Well, there is. I'm honestly surprised, this is one of the few templates classes I've come up with that has no known analogue even in boost. This seems to be completely unknown or ignored, and I posit that it should not be.

reference_array

It's a simple solution, actually. All we need to do is create an internal array of pointers. To add pointers, get pointers to the passed references. To read out references, dereference the pointers.

Here is my C++0x implementation, with full support for dynamic realloc() resizing, amortized growth, foreach() iteration, copy and move semantics:

template<typename T> struct reference_array {
protected:
  typedef typename std::remove_reference<T>::type *Tptr;
  Tptr *pool;
  unsigned poolsize, buffersize;

public:
  unsigned size() const { return buffersize; }
  unsigned capacity() const { return poolsize; }

  void reset() {
    if(pool) free(pool);
    pool = 0;
    poolsize = 0;
    buffersize = 0;
  }

  void reserve(unsigned newsize) {
    if(newsize == poolsize) return;

    pool = (Tptr*)realloc(pool, newsize * sizeof(T));
    poolsize = newsize;
    buffersize = min(buffersize, newsize);
  }

  void resize(unsigned newsize) {
    if(newsize > poolsize) reserve(bit::round(newsize));  //round up to nearest power of two
    buffersize = newsize;
  }

  void append(const T data) {
    unsigned index = buffersize++;
    if(index >= poolsize) resize(index + 1);
    pool[index] = &data;
  }

  template<typename... Args> reference_array(Args&... args) : pool(0), poolsize(0), buffersize(0) {
    construct(args...);
  }

  ~reference_array() {
    reset();
  }

  reference_array& operator=(const reference_array &source) {
    if(pool) free(pool);
    buffersize = source.buffersize;
    poolsize = source.poolsize;
    pool = (Tptr*)malloc(sizeof(T) * poolsize);
    memcpy(pool, source.pool, sizeof(T) * buffersize);
    return *this;
  }

  reference_array& operator=(const reference_array &&source) {
    if(pool) free(pool);
    pool = source.pool;
    poolsize = source.poolsize;
    buffersize = source.buffersize;
    source.pool = 0;
    source.reset();
    return *this;
  }

  inline T operator[](unsigned index) {
    if(index >= buffersize) throw "reference_array[] out of bounds";
    return *pool[index];
  }

  inline const T operator[](unsigned index) const {
    if(index >= buffersize) throw "reference_array[] out of bounds";
    return *pool[index];
  }

private:
  void construct() {
  }

  void construct(const reference_array &source) {
    operator=(source);
  }

  void construct(const reference_array &&source) {
    operator=(std::move(source));
  }

  template<typename... Args> void construct(T data, Args&... args) {
    append(data);
    construct(args...);
  }
};

//foreach() concept support; no iterators required
template<typename T> struct has_size<reference_array<T>> { enum { value = true }; };

I chose to require the & inside the template type, as an additional visual indicator that the container holds reference types; although this is technically optional. I did not get fancy, but we could specialize the template against std::has_reference to be 100% safe.

Now, let's look at what we can do with this new container. Let's say you were implementing a static function, RadioBox::group(), and you wanted it to take a list of RadioBox controls that should be linked together, for the purpose of stating that only one of the controls in the list can be checked at a time.

Before:

template<typename... Args> static void RadioBox::group(Args... args) { groupList({ args... }); }
static void RadioBox::groupList(pointer_array<RadioBox*> const &list) {
  foreach(item, list) item->setGroup(list);  //link all items to the same list
  if(list.size()) list[0]->setChecked();     //check first item
}
RadioBox radioAuto, radioEnable, radioDisable;
RadioBox::group(&radioAuto, &radioEnable, &radioDisable);

After:

template<typename... Args> static void RadioBox::group(Args... args) { groupList({ args... }); }
static void RadioBox::groupList(reference_array<RadioBox&> const &list) {
  foreach(item, list) item.setGroup(list);  //link all items to the same list
  if(list.size()) list[0].setChecked();     //check first item
}
RadioBox radioAuto, radioEnable, radioDisable;
RadioBox::group(radioAuto, radioEnable, radioDisable);

Or for a smaller example, say you wanted to increment a list of integers:

Before:

pointer_array<int*> list = { &a, &b, &c, &d /* , 0 would cause a crash */ };
foreach(item, list) ++(*item);
//foreach(item, list) if(item) ++(*item);  //this is safer

After:

reference_array<int&> list = { a, b, c, d /* null items are not possible */ };
foreach(item, list) ++item;

There are actually quite a few different uses for this concept. The reason we use references instead of pointers, is to avoid derefencing, and to state that our references should never be null. This is useful information to convey. Of course, because we are storing pointers internally, the compiler optimization benefits of references are lost; but I still find the other benefits useful anyway.

I have found this to be a great way to keep a list of zero or more items, and to have easy iteration and access of them via foreach().

Final words

I'm not saying this is some major concept that is going to greatly clean up your code; far from it. But it is a nice syntactical improvement, and it's a shame one has to create their own container to take advantage of it.