Indexable versus Iterable Collections - InformationWeek

InformationWeek is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them.Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

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

 

We welcome your comments on this topic on our social media channels, or [contact us directly] with questions about the site.
Comment  | 
Print  | 
More Insights
Commentary
Study Proposes 5 Primary Traits of Innovation Leaders
Joao-Pierre S. Ruth, Senior Writer,  11/8/2019
Slideshows
Top-Paying U.S. Cities for Data Scientists and Data Analysts
Cynthia Harvey, Freelance Journalist, InformationWeek,  11/5/2019
Slideshows
10 Strategic Technology Trends for 2020
Jessica Davis, Senior Editor, Enterprise Apps,  11/1/2019
White Papers
Register for InformationWeek Newsletters
Video
Current Issue
Getting Started With Emerging Technologies
Looking to help your enterprise IT team ease the stress of putting new/emerging technologies such as AI, machine learning and IoT to work for their organizations? There are a few ways to get off on the right foot. In this report we share some expert advice on how to approach some of these seemingly daunting tech challenges.
Slideshows
Flash Poll