Re: [boost] [iterator] why isn't there a mapped_type iterator adaptor in boost?

Subject: Re: [boost] [iterator] why isn't there a mapped_type iterator adaptor in boost?
From: Neil Groves (neil_at_[hidden])
Date: 2010-05-15 17:59:25

On Sat, May 15, 2010 at 8:18 PM, Mostafa <mostafa_working_away_at_[hidden]>wrote:

> Mostafa wrote:
>>
>>> Hi all,
>>>
>>
>>  Why isn't there a mapped_type/key_type iterator adaptor in
>>> boost?  (Just in case it's not clear, something which allow one to
>>> iterator
>>> over the keys or the mapped-values of a map/multimap.)  I would think
>>> this
>>> is a pretty common need.
>>>
>>
>> any_iterator<...> it_any =
> my_mapped_type_iterator_adaptor(map_instance.begin());
>
>
I feel compelled to suggest caution at performing type-erasure at an
iterator level. This would often be the wrong place to incur runtime
overhead for compiler-time advantage. The deterioration in locality of data,
the worsening of cache-line performance and reduced in-lining capability
would often make this a poor design choice. Indeed there were a number of
older library designs that used runtime polymorphism with iterator
hierarchies that ultimately discovered that this approach was vastly
inferior to the generic iterator approach of the standard library. However I
can certainly see that this is useful across module interface boundaries for
small collections etc.

You can use the boost::iterator_range type and the
boost::make_iterator_range function to help create a range from iterators.
This is the core use-case for these features. However for cases like these
where you would like to have some syntactic sugar I would write this:

        template<
            class Value,
            class CategoryOrTraversal,
            class Reference = Value&,
            class Difference = std::ptrdiff_t
        >
        class any_range
            : public boost::iterator_range<
                        IteratorTypeErasure::any_iterator< Value,
CategoryOrTraversal, Reference, Difference >
                    >
        {
            typedef boost::iterator_range<
                        IteratorTypeErasure::any_iterator< Value,
CategoryOrTraversal, Reference, Difference >
                    > base_t;
        public:
            template<class Range>
            explicit any_range(Range& r) : base_t(r) {}

            template<class Range>
            explicit any_range(const Range& r) : base_t(r) {}
        };

Once you have the above abstraction you can then use the any_range and all
of the Boost.Range features. Composition of adaptor types is far better done
using the Range concepts than the Iterator concepts. Please see the
Boost.Range documentation for further explanation behind this rationale.

How would I go about doing that with ranges?
>
>
The most directly equivalent ways would be like this:

any_range< ... > any_rng( map_instance | boost::adaptors::map_values );

Thanks,
>
> -Mostafa
>
>
Thank you for an interesting problem. I do wonder if it might be a good idea
to provide a type-erasure Boost.Range adaptor so that you could write
something like:

map_instance | boost::adaptors::map_values |
boost::adaptors::type_erased<int, boost::forward_traversal_tag>

Is there much interest in using the library in this way? I'm happy to
implement this if there is.

Regards,
Neil Groves