RangeLib

Welcome to the home of RangeLib (standing for Range Library), which provides information about the Range concept, and implementing libraries. The Range concept is a compliment to the Iterator concept, where the focus is on manipulating collections of elements en bloc, rather than individually. As well as simplifying C++ code in many use cases, Ranges are also able to represented a wider range of collections than are Iterators.

The Range concept is the result of a collaboration between John Torjo and Matthew Wilson, both frustrated by limitations in the STL Iterator concept. Among their other incarnations, John and Matthew are contributing editors to C/C++ Users Journal, in which the Range concept has been documented in recent articles.

Contents

Motivation

The motivation for the development of the Range concept is twofold.

Messy Iterator Code

Using STL iterators with algorithms can bring great benefits in terms of succinctness and clarity. For example, statements such as the following are obvious, efficient and succinct: 

  std::copy(container.begin(), container.end(), std::ostream_iterator<int>());

Unfortunately, these characteristics are quickly turned on their head when one needs to carry out more sophisticated manipulation of the elements in a collection. The two choices, neither of which are attractive, are:

(i) to break out the loop 

  string_t               program = . . .;

  . . .

  std::vector<string_t>  programs;
  tokeniser_t            paths(. . ., ':');

  for(tokeniser_t::const_iterator b = paths.begin(); b != paths.end(); ++b)
  {
      platform_stl::path  path(*b);

      path /= program;

      if(platform_stl::filesystem_traits<char>::file_exists(path))
      {
          programs.push_back(path);
      }
  }

The first thing to be observed is that the for statement is quite complex, due to the need to stipulate the b iterator's type. This apparent complexity does not reflect the simple fact that we wish to enumerate through all the contents of the paths collection.

The scrappy aspect is further complicated by the patchy support for the old and new for-loop semantics, between several modern compilers. In the code shown above, a second loop in the same scope will require a different name for the iterator if you want the code to be portable to compilers supporting the old for-loop semantics.

(ii) to write custom functors. 

  string_t               program = . . .;

  . . .

  std::vector<string_t>  programs;
  tokeniser_t            paths(. . ., ':');

  struct path_verifier
  {
  public:
    path_verifier(std::vector<string_t> &programs, string_t const &program)
      : m_programs(programs)
      , m_program(program)
    {}

  public:
    void operator ()(tokeniser_t::value_type const &v)
    {
      platform_stl::path  path(v);

      path /= m_program;

      if(platform_stl::filesystem_traits<char>::file_exists(path))
      {
          m_programs.push_back(path);
      }
    }

  private:
    std::vector<string_t>  &m_programs;
    string_t const         &m_program;
  };

  std::for_each(paths.begin(), paths.end(), path_verifier(program));

The problem here is that we have had to create a complicated functor class - path_verifier - which will only be used in this one context. That's a lot of work for little gain, not to mention the fact that such functor classes are not easily amenable to quality control (i.e unit-testing).

Abstract of Wider Spectrum of Collections

As Matthew Wilson showed in his article "Adapting Callback Enumeration APIs to the Input Iterator Concept" in February 2004's issue of C/C++ Users Journal, the STL iterator concept cannot be made to incorporate callback enumeration APIs without significant restrictions, platform-dependence, and costs in efficiency and/or data integrity. The Range concept, in the form of the Indirect Range, is able to incorporate such APIs.

Concepts

A Range, as its name implies, represents a bounded collection of elements, which may be accessed in an incremental fashion. There are three levels of range concept: Notional, Iterable and Indirect.

Ranges are said to be Open or Closed. An open range can be advanced (by the ++ operator or the advance() method) and accessed (by the * operator or current() method). Attempting to advance or access closed ranges is invalid, nor can they be re-opened. The state of a range is indicated by the "bool" operator or the is_open() method, which may be called on any range in any state.

Notional Range

A Notional Range is one that represents a notional, rather than actual, range. An example would be the range of numbers between -100 and 99 divisible by 5. This range does not exist in the sense that we have an array of 40 ints, with the corresponding values. Of course, we can create STL iterators that can give some semblance of reality to this range if we wished, but it is not necessary. With Ranges, we can avoid the complexity, and simply use a class such as STLSoft's integral_range<>, as follows: 

  // Create values in the range [-100, 200), in increments of 5
  stlsoft::integral_range<int>   r(-100, +100, +5);

Notional Ranges may be manipulated either by methods 

  // Enumerate using the method syntax:
  for(; r.is_open(); r.advance())
  {
    std::cout << r.current();
  }

or by the more usual operator syntax: 

  // Enumerate using the method syntax
  for(; r; ++r)
  {
    std::cout << *r;
  }

Iterable Range

An Iterable Range is a superset of the Notional Range. In effect it is a "smarter" pair of iterators (begin and end). It allows manipulation of both iterators (begin and end), and preserves the underlying iterator type (for example, if the underlying iterators are bidirectional, so will the range be).

