Indexable versus Iterable Collections - InformationWeek
IoT
IoT
Software // Enterprise Applications
Commentary
10/31/2008
12:00 AM
Commentary
Commentary
Commentary
50%
50%
RELATED EVENTS
How Cloud Can Streamline Business Workflow
Jul 11, 2017
In order to optimize your utilization of cloud computing, you need to be able to deliver reliable ...Read More>>

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
[Interop ITX 2017] State Of DevOps Report
[Interop ITX 2017] State Of DevOps Report
The DevOps movement brings application development and infrastructure operations together to increase efficiency and deploy applications more quickly. But embracing DevOps means making significant cultural, organizational, and technological changes. This research report will examine how and why IT organizations are adopting DevOps methodologies, the effects on their staff and processes, and the tools they are utilizing for the best results.
Register for InformationWeek Newsletters
White Papers
Current Issue
IT Strategies to Conquer the Cloud
Chances are your organization is adopting cloud computing in one way or another -- or in multiple ways. Understanding the skills you need and how cloud affects IT operations and networking will help you adapt.
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