iterator_adaptor: disguise iterator as const_iterator?
Hi all, I am trying to disguise a std container non-const iterator as a const_iterator. My guess is that iterator_adaptor could be useful for this, but I can't figure it out myself. I am trying to solve an old problem with the standard library, which is that you can't convert a const_iterator into an iterator. [There are two "solutions" to that problem, one uses distance and is expensive, the other one does a brutal conversion on bitlevel which breaks for several std implementations.] My use case: I have written a wrapper class mymap for std::map. I only want to give map::const_iterators to the users of this class. If the user wants to erase an element from the map, he must pass a const_iterator back to the wrapper class and call "mymap::erase(const_iterator)". The problem is that mymap has no way to convert the const_iterator into an iterator to call "map::erase(iterator)" in turn [there is no "map::erase(const_iterator)"]. So my idea was to write a iterator_adaptor for iterator that lets it behave like a const_iterator. Unfortunately I didn't get very far. I have to say that the documentation was not of much help to me. There are lots of complicated implementation details but only small examples. So any help is appreciated. How can I solve my problem? Side note: In the following code sample, iterator_adaptor accidentally turns a const_iterator into a non-const iterator. (Seemingly, some bit-level casting is done somewhere). Is this a bug? #include <boost/iterator/iterator_adaptor.hpp> #include <map> template <class Value> class node_iter :public boost::iterator_adaptor<node_iter<Value>, Value> { public: node_iter() : node_iter::iterator_adaptor_(0) {} node_iter(Value p) : node_iter::iterator_adaptor_(p) {} }; int main() { typedef std::map<int, int> mymap_type; mymap_type testmap; node_iter<mymap_type::const_iterator> ni(testmap.begin()); ni->second = 42; //this works, not a const_iterator anymore } ___________________________________________________________________________ Die einen haben es, die anderen werden es! http://my-mail.ch/?redirect=9905 So macht schenken richtig Freude! Schenken und Helfen mit World Vision! http://www.my-mail.ch/?redirect=1958
Hi all, I am trying to disguise a std container non-const iterator as a const_iterator. My guess is that iterator_adaptor could be useful for
"Martin Wartens" <martin.wartens@my-mail.ch> wrote in message news:380-2200411230224347494@my-mail.ch... this,
but I can't figure it out myself.
I am trying to solve an old problem with the standard library, which is that you can't convert a const_iterator into an iterator. [There are two "solutions" to that problem, one uses distance and is expensive, the other one does a brutal conversion on bitlevel which breaks for several std implementations.]
A third solution?: (untested) const_iterator_type wrapper::erase( const_iterator_type aItr ) { thismaptype::iterator lItr = thismap.find( aItr->first ); if( lItr == thismap.end() ) throw something; return thismap.erase( lItr ); } Jeff Flinn
Jeff Flinn <TriumphSprint2000 <at> hotmail.com> writes:
A third solution?: (untested)
const_iterator_type wrapper::erase( const_iterator_type aItr ) { thismaptype::iterator lItr = thismap.find( aItr->first );
if( lItr == thismap.end() ) throw something;
return thismap.erase( lItr ); }
You are right, for a map this would be much better than the distance solution, but it is still basically the same problem: You are searching an element that you already know. For a map the overhead is not so big, for containers like list it really hurts. Thanks for your effort, Martin Wartens
Martin Wartens wrote:
Hi all, I am trying to disguise a std container non-const iterator as a const_iterator. My guess is that iterator_adaptor could be useful for this, but I can't figure it out myself.
I am trying to solve an old problem with the standard library, which is that you can't convert a const_iterator into an iterator. [There are two "solutions" to that problem, one uses distance and is expensive, the other one does a brutal conversion on bitlevel which breaks for several std implementations.]
That's not the problem, and "fixing" it actually causes new const-correctness problems. The actual problem is that the standard library doesn't allow const_iterators to be used as position indicators in mutating container operations. The constness of the container should be enough to control whether you can insert. That said, you may have to do this as a workaround for that interface deficiency.
My use case: I have written a wrapper class mymap for std::map. I only want to give map::const_iterators to the users of this class. If the user wants to erase an element from the map, he must pass a const_iterator back to the wrapper class and call "mymap::erase(const_iterator)". The problem is that mymap has no way to convert the const_iterator into an iterator to call "map::erase(iterator)" in turn [there is no "map::erase(const_iterator)"].
So my idea was to write a iterator_adaptor for iterator that lets it behave like a const_iterator. Unfortunately I didn't get very far. I have to say that the documentation was not of much help to me. There are lots of complicated implementation details but only small examples.
You're not kidding? Did you go through the tutorial starting with iterator_facade (http://tinyurl.com/2gzpz#tutorial-example) which continues on to the iterator adaptor tutorial (http://tinyurl.com/58e2p#tutorial-example)? Gee, it looks from the below like you did!
So any help is appreciated. How can I solve my problem?
Side note: In the following code sample, iterator_adaptor accidentally turns a const_iterator into a non-const iterator. (Seemingly, some bit-level casting is done somewhere). Is this a bug?
#include <boost/iterator/iterator_adaptor.hpp> #include <map> template <class Value> class node_iter :public boost::iterator_adaptor<node_iter<Value>, Value> ^^^^^ This thing needs to be an iterator; naming it Value is a bit confusing since that's normally used for the iterator's value_type. { public: node_iter() : node_iter::iterator_adaptor_(0) {}
node_iter(Value p) : node_iter::iterator_adaptor_(p) {} };
int main() { typedef std::map<int, int> mymap_type; mymap_type testmap; node_iter<mymap_type::const_iterator> ni(testmap.begin()); ni->second = 42; //this works, not a const_iterator anymore }
Wow, thanks for finding that case! We're being bitten by the constructor/cast ambiguity. In short, return T(a); is fine when T is not a built-in type, but when it is, all sorts of nasty violations can occur. So I've attached a partial fix (iterator_facade.patch, committed to CVS). The reason it's only partial is that the "pointer" type of your iterator still comes out wrong. So ending your program with return ni->second; also fails to compile. To get around that you can add -DBOOST_ITERATOR_REF_CONSTNESS_KILLS_WRITABILITY to your compiler's command line. The question I have for Jeremy and Thomas is, what would we be giving up by enabling that always? I think it means that some obscure corner cases would fail to work. I think the minimal change needed to get it going is to change: typedef typename mpl::eval_if< detail::iterator_writability_disabled<ValueParam,Reference> , add_pointer<typename add_const<value_type>::type> , add_pointer<value_type> >::type pointer; to: typedef typename mpl::eval_if< mpl::or_< detail::iterator_writability_disabled<ValueParam,Reference> , indirect_traits::is_reference_to_const<Reference> > , add_pointer<typename add_const<value_type>::type> , add_pointer<value_type> >::type pointer; Though I am inclined to think we should just do the simple thing and turn on the #define always. Thoughts? -- Dave Abrahams Boost Consulting http://www.boost-consulting.com --- iterator_facade.hpp.~1.30.~ 2004-09-02 16:07:58.613356800 -0400 +++ iterator_facade.hpp 2004-12-01 11:18:43.026366400 -0500 @@ -7,8 +7,6 @@ #ifndef BOOST_ITERATOR_FACADE_23022003THW_HPP #define BOOST_ITERATOR_FACADE_23022003THW_HPP -#include <boost/static_assert.hpp> - #include <boost/iterator.hpp> #include <boost/iterator/interoperable.hpp> #include <boost/iterator/iterator_traits.hpp> @@ -16,6 +14,9 @@ #include <boost/iterator/detail/facade_iterator_category.hpp> #include <boost/iterator/detail/enable_if.hpp> +#include <boost/implicit_cast.hpp> +#include <boost/static_assert.hpp> + #include <boost/type_traits/is_same.hpp> #include <boost/type_traits/add_const.hpp> #include <boost/type_traits/add_pointer.hpp> @@ -322,7 +323,7 @@ static type make(Reference x) { - return type(&x); + return implicit_cast<type>(&x); } };
I have to say that the documentation was not of much help to me. There are lots of complicated implementation details but only small examples.
You're not kidding? Did you go through the tutorial starting with iterator_facade (http://tinyurl.com/2gzpz#tutorial-example) which continues on to the iterator adaptor tutorial (http://tinyurl.com/58e2p#tutorial-example)? Gee, it looks from the below like you did! No, I am serious. Looking at the iterator_facade doc, first of all it does not tell me what it is all about. The one sentence in the abstract is indeed very abstract. I would like to see the doc starting with a motivating use case. It should explain me why I would want to use it. Then the overview is concerned mainly with the implementation history and why policy classes are not used anymore. These are details that I would expect in the darkest corner of the appendix. The doc continues with more implementation details and describes problems that had to be solved. That is interesting, but it doesn't give me a start on how to use this library. The Reference listing with the class interface I would expect at the end of the doc. I noticed that the template parameters are not explained before the tutorial. I would like to see more examples, if that is possible. I hope this didn't sound rude, I know it must be hard to write a doc for such a complicated library.
Martin
Martin Wartens wrote:
I have to say that the documentation was not of much help to me. There are lots of complicated implementation details but only small examples.
You're not kidding? Did you go through the tutorial starting with iterator_facade (http://tinyurl.com/2gzpz#tutorial-example) which continues on to the iterator adaptor tutorial (http://tinyurl.com/58e2p#tutorial-example)? Gee, it looks from the below like you did!
No, I am serious. Looking at the iterator_facade doc, first of all it does not tell me what it is all about. The one sentence in the abstract is indeed very abstract.
Wow, good point.
I would like to see the doc starting with a motivating use case. It should explain me why I would want to use it. Then the overview is concerned mainly with the implementation history and why policy classes are not used anymore.
Yep. You're supposed to jump to the tutorial, but that really belongs at the front, doesn't it?
These are details that I would expect in the darkest corner of the appendix.
Yep.
The doc continues with more implementation details and describes problems that had to be solved. That is interesting, but it doesn't give me a start on how to use this library. The Reference listing with the class interface I would expect at the end of the doc. I noticed that the template parameters are not explained before the tutorial.
Okay.
I would like to see more examples, if that is possible.
Hm. Examples of what?
I hope this didn't sound rude, I know it must be hard to write a doc for such a complicated library.
Yes, but that usually means the library needs to be simplified ;-) -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
I've started doing a conversion of many old iterators to the new iterators. I also have been going through the docs, so I thought I would add a few comments. --- At Thu, 2 Dec 2004 13:07:48 -0500, David Abrahams wrote:
Martin Wartens wrote:
I have to say that the documentation was not of much help to me. There are lots of complicated implementation details but only small examples.
You're not kidding? Did you go through the tutorial starting with iterator_facade (http://tinyurl.com/2gzpz#tutorial-example) which continues on to the iterator adaptor tutorial (http://tinyurl.com/58e2p#tutorial-example)? Gee, it looks from the below like you did!
No, I am serious. Looking at the iterator_facade doc, first of all it does not tell me what it is all about. The one sentence in the abstract is indeed very abstract.
Wow, good point.
The biggest thing missing for me is what the difference is between facade and adaptor. In particular when would you choose one over the other. I think i know the answer, but it wasn't clear that the docs explained that very well.
I would like to see more examples, if that is possible.
Hm. Examples of what?
The example with details shows a forward iterator that can also be used as an adaptor. Clever for continuity, but reality is seldom that cooperative. I would like to see a full random access facade. For example: build the full suite of four iterators for std::vector from the outside of std: :vector. That is assume std::vector had no iterators; how would iterators be implemented?
I hope this didn't sound rude, I know it must be hard to write a doc for such a complicated library.
Yes, but that usually means the library needs to be simplified ;-)
I have found boost::iterator to be awesome. Using boost::iterator to build new iterators is actually easier than the docs seem to make it out to be. It seems like it might be a case of "you can't see the forest because of the trees." ...Duane
Duane Murphy wrote:
I've started doing a conversion of many old iterators to the new iterators. I also have been going through the docs, so I thought I would add a few comments.
No, I am serious. Looking at the iterator_facade doc, first of all it does not tell me what it is all about. The one sentence in the abstract is indeed very abstract.
Wow, good point.
The biggest thing missing for me is what the difference is between facade and adaptor. In particular when would you choose one over the other. I think i know the answer, but it wasn't clear that the docs explained that very well.
The answer is, ``you'd choose adaptor when you want to build a new iterator that's "just like" some other iterator in some of its behaviors, but (usually) different in some others.'' Yes, seeing that could help.
I would like to see more examples, if that is possible.
Hm. Examples of what?
The example with details shows a forward iterator that can also be used as an adaptor. Clever for continuity, but reality is seldom that cooperative.
You might be surprised to learn that I didn't plan it that way. I said to myself, "I need to build a simple iterator. Probably the simplest thing I can imagine is a linked list iterator. Okay... Hey, that same iterator could be built pretty well with iterator_adaptor after all!"
I would like to see a full random access facade. For example: build the full suite of four iterators for std::vector from the outside of std: :vector. That is assume std::vector had no iterators; how would iterators be implemented?
Well, that's really uninteresting. You'd use pointers, and if you didn't like pointers you'd use iterator_adaptor over the raw pointers, with no behaviors implemented. You'd never implement the two reverse iterators using iterator_facade because according to the standard they're required to be built from std::reverse_iterator, and even if you didn't do that you should build them using boost::reverse_iterator.
I hope this didn't sound rude, I know it must be hard to write a doc for such a complicated library.
Yes, but that usually means the library needs to be simplified ;-)
I have found boost::iterator to be awesome. Using boost::iterator to build new iterators is actually easier than the docs seem to make it out to be. It seems like it might be a case of "you can't see the forest because of the trees."
Might be. But actually I think we have some serious usability problems. The way defaults are computed in this library is very complicated, to the point that documenting it is nearly impossible. We should revisit that problem starting from the specification side and then proceeding to coding. The authors of this library are somewhat swamped and burned out on it at the moment, so if anyone would like to volunteer to help with these improvements (I mean with the authors' participation) they'd be more likely to get done. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
Duane Murphy wrote:
I have found boost::iterator to be awesome. Using boost::iterator to build new iterators is actually easier than the docs seem to make it out to be. It seems like it might be a case of "you can't see the forest because of the trees."
Well the truth of the matter is that there are quite a few trees. The bad news is that iterators are way more subtle than one might think. The good news is that most of the time you won't realize that. Though that might cause problems down the line. Think about the old don't derive from an iterator problem. You can get away with it for a long time. As far as the library doc's are concerned I think they have to deal with the trees, though it is perfectly possible that the docs are to focused on the subtleties. Thomas -- Thomas Witt witt@acm.org
Hi, I came up with a solution that seems to work. It is as simple as adding "const" to the Value template parameter of the iterator_adapter. Then I can have a non- const iterator that always returns const when dereferenced. Unfortunately, the iterator_adapter class has a public member function "base" that returns the underlying iterator. Since I want to prevent public access to the underlying operator, I had to tweak iterator_adapter and make this function protected. Then I want to give access to the base function only to the container adaptor (a map adaptor in my example). Providing the friend access in a generic way is a little bit awkward, as it has to be done through a helper class. Some sample code for this is given below. I have not yet fully explored this solution, I hope I won't face any nasty surprises. Martin #include <boost/iterator/iterator_adaptor.hpp> template<class GetsAccess> class FriendHelper; //non-const Iterator that will be disguised as const iterator, //only ContainerAdaptor will get access to the real iterator template <class Iterator, class ContainerAdaptor> class const_iter :public boost::iterator_adaptor< const_iter<Iterator, ContainerAdaptor>, //a std iterator Iterator, //the type that the iterator points to, but constified const typename Iterator::value_type > { public: const_iter() : const_iter::iterator_adaptor_() {} explicit const_iter(const Iterator& p) : const_iter::iterator_adaptor_(p) {} protected: //provide access to the underlying iterator to the //ContainerAdaptor friend class FriendHelper< ContainerAdaptor >; const_iter<Iterator, ContainerAdaptor> const& base() const { return base(); } }; //the ContainerAdaptor gets access to the constiter base function template<class ContainerAdaptor> class FriendHelper { typedef typename ContainerAdaptor::constiter_type constiter_type; public: constiter_type const& base( const constiter_type& constit ) { return constit.base(); } }; //sketch of an adaptor to map class mymap{ private: friend class FriendHelper<mymap>; typedef std::map<int, int> mymap_type; typedef const_iter<mymap_type::iterator, mymap > constiter_type; public: void dosomething() { mymap_type testmap; constiter_type mit(testmap.begin()); //access the underlying operator through FriendHelper FriendHelper<mymap>().base(mit); } };
Martin Wartens wrote:
Hi,
I came up with a solution that seems to work. It is as simple as adding "const" to the Value template parameter of the iterator_adapter.
Yes, I could (and should) have told you that would work. But it's not a good answer. The library really ought to do the right thing for this sort of iterator.
Then I can have a non- const iterator that always returns const when dereferenced. Unfortunately, the iterator_adapter class has a public member function "base" that returns the underlying iterator. Since I want to prevent public access to the underlying operator, I had to tweak iterator_adapter and make this function protected.
The right answer for that case is not to advertise the function to your clients. If they don't know it's there, they can't call it. We could consider making it a free function in the library, but I don't see how that could be any more "hidden." Your FriendHelper is just as publicly accessible as the base() member function is today. You can also make it private in your derived class, or hide it with another member named "base." That would make it inaccessible unless your clients actually cast your iterator to its base class.
Then I want to give access to the base function only to the container adaptor (a map adaptor in my example). Providing the friend access in a generic way is a little bit awkward, as it has to be done through a helper class. Some sample code for this is given below. I have not yet fully explored this solution, I hope I won't face any nasty surprises.
-- Dave Abrahams Boost Consulting http://www.boost-consulting.com
The library really ought to do the right thing for this sort of iterator.
Sorry, I didn't get that. Which library?
The right answer for that case is not to advertise the function to your clients. If they don't know it's there, they can't call it.
Yes indeed, meanwhile I have decided to go that way. Martin
Martin Wartens wrote:
The library really ought to do the right thing for this sort of iterator.
Sorry, I didn't get that. Which library?
The boost iterators library. What you tried to do the first time ought to work.
The right answer for that case is not to advertise the function to your clients. If they don't know it's there, they can't call it.
Yes indeed, meanwhile I have decided to go that way.
Good plan. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
Martin Wartens wrote:
The library really ought to do the right thing for this sort of iterator.
Sorry, I didn't get that. Which library?
The boost iterators library. What you tried to do the first time ought to work.
Okay, fixed in CVS. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
participants (4)
-
David Abrahams -
Duane Murphy -
Jeff Flinn -
Martin Wartens -
Thomas Witt