C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  tr1 iterator concepts Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message James Hopkin Guest Posted: Fri Nov 12, 2004 3:16 am    Post subject: tr1 iterator concepts The tr1 iterator concepts are certainly a great improvement on the current concepts. Splitting the concepts into traversal and access definitely clarifies things immensely. My question is: why is incremental the most basic traversal concept? (I'll also ask a similar, but less important, question about the access concepts later) Following SGI's example, I'll call a simpler traversal concept 'trivial'. An iterator which models only this trivial traversal concept would have no traversal functionality. The traversal concept hierarchy could look like trivial -> incrementable -> single pass -> forward -> bidirectional -> random I don't think this is just a matter of completeness. Although pointer types model random access traversal, in practice, most pointers really only model this trivial traversal concept. A pointer must point into an array to be even incrementable. For example, the boost::iterator_adaptor tutorial adapts a pointer to single elements in a linked list. It cannot use any of the traversal functionality the pointer advertises. It seems reasonable to want to do something similar, except, where the tutorial adapts a pointer, instead adapt a user type, which models only trivial traversal and some appropriate access concept. I believe currently the only way to do this is to advertise incrementable traversal, but have that fail at run time. Not ideal, to say the least. Any insights into this would be much appreciated. Just briefly, I'd like also to see a trivial access concept (i.e. no dereference). For example, this would seem to be what boost's counting_iterator adaptor theoretically requires. It's currently not a problem since boost::iterator_adaptor currently only requires adaptees to provide a traversal concept (or old-style category). James [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Dennett Guest Posted: Fri Nov 12, 2004 3:05 pm    Post subject: Re: tr1 iterator concepts James Hopkin wrote: Quote: The tr1 iterator concepts are certainly a great improvement on the current concepts. Splitting the concepts into traversal and access definitely clarifies things immensely. My question is: why is incremental the most basic traversal concept? (I'll also ask a similar, but less important, question about the access concepts later) Following SGI's example, I'll call a simpler traversal concept 'trivial'. An iterator which models only this trivial traversal concept would have no traversal functionality. The traversal concept hierarchy could look like trivial -> incrementable -> single pass -> forward -> bidirectional - random I don't think this is just a matter of completeness. Although pointer types model random access traversal, in practice, most pointers really only model this trivial traversal concept. A pointer must point into an array to be even incrementable. Actually, any pointer to an object is incrementable, even if that object is not in an array -- for purposes of pointer arithmetic, it is as if it is the first object in an array with one element. Which isn't to say that the "trivial" traversal category doesn't have uses, just that regular pointers don't fit into that group (with the possible exception of the null pointer value.) -- James [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jonathan Turkanis Guest Posted: Fri Nov 12, 2004 7:38 pm    Post subject: Re: tr1 iterator concepts "James Hopkin" <jhopkin (AT) reflectionsinteractive (DOT) com> wrote Quote: The tr1 iterator concepts are certainly a great improvement on the current concepts. Splitting the concepts into traversal and access definitely clarifies things immensely. Unfortunately the iterator concepts and iterator adaptor library didn't make it into TR1. Quote: Just briefly, I'd like also to see a trivial access concept (i.e. no dereference). For example, this would seem to be what boost's counting_iterator adaptor theoretically requires. It's currently not a problem since boost::iterator_adaptor currently only requires adaptees to provide a traversal concept (or old-style category). I have a couple of other requests, which I've never felt strongly enough about to voice, but this seems like as good a time as any. For traversal, I'd like to see a 'Contiguous Traversal' category below 'Random Access Traversal', applying to iterators which iterate over elements arranged contiguously in memory (i.e., over arrays of elements). It bothers me that some algorithms can apply better optimizations if a vector happens to use native pointers as iterators rather than class types. A Contiguous Traversal category would even the playing field. For access, I'd like to see an 'Opaque Iterator' concept, which applies to non-dereferenceable iterators which are only useful as handles for passing back to the container that generated them. For example, the filtering streams from the yet-to-be-released Boost iostreams library maintain internal chains of filters and source/sinks. It might be useful to provide iterators which could be used to manipulate the chains with a std::list-type interface. However, end-users should not have access to the individual elements of the chain, so the iterators should not be dereferenceable; there's not even a natural value_type. It's easy to define iterators which behave this way, but I'd like to have a standard name for them. Quote: James Jonathan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Sat Nov 13, 2004 3:25 am    Post subject: Re: tr1 iterator concepts [email]jhopkin (AT) reflectionsinteractive (DOT) com[/email] (James Hopkin) writes: Quote: The tr1 iterator concepts are certainly a great improvement on the current concepts. Splitting the concepts into traversal and access definitely clarifies things immensely. My question is: why is incremental the most basic traversal concept? (I'll also ask a similar, but less important, question about the access concepts later) You mean "incrementable." Quote: Following SGI's example, I'll call a simpler traversal concept 'trivial'. An iterator which models only this trivial traversal concept would have no traversal functionality. The traversal concept hierarchy could look like trivial -> incrementable -> single pass -> forward -> bidirectional - random I don't think this is just a matter of completeness. It is. The way to discover what concepts are important is to look at a whole family of non-generic algorithm examples over ordinary non-generic data-structures, and find the concepts that capture the common functionality and allow the algorithms to be generalized. I challenge you to find a place where trivial iterator allows a significant and useful algorithm generalization. Quote: Although pointer types model random access traversal, in practice, most pointers really only model this trivial traversal concept. A pointer must point into an array to be even incrementable. As pointed out elsewhere, every pointer to an object (or just past an object) points into an array. Quote: For example, the boost::iterator_adaptor tutorial adapts a pointer to single elements in a linked list. It cannot use any of the traversal functionality the pointer advertises. That doesn't prove anything about the importance of your suggested concept. Quote: It seems reasonable to want to do something similar, except, where the tutorial adapts a pointer, instead adapt a user type, which models only trivial traversal and some appropriate access concept. We call that "dereferenceable." See indirect_iterator. It's a valid concept, but that doesn't mean it belongs in the iterator concept refinement hierarchy. Quote: I believe currently the only way to do this is to advertise incrementable traversal, but have that fail at run time. Not ideal, to say the least. I don't know what you mean. Dereferenceability is detectable at compile-time with no advertisement. Quote: Any insights into this would be much appreciated. Hope this helps, -- Dave Abrahams Boost Consulting http://www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Sat Nov 13, 2004 3:25 am    Post subject: Re: tr1 iterator concepts "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: Quote: "James Hopkin" <jhopkin (AT) reflectionsinteractive (DOT) com> wrote in message news:a0368c9c.0411110331.33be94b5 (AT) posting (DOT) google.com... The tr1 iterator concepts are certainly a great improvement on the current concepts. Splitting the concepts into traversal and access definitely clarifies things immensely. Unfortunately the iterator concepts and iterator adaptor library didn't make it into TR1. Just briefly, I'd like also to see a trivial access concept (i.e. no dereference). For example, this would seem to be what boost's counting_iterator adaptor theoretically requires. Not unless you really think integers are "trivial access iterators." Quote: It's currently not a problem since boost::iterator_adaptor currently only requires adaptees to provide a traversal concept (or old-style category). It doesn't require that at all; the programmer can supply a traversal concept or old-style category manually. Quote: I have a couple of other requests, which I've never felt strongly enough about to voice, but this seems like as good a time as any. For traversal, I'd like to see a 'Contiguous Traversal' category below 'Random Access Traversal', applying to iterators which iterate over elements arranged contiguously in memory (i.e., over arrays of elements). It bothers me that some algorithms can apply better optimizations if a vector happens to use native pointers as iterators rather than class types. A Contiguous Traversal category would even the playing field. I find it difficult to imagine an algorithm whose generic implementation can be improved when you know its iterators are pointers rather than any other random access iterator. I can imagine special cases where dispatching to some intrinsic function is an advantage when the iterators are pointers, but that's not quite the same thing. Quote: For access, I'd like to see an 'Opaque Iterator' concept, which applies to non-dereferenceable iterators which are only useful as handles for passing back to the container that generated them. That's called a "cursor." Quote: For example, the filtering streams from the yet-to-be-released Boost iostreams library maintain internal chains of filters and source/sinks. It might be useful to provide iterators which could be used to manipulate the chains with a std::list-type interface. However, end-users should not have access to the individual elements of the chain, so the iterators should not be dereferenceable; there's not even a natural value_type. It's easy to define iterators which behave this way, but I'd like to have a standard name for them. What both of you are asking for is outside the scope of the goals of the original proposal, which was to break the bond between access and traversal so that a wider variety of useful iterators can be used efficiently with standard algorithms. These "trivial access/opaque ``iterators'' " aren't really useful with any standard algorithms other than distance (if you can call that an algorithm). -- Dave Abrahams Boost Consulting http://www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jonathan Turkanis Guest Posted: Sun Nov 14, 2004 10:42 am    Post subject: Re: tr1 iterator concepts "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote Quote: "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: I have a couple of other requests, which I've never felt strongly enough about to voice, but this seems like as good a time as any. For traversal, I'd like to see a 'Contiguous Traversal' category below 'Random Access Traversal', applying to iterators which iterate over elements arranged contiguously in memory (i.e., over arrays of elements). It bothers me that some algorithms can apply better optimizations if a vector happens to use native pointers as iterators rather than class types. A Contiguous Traversal category would even the playing field. I find it difficult to imagine an algorithm whose generic implementation can be improved when you know its iterators are pointers rather than any other random access iterator. I can imagine special cases where dispatching to some intrinsic function is an advantage when the iterators are pointers, but that's not quite the same thing. I don't understand the distinction you are drawing, and I don't see how it relates to whether Contiguous Traversal would be a useful category, so let me give an example.Consider an implementation of std::copy like this: template<typename InIt, typename OutIt> OutIt copy(InIt first, InIt last, OutIt Dest) { // uses a for loop. } template<typename T> T* copy(T* first, T* last, T* Dest) { // If T is POD, delegates to a function using // memmove; otherwise, delegates to a function // using a for loop. } // other overloads The problem here is that the optimization using memmove is missed for random-access iterators over POD types arranged contiguously in memory, if they happen to be implemented as classes. Quote: For access, I'd like to see an 'Opaque Iterator' concept, which applies to non-dereferenceable iterators which are only useful as handles for passing back to the container that generated them. That's called a "cursor." Okay, then call them a "cursors." Quote: For example, the filtering streams from the yet-to-be-released Boost iostreams library maintain internal chains of filters and source/sinks. It might be useful to provide iterators which could be used to manipulate the chains with a std::list-type interface. However, end-users should not have access to the individual elements of the chain, so the iterators should not be dereferenceable; there's not even a natural value_type. It's easy to define iterators which behave this way, but I'd like to have a standard name for them. What both of you are asking for is outside the scope of the goals of the original proposal, which was to break the bond between access and traversal so that a wider variety of useful iterators can be used efficiently with standard algorithms. These "trivial access/opaque ``iterators'' " aren't really useful with any standard algorithms other than distance (if you can call that an algorithm). I agree that Opaque Iterators are probably not useful with standard algorithms. But I still think they're still iterators. Here's why. - They're incrementable and optionally decrementable - They occur in expression like c.erase(pos1, pos2); c1.splice(pos1, c2, pos2, pos3); etc. - The easiest way to build them is to use the Boost Iterator library. One of the goals of the STL was to establish standard conventions so that users could learn to use new components quickly. I think Opaque Iterators may be common enough that they deserve a name, even if they don't figure in the requirements of any generic algorithm. But as I said at the beginning, I've never felt strongly about it. Jonathan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Sun Nov 14, 2004 8:39 pm    Post subject: Re: tr1 iterator concepts "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: Quote: "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote in message news:upt2iya60.fsf (AT) boost-consulting (DOT) com... "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: I don't understand the distinction you are drawing, and I don't see how it relates to whether Contiguous Traversal would be a useful category I never argued that it wouldn't be. Quote: so let me give an example.Consider an implementation of std::copy like this: template OutIt copy(InIt first, InIt last, OutIt Dest) { // uses a for loop. } template T* copy(T* first, T* last, T* Dest) { // If T is POD, delegates to a function using // memmove; otherwise, delegates to a function // using a for loop. } // other overloads The problem here is that the optimization using memmove is missed for random-access iterators over POD types arranged contiguously in memory, if they happen to be implemented as classes. Yes, I understood that. The distinction I'm drawing is that concepts are mostly designed to dictate big-O changes in algorithmic approach. These two are actually the same algorithm, and the for loop (given proper loop unrolling either in the library or in the compiler) could be expected to be just as efficient as memmove, or the compiler might in theory be expected to simply notice that the iterator is just a wrapper around a pointer and optimize the copy into memmove... although I believe that aliasing problems may prevent that. What I'm saying is that the introduction of a contiguous traversal concept, though useful, would represent a change in the way concepts have been used in the standard library so far. Not neccessarily a bad thing, but worth noting. Quote: For access, I'd like to see an 'Opaque Iterator' concept, which applies to non-dereferenceable iterators which are only useful as handles for passing back to the container that generated them. That's called a "cursor." Okay, then call them a "cursors." Good, then they don't have to go in the iterator refinement hierarchy. Quote: For example, the filtering streams from the yet-to-be-released Boost iostreams library maintain internal chains of filters and source/sinks. It might be useful to provide iterators which could be used to manipulate the chains with a std::list-type interface. However, end-users should not have access to the individual elements of the chain, so the iterators should not be dereferenceable; there's not even a natural value_type. It's easy to define iterators which behave this way, but I'd like to have a standard name for them. What both of you are asking for is outside the scope of the goals of the original proposal, which was to break the bond between access and traversal so that a wider variety of useful iterators can be used efficiently with standard algorithms. These "trivial access/opaque ``iterators'' " aren't really useful with any standard algorithms other than distance (if you can call that an algorithm). I agree that Opaque Iterators are probably not useful with standard algorithms. It's not just standard algorithms, it's *any* algorithm that can take extra advantage of the capabilities of the "other" iterators. Quote: But I still think they're still iterators. Here's why. - They're incrementable and optionally decrementable - They occur in expression like c.erase(pos1, pos2); c1.splice(pos1, c2, pos2, pos3); etc. - The easiest way to build them is to use the Boost Iterator library. Sort of like the way modern psychiatrists diagnose particular mental conditions based on which drugs are effective in treating them? Quote: One of the goals of the STL was to establish standard conventions so that users could learn to use new components quickly. I think Opaque Iterators may be common enough that they deserve a name, even if they don't figure in the requirements of any generic algorithm. But as I said at the beginning, I've never felt strongly about it. They should be named, but I have doubts about whether that ought to have been part of our iterators proposal. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jonathan Turkanis Guest Posted: Mon Nov 15, 2004 11:37 am    Post subject: Re: tr1 iterator concepts "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote Quote: "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote in message news:upt2iya60.fsf (AT) boost-consulting (DOT) com... "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: I don't understand the distinction you are drawing, and I don't see how it relates to whether Contiguous Traversal would be a useful category I never argued that it wouldn't be. Okay. <snip example> Quote: ... The distinction I'm drawing is that concepts are mostly designed to dictate big-O changes in algorithmic approach. These two are actually the same algorithm, and the for loop ... What I'm saying is that the introduction of a contiguous traversal concept, though useful, would represent a change in the way concepts have been used in the standard library so far. Not necessarily a bad thing, but worth noting. I've never thought of the motivation for concepts being so limited. To me, for any difference in behavior that can lead to a significant optimization - big-O or not -- it's worth considering isolating it as a concept. Some concepts are useful even though they don't allow any optimization in the traditional sense -- they might simply allow specialization of an algorithm for a class of types with an interface completely different than the types the algorithm usually works with. Quote: For access, I'd like to see an 'Opaque Iterator' concept, which applies to non-dereferenceable iterators which are only useful as handles for passing back to the container that generated them. That's called a "cursor." Okay, then call them a "cursors." Good, then they don't have to go in the iterator refinement hierarchy. See below. Quote: I agree that Opaque Iterators are probably not useful with standard algorithms. It's not just standard algorithms, it's *any* algorithm that can take extra advantage of the capabilities of the "other" iterators. Yes, that's what I meant. It's *obvious* they're not useful with the standard algorithms; they're *probably* not useful for other generic algorithms. Quote: But I still think they're still iterators. Here's why. - They're incrementable and optionally decrementable - They occur in expression like c.erase(pos1, pos2); c1.splice(pos1, c2, pos2, pos3); etc. - The easiest way to build them is to use the Boost Iterator library. Sort of like the way modern psychiatrists diagnose particular mental conditions based on which drugs are effective in treating them? That's the best we can do, sometimes. ;-) Suppose we agree that they're not iterators because they can't be used with generic algorithms. So call them schmitterators. Then the Boost Iterator library would be the Boost Iterator and Schmitterator library -- useful for producing (i) iterators for generic algorithms and (ii) schmiterators, which are almost iterators but didn't quite make the cut. I'd rather call them Opaque Iterators and explain that they're not useful for generic algorithms. Quote: One of the goals of the STL was to establish standard conventions so that users could learn to use new components quickly. I think Opaque Iterators may be common enough that they deserve a name, even if they don't figure in the requirements of any generic algorithm. But as I said at the beginning, I've never felt strongly about it. They should be named, but I have doubts about whether that ought to have been part of our iterators proposal. Fair enough. Jonathan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Mon Nov 15, 2004 11:40 am    Post subject: Re: tr1 iterator concepts David Abrahams <dave (AT) boost-consulting (DOT) com> writes: Quote: so let me give an example.Consider an implementation of std::copy like this: template OutIt copy(InIt first, InIt last, OutIt Dest) { // uses a for loop. } template T* copy(T* first, T* last, T* Dest) { // If T is POD, delegates to a function using // memmove; otherwise, delegates to a function // using a for loop. } // other overloads The problem here is that the optimization using memmove is missed for random-access iterators over POD types arranged contiguously in memory, if they happen to be implemented as classes. Yes, I understood that. The distinction I'm drawing is that concepts are mostly designed to dictate big-O changes in algorithmic approach. These two are actually the same algorithm, and the for loop (given proper loop unrolling either in the library or in the compiler) could be expected to be just as efficient as memmove, or the compiler might in theory be expected to simply notice that the iterator is just a wrapper around a pointer and optimize the copy into memmove... although I believe that aliasing problems may prevent that. What I'm saying is that the introduction of a contiguous traversal concept, though useful, would represent a change in the way concepts have been used in the standard library so far. Not neccessarily a bad thing, but worth noting. One further point: contiguousness is not enough to turn std::copy into a memmove. You also need to know that operations on the iterators don't have any side effects and don't throw any exceptions. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Hopkin Guest Posted: Mon Nov 15, 2004 9:34 pm    Post subject: Re: tr1 iterator concepts James Dennett <jdennett (AT) acm (DOT) org> wrote Quote: Actually, any pointer to an object is incrementable, even if that object is not in an array -- for purposes of pointer arithmetic, it is as if it is the first object in an array with one element. Thank you for that. Looks like that's something I've always misunderstood. Quote: Which isn't to say that the "trivial" traversal category doesn't have uses, just that regular pointers don't fit into that group (with the possible exception of the null pointer value.) I agree. The point I was trying to make was that pointers to non-array objects are pretty good examples of this "trivial" traversal category, even if they technically have more functionality. 'boost::optional' would have been a better example. James [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Hopkin Guest Posted: Mon Nov 15, 2004 9:38 pm    Post subject: Re: tr1 iterator concepts David Abrahams <dave (AT) boost-consulting (DOT) com> wrote Quote: I don't think this is just a matter of completeness. It is. The way to discover what concepts are important is to look at a whole family of non-generic algorithm examples over ordinary non-generic data-structures, and find the concepts that capture the common functionality and allow the algorithms to be generalized. I challenge you to find a place where trivial iterator allows a significant and useful algorithm generalization. Looking at it that way, I can see that a trivial traversal category would not be generally useful. I might be barking up the wrong tree with the traversal concepts. Quote: For example, the boost::iterator_adaptor tutorial adapts a pointer to single elements in a linked list. It cannot use any of the traversal functionality the pointer advertises. That doesn't prove anything about the importance of your suggested concept. True. Though it was only meant as an example. Quote: It seems reasonable to want to do something similar, except, where the tutorial adapts a pointer, instead adapt a user type, which models only trivial traversal and some appropriate access concept. We call that "dereferenceable." See indirect_iterator. It's a valid concept, but that doesn't mean it belongs in the iterator concept refinement hierarchy. Fair enough. Quote: I believe currently the only way to do this is to advertise incrementable traversal, but have that fail at run time. Not ideal, to say the least. I don't know what you mean. Dereferenceability is detectable at compile-time with no advertisement. Maybe it would clearer if I explain what I'm working on as an example. I'm using iterator_adaptor in a very similar way to the linked list tutorial example, except that I need to use boost::optional rather than a pointer type. boost::optional is only 'dereferencable' (or models only trivial traversal, the way I put it). I can specialise iterator_traits for my specialisation of boost::optional, but what traversal concept can I give it? Certainly the old categories don't cover it. Perhaps adding a trivial traversal concept is like cracking a nut with a sledgehammer, but it still seems logically correct to me. Quote: Any insights into this would be much appreciated. Hope this helps, Definitely, thanks. David Abrahams also wrote (in another reply): Quote: Just briefly, I'd like also to see a trivial access concept (i.e. no dereference). For example, this would seem to be what boost's counting_iterator adaptor theoretically requires. Not unless you really think integers are "trivial access iterators." If counting_iterator really is an iterator *adaptor*, that's what they're being used as in this case. On the other hand, if something isn't dereferencable, it's moving away from iterator-ness. Presumably in an ideal world, iterator_adaptor's first question of adaptees would be 'is_iterator?'. Since this option isn't available (as has been discussed in other threads), perhaps 'trivial access' fills a gap. Quote: It's currently not a problem since boost::iterator_adaptor currently only requires adaptees to provide a traversal concept (or old-style category). It doesn't require that at all; the programmer can supply a traversal concept or old-style category manually. Sorry, I don't see how your reply differs from what I wrote. James [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Raoul Gough Guest Posted: Mon Nov 15, 2004 9:39 pm    Post subject: Re: tr1 iterator concepts David Abrahams <dave (AT) boost-consulting (DOT) com> wrote Quote: jhopkin (AT) reflectionsinteractive (DOT) com (James Hopkin) writes: [snip] It seems reasonable to want to do something similar, except, where the tutorial adapts a pointer, instead adapt a user type, which models only trivial traversal and some appropriate access concept. We call that "dereferenceable." See indirect_iterator. It's a valid concept, but that doesn't mean it belongs in the iterator concept refinement hierarchy. Seems to me that the "dereferencable" concept is more fundamental, and also necessary for, iterator concepts. An iterator that is not dereferencable is not very useful (except maybe for counting elements - is this a significant case to consider?). On the other hand, a smart pointer or handle or proxy object can be useful without being an iterator. This suggests to me that the iterator concepts should be based on the more fundamental idea of dereferencability. That could encapsulate the knowledge of referenced type in a generic way, useful for iterators and non-iterable handles. For example, a function that takes a single dereferencable object as parameter should be able to work equally well with std::vector<int>::iterator as with boost::shared_ptr<int>. Obviously shared_ptr<int> is not an iterator, whereas vector<int>::iterator is dereferencable. e.g. template<typename T> void foo(T handle) { deref_type<T>::type x (*handle); // ... } Quote: I believe currently the only way to do this is to advertise incrementable traversal, but have that fail at run time. Not ideal, to say the least. I don't know what you mean. Dereferenceability is detectable at compile-time with no advertisement. You mean it's always possible to deduce whether *x is valid (for x of type some_type)? I guess you would still need some way to identify the type of the resulting value, though. Regards, Raoul Gough. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Jonathan Turkanis Guest Posted: Mon Nov 15, 2004 11:47 pm    Post subject: Re: tr1 iterator concepts "David Abrahams" <dave (AT) boost-consulting (DOT) com> wrote: Quote: David Abrahams <dave (AT) boost-consulting (DOT) com> wrote: What I'm saying is that the introduction of a contiguous traversal concept, though useful, would represent a change in the way concepts have been used in the standard library so far. Not neccessarily a bad thing, but worth noting. One further point: contiguousness is not enough to turn std::copy into a memmove. You also need to know that operations on the iterators don't have any side effects and don't throw any exceptions. Good point. This would have to go into the contiguous traversal concept as well. Maybe a better name would be pointer-like. Jonathan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Mon Nov 15, 2004 11:48 pm    Post subject: Re: tr1 iterator concepts "Jonathan Turkanis" <technews (AT) kangaroologic (DOT) com> writes: Quote: Suppose we agree that they're not iterators because they can't be used with generic algorithms. So call them schmitterators. Then the Boost Iterator library would be the Boost Iterator and Schmitterator library -- useful for producing (i) iterators for generic algorithms and (ii) schmiterators, which are almost iterators but didn't quite make the cut. I'd rather call them Opaque Iterators and explain that they're not useful for generic algorithms. Oh, that's fine, and no explanation needed. I'm only arguing against the suggestion that our proposal isn't quite complete without them. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top David Abrahams Guest Posted: Wed Nov 17, 2004 2:14 am    Post subject: Re: tr1 iterator concepts [email]jhopkin (AT) reflectionsinteractive (DOT) com[/email] (James Hopkin) writes: Quote: Not unless you really think integers are "trivial access iterators." If counting_iterator really is an iterator *adaptor*, that's what they're being used as in this case. It's an adaptor that makes iterators. That doesn't mean it has to adapt iterators ;-) Quote: On the other hand, if something isn't dereferencable, it's moving away from iterator-ness. I would think that the very _essence_ of iterator-ness would be... er... the ability to iterate. IOW, incrementability and equality comparison. Quote: Presumably in an ideal world, iterator_adaptor's first question of adaptees would be 'is_iterator?'. I'm not sure. Why would that be ideal? Quote: Since this option isn't available (as has been discussed in other threads), perhaps 'trivial access' fills a gap. I don't see why. If the thing isn't an iterator, the user has to supply the information somehow. You're doing it by specializing iterator_traits, which incidentally is probably a no-no. It's usually a bad idea to specialize library A's template for library B's type unless you're the author of A or B. Someone else may come along and have a different idea of what the specialization should be. ODR. Quote: It's currently not a problem since boost::iterator_adaptor currently only requires adaptees to provide a traversal concept (or old-style category). It doesn't require that at all; the programmer can supply a traversal concept or old-style category manually. Sorry, I don't see how your reply differs from what I wrote. Maybe you meant what I said , but "adaptee" means "the thing being adapted." The thing doesn't have to supply a traversal concept. It can be supplied by the programmer. -- Dave Abrahams Boost Consulting http://www.boost-consulting.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.