More C++ Idioms/Iterator Pair

Iterator Pair

Intent

Specify a range of data values without worrying about the underlying data structure used by the data values.

Also Known As

Sometimes this is referred to as an Iterator Range.

Motivation

It is well understood that it is useful to create a vector<int> from another vector<int> using a copy constructor. Similarly, it is useful to create a vector<double> from a vector<int> using Coercion by Member Template idiom applied on a member template constructor. A code example is given below.

template <class T>
class vector
{
  public:
    vector (const vector<T> &); // copy constructor
    template <class U>
    vector (const vector<U> &); // constructor using Coercion by Member Template Idiom.
};

The vector interface is still not flexible enough for some needs. For example, A vector can't create itself from a list or a set or a POD array.

template <class T>
class vector
{
  public:
    vector (const list<T> &); 
    // constructor must know the interface of list<T> (not necessarily std::list)
    vector (const set<T> &); 
    // constructor must know the interface of set<T> (not necessarily std::set)
    vector (const T * pod_array);
    // another constructor - does not know where pod_array ends - too inflexible!
};

Iterator-pair is an idiom that addresses this challenge. It is based on the Iterator design pattern (obviously!) Iterator pattern intent: Provide an object which traverses some aggregate structure, abstracting away assumptions about the implementation of that structure.

Solution and Sample Code

A pair of iterators is used to designate a beginning and an end of a range of values. By virtue of the iterator design pattern whoever (in our example vector) uses iterator pair idiom can access the range without worrying about the implementation of the aggregate data structure. The only requirement is that the iterators should expose a fixed, minimal interface such as a pre-increment operator.

template <class T>
class vector
{
    T * mem;
  public:
    template <class InputIterator>
    vector (InputIterator begin, InputIterator end) // Iterator-pair constructor
    {
      // allocate enough memory and store in mem.
      mem=new T[std::distance(begin, end)];
      for (int i = 0; begin != end; ++i)
      {
        mem[i] = *begin;
        ++begin;
      }
    }
};
int main (void)
{
  std::list<int> l(4);
  std::fill(l.begin(),l.end(), 10);    // fill up list using iterator pair technique.
  std::set<int> s(4);
  std::fill(s.begin(),s.end(), 20);    // fill up set using iterator pair technique.

  std::vector<int> v1(l.begin(), l.end());  // create vector using iterator pair technique.
  std::vector<int> v2(s.begin(), s.end());  // create another vector.
}

Iterator-pair idiom is often combined with member templates because the exact type of the iterators is not known apriori. It could be set<T>::iterator or list<T>::iterator or a POD array. Irrespective of the type, any generic algorithm written in terms of the iterator pairs works. It is often useful to indicate the concept that iterator types are supposed to model. In the example above, the iterators are required to model at least the InputIterator concept. More information about iterator categories (tags) and their uses are described in Tag Dispatching idiom.

Sometime iterator pair idiom is unavoidable. For example, to construct a std::string from a buffer of characters with embedded null characters iterator-pair idiom is unavoidable.

char buf[] = { 'A', 'B', 0, 'C', 0, 'D'};
std::string str1 (buf); // only creates "AB"
std::string str2 (buf, buf + sizeof (buf) / sizeof (*buf)); // Using iterator pair. Creates "AB_C_D"
// buf is start of the range and buf + sizeof (buf) / sizeof (*buf) is the end of the range.

std::cout << str1 << " length = " << str1.length() << std::endl; // AB length = 2
std::cout << str2 << " length = " << str2.length() << std::endl; // AB_C_D length = 6

Known Uses

All standard containers

Related Idioms

• Coercion by Member Template
• Tag Dispatching