Channels ▼

Christopher Diggins

Dr. Dobb's Bloggers

Indexable versus Iterable Collections

October 31, 2008

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

 

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video