Concepts

A concept, from a Generic Programming standpoint, is an abstract notion of what a type is. This includes the set of public member function signatures, public member types, public fields, class invariants, along with the semantics, preconditions, and postconditions of all the member functions. There is no prescribed way to express and verify concepts in the current C++ standard, though various ad-hoc methods exist.

For more information on concepts and models, please consult http://www.boost.org/more/generic_programming.html and http://www.sgi.com/tech/stl/stl_introduction.html. These provide an excellent introduction to generic programming techniques.

The OOTL is built on a different set of concepts than the STL. One of the major deparatures of the OOTL from the STL, is a tighter cohesion of algorithm and data structure. This is more in line with the object-oriented philosophy. The OOP methodology prescribes a coupling of data structures and operations which perform on the data structure, while the Generic Programming (GP) methodology prescribes a maximal decoupling of data structure and algorithm. The trade-off can be summarized as: generality (GP) versus simplicity (OOP).

Iterable Concept

  concept {
    typedef value_type;
    template<typename Procedure>
    void for_each(Procedure& proc);
  }
  

The Iterable concept is a way of providing a highly abstract and minimalist functional interface to a collection. In the way that the STL collections start from the Container concept, the Iterable concept provides a foundation for the OOTL collections.

A model of the Iterable concept applies a Procedure to values it contains in a sequential manner. A simple example of an Iterable model in action is below:

  void array_adaptor_test() {
    writeln("This is a test of the array adapter");
    writeln("Expect the numbers 1 to 3 in sequence separated by spaces");
    int a[] = { 1, 2, 3 };
    output(array_to_iterable(a, 3));
    writeln();
  }
  

The Iterable concept is more flexible than a Container since it can easily model purely functional notions such as infinite series, or input streams, but it lacks the computational power which comes with positional information. This is similar to the trade off inherent in the usage of Input Iterators versus Random Access Iterators.

A model of the Iterable concept is expected to have shallow assignment semantics. Whether or not an iterable is single pass, is not specified at this time.

Iterable Generators

The ootl generators provide models of the Iterable concept, but which are defined in terms of functions. A sample generator is the following:

    template<typename Value, typename Function, typename Predicate>
    struct iterable_generator {
      iterable_generator(Value initial, Function fxn, Predicate conditional)
        : value(initial), f(fxn), cond(conditional) { }
      typedef Value value_type;
      template<typename Procedure>
      void for_each(Procedure proc) {
        while (cond(value)) {
          proc(value);
          value = f(value);
        }
      }
      Function f;
      value_type value;
      Predicate cond;
    };
  

The iterable_generator works as follows: first it is seeded with an initial value, then a while loop applies the function to the current value, while the Predicate evaluates to true. You can create an iterable_generator by calling the function iterable_gen(Value v, Function f, Predicate p). For convenience the function iterable_gen(Value v, Function f, int n) is provided also.

A generator is very useful, because it is an extremely light-weight way of representing a series of values, when the series can be expressed as a function.

Iterable Adapters

There are currently two adapters. The iterator_range_to_iterable_adapater template allows the user to use an arbitrary pair of iterators as an Iterable model. The value_range_to_iterable_adapater is used to represent a contiguous range of values as an Iterable model. The following functions construct iterable adapters from their input:

    int_range(int i, int j);

    template<typename Value>
    value_range_to_iterable(Value i, Value j);

    template<typename Iterator>
    iterator_range_to_iterable(Iterator i, Iterator j);

    template<typename Iterator>
    array_to_iterable(Iterator i, int n)
  

Iterable Models

There following models of the Iterator concept are provided in the ootl_iterable.hpp header:

• The composed_iterable template, which can be constructed from a call to compose, takes an existing iterable, and applies a function to each value before applying the procedure to it.
• The predicated_iterable template, which can be constructed from a call to filter, take an existing iterable, and iterates only over values which satisfy the predicate (when passed to the predicate cause it to return true).
• The concatenated_iterable template, which can be constructed from a call to cat concatenates two iterable models.

Other models of the Iterator concept can be found in ootl_adapters.hpp and ootl_generators.hpp

Procedure Concept

    concept Procedure {
      template<typename T>
      void operator()(T& x);
    }
  

The Procedure concept is provided as an efficient alternative to unary functions. Because a procedure uses reference parameters it can bypass the overhead of superflous assignment operations. The Procedure concept is key to the Iterable concept.

Predicate Concept

    concept Predicate {
      template<typename T>
      bool operator()(const T& x);
    }
  

A model of the Predicate concept is a function object which returns a boolean value. The header ootl_predicate.hpp provides the following models of the Predicate concept.

    truth
    fallacy
    matches
    lt
    gt
    eq
    between
    is_even
    is_odd
    mod_x
    is_prime
  

The following Predicate models are used for modifying or combining Predicates.

    or_
    and_
    negater
  

The following count_xxx Predicates compare an internal counter to a stored value. This is particularly important when working with Iterable models because they maintain no index.

    count_lt
    count_gt
    count_eq
    count_between
  

Function Concept

    concept Function {
      template<typename T>
      T operator()(const T& x);
    }
  

The ootl provides the following models of the Function concept:

    identity
    negative
    constant_fxn
    next_even
    next_odd
    adder
    multiplier
    divider
    exponent
    square
    quadratic
    fractional
    inc
    dec
  

Currently most of the Function models manipulate integers. The following Function models modify existing Function objects to create new ones:

    cond_fxn
    predicate_fxn
    compose_fxn
  

back to the OOTL documentation home page
back to the OOTL.org home page

http://www.ootl.org
last modified: November 13, 2005
Copyright Christopher Diggins, 2005
OOTL logo copyright 2005 Paige Lybbert.