mr-edd.co.uk :: horsing around with the C++ programming language

The beginnings of an opaque iterator library

[28th May 2007]

I've been toying with this idea for quite some time now. In fact, I'm sure I'm not the first to come up with it, but it's been a bit of a pain to implement so that might explain why I've failed to find any similar code elsewhere on the web.

The basic idea of the opqit::opaque_iterator template class that I'll present here is that it allows you to minimise dependencies in a similar way to the pimpl idiom.

In general, to declare a function taking or returning a particular type of iterator, you may need to #include a bunch of headers for containers, adaptors and so forth. These will in turn bring in other headers, racking up the header dependencies.

The opqit library presented here is designed to solve or at least alleviate this problem by implementing an opaque_iterator class which can be forward declared in your headers.

A motivating example

Suppose we have a database of cooking recipes, implemented in terms of a custom hash-map and also suppose that this database provides a means of iterating over its recipes:

// recipe_database.h
#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/filter_iterator.hpp>
#include <boost/function.hpp>

#include <string>

#include <my_hash_map.h>

class recipe_database
{
    public:
        typedef /* ... */ entry; 

        typedef my_hash_map<entry>::iterator iterator; 
        typedef my_hash_map<entry>::const_iterator const_iterator; 

        iterator begin();
        iterator end();

        const_iterator begin() const;
        const_iterator end() const;

        // ...

    private:
        my_hash_map<entry> entries_;
};

