iterator_adaptor: making dereference of adapted tree node* return node value

Rob Desbois

23 Feb 2012 23 Feb '12

9:57 a.m.

I have the following iterator_adaptor type: template< class NODE > struct node_iterator: public boost::iterator_adaptor< node_iterator<NODE>, // Derived NODE*, // Base typename NODE::value_type // Value > { typename NODE::value_type dereference() const { return this->base_reference()->data(); } }; // and later: typedef detail::node_iterator iterator; typedef detail::node_iterator<const node_type> const_iterator; This throws up the issue that in const_iterator, Value is not const, producing the following error: /usr/include/boost/iterator/iterator_facade.hpp:517:32: error: invalid initialization of non-const reference of type ‘container::detail::node_iterator::reference {aka long unsigned int&}’ from an rvalue of type ‘container::detail::node<long unsigned int>::value_type {aka long unsigned int}’ I could do some type traits magic with is_same, is_const and add_const to add the constness to Value if present on NODE, but is this the right way to do it? I've also thought about indirect_iterator - but adding operator*() to the node type seems not quite right. Perhaps transform_iterator...or is there some different method that might be more suitable? TIA, --rob -- Rob Desbois Blog: http://theotherbranch.wordpress.com/ "I disapprove of what you say, but I’ll defend to the death your right to say it", Voltaire

Show replies by date

Robert Jones

23 Feb 23 Feb

2:39 p.m.

On Thu, Feb 23, 2012 at 9:57 AM, Rob Desbois wrote:

...

I have the following iterator_adaptor type:

template< class NODE > struct node_iterator: public boost::iterator_adaptor< node_iterator<NODE>, // Derived NODE*, // Base typename NODE::value_type // Value > { typename NODE::value_type dereference() const { return this->base_reference()->data(); } };

// and later: typedef detail::node_iterator iterator; typedef detail::node_iterator<const node_type> const_iterator;

This throws up the issue that in const_iterator, Value is not const, producing the following error: /usr/include/boost/iterator/iterator_facade.hpp:517:32: error: invalid initialization of non-const reference of type ‘container::detail::node_iterator::reference {aka long unsigned int&}’ from an rvalue of type ‘container::detail::node<long unsigned int>::value_type {aka long unsigned int}’

I could do some type traits magic with is_same, is_const and add_const to add the constness to Value if present on NODE, but is this the right way to do it? I've also thought about indirect_iterator - but adding operator*() to the node type seems not quite right. Perhaps transform_iterator...or is there some different method that might be more suitable?

I favoured the type traits magic approach, and publish the resulting value type as the value type of the iterator... typedef typename if_::type value_type; - Rob (J)

Jeffrey Lee Hellrung, Jr.

6:58 p.m.

On Thu, Feb 23, 2012 at 1:57 AM, Rob Desbois wrote:

...

I have the following iterator_adaptor type:

template< class NODE > struct node_iterator: public boost::iterator_adaptor< node_iterator<NODE>, // Derived NODE*, // Base typename NODE::value_type // Value > { typename NODE::value_type dereference() const { return this->base_reference()->data(); } };

// and later: typedef detail::node_iterator iterator; typedef detail::node_iterator<const node_type> const_iterator;

This throws up the issue that in const_iterator, Value is not const, producing the following error: /usr/include/boost/iterator/iterator_facade.hpp:517:32: error: invalid initialization of non-const reference of type ‘container::detail::node_iterator::reference {aka long unsigned int&}’ from an rvalue of type ‘container::detail::node<long unsigned int>::value_type {aka long unsigned int}’

I could do some type traits magic with is_same, is_const and add_const to add the constness to Value if present on NODE, but is this the right way to do it?

To reiterate Robert Jones' reply, yes, AFAIK, a const iterator should pass a const-qualified value_type to iterator_facade/iterator_adaptor, as implied by the constant node_iterator example in the docs: http://www.boost.org/doc/libs/1_48_0/libs/iterator/doc/iterator_facade.html#... On a related note, you should specify your reference type you pass to iterator_adaptor explicitly as the return type of your dereference member function. Otherwise I think you'll end up returning a reference to a temporary within operator*. I believe that's *actually* what the quoted error is trying to tell you. HTH, - Jeff

Rob Desbois

24 Feb 24 Feb

10:51 a.m.

On 23 February 2012 14:39, Robert Jones wrote:

...

I favoured the type traits magic approach, and publish the resulting value type as the value type of the iterator...

typedef typename if_::type value_type;

Thanks for the input Rob - see below for the solution I settled on. On 23 February 2012 18:58, Jeffrey Lee Hellrung, Jr. wrote:

...

To reiterate Robert Jones' reply, yes, AFAIK, a const iterator should pass a const-qualified value_type to iterator_facade/iterator_adaptor, as implied by the constant node_iterator example in the docs:

http://www.boost.org/doc/libs/1_48_0/libs/iterator/doc/iterator_facade.html#...

Actually iterator_facade/iterator_adaptor's value type in the tutorials is the _node_ type, not the node's value_type.

...

On a related note, you should specify your reference type you pass to iterator_adaptor explicitly as the return type of your dereference member function. Otherwise I think you'll end up returning a reference to a temporary within operator*. I believe that's *actually* what the quoted error is trying to tell you.

Thanks - I've updated to use node_iterator::iterator_adaptor_::reference as the return type from dereference(). The docs show that this defaults to Value&. The error message still stands though, since const node_type::value_type is still not const. I settled on implementing the boost::mpl::if_ method as shown by Rob, which turned out to be a viable solution to the problem I faced, but then after some more thinking and coding realised that I didn't actually want the mutable iterator type to enable modification of the data in the referenced node. Since this is an ordered tree, modifying the data of a node is clearly a Bad Thing! Feeling somewhat silly that I didn't recognise this before leaping down the rabbit hole...what I now have is that Value is *always* const: template< class NODE > node_iterator: public boost::iterator_adaptor< node_iterator<NODE>, // Derived NODE*, // Base const typename NODE::value_type // Value

