Like Tree1Likes
  • 1 Post By Elysia

Vector erase loop invalidating iterators

This is a discussion on Vector erase loop invalidating iterators within the C++ Programming forums, part of the General Programming Boards category; How do you do something like check all elements in a vector for some condition, and erase those that meet ...

  1. #1
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183

    Vector erase loop invalidating iterators

    How do you do something like check all elements in a vector for some condition, and erase those that meet the condition?

    I have always been doing something like this -
    Code:
    for (std::vector<T>::iterator it = v.begin(); it != v.end();)
    {
         std::vector<T>::iterator next = it + 1;
         if (should_remove(*it))
         {
              v.erase(it);
         }
         it = next;
    }
    The problem is, I just realized, if the element removed is the last element, "it" will end up pointing to end()+1, and bad things will happen.

    I can do a special case for last element, but is there a cleaner way?

  2. #2
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    Ah! Found it. erase() returns iterator to the next element, or endl if last.

    Code:
    for (std::vector<T>::iterator it = v.begin(); it != v.end();)
    {
         if (should_remove(*it))
         {
              it = v.erase(it);
         }
         else
         {
              ++it;
         }
    }

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    you can also use remove_if():

    #include <algorithm>
    remove_if(v.begin(), v.end(), should_remove);

  4. #4
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,528
    Btw...shouldn't you be using std::list for this?

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,183
    you can also use remove_if():

    #include <algorithm>
    remove_if(v.begin(), v.end(), should_remove);
    Cool! I didn't know that.

    Btw...shouldn't you be using std::list for this?
    Nope... I only need to do this very infrequently, and need fast random access all the time.

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,029
    Bjarne recently (well, okay, in february this year) showed a slide (okay, so it wasn't visible, but he explained his point) where it showed that a vector usually beats a list in many cases where you wouldn't expect it.
    The reason is cache performance, since linked lists jump randomly, they're horrible for cache performance, but vectors are contiguous, which caches love.
    So actually, try a vector first, and if it's slow, then time it with a list. You might be surprised at the results.
    Elkvis likes this.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Oct 2006
    Posts
    2,590
    Quote Originally Posted by Elysia View Post
    since linked lists jump randomly, they're horrible for cache performance, but vectors are contiguous, which caches love.
    it's for this reason that managed technologies like java and .Net have trouble competing with the performance of fully native code. even arrays in those languages are still just arrays of pointers, which may point to anywhere in the process's address space.

  8. #8
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    I am trying to think of a time I used std::list for something. I am coming up blank.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  9. #9
    Registered User
    Join Date
    Oct 2006
    Posts
    2,590
    for very large collections of items, a std::list will be more efficient on insertions and deletions, but because the items are not guaranteed to be contiguous in memory, iterating over them will likely be slower than a vector or a real array.

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,274
    Quote Originally Posted by Elkvis View Post
    for very large collections of items, a std::list will be more efficient on insertions and deletions, but because the items are not guaranteed to be contiguous in memory, iterating over them will likely be slower than a vector or a real array.
    Not really. For a vector, locating the correct position to insert is O(1) and inserting is O(n). For list, inserting is O(1) but finding the location to insert is O(n). I've never seen a situation where the trade-off favored list. There are obviously siyuations where it might, but those are academic, mostly.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,029
    If you have a double-linked list, you don't need to find the location to insert... well, at least if you don't want to keep your structure sorted.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Elysia View Post
    If you have a double-linked list, you don't need to find the location to insert... well, at least if you don't want to keep your structure sorted.
    And if you do want to keep it sorted, then a list is not necesarily the best choice.

    I think it's more a case that a lookup, for the reasons of inserting or otherwise, is O(n).
    I can only think of about one place where I think I used list over all the other cotainers.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. List Iterators, erase() -- help
    By Syndacate in forum C++ Programming
    Replies: 16
    Last Post: 02-11-2011, 10:04 PM
  2. About STL vector.erase
    By -pete- in forum C++ Programming
    Replies: 5
    Last Post: 04-01-2007, 04:16 AM
  3. vector.erase(pointer?!?!);
    By misplaced in forum C++ Programming
    Replies: 3
    Last Post: 09-25-2004, 08:17 AM
  4. vector::erase!
    By aker_y3k in forum C++ Programming
    Replies: 3
    Last Post: 11-27-2002, 02:30 PM
  5. erase in vector
    By stimpyzu in forum C++ Programming
    Replies: 18
    Last Post: 11-23-2002, 01:23 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21