C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Iterator in STL. Goto page 1, 2  Next          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message yijun_lily@yahoo.com Guest Posted: Mon Jun 20, 2005 9:12 am    Post subject: Iterator in STL. Dear all, I know iterator like a pointer, but I still don't quite understand it. How is iterator implemented? Container is just a template class, what is iterator?Thanks, [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carlos Moreno Guest Posted: Tue Jun 21, 2005 9:58 am    Post subject: Re: Iterator in STL. [email]yijun_lily (AT) yahoo (DOT) com[/email] wrote: Quote: Dear all, I know iterator like a pointer, but I still don't quite understand it. How is iterator implemented? Container is just a template class, what is iterator?Thanks, Iterator is typically class -- defined inside the corresponding container class (as we can know when seeing vector<int>::iterator). It could be any type that behaves as pointers; including pointers themselves (IOW, an iterator's implementation can be simply a pointer). For instance: template <typename T> class Array { T * data; public: typedef T * iterator; typedef const T * const_iterator; // ... }; The above meets the requirements for an iterator -- but it is not considered a good practice (it allows *other* things to happen, such as assigning NULL or comparing against NULL, which should have nothing to do with iterators). Also, the above is an example for an array-like data structure; it could never work for a linked list, since operator++ and -- would not work. A more general implementation could simply be a class (one class per type of iterator, that is) that contains the pointer (or whatever data members that allow us to access the container's data) and implements the required operators. Notice that an iterator is a concept more abstract than a way of accessing the elements of a container (e.g., stream iterators), and so the actual implementation (data members and the member functions implementation) can vary a lot for different types of iterators. HTH, Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Razvan Cojocaru Guest Posted: Tue Jun 21, 2005 10:00 am    Post subject: Re: Iterator in STL. An iterator is an object that allows you to go through a container, one element at a time. An iterator can behave (almost) just like a pointer: it can point to an element in the container, it can be dereferenced to get the value it points to, you can compare it to other iterators, and you can increment and decrement it. Iterators are specific to containers, so obtaining an iterator to a container requires specifying the container type in the iterator definition. Like so: container::iterator i; // or container::const_iterator i; where an iterator behaves like a pointer, and a const_iterator behaves like a pointer-to-const. There are several types of iterators. You can advance a random iterator several elements with one operation, for example. The implementation for iterators should not concern you. Just treat them like opaque pointer-like object. The standard doesn't specify the exact implementation, just algorithm complexity requirements. I hope that clears it up for you some. Cheers, Razvan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ron Natalie Guest Posted: Tue Jun 21, 2005 10:04 am    Post subject: Re: Iterator in STL. [email]yijun_lily (AT) yahoo (DOT) com[/email] wrote: Quote: Dear all, I know iterator like a pointer, but I still don't quite understand it. How is iterator implemented? Container is just a template class, what is iterator?Thanks, An iterator is some type that is specific to the container it belongs. You don't need to know what it is, just that it supports a certain set of operations such as ++ or [] (depending on the traits of the container you using). It might be a pointer (for vector it frequently is) or it might be some sort of class with all those operators overloaded on it. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ben Hutchings Guest Posted: Tue Jun 21, 2005 10:07 am    Post subject: Re: Iterator in STL. [email]yijun_lily (AT) yahoo (DOT) com[/email] <yijun_lily (AT) yahoo (DOT) com> wrote: Quote: Dear all, I know iterator like a pointer, but I still don't quite understand it. How is iterator implemented? Container is just a template class, what is iterator?Thanks, A container is an instance of a class, which may or may not be instantiated from a template. An iterator is usually an instance of a class that overloads the operators required for its iterator category. For some containers, the iterators are actually pointers, but this is an implementation detail. -- Ben Hutchings Having problems with C++ templates? Your questions may be answered by <http://womble.decadentplace.org.uk/c++/template-faq.html>. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top tony_in_da_uk@yahoo.co.uk Guest Posted: Tue Jun 21, 2005 4:11 pm    Post subject: Re: Iterator in STL. An iterator generalises the task of referring to a position within data. This may be useful when a pointer is unworkable for the task, such as when wishing to refer to a single bit within a byte, a position in an I/O stream, when the data may move around in memory, but can be found again on demand using a base address and offset or index, or when the data is generated on demand. An iterator may also have an awareness of the type of container it addresses, such that incrementing or decrementing it can select the next item, whereas pointers move by multiples of the pointed-to type's size. Re "Container is just a template class", that's not literally true, but I guess we all know what you mean: the templated nature of containers are the magic which is new to people coming from C backgrounds.... Cheers - Tony [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top frantzdale3i@gmail.com Guest Posted: Tue Jun 21, 2005 4:18 pm    Post subject: Re: Iterator in STL. It can be implemented any number of ways. STL's std::vector<T>::iterator is usually a T*, although it doesn't have to be. Remember, templated code is polymorphic at compile time not run time, so an iterator is simply anything that acts like an iterator, including a pointer. It doesn't have to inherit from an abstract iterator interface class or anything like that. --Ben [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Cristian Iorga Guest Posted: Tue Jun 21, 2005 4:19 pm    Post subject: Re: Iterator in STL. Check out the Iterator pattern on Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (http://www.amazon.com/exec/obidos/tg/detail/-/0201633612/104-8577420-4812740?v=glance) or you can search the Internet for resources like this : http://www.dofactory.com/Patterns/PatternIterator.aspx [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top msalters Guest Posted: Tue Jun 21, 2005 6:33 pm    Post subject: Re: Iterator in STL. Razvan Cojocaru schreef: Quote: An iterator is an object that allows you to go through a container, one element at a time. That's a common use, but actually anything that looks like a container can have iterators too. E.g. If I have two containers C1 and C2, i could make an iterator that iterates over all combinations of elements (e1|C1,e2|C2). That iterator would simply keep two iterators i1 and 12 into C1 and C2. In operator++(), every time i1==C1.end(), increment i2 and reset i1. Basically, an iterator is any type that satifies the requirements of iterator spelled out in the standard (roughly, operators ++ and *) HTH, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top meadori Guest Posted: Tue Jun 21, 2005 6:33 pm    Post subject: Re: Iterator in STL. Razvan Cojocaru wrote: Quote: An iterator is an object that allows you to go through a container, one element at a time. An iterator can behave (almost) just like a pointer: it can point to an element in the container, it can be dereferenced to get the value it points to, you can compare it to other iterators, and you can increment and decrement it. Decrement is only available for bidirectional and random access iterators. Quote: Iterators are specific to containers, so obtaining an iterator to a container requires specifying the container type in the iterator definition. Like so: container::iterator i; // or container::const_iterator i; where an iterator behaves like a pointer, and a const_iterator behaves like a pointer-to-const. There are several types of iterators. You can advance a random iterator several elements with one operation, for example. The implementation for iterators should not concern you. Just treat them like opaque pointer-like object. The standard doesn't specify the exact implementation, just algorithm complexity requirements. The standard specifies more than that. It also has interface requirements and the semantics of the features exposed in the interface. Quote: I hope that clears it up for you some. Cheers, Razvan [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Calum Grant Guest Posted: Wed Jun 22, 2005 8:03 am    Post subject: Re: Iterator in STL. [email]yijun_lily (AT) yahoo (DOT) com[/email] wrote: Quote: Dear all, I know iterator like a pointer, but I still don't quite understand it. How is iterator implemented? That depends on the container. For a std::vector or std::string etc, an iterator can be a pointer into the array. begin() returns the "memory address" of the start of the array, and end() returns the memory address of the end of the array. ++ and -- advance the pointer by sizeof the element just like C. For a std::map, std::multimap, std::set and std::multiset, an iterator is a pointer to a "node" in the tree. ++ and -- perform a tree-walking algorithm to discover the next/previous node, and there is a special node meaning "end" (which may be null). Of course, these implementations are "typical", the standard does not specify how they should be implemented providing they behave in certain ways. The beauty of polymorphism (in this case, parametric polymorphism, aka templates) is that is does not matter how the iterator is implemented for your code to work. Calum [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top msalters Guest Posted: Wed Jun 22, 2005 1:04 pm    Post subject: Re: Iterator in STL. Calum Grant schreef: Quote: For a std::map, std::multimap, std::set and std::multiset, an iterator is a pointer to a "node" in the tree. ++ and -- perform a tree-walking algorithm to discover the next/previous node, and there is a special node meaning "end" (which may be null). This is one implementation, but IIRC there is no reason why the iterator and the node have to be separate objects. Even if you have nodes holding keys and values, the iterator may hold the pointers to the previous and next iterator. In both cases the map::iterator would not be a simple wrapper for a single pointer. In any case, map::iterator is never exactly a pointer. It has an operator++ which is incompatible with the operator++ of pointers. HTH, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Wed Jun 22, 2005 1:10 pm    Post subject: Re: Iterator in STL. Cristian Iorga wrote: Quote: Check out the Iterator pattern on Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (http://www.amazon.com/exec/obidos/tg/detail/-/0201633612/104-8577420-4812740?v=glance) or you can search the Internet for resources like this : http://www.dofactory.com/Patterns/PatternIterator.aspx But pay attention: what the C++ standard (and most of the C++ community) calls an iterator is NOT an iterator according to the classical definition (such as in the GoF book): in the context of C++, an "iterator" is generally a sort of smart pointer, rather than what is classically known as an iterator. -- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carlos Moreno Guest Posted: Thu Jun 23, 2005 9:41 am    Post subject: Re: Iterator in STL. [email]kanze (AT) gabi-soft (DOT) fr[/email] wrote: Quote: Cristian Iorga wrote: Check out the Iterator pattern on Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (http://www.amazon.com/exec/obidos/tg/detail/-/0201633612/104-8577420-4812740?v=glance) or you can search the Internet for resources like this : http://www.dofactory.com/Patterns/PatternIterator.aspx But pay attention: what the C++ standard (and most of the C++ community) calls an iterator is NOT an iterator according to the classical definition (such as in the GoF book): in the context of C++, an "iterator" is generally a sort of smart pointer, rather than what is classically known as an iterator. I disagree. The way I see it, the STL implements iterators with a syntax that looks like pointer operations. You have iterators for different data structures -- arrays/strings, linked lists, deques, and even the tree-like associative containers. I hardly call that a "smart pointer". You also have stream iterators, insert iterators -- those are in no way "smart pointers", as they encapsulate actions that are *very* different in terms of physical meaning, even though they're equivalent in terms of "logical" meaning. The very notion of reverse_iterators hints you that the concept does not really follow closely the behaviour of a pointer, in which ++ is directly related with the physical action of adding something to the memory address. With reverse_iterators, ++ means moving to the next element of the iteratee (the next element in the logical sequence, which is the sequence going from last to first) OTOH, I can hear you screaming: NOOOO, incrementing a pointer IS NOT the same as adding something to a memory address -- incrementing a pointer is an abstract operation that means pointing to the "next" object, not unlike iterators. Well, in that case, I would argue that a pointer is then a particular implementation of the iterator design pattern. IOW, a pointer is a "dumb iterator", instead of an iterator being a "smart pointer" :-) A pointer would be a particular type of iterator, that we could think of as, say, memory_iterator<type>. Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Thu Jun 23, 2005 11:09 am    Post subject: Re: Iterator in STL. Carlos Moreno wrote: Quote: kanze (AT) gabi-soft (DOT) fr wrote: Cristian Iorga wrote: Check out the Iterator pattern on Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides (http://www.amazon.com/exec/obidos/tg/detail/-/0201633612/104-8577420-4812740?v=glance) or you can search the Internet for resources like this : http://www.dofactory.com/Patterns/PatternIterator.aspx But pay attention: what the C++ standard (and most of the C++ community) calls an iterator is NOT an iterator according to the classical definition (such as in the GoF book): in the context of C++, an "iterator" is generally a sort of smart pointer, rather than what is classically known as an iterator. I disagree. There's really nothing to disagree with. The term "iterator" was in common use for something like twenty-five or thirty years before the STL started using it. It had a meaning then, and the references quoted used that meaning, and not the STL meaning. Smart pointers, in C++, also predate the STL. And according to the usual definition back then, STL iterators are smart pointers. (The overload unary * and ->.) Quote: The way I see it, the STL implements iterators with a syntax that looks like pointer operations. The classical iterator is a single object which encapsulates three functions: accessing an element in a sequence, advancing to the next element in a sequence, and determining the end of the sequence. The STL iterators don't meet the last requirement. Of course, the *use* and the *purpose* of STL iterators is the same as that of classical iterators. So there is definitly some justification in using the term. And the meaning of words evolves with time. But when considering literature concerning classical iterators, it's important to realize that STL iterators don't conform to the classical definition. Quote: You have iterators for different data structures -- arrays/strings, linked lists, deques, and even the tree-like associative containers. I hardly call that a "smart pointer". Traditionally, a "smart pointer" is a class which implements the pointer operations, * and ->. I've never seen a smart pointer which emulated everything a C pointer does -- most don't emulate pointer arithmetic, for example. An STL iterator *is* a smart pointer. It's probably more than just a smart pointer, but it is certainly closer to a traditional smart pointer than it is to a traditional iterator. Quote: You also have stream iterators, insert iterators -- those are in no way "smart pointers", as they encapsulate actions that are *very* different in terms of physical meaning, even though they're equivalent in terms of "logical" meaning. So. That's the basic principle behind a lot of smart pointers. The whole point of a smart pointer is that it encapsulates something different from the pure physical meaning. Otherwise, there's no point; just use a raw pointer. Quote: The very notion of reverse_iterators hints you that the concept does not really follow closely the behaviour of a pointer, in which ++ is directly related with the physical action of adding something to the memory address. With reverse_iterators, ++ means moving to the next element of the iteratee (the next element in the logical sequence, which is the sequence going from last to first) OTOH, I can hear you screaming: NOOOO, incrementing a pointer IS NOT the same as adding something to a memory address -- incrementing a pointer is an abstract operation that means pointing to the "next" object, not unlike iterators. It's a question of the level of abstraction. Raw pointers have no real abstraction; it's all very physical. The whole point of smart pointers is to add some additional abstraction: ownership, for example, or locking... or a different meaning of incrementation. Quote: Well, in that case, I would argue that a pointer is then a particular implementation of the iterator design pattern. IOW, a pointer is a "dumb iterator", instead of an iterator being a "smart pointer" An iterator is a much higher level concept. An iterator (traditionally, at least) knows the "bounds". That is an essential part of an iterator, and that is lacking in a raw pointer. -- James Kanze GABI Software Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ 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.