[iterator] iterator_facade reference type problem
Dear All, I have a problem with boost::iterator_facade. Here's an example: say I'm implementing an associative container that stores a sorted vector of keys and a separate sorted vector of values: template <typename KEY, typename VALUE> class vecmap { std::vector<KEY> keys; std::vector<VALUE> values; I can make an iterator for this that stores one iterator for each of the vectors: class iterator: public boost::iterator_facade<iterator, std::pair<KEY,VALUE>, boost::bidirectional_traversal_tag> { std::vector<KEY>::iterator ki; std::vector<VALUE>::iterator vi; void increment() { ++ki; ++vi; } void decrement() { --ki; --vi; } .... But what do I do about the reference type? I can't use std::pair<const KEY,VALUE>& because I'm not storing the keys and values in that way. It's almost possible to use std::pair<KEY,VALUE> for a const_iterator, but not if you want to allow the user to change the value through the reference. What I think I want to use is std::pair<KEY,VALUE&> i.e. the key is returned by value and only the value is returned by reference. But when I try this I get various cryptic errors about references to references and mpl things. So, has anyone else tried to do something like this? I wonder if boost::reference could be part of the solution. Thanks for any suggestions, Phil.
Phil Endecott wrote:
Dear All,
But what do I do about the reference type? I can't use std::pair<const KEY,VALUE>& because I'm not storing the keys and values in that way. It's almost possible to use std::pair<KEY,VALUE> for a const_iterator, but not if you want to allow the user to change the value through the reference.
You are iterating over 2 vectors in parallel? Isn't that the job of zip_iterator? If you insist on using iterator_facade, my guess would be, since dereferencing creates a temporary, that iterator_facade::Reference must be explicitly Value, not Value& (the default).
But what do I do about the reference type? I can't use std::pair<const KEY,VALUE>& because
Provided I understood correctly, would this be a possibility? #ifndef BOOST_MAP2_ZIP_FUNC #define BOOST_MAP2_ZIP_FUNC #include <boost/tuple/tuple.hpp> #include <boost/iterator/zip_iterator.hpp> #include <boost/iterator/transform_iterator.hpp> #include <boost/ref.hpp> #include <utility> namespace boost{ namespace map2{ template<typename Key,typename Value> struct zip_func { zip_func(){} typedef const boost::tuple< const Key&, Value& >& argument_type; typedef std::pair<Key,boost::reference_wrapper<Value> > result_type; result_type operator()(argument_type t) const { return result_type( boost::get<0>(t), boost::ref(boost::get<1>(t)) ); } }; template<typename ItK,typename ItV> struct iterator{ typedef boost::tuple< ItK, ItV > it_tuple_; typedef typename boost::zip_iterator<it_tuple_> zip_iter_; typedef typename boost::iterator_value<ItK>::type k_; typedef typename boost::iterator_value<ItV>::type v_; typedef zip_func<k_,v_> func_; typedef boost::transform_iterator<func_,zip_iter_> type; static type call(ItK it_k,ItV it_v){ return type(zip_iter_(it_tuple_(it_k,it_v)),func_()); } }; }// map2 }// boost #endif #include <vector> #include <iostream> #include <boost/assign/std/vector.hpp> #include <map2_iterator.hpp> int main (int argc, char * const argv[]) { typedef int key_; typedef int val_; typedef std::vector<key_> keys_; typedef std::vector<val_> vals_; using namespace boost::assign; keys_ keys; keys += 1,2,3; vals_ vals; vals += 1,2,3; typedef boost::range_iterator<keys_>::type it_k_; typedef boost::range_iterator<vals_>::type it_v_; typedef boost::map2::iterator<it_k_,it_v_> meta_map2_; typedef meta_map2_::type it_map_; it_map_ b_map = meta_map2_::call(boost::begin(keys),boost::begin(vals)); it_map_ e_map = meta_map2_::call(boost::end(keys),boost::end(vals)); int i = 1; while(b_map!=e_map){ BOOST_ASSERT(vals[i-1] == i); ++(b_map->second); BOOST_ASSERT(vals[i-1] == i+1); ++b_map; ++i; } return 0; }
Phil Endecott wrote: <snip>
reference. What I think I want to use is std::pair<KEY,VALUE&> i.e. the key is returned by value and only the value is returned by reference. But when I try this I get various cryptic errors about references to references and mpl things.
So, has anyone else tried to do something like this? I wonder if boost::reference could be part of the solution.
Thanks for any suggestions,
Phil.
I think your "references to references" problem could have to do with std::pair not being able to handle references "correctly" :( You might have to roll your own pair type that uses call_traits to avoid references to references... (I've had to do this myself) er's solution seems to do mostly what you want, except the value is wrapped in a reference_wrapper, which could be inconvenient. Also, probably want the mutable reference type to be a std::pair< const Key, ... >. - Jeff
Phil Endecott wrote:
But what do I do about the reference type? I can't use std::pair<const KEY,VALUE>& because I'm not storing the keys and values in that way. It's almost possible to use std::pair<KEY,VALUE> for a const_iterator, but not if you want to allow the user to change the value through the reference. What I think I want to use is std::pair<KEY,VALUE&> i.e. the key is returned by value and only the value is returned by reference. But when I try this I get various cryptic errors about references to references and mpl things.
I've done some more experiments, and it seems to work with std::pair<const KEY, value&> if i write (*iter).second rather than iter->second. Looking at the iterator_facade source, operator-> calls operator* and passes the result to operator_arrow_result::make(). This takes its address and, because std::pair<const KEY,VALUE&> is not a reference, it tries to convert it to operator_arrow_proxy<...>. This fails because std::pair<const KEY,VALUE&> is not convertible to std::pair<KEY,VALUE>. I think I just want operator-> to return a pointer to my reference type, but the operator_arrow_result stuff is trying to do something more complicated. In what case is the operator_arrow_proxy useful? Is there some way to get what I want using iterator_facade? (Thanks to er for the comments about zip_iterator. It's interesting that zip_iterator uses iterator_facade internally and doesn't appear to do anything special to avoid this problem. Thanks also to Jeffrey for the comments about std::pair's deficiencies wrt references; I think that by fixing that I could make pair<A,B&> convertible to pair<A,B> and get the code to compile, but it would still be broken due to a reference to a temporary.) BTW I have been testing with an oldish version of Boost, but I've looked at the source in svn and it doesn't seem to have changed much. Cheers, Phil.
Phil Endecott wrote:
I've done some more experiments, and it seems to work with std::pair<const KEY, value&> if i write (*iter).second rather than iter->second.
Looking at the iterator_facade source, operator-> calls operator* and passes the result to operator_arrow_result::make(). This takes its address and, because std::pair<const KEY,VALUE&> is not a reference, it tries to convert it to operator_arrow_proxy<...>. This fails because std::pair<const KEY,VALUE&> is not convertible to std::pair<KEY,VALUE>.
I think I just want operator-> to return a pointer to my reference type, but the operator_arrow_result stuff is trying to do something more complicated. In what case is the operator_arrow_proxy useful? Is there some way to get what I want using iterator_facade? <snip> BTW I have been testing with an oldish version of Boost, but I've looked at the source in svn and it doesn't seem to have changed much.
Cheers, Phil.
(Also looking at the code) operator_array_proxy should be probably be instantiated with the Reference, not ValueType...??? Would that be correct? I.e., operator_array_proxy should wrap a reference (which is not a real C++ reference), not a value... You *could* just overload operator-> in the derived class to do something else (in this case, I would say try using a proxy that wraps a reference). Also, just to be clear, the operator_array_proxy stuff in iterator_facade fails not because std::pair< const KEY, VALUE& > isn't convertible to std::pair< KEY, VALUE >, but because their pointers aren't convertible. At least that's what I'm seeing... Seems like I stumbled on this in the past and rather than figure out what was wrong, I just redefined operator-> in the derived class to work... - Jeff
Jeffrey Hellrung wrote:
Phil Endecott wrote:
I've done some more experiments, and it seems to work with std::pair<const KEY, value&> if i write (*iter).second rather than iter->second.
Looking at the iterator_facade source, operator-> calls operator* and passes the result to operator_arrow_result::make(). This takes its address and, because std::pair<const KEY,VALUE&> is not a reference, it tries to convert it to operator_arrow_proxy<...>. This fails because std::pair<const KEY,VALUE&> is not convertible to std::pair<KEY,VALUE>.
I think I just want operator-> to return a pointer to my reference type, but the operator_arrow_result stuff is trying to do something more complicated. In what case is the operator_arrow_proxy useful? Is there some way to get what I want using iterator_facade? <snip> BTW I have been testing with an oldish version of Boost, but I've looked at the source in svn and it doesn't seem to have changed much.
Cheers, Phil.
(Also looking at the code) operator_array_proxy should be probably be instantiated with the Reference, not ValueType...??? Would that be correct? I.e., operator_array_proxy should wrap a reference (which is not a real C++ reference), not a value...
You *could* just overload operator-> in the derived class to do something else (in this case, I would say try using a proxy that wraps a reference).
Also, just to be clear, the operator_array_proxy stuff in iterator_facade fails not because std::pair< const KEY, VALUE& > isn't convertible to std::pair< KEY, VALUE >, but because their pointers aren't convertible. At least that's what I'm seeing...
Seems like I stumbled on this in the past and rather than figure out what was wrong, I just redefined operator-> in the derived class to work...
Hi Jeff, s/operator_array_proxy/operator_arrow_proxy/g There seem to be a couple of issues here. Firstly, as you say operator_arrow_proxy is being instantiated with the ValueType but there would be more chance of it working if it were instantiated with the Reference. Secondly, std::pair containing a non-const reference for the value causes a "forming reference to reference" error in is_convertible<pair<KEY,VALUE&>,pair<KEY,VALUE>> (is_convertible_basic_impl gcc version; is_convertible.hpp line 137). Is this a SFINAE issue? This is being called from iterator_facade_default_category "check for readability". I'm out of my depth trying to track this down any further. I have fixed it, presumably as you did, with a custom pair-like type and a custom arrow_proxy type, something like this: struct iter_ref_t { // replacement for std::pair const KEY first; VALUE& second; iter_ref_t(const KEY first_, VALUE& second_): first(first_), second(second_) {} }; class iterator: public boost::iterator_facade<iterator, std::pair<KEY,VALUE>, boost::bidirectional_traversal_tag, iter_ref_t> { iter_ref_t dereference() const { return iter_ref_t(....); } struct arrow_proxy { // replacement for iterator_facade::operator_arrow_proxy mutable iter_ref_t r; arrow_proxy(const iter_ref_t& r_): r(r_) {} iter_ref_t* operator->() const { return &r; } }; public: arrow_proxy operator->() const { // override version in iterator_facade return arrow_proxy(dereference()); } }; Would any Boost.Iterator experts care to comment? BTW it seems to me that the operator_arrow_proxy thing is really a sort of "smart pointer" - it's an object that looks like a pointer, but it always points to an object that it contains. Does it have more general applications? Regards, Phil.
participants (3)
-
er -
Jeffrey Hellrung -
Phil Endecott