[Bug libstdc++/17948] New: iterator increment bug in _Rb_tree::erase(it,it)

[gcc-bugzilla at gcc dot gnu dot org]

I expect the following program to produce the following output:

a 2
b 1 1

i.e, two elements go into the set, we delete one, and one remains.

However, when i compile this with the current cvs head, the program
actually does the following:

$ g++ -g -o x x.cc
$ ./x
a 2
b 0 1
$

i.e., two elements go in, take away one, and none are left.
Someone's arithmetic is bad...

It looks like the problem is in this function in stl_tree.h:


  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    erase(iterator __first, iterator __last)
    {
      if (__first == begin() && __last == end())
        clear();
      else
        for (; __first != __last; ++__first)
          erase(__first);
    }

Note that in the loop, the iterator __first is referenced in the
increment _after_ it has been erased from the container --- which
is undefined behavior.

Below is an attempt to fix this.  With this patch, the test behaves
as expected.

Environment:
System: Linux karma 2.6.8.1 #20 Mon Sep 13 23:48:47 EDT 2004 i686 i686 i386 GNU/Linux
Architecture: i686

        <machine, os, target, libraries (multiple lines)>
host: i686-pc-linux-gnu
build: i686-pc-linux-gnu
target: i686-pc-linux-gnu
configured with: /home/sss/gcc/gcc/configure --prefix=/usr/local/gcc 
--enable-threads=posix --enable-long-long --enable-languages=c,c++,f95

How-To-Repeat:

-------------------------------------------
#include <set>

void test2 ()
{
  std::set<int> s;
  
  s.insert(2);
  s.insert(3);

  printf ("a %d\n", s.size());
  int x = s.erase (3);
  printf ("b %d %d\n", s.size(), x);
}


int main ()
{
  test2 ();
  return 0;
}
-------------------------------------------
------- Additional Comments From snyder at fnal dot gov  2004-10-12 16:29 -------
Fix:

2004-10-11  scott snyder  <[EMAIL PROTECTED]>

        * include/bits/stl_tree.h (erase(iterator,iterator)): Fix iterator
        loop.

--- libstdc++-v3/include/bits/stl_tree.h-orig   2004-10-11 23:17:30.096014584 -0400
+++ libstdc++-v3/include/bits/stl_tree.h        2004-10-11 23:19:39.688313560 -0400
@@ -1087,8 +1087,12 @@
       if (__first == begin() && __last == end())
        clear();
       else
-       for (; __first != __last; ++__first)
+       for (iterator __next = __first; __first != __last; __first = __next)
+        {
+         ++__next;
          erase(__first);
+       }
+       
     }
 
   template<typename _Key, typename _Val, typename _KeyOfValue,

-- 
           Summary: iterator increment bug in _Rb_tree::erase(it,it)
           Product: gcc
           Version: 0.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: snyder at fnal dot gov
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=17948