Also in this header, we implement a view over the database through which we may extract all the quick-and-easy recipes as strings. We can do this using the extremely useful iterator adaptors from boost (hence the #includes in the previous snippet).

class quick_and_easy_view
{
    public:
        struct is_quick_and_easy
        {
            bool operator() (const recipe_database::entry &e) const
            { 
                return e.cooking_time_mins() <= 20 && e.ingredients_count() < 10;
            }
        };

        typedef 
        <
            boost::transform_iterator
            <
                boost::function<std::string (const recipe_database::entry &)>,
                boost::filter_iterator<is_quick_and_easy, recipe_database::const_iterator>
            >
        >
        iterator;

        iterator view_begin(const recipe_database &db);
        iterator view_end(const recipe_database &db);
};

Note that we've pulled in a good number of reasonably hefty headers, here. When compiling with MinGW g++, the following headers are #included merely as a by-product of bringing in the three boost headers[1]:

P:\software\tests\boost_tests>g++ -MM headers.cpp -I%BOOST_ROOT%
headers.o: headers.cpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/transform_iterator.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/iterate.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/iteration/iterate.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/arithmetic/dec.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/config/config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/arithmetic/inc.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/array/elem.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/array/data.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/tuple/elem.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/array/size.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/cat.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/slot/slot.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/slot/detail/def.hpp \
  C:/development/boost/include/boost-1_33_1/boost/detail/workaround.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function/detail/prologue.hpp \
  C:/development/boost/include/boost-1_33_1/boost/throw_exception.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/user.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/select_compiler_config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/compiler/gcc.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/select_stdlib_config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/stdlib/libstdcpp3.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/select_platform_config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/platform/win32.hpp \
  C:/development/boost/include/boost-1_33_1/boost/config/suffix.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function/function_base.hpp \
  C:/development/boost/include/boost-1_33_1/boost/assert.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_integral.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/bool_trait_def.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/template_arity_spec.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/int.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/int_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/adl_barrier.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/adl.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/msvc.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/intel.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/gcc.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/workaround.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/nttp_decl.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/nttp.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/integral_wrapper.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/integral_c_tag.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/static_constant.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/static_cast.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/template_arity_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessor/params.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/preprocessor.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/comma_if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/punctuation/comma_if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/control/if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/control/iif.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/logical/bool.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/facilities/empty.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/punctuation/comma.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/repeat.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/repetition/repeat.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/debug/error.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/detail/auto_rec.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/tuple/eat.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/inc.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/lambda.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/ttp.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/ctps.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/overload_resolution.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/integral_constant.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/bool.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/bool_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/integral_c.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/integral_c_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/lambda_support.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/bool_trait_undef.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/composite_traits.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_array.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_enum.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/add_reference.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_reference.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/type_trait_def.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/type_trait_undef.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_arithmetic.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_float.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/ice_or.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_convertible.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/yes_no_type.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/ice.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/ice_and.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/ice_not.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/ice_eq.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_abstract.hpp \
  C:/development/boost/include/boost-1_33_1/boost/static_assert.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/yes_no_type.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_class.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_union.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/remove_cv.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/broken_compiler_spec.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/cv_traits_impl.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/intrinsics.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_function.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/false_result.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/is_function_ptr_helper.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/config.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_union.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_member_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_member_function_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/is_mem_fun_pointer_impl.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_stateless.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/has_trivial_constructor.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_pod.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_void.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_scalar.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/has_trivial_copy.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_volatile.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/has_trivial_destructor.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_empty.hpp \
  C:/development/boost/include/boost-1_33_1/boost/ref.hpp \
  C:/development/boost/include/boost-1_33_1/boost/utility/addressof.hpp \
  C:/development/boost/include/boost-1_33_1/boost/pending/ct_if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/utility/enable_if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function_equal.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mem_fn.hpp \
  C:/development/boost/include/boost-1_33_1/boost/get_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/bind/mem_fn_template.hpp \
  C:/development/boost/include/boost-1_33_1/boost/bind/mem_fn_cc.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/enum.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/repetition/enum.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/tuple/rem.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/enum_params.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/repetition/enum_params.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/iteration/detail/iter/forward1.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/iteration/detail/bounds/lower1.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/slot/detail/shared.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/iteration/detail/bounds/upper1.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function/detail/function_iterate.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function/detail/maybe_include.hpp \
  C:/development/boost/include/boost-1_33_1/boost/function/function_template.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/detail/enable_if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/identity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/na_spec.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/lambda_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/void_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/na.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/na_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/lambda_arity_param.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/arity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/dtp.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessor/enum.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessor/def_params_tail.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/limits/arity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/logical/and.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/logical/bitand.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/identity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/facilities/identity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/empty.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/arithmetic/add.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/control/while.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/list/fold_left.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/list/detail/fold_left.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/control/expr_iif.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/list/adt.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/detail/is_binary.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/detail/check.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/logical/compl.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/list/fold_right.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/list/detail/fold_right.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/list/reverse.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/control/detail/while.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/arithmetic/sub.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/eti.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/detail/config_def.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/detail/config_undef.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/iterator_adaptor.hpp \
  C:/development/boost/include/boost-1_33_1/boost/detail/iterator.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/iterator_categories.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/eval_if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/if.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/value_wknd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/integral.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/placeholders.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/arg.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/arg_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/na_assert.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/assert.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/not.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/nested_type_wknd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/yes_no.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/arrays.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/arity_spec.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/arg_typedef.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/use_preprocessed.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/include_preprocessed.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/compiler.hpp \
  C:/development/boost/include/boost-1_33_1/boost/preprocessor/stringize.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/arg.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/placeholders.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_convertible.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/iterator_facade.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/interoperable.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/or.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/or.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/iterator_traits.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/detail/facade_iterator_category.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/and.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/and.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_same.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_const.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_reference.hpp \
  C:/development/boost/include/boost-1_33_1/boost/detail/indirect_traits.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_volatile.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_member_function_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_member_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/remove_cv.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/remove_reference.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/remove_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/detail/ice_and.hpp \
  C:/development/boost/include/boost-1_33_1/boost/implicit_cast.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/add_const.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/add_pointer.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/remove_const.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/is_pod.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/always.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/apply.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/apply_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/apply_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/apply_wrap.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/has_apply.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/has_xxx.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/type_wrapper.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/has_xxx.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/msvc_typename.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/has_apply.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/msvc_never_true.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/apply_wrap.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/lambda.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/bind.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/bind_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/config/bind.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/bind_fwd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/next.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/next_prior.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/common_name_wknd.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/protect.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/bind.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/full_lambda.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/quote.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/void.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/has_type.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/quote.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/template_arity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/template_arity.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/full_lambda.hpp \
  C:/development/boost/include/boost-1_33_1/boost/mpl/aux_/preprocessed/gcc/apply.hpp \
  C:/development/boost/include/boost-1_33_1/boost/type_traits/function_traits.hpp \
  C:/development/boost/include/boost-1_33_1/boost/iterator/filter_iterator.hpp

P:\software\tests\boost_tests>

Whoa! And on top of these, we also have the headers #included from inside <my_hash_map.h>, which may also be significant in number. So any code that #includes our header clearly brings a lot of baggage along for the ride. This is a dependencies head-ache. If any of the listed headers change, we'll need to recompile all files that #include our header directly or indirectly[2].

To avoid this nastiness, we rummage around in our toolbox and come across the pimpl idiom. In a number of situations we can employ the pimpl idiom to hide the implementation of a class behind an opaque pointer. But alas, we can't do this for our recipe_database class.

Why not? Well, the return type of the recipe_database::begin() and recipe_database::end() member functions need to be known at compile time and they're defined in terms of my_hash_map's iterators. So even if we did hide the hash-map data member behind an opaque pointer, we'd still have to #include the <my_hash_map.h> header in our own so that we get the definitions of the iterator types.

Similarly, the iterator types for the quick_and_easy_view require that all three of the boost headers stay where they are.

opaque_iterator to the rescue!

Using opaque_iterator, we can re-write our recipe_database.h header like so:

// recipe_database.h
#include <opaque_iterator_fwd.hpp>
#include <string>

template<typename T>
class my_hash_map;

class recipe_database
{
    public:
        typedef /* ... */ entry; 

        typedef opqit::opaque_iterator<entry, opqit::input> iterator; 
        typedef opqit::opaque_iterator<const entry, opqit::input> const_iterator; 

        iterator begin();
        iterator end();

        const_iterator begin() const;
        const_iterator end() const;

        // ...

    private:
        my_hash_map<entry> *pimpl_;
};

class quick_and_easy_view
{
    public:
        typedef opqit::opaque_iterator<std::string, opqit::input> iterator;

        iterator view_begin(const recipe_database &db);
        iterator view_end(const recipe_database &db);
};

We've managed to get rid of the all the boost headers now, and the one for the hash-map. And we can now move the is_quick_and_easy class in to an implementation file, reducing the effort needed to parse and generally make sense of the header.

But hold on, what lurks inside opaque_iterator_fwd.hpp?! Not very much at all. Here is the entire contents of that file:

namespace opqit
{

template<typename Val, typename Tag>
class opaque_iterator;

struct output { };
struct input { };
struct forward { };
struct bidir { };
struct random { };

} // close namespace opqit

The net result is that we've reduced the dependencies of our code by about 260 headers. Not too shabby!

So what does the implementation of the recipe database look like?

Believe it or not, the implementation of each member function will remain largely unchanged. For example:

recipe_database::iterator recipe_database::begin()
{
    // opaque_iterator<entry, opqit::input> provides 
    // a template conversion-constructor
    return pimpl_->begin(); 
}

Nice :)