The fact that an iterable range holds two iterators (representing its position and its end position) makes it easier to:

  • create sub-ranges
  • implement range algorithms (all the STL algorithms have Iterable Range counterparts). The range algorithms are smart, and work for containers as well. Any container you pass to a range algorithm will automatically be converted to an Iterable Range.
  • perform range composition (take a range as input, and yield another range as output)

The following demonstrates the use of the STLSoft sequence_range adaptor to generalise the dumping of any types of containers of any types of elements to stdout via manual enumeration: 

  template <typename T>
  void dump_elements(T const &t)
  {
    for(stlsoft::sequence_range<T> r(t.begin(), t.end()); r; ++r)
    {
      std::cout << *r; // Dump the current value to stdout
    }
  }

  std::vector<int>  v;

  ... // populate v

  dump_elements(v); // Dump contents of v to stdout

This example shows the use of Range algorithms from the Boost implementation of RangeLib: 

  std::vector<int> v;
  std::list<int>   l;

  // print vector
  rng::copy(v, std::ostream_iterator<int>(std::cout," "));

  // copy vector to list
  rng::copy(v, std::back_inserter(l));

This example demonstrates the use of Range composition from the Boost implementation of RangeLib: 

  bool is_even(int i)
  {
    return (i % 2) == 0;
  }

  ...

  std::list l;

  // ... fill it

  // print only even numbers
  rng::copy(filtered(l, &is_even), std::ostream_iterator(std::cout, " "));

Indirect Range

The last kind of range is arguably the most interesting, and where the concept represents a manifest win over the Iterator concept. An Indirect Range is one whose elements may not be accessed in an incremental manner directly from the client code context in which the range instance is declared and/or manipulated. Rather, the elements may only be accessed indirectly by passing in functions (or function objects), which will be applied to the each element in turn. Practically speaking, the Indirect Range maps to callback enumeration APIs.

As Matthew demonstrated in his article "Adapting Callback Enumeration APIs to the Input Iterator Concept" (C/C++ Users Journal, Feb 2004), without standard and efficient co-routines (fibers, to Win32 aficionados), there is no practical and efficient mechanism to adapt callback enumeration APIs to the Input (or any other!) STL Iterator concept. However, the Range concept can encapsulate callback enumeration APIs, because it focuses on operations that may be applied to collections as a whole, rather than to individual items, for which the Iterator concept is ideally suited.

Manipulation of Indirect Range instances is always via range algorithms, as in: 

  struct print_hwnd
  {
  public:
    void operator ()(HWND hwnd) const
    {
      ... // print window text/contents to stdout;
    }
  };

  ... 

  // Create an instance of the ChildWindows_range class, which is an
  // Indirect Range
  ChildWindows_range  r(::GetDesktopWindow());

  // Print all contents of the range using the print_hwnd functor
  r_for_each(r, print_hwnd());

Examples

An example of the use of Notional, Iterable and Indirect Ranges was included with the article Ranges, part 1: Concepts and Implementation in October 2004's C/C++ Users Journal. The code for that is available from www.cuj.com/code.

We will be providing more examples of the use of Ranges here from time to time.

Implementations

Currently, there are two implementations of the Range concept in C++, in the Boost and STLSoft libraries.

Boost RangeLib

The Boost (C++) implementation of RangeLib was done by John Torjo, and is available here.

STLSoft RangeLib

The STLSoft (C++) implementation of RangeLib was done by Matthew Wilson, and is available, from version 1.8.1 onwards, via www.stlsoft.org/downloads.html.

The documentation is available online, at www.stlsoft.org/help/group___range_lib.html.

D Template Library

Ranges are also being incorporated into the D Template Library, which is being done by Matthew Wilson. Beta versions are available via www.synsoft.org/d/dtl.

Related Publications

Articles

  • "Ranges, part 2: Iterable Range Adaptors, Algorithms and Composition", John Torjo and Matthew Wilson, C/C++ User's Journal, Accepted, pending publication
  • "Ranges, part 1: Concepts and Implementation", Matthew Wilson and John Torjo, C/C++ User's Journal, Volume 22 Number 10, October 2004
  • "Adapting Callback Enumeration APIs to the Input Iterator Concept", Matthew Wilson, C/C++ User's Journal, Volume 23 Number 2, February 2005

Books

  • The Notional and Iterable Range concepts are also discussed in Chapter 34 of Matthew Wilson's book Imperfect C++ (Addison-Wesley, Oct 2004). The Indirect concept came after the deadline

    Matthew is currently finishing up Extended STL, volume 1 (Addison-Wesley, 2007). The full gamut of Range concepts and algorithms (along with other similar extension concepts) will be covered in several chapters of volume 2, which he'll be working on as soon as volume 1 has gone to the presses.

Newsgroup

Digital Mars and SmartSoft, LLC have been kind enough to host the RangeLib newsgroup, for which we're very grateful.

Links

RangeLib newsgroup
www.cuj.com
www.boost.com
www.stlsoft.org
John's homepage
Matthew's homepage