Indexable versus Iterable Collections

The C++ standard template library design emphasizes collections that support generic iterators. In this post I propose an alternative design approach for collections that uses generic indexers.

In the C++ standard library many collections are iterable. They provide an iterator type that  may support assignment (if the collection is not read-only) and can be incremented and maybe  decremented. The collection returns an iterator representing the first value in the collection  using a "begin()" method, and an "end()" method returns an iterator indicating that the end of  the collection has been reached.

Let's look at how a generic "ScaleVector" procedure might work on an iterable Array collection in C++.

void ScaleVector(Array& xs, int x) {
  for (Array::iterator i = xs.begin();
       i != xs.end();
       ++i)
  {
     *i = *i + x;
  }
}

What this code does is it decouple the notion of iterator from the collection itself. We ask the collection for its iterator, and let the collection class and the iterator takes care of the details of initialization, incrementing, and checking the invariant.

One characteristic of many collections and arrays in particular, is that elements can be accessed using an index. In other words they are indexable. Sometimes having access to the index in a loop is useful. So consider if instead of abstracting the notion of iterator, we abstracted the notion of an  indexer? Then we might be able to write:

void ScaleVector(Array& xs, int x) {
  for (Array::indexer i = xs.begin_index();
       i < xs.end_index();
       ++i)
  {
     xs[i] = xs[i] + x;
  }
}

In this example, the most obvious gains is the improvement to the readability of the assignment statement. An observer can quickly see that the statement "xs[i] = xs[i] + x;" will modify the collection, whereas that information is a bit less obvious in the earlier example's statement "*i = *i + x;".

The power of indexing lies in the fact that they remain valid as long as they remain in a valid range of indexes. So for example, if an array is resized the index remains valid as long as it stays within the valid range.

Consider the following  bad code in C++:

int DontDoThis(std::vector<int> xs, int x) {
  // this example assumes a non-empty vector
  assert(xs.begin() != xs.end());
  std::vector::iterator i = xs.begin();
  xs.resize(xs.size() + 100);
  // bad, bad, bad
  return *i;  
}

STL iterators aren't valid after a collection is resized. This design decision was so that they could be dependent on the memory locations for fast implementation.

An indexer is assumed to remain valid if it is within the valid range, regardless of how memory is arranged. So the following would remain valid:

int DoDoThis(Array<int>& xs, int x) {
  // this example assumes a non-empty array
  assert(xs.begin_index() != xs.end_index());
  Array::index i = xs.begin_index();
  xs.resize(xs.size() + 100);
  return xs[i];  
}

The final question I should address is "why not just use ints"? The answer is another question: Why not use size_t's? Or unsigned longs? Or why not use a pair of value because the internal layout is a two-dimensional array?

The problem with hard-coding ints as your indexing mechanism, or any other particular types is that it locks you into a particular implementation. The internal implementation of the collection is exposed to the consumer of the collection, and any refactoring of the collection type, forces all usage to be rewritten as well. As I imply above, one very nice implementation of an index is to use a pair of values.

So here is one way you might construct an indexable collection:

template<T>
struct Array
{
  std::vector<T> mvec;
  typedef size_t indexer;
  indexer begin_index() const { return 0; }
  indexer end_index() const { return mvec; }
  T& operator[](indexer i) { return mvec[i]; }
  const T& operator[](indexer i) const { return mvec[i]; }
  size_t size() { return mvec.size(); }
  void resize(size_t sz) { mvec.resize(sz); }
  void push(const T& x) { mvec.push_back(x); }
  T& top() { return mvec.back(); }
  const T& top() const { return mvec.back(); }
  void pop() { mvec.pop_back(); }
  void swap(indexer i, indexer j) { if (i != j) std::swap(mvec[i], mvec[j]); }
};