Indexable versus Iterable Collections - InformationWeek
IoT
IoT
Software // Enterprise Applications
Commentary
10/31/2008
12:00 AM
Commentary
Commentary
Commentary
50%
50%

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.

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]); }
}; 

 

Comment  | 
Print  | 
More Insights
Comments
Newest First  |  Oldest First  |  Threaded View
How Enterprises Are Attacking the IT Security Enterprise
How Enterprises Are Attacking the IT Security Enterprise
To learn more about what organizations are doing to tackle attacks and threats we surveyed a group of 300 IT and infosec professionals to find out what their biggest IT security challenges are and what they're doing to defend against today's threats. Download the report to see what they're saying.
Register for InformationWeek Newsletters
White Papers
Current Issue
2017 State of Data and Analytics
Today's companies are differentiating themselves using data analytics, but the journey requires adjustments to people, processes, technology, and culture. 
Video
Slideshows
Twitter Feed
InformationWeek Radio
Archived InformationWeek Radio
Join us for a roundup of the top stories on InformationWeek.com for the week of November 6, 2016. We'll be talking with the InformationWeek.com editors and correspondents who brought you the top stories of the week to get the "story behind the story."
Sponsored Live Streaming Video
Everything You've Been Told About Mobility Is Wrong
Attend this video symposium with Sean Wisdom, Global Director of Mobility Solutions, and learn about how you can harness powerful new products to mobilize your business potential.
Flash Poll