Re: [Boost-users] [iterator] [iterator_facade] Why is advance not defined for bidirectional iterators?

Subject: Re: [Boost-users] [iterator] [iterator_facade] Why is advance not defined for bidirectional iterators?
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2011-08-22 10:53:31

On 22.08.2011 13:09, Ovanes Markarian wrote:
> Sebastian,
>
> thanks for your answer.
>
> On Mon, Aug 22, 2011 at 11:40 AM, Sebastian Redl 
> <sebastian.redl_at_[hidden] <mailto:sebastian.redl_at_[hidden]>> 
> wrote:
>
>     On 22.08.2011 10:51, Ovanes Markarian wrote:
>
> [...]
>
>
>     This mismatch is why the split of traversal and access categories
>     was introduced in Boost.Iterator, but it didn't make it into the
>     new standard, and it was never in the old to begin with, so
>     std::advance is not aware of it. What you basically need is a
>     traversal-aware std::advance.
>
> I will try to fix this with a proper reference type. Or what do you 
> mean with traversal-aware std::advance?

std::advance will switch implementations based on the standard iterator 
tags, i.e. std::input_iterator_tag, std::forward_iterator_tag, 
std::bidirectional_iterator_tag and std::random_access_iterator_tag. 
(Actually, forward isn't treated any different than input in 
std::advance.) These categories conflate traversal and access. The 
problem is that to be a forward iterator, the associated type 
'reference' must be a true reference. So whenever that isn't the case, 
the iterator is an input_iterator, no matter how you can navigate it.

Boost.Iterator separates the concepts, and so it has 
boost::one_pass_traversal_tag, boost::forward_traversal_tag, 
boost::bidirectional_traversal_tag, and 
boost::random_access_traversal_tag. However, you would need an advance 
algorithm that is aware of these tags. No std::advance I know is, so 
basically, you can't use it. (I'm not sure if you're allowed to 
specialize std::advance.)

Sebastian