[iterator] [iterator_facade] Why is advance not defined for bidirectional iterators?
Hello *! I defined a custom bidi-iterator and assumed it was going to support std::advance(iterator, Difference n), where n can be negative for random access and bidirectional iterators. The definition of my iterator's facade base looks like: struct my_iter : boost::iterator_facade < my_iter , const byte , boost::bidirectional_traversal_tag , const byte > { // some impl stuff follows... }; My tests show that calling: advance(instance_of_my_iter, N) works fine (increment implementation is called) advance(instance_of_my_iter, -N) does not work, because increment (instead of decrement) is called as well While reading through the docs for iterator facade at http://www.boost.org/doc/libs/1_46_0/libs/iterator/doc/iterator_facade.html I found the section iterator_facade Core Operations. For the advance implementation is stated there that it is only gets called for Random Access Iterators. C++ Standard clearly defines that N-Parameter to std::advance can be negative to random access and bidi iterators. Implementing void advance member in my_iter still results in the call to increment member. Can someone give me any suggestions or is it a bug in the iterator lib? My compiler is gcc 4.3 under Debian Linux with Kernal 2.6.26. and Boost 1.42. With Kind Regards, Ovanes
Hi!
Is someone responsible for iterator_facade? Would be great if I'd be able to
clarify this with one of the authors...
Many thanks,
Ovanes
On Wed, Aug 17, 2011 at 2:58 PM, Ovanes Markarian
Hello *!
I defined a custom bidi-iterator and assumed it was going to support std::advance(iterator, Difference n), where n can be negative for random access and bidirectional iterators.
The definition of my iterator's facade base looks like: struct my_iter : boost::iterator_facade < my_iter , const byte , boost::bidirectional_traversal_tag , const byte > {
// some impl stuff follows... };
My tests show that calling: advance(instance_of_my_iter, N) works fine (increment implementation is called)
advance(instance_of_my_iter, -N) does not work, because increment (instead of decrement) is called as well
While reading through the docs for iterator facade at http://www.boost.org/doc/libs/1_46_0/libs/iterator/doc/iterator_facade.html I found the section iterator_facade Core Operations.
For the advance implementation is stated there that it is only gets called for Random Access Iterators. C++ Standard clearly defines that N-Parameter to std::advance can be negative to random access and bidi iterators. Implementing void advance member in my_iter still results in the call to increment member. Can someone give me any suggestions or is it a bug in the iterator lib?
My compiler is gcc 4.3 under Debian Linux with Kernal 2.6.26. and Boost 1.42.
With Kind Regards, Ovanes
On 22.08.2011 10:51, Ovanes Markarian wrote:
Hi! Is someone responsible for iterator_facade? Would be great if I'd be able to clarify this with one of the authors...
Many thanks, Ovanes
On Wed, Aug 17, 2011 at 2:58 PM, Ovanes Markarian
mailto:om_boost@keywallet.com> wrote: Hello *!
I defined a custom bidi-iterator and assumed it was going to support std::advance(iterator, Difference n), where n can be negative for random access and bidirectional iterators.
The definition of my iterator's facade base looks like: struct my_iter : boost::iterator_facade < my_iter , const byte , boost::bidirectional_traversal_tag , const byte > {
// some impl stuff follows... };
My tests show that calling: advance(instance_of_my_iter, N) works fine (increment implementation is called)
advance(instance_of_my_iter, -N) does not work, because increment (instead of decrement) is called as well
The problem is not with Boost. std::advance is a standard library algorithm, and its behavior is up to the standard library implementation. What happens here is that while your iterator has bidirectional traversal, std::advance queries the standard iterator tag, which is (because your reference is not a proper reference type) input_iterator_tag. Thus, std::advance dispatches to the input iterator version, which does not support negative offsets. 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.
For the advance implementation is stated there that it is only gets called for Random Access Iterators.
The advance operation of iterator_facade has nothing to do with std::advance. Sebastian
Sebastian, thanks for your answer. On Mon, Aug 22, 2011 at 11:40 AM, Sebastian Redl < sebastian.redl@getdesigned.at> 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? If it is not a part of the current STD lib, how do I get it? I could also specialize std::advance for my iterator to work correctly, this would be a potential fix. [...] With Kind Regards, Ovanes
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
mailto:sebastian.redl@getdesigned.at> 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
On Mon, Aug 22, 2011 at 4:53 PM, Sebastian Redl < sebastian.redl@getdesigned.at> wrote:
On 22.08.2011 13:09, Ovanes Markarian wrote:
[..]
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.
Ok, thanks. I was aware of iterator categories, but did not know that advance really is going to make a decision dependent on reference type and not the iterator category. If that is true what you have written, than vector<bool> must be either a forward_iterator sequence or advance is also specialized for vector<boost>::iterator and ...const_iterator respectively.
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.)
AFAIK users are allowed to specialize the std templates but are disallowed to overload them. I was hoping to solve it more elegantly, but thanks for your help anyway. With Kind Regards, Ovanes
participants (2)
-
Ovanes Markarian
-
Sebastian Redl