Looking at the library in a bit more detail

The C++ standard library defines 5 different iterator categories, each with a corresponding type, or tag:

  1. output iterator — std::output_iterator_tag
  2. input iterator — std::input_iterator_tag
  3. forward iterator — std::forward_iterator_tag
  4. bi-directional iterator — std::bidirectional_iterator_tag
  5. random access iterator — std::random_access_iterator_tag

Every well behaved iterator type exposes a number of internal typedefs that describe various attributes of the iterator, that will vary according to the iterator's tag. Consult your favourite reference book for more information[3].

The opqit library defines 5 corresponding structures, that we saw in the <opaque_iterator_fwd.hpp> header:

  1. opqit::output
  2. opqit::input
  3. opqit::forward
  4. opqit::bidir
  5. opqit::random

You can give any one of these types or any of the std:: iterator tags as the second template argument to opqit::opaque_iterator.

For a given type X, an opqit::opaque_iterator<X, opqit::output> is implicitly convertible to an opqit::opaque_iterator<X, std::output_iterator_tag> and vice versa. Furthermore, either of these types may be constructed from any output iterator from the standard library or elsewhere that iterates over a sequence of X objects.

The equivalent conversions exist for the other categories, too.

The first template argument to an opqit::opaque_iterator template instantiation represents the type of value you are iterating over. This type should be const if the elements of the underlying sequence are immutable.

Tertiary facilities

The main component of the opqit library is of course the opaque_iterator template class. But there are some other bits and pieces provided for convenience.

For example, there's an opaque_iterator_cast() template function that allows you to extract the underlying iterator from an opqit::opaque_iterator e.g.

std::vector<int> numbers;

// ...

opaque_iterator<int, random> b(numbers.begin());
opaque_iterator<int, random> e(numbers.end());

opaque_iterator<int, random> it =
    std::remove(b, e, 42);

typedef std::vector<int>::iterator vec_iter_t;

// May throw bad_iterator_cast
vec_iter_t erase_begin = opaque_iterator_cast<vec_iter_t>(it);

numbers.erase(erase_begin, numbers.end());

Compiler support

opqit is a header-only library, but I've created some test and example programs to exercise it, which compile just fine with the following compilers:

If you manage to get opqit to work with a compiler not listed here, I'd love to hear from you.

Unfortunately Digital Mars falls flat on its face and I think it would be too much work to support this compiler.

I've given up on Borland for now. Initially I was at a stumbling block because the implementation used SFINAE, which bcc32 5.82 couldn't cope with. I found a way to implement the code without SFINAE, however, but the workaround made the compiler crash! I've tried a couple of alternatives, but they lead to incorrect error diagnoses. So I'm going to have to wait until they fix their compiler.

EDIT: 18th June 2007

I've finished the implementation of the library. It's still not quite as a I would like it, but it works. Head over to the permanent opqit library page for more information.

Footnotes
  1. similar results apply for other compilers, but out of the compilers I have access to, g++ makes finding such statistics easiest []
  2. the boost headers are usually pretty stable, and the standard library headers for your implementation more so, I would expect. But I've only used the boost headers as an illustration, this kind of situation could arise anywhere in production code []
  3. Nicolai Josuttis' The C++ Standard Library has a very down-to-earth section on iterator categories and behaviours []

Comments

(optional)
(optional)
(required, hint)

Links can be added like [this one -> http://www.mr-edd.co.uk], to my homepage.
Phrases and blocks of code can be enclosed in {{{triple braces}}}.
Any HTML markup will be escaped.