C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Vector Iterator headache          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Richard Guest Posted: Mon Jul 25, 2005 7:26 pm    Post subject: Vector Iterator headache Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? If so, what is the best way of doing this? The code I call to add more elements to the vector uses push_back() in a loop to push x elements onto the vector, I was thinking of storing the iterator to the first elements pushed back and using this, but can't find a nice way of doing this either as push_back, unlike insert doesn't return an iterator. Can anyone help? Cheers Rich [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Bob Bell Guest Posted: Tue Jul 26, 2005 12:24 am    Post subject: Re: Vector Iterator headache Richard wrote: Quote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? If so, what is the best way of doing this? The code I call to add more elements to the vector uses push_back() in a loop to push x elements onto the vector, I was thinking of storing the iterator to the first elements pushed back and using this, but can't find a nice way of doing this either as push_back, unlike insert doesn't return an iterator. Can anyone help? Your problem is not the vector iterator reaching the end; it's that vector iterators are invalidated when you push_back(), insert(), or otherwise grow the vector. Before adding items, get the index of the iterator. You can obtain this by subtracting the iterator from vec.begin(), or since you know the iterator is at the end, the index you want is equal to vec.size(). Then add more items, and then reset the iterator to vec.begin() + index. typedef std::vector<your_type>::size_type size_type; std::vector<your_type> vec; std::vector<your_type>::iterator it(vec.begin()); // when "it" reaches vec.end() size_type index = vec.size(); // add more items here... it = vec.begin() + index; // keep on steppin' Bob [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Edson Manoel Guest Posted: Tue Jul 26, 2005 12:25 am    Post subject: Re: Vector Iterator headache You can never push_back elements to a vector and then keep using old iterators, because push_back can invalidate old iterators. A good approach in this case is: // ... myVector and myIterator declarations for (myIterator = myVector.begin(); myIterator != myVector.end(); ++myIterator) { // do something on *myIterator } // convert to numeric position size_t lastPos = myIterator - myVector.begin(); myVector.push_back(...); // do the push_back's myVector.push_back(...;) myIterator = myVector.begin() + lastPos; // now it is valid and points to the first element pushed back above. If the container doesn't invalidate iterators on push_backs (e.g, list), and if the iterator is bidirectional, you can step back the iterator, do the push_back's and then step it forward again: // ... myList and myIterator declarations for (myIterator = myList.begin(); myIterator != myList.end(); ++myIterator) { // do something on *myIterator } // step back --myIterator; // now it points to a valid element (the back element) myList.push_back(...); myList.push_back(...); ++myIterator; // now it points to the first element pushed back above. Richard escreveu: Quote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? If so, what is the best way of doing this? The code I call to add more elements to the vector uses push_back() in a loop to push x elements onto the vector, I was thinking of storing the iterator to the first elements pushed back and using this, but can't find a nice way of doing this either as push_back, unlike insert doesn't return an iterator. Can anyone help? Cheers Rich [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Rupert Kittinger Guest Posted: Tue Jul 26, 2005 12:27 am    Post subject: Re: Vector Iterator headache Richard wrote: Quote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? If so, what is the best way of doing this? The code I call to add more elements to the vector uses push_back() in a loop to push x elements onto the vector, I was thinking of storing the iterator to the first elements pushed back and using this, but can't find a nice way of doing this either as push_back, unlike insert doesn't return an iterator. Can anyone help? Cheers Rich A fundamental problem with your approach is that adding elements to the vector with push_back(), insert(), etc. invalidates your iterator. Rupert [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ethan Eade Guest Posted: Tue Jul 26, 2005 12:28 am    Post subject: Re: Vector Iterator headache Richard wrote: Quote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? If so, what is the best way of doing this? The code I call to add more elements to the vector uses push_back() in a loop to push x elements onto the vector, I was thinking of storing the iterator to the first elements pushed back and using this, but can't find a nice way of doing this either as push_back, unlike insert doesn't return an iterator. Can anyone help? typedef std::vector<my_class>::iterator my_iterator; my_iterator it; for (it = v.begin(); it!=v.end(); it++) { // this is your iteration loop } size_t pos = v.size(); // this is where you are now add_some_stuff_on_the_end_of(v); // this calls push_back(), etc it = v.begin() + pos; // now it points to the first element you added - Ethan Eade [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Sean Kelly Guest Posted: Tue Jul 26, 2005 12:31 am    Post subject: Re: Vector Iterator headache Richard wrote: Quote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? For what it's worth, a plain old pointer is entirely acceptable as an iterator. Indeed, many vector implementations have (of used to have) pointers as their iterator types. So with this in mind, we can assume a few basic things about iterators (pointers) to vectors: - if you increment your way to myVector.end() you should be free to decrement your way back - any vector operation which may cause a reallocation of the underlying array will invalidate all iterators to that vector So the iterator still works fine when you hit myVector.end(), but you must assume that the insertion will invalidate the iterator. So what you need to do is reassign the iterator after every insertion. Fortunately, the insert method for vector returns an iterator to the newly inserted element, so you should be able to do something like this: for (; { if (myIterator == myVector.end()) myIterator = doInsertAt(myIterator); else ++myIterator; } Where doInsertAt does something like this: myIteratorType doInsert(myIteratorType i) { return myVector.insert(i, newValue); } Sean [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Gene Bushuyev Guest Posted: Tue Jul 26, 2005 12:31 am    Post subject: Re: Vector Iterator headache "Richard" <richardd (AT) hmgcc (DOT) gsi.gov.uk> wrote Quote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. I don't know much about the implementation of iterators or vectors for that matter, but it seems that once an iterator equals end(), it cannot be used further even when more elements are added to the vector. Is this correct? No, it's not correct. Quote: If so, what is the best way of doing this? The code I call to add more elements to the vector uses push_back() in a loop to push x elements onto the vector, I was thinking of storing the iterator to the first elements pushed back and using this, but can't find a nice way of doing this either as push_back, unlike insert doesn't return an iterator. Can anyone help? The problem is that when you call push_back() it may require vector to reallocate memory invalidating all iterators. So if you want to iterate in these conditions don't use iterators, use indexes: vector<Type> v; .... for(size_t i = 0; i < v.size(); ++i) { ... v.push_back(); // won't hurt ... } - gene [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Dave Harris Guest Posted: Tue Jul 26, 2005 6:13 pm    Post subject: Re: Vector Iterator headache [email]e.tadeu (AT) gmail (DOT) com[/email] (Edson Manoel) wrote (abridged): Quote: You can never push_back elements to a vector and then keep using old iterators, because push_back can invalidate old iterators. You can if the vector has sufficient capacity. If the original poster knows how many items he wants to add, a reasonable solution is to call reserve() before he starts iterating. -- Dave Harris, Nottingham, UK. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Martin Bonner Guest Posted: Wed Jul 27, 2005 12:36 pm    Post subject: Re: Vector Iterator headache Bob Bell wrote: Quote: Richard wrote: Hi, Can anyone help me with my current iterator nightmare! I have a vector of objects and use an interator to iterate through them. When myIterator == myVector.end(), I want to execute code which adds more elements to the vector and carry on using the same iterator. The application is single-threaded. Your problem is not the vector iterator reaching the end; it's that vector iterators are invalidated when you push_back(), insert(), or otherwise grow the vector. Before adding items, get the index of the iterator. Alternatively, this may be an appropriate time to do ALL the looping with an index rather than iterator. [ 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 Page 1 of 1   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.