...

The reference type is then const typename NODE::value_type& as expected and everything works fine. It was only after discovering that std::set and friends' iterators can be the same type as the const_iterator that this finally clicked! Thanks for the guidance, nice to know I wasn't going completely off my rocker with the mpl approach :-D --rob

Jeffrey Lee Hellrung, Jr.

3:25 p.m.

On Fri, Feb 24, 2012 at 2:51 AM, Rob Desbois wrote:

...

On 23 February 2012 14:39, Robert Jones wrote:

...
I favoured the type traits magic approach, and publish the resulting value type as the value type of the iterator...

typedef typename if_::type value_type;

Thanks for the input Rob - see below for the solution I settled on.

...
To reiterate Robert Jones' reply, yes, AFAIK, a const iterator should

On 23 February 2012 18:58, Jeffrey Lee Hellrung, Jr. wrote: pass a

...
const-qualified value_type to iterator_facade/iterator_adaptor, as implied by the constant node_iterator example in the docs:

http://www.boost.org/doc/libs/1_48_0/libs/iterator/doc/iterator_facade.html#...

Actually iterator_facade/iterator_adaptor's value type in the tutorials is the _node_ type, not the node's value_type.

I never said anything to the contrary, AFAIK...

...

On a related note, you should specify your reference type you pass to

...
iterator_adaptor explicitly as the return type of your dereference member function. Otherwise I think you'll end up returning a reference to a temporary within operator*. I believe that's *actually* what the quoted error is trying to tell you.

Thanks - I've updated to use node_iterator::iterator_adaptor_::reference as the return type from dereference(). The docs show that this defaults to Value&. The error message still stands though, since const node_type::value_type is still not const.

Huh? I don't understand. "const node_type::value_type" *is* const-qualified. IIRC, in your original post, your dereference member function returned an rvalue (based on the member function definition, not the actual return type). This suggests that the reference type you give to iterator_facade should be Value, rather than accepting the default of Value&.

...

I settled on implementing the boost::mpl::if_ method as shown by Rob, which turned out to be a viable solution to the problem I faced, but then after some more thinking and coding realised that I didn't actually want the mutable iterator type to enable modification of the data in the referenced node. Since this is an ordered tree, modifying the data of a node is clearly a Bad Thing! Feeling somewhat silly that I didn't recognise this before leaping down the rabbit hole...what I now have is that Value is *always* const: template< class NODE > node_iterator: public boost::iterator_adaptor< node_iterator<NODE>, // Derived NODE*, // Base const typename NODE::value_type // Value

...
The reference type is then const typename NODE::value_type& as expected and everything works fine. It was only after discovering that std::set and friends' iterators can be the same type as the const_iterator that this finally clicked!

Thanks for the guidance, nice to know I wasn't going completely off my rocker with the mpl approach :-D --rob

Okay, good to know you got things working, I just wanted to give you a head's up on double-checking to ensure you're not returning an lvalue reference bound to a temporary :) - Jeff

Rob Desbois

4:45 p.m.

On 24 February 2012 15:25, Jeffrey Lee Hellrung, Jr. wrote:

...

On Fri, Feb 24, 2012 at 2:51 AM, Rob Desbois wrote:

...
On 23 February 2012 18:58, Jeffrey Lee Hellrung, Jr. wrote:

...
To reiterate Robert Jones' reply, yes, AFAIK, a const iterator should pass a const-qualified value_type to iterator_facade/iterator_adaptor, as implied by the constant node_iterator example in the docs:

http://www.boost.org/doc/libs/1_48_0/libs/iterator/doc/iterator_facade.html#...

Actually iterator_facade/iterator_adaptor's value type in the tutorials is the _node_ type, not the node's value_type.

I never said anything to the contrary, AFAIK...

You didn't no, but in both iterator_facade and iterator_adaptor tutorials, the dereference operation returns reference to node, not reference to node data.

...

...
...
On a related note, you should specify your reference type you pass to iterator_adaptor explicitly as the return type of your dereference member function. Otherwise I think you'll end up returning a reference to a temporary within operator*. I believe that's *actually* what the quoted error is trying to tell you.

Thanks - I've updated to use node_iterator::iterator_adaptor_::reference as the return type from dereference(). The docs show that this defaults to Value&. The error message still stands though, since const node_type::value_type is still not const.

Huh? I don't understand. "const node_type::value_type" *is* const-qualified.

Hehe sorry, that was clear as mud! The code was roughly: template<class T> struct node { typedef T value_type; /* ... */ }; template<class NODE> struct node_iterator: public node_adaptor<..., /*Value = */ typename NODE::value_type> { /* ... */ }; So node_iterator has Value == node<T>::value_type == T But in node_iterator we have Value == (const node<T>)::value_type == T - the parentheses show the const is bound to the node, not the value type.

...

IIRC, in your original post, your dereference member function returned an rvalue (based on the member function definition, not the actual return type). This suggests that the reference type you give to iterator_facade should be Value, rather than accepting the default of Value&.

Oh yes, didn't even spot that! IIRC the original code returned the typedef 'reference', so was probably just a typo in the copying. Quite a fundamental change though, so apologies for that >.< --rob

4643

Age (days ago)

4644

Last active (days ago)

List overview

Download

5 comments

3 participants

participants (3)

Jeffrey Lee Hellrung, Jr.
Rob Desbois
Robert Jones