Views - a C++ Standard Template Library extension

Last updated: 7th January, 1996

Overview

The C++ Standard Template Library provides templates that define generic container and iterator classes. The software described here extends the Standard Template Library by adding template classes that define views.

What is a view?

A view is an abstract container whose contents are determined by applying a filtering transformation to an encapsulated domain of elements. In the most general case, a view is defined in terms of the encapsulated domain, a filtering predicate and a transformation function.

A view's encapsulated domain is an entity that behaves like an abstract container. In particular it defines an iterator class that conforms to the interface of an STL bidirectional iterator and two member functions (begin, end) that generate appropriately initialised iterators. Any instance of an STL container that supports use of a bidirectional iterator conforms to the specification of a domain used here. Although a domain is usually implemented by a physical container, it need not be. The header file domain.h contains an example of a domain (scalar_domain) built from a non-container.

An important specialisation of a view is a class known as a subdomain. A subdomain is a view whose transformation function is implemented by the identity function. In other words, a subdomain is the subset of the encapsulated domain that complies with the subdomain's predicate.

It should be noted that an important property of a view is that it is not formed by copying the encapsulated domain. Instead a view is implemented by defining new iterator classes that adapt to iterators of the encapsulated domain. The end result is that the user uses a view that behaves to all and intents and purposes like a normal STL container.

How are domain views related to relational views?

Relational database theory also defines a concept known as a view. There is a fairly strong analogy between the concept of a relational view and that of the domain view defined here. For example, consider a relational view that is described by SQL of the form: 
   select column_expression_list from table  where where_clause.
The following table shows the analogy between a domain view and a relational view of that form.
  • Domain view Relational view
    transformation column_expression_list
    domain table
    predicate where_clause
    subdomain select * from table where where_clause

    • Why use a view?

    One reason for using a view is reduce the complexity of code that works with containers.

    It is often the case that only a subset of a container's elements are interesting to a user of the container. Views allow the user to create an abstract container that contains only the interesting elements.

    A view constructed in this way is represented by a single object. Such an object (or the iterators it generates) can be passed to algorithms that operate on containers without these algorithms needing to know precisely how the view was constructed.

    A trivial benefit of using a view is that conditional filtering code can be eliminated from the body of processing loops. Examples of this can be seen in the sample program, examples.cpp.

    A view can be useful when the user of a container needs to use a set of objects functionally derived from the objects in the container, rather than the objects themselves. In this case, the user defines a view using a transformation function that implements the required transformation. For an example of a view being used for this purpose, see the definition of the map_keys template in mapview.h and the associated example in examples.cpp.

    Template Directory

    This directory lists the major templates provided by this software:
    downcast_dereference in downcast.h
    The downcast_dereference template implements a function that converts a base class pointer to a subclass reference using a safe downcast member defined by the base class.

    This template class is used as the transform class by the downcast_dereference_view template.

    downcast_dereference_view in downcast.h
    The downcast reference view template converts a container of base class pointers into an abstract container of objects of a particular sub class.

    identity in transform.h
    The identity template implements the identity function by returning a reference to its argument.

    This template is used as the transform class by the subdomain template.

    is_subtype in downcast.h
    The is_subtype template implements a test on the subclass of the object referred to by a base class pointer using a safe downcast member function defined by the base class.

    This is_subtype template class is used as predicate class by the downcast_dereference_view template.

    map_keys in mapview.h
    The map_keys template defines an abstract container that contains the keys of a map.

    The map_keys template is an example of a view implements a non-filtering transformation.

    map_values in mapview.h
    The map_values template defines an abstract container that contains the values of a map.

    The map_values template is an another example of a view implements a non-filtering transformation.

    pair_first in transform.h
    A transformation function that answers the first element of a pair.

    Used as the transformation function by the map_keys template to answer the key part of map pair.

    pair_second in transform.h
    A transformation function that answers the second element of a pair.

    Used as the transformation function by the map_values template to answer the value part of map pair.

    scalar_domain in domain.h
    The scalar_domain template forms a domain from a range of scalars.

    subdomain in domain.h
    The subdomain template is a subclass of a view template in which the transformation function is implemented by the identity function.

    A property of a subdomain is that all members of the subdomain are also members of the encapsulated domain.

    subrange_domain in domain.h
    The subrange_domain template defines a domain delimited by a pair of iterators.

    unary_tautology in predicate.h
    A unary predicate that is always true. This predicate is used by non-filtering views.

    view in view.h
    The view template defines an abstract container in terms of an encapsulated domain, a filtering predicate and a transformation function.

    Examples

    For examples of the use of this software, see examples.cpp.

    Changes

    v1.0 - 30th December, 1995
    Implemented the concept of a filtering iterator.

    v2.0 - 6th January, 1996
    Made explicit the subdomain concept implicit in the definition of the filtering iterator. Generalised the subdomain concept to yield the concept of a view.

    Note: What was called a filtering iterator in v1.0 is now simply the iterator class defined by the subdomain template. Filtering iterators have disappeared as a distinct concept.

    v2.0a - 7th January, 1996
    Fixed a bug in downcast_dereference_view. Minor edits in documentation. Removed range.h. Removed range parameter from view template. Removed operator that did assignment from domain_iterator_t in view<>::iterator. Changed semantics of operator ==(iterator, domain_iterator_t) in view<>::iterator.

    Acknowledgements

    Thanks to James Kanze and John Max Skaller for critiquing my initial implementation of filtering iterators.

    To do

    This software could be extended in a number of ways, including:

    If you have need for such an extension or would like to add one, send me a note.

    Feedback

    I'd appreciate feedback about the design and implementation of this software. If you have any such comments please send me a note.

    Files

    views.zip contains:
    include/view.h
    view templates
    include/domain.h
    domain templates
    include/downcast.h
    support for typesafe dereferencing of pointer containers
    include/predicate.h
    useful predicates
    include/mapview.h
    STL map views
    samples/examples.cpp
    sample program
    include/transform.h
    useful transformation functions
    doc/views.html
    documentation
    include/views.h
    top level header file for views related headers

    Copyright

    Copyright (c) 1995, 1996 - Jon Seymour

    Views - a C++ Standard Template Library extension

    Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose is hereby granted without fee, provided that this notice appears unmodified in all derivative works.

    The author makes no representations about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty.

    For more information about this software, refer to:

  • http://www.zeta.org.au/~jon/STL/views/doc/views.html

    • Please send comments about this software to:

  • Jon Seymour (jon@zeta.org.au)

    • Copyright (c) 1995, 1996 jon seymour