[Bug c++/23633] New: map::insert() invalidates reverse_iterators

[Bug c++/23633] New: map::insert() invalidates reverse_iterators

[relf at os2 dot ru]

gcc (GCC) 4.0.2 20050821 (prerelease) (Debian 4.0.1-6)

In the following program inserting a new element into a map (i.e., M[2]=2)
invalidates an existing map::reverse_iterator im2. Before this insertion the
reverse_iterator im2 points to the pair (1,1), and after the insertion it
becomes erroneously pointing to the newly inserted pair (2,2).
There is no such problem with map::iterator m1.

Sample output:

before insertion:
im1->first = 1
im2->first = 1
after insertion:
im1->first = 1
im2->first = 2


#include <map>
#include <iostream>
using namespace std;

int main() {
    map<int,int> M;
    M[1] = 1;
    map<int,int>::iterator im1=M.begin();
    map<int,int>::reverse_iterator im2=M.rbegin();

    cout << "before insertion:" << endl;
    cout << "im1->first = " << im1->first << endl;
    cout << "im2->first = " << im2->first << endl;

    M[2] = 2;

    cout << "after insertion:" << endl;
    cout << "im1->first = " << im1->first << endl;
    cout << "im2->first = " << im2->first << endl;

    return 0;
}

-- 
           Summary: map::insert() invalidates reverse_iterators
           Product: gcc
           Version: 4.0.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: relf at os2 dot ru
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug libstdc++/23633] map::insert() invalidates reverse_iterators

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|c++                         |libstdc++


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

[Bug libstdc++/23633] map::insert() invalidates reverse_iterators

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-08-30 15:35 -------
While this behaviour is suprising, it is also not a bug. The problem comes from the fact that
&*(reverse_iterator(i)) = &*(i-1), so when you dereference a reverse_iterator the value you actually get is 
from the iterator before the one is stored inside the reverse_iterator (I hope that makes sense). That might 
seem strange, but there are good reasons for it, and it's unavoidable.

in std::map, this causes problems, as the an iterator can be inserted between i and i-1 (as in this case 
here), making the thing a reverse_iterator points at can change.

Personally, I've always considered reverse_iterator a bit of a nasty hack. In this case I'm sure we are correct 
with respect to the standard, and there really isn't a good way to fix either map or reverse_iterator so this 
code acts as you expect I'm afraid.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net


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

[Bug libstdc++/23633] map::insert() invalidates reverse_iterators

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-08-30 20:16 -------
Just so we are 100% clear on what is occuring (I realise it might not be obvious from my message)

M.rbegin() returns an iterator i =  std::reverse_iterator(M.end());

*i therefore returns *--(M.end()), which at first is the same as M.begin().

After we stick some more stuff into the container, then *i (which is still equal *--(M.end())) becomes 
something different, as more stuff has been pushed into the container.

This is exactly what the standard requires we do, it's just unfortunatly that reverse_iterator is a little fragile 
in the presence of changing containers.

-- 


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

[Bug libstdc++/23633] map::insert() invalidates reverse_iterators

[pcarlini at suse dot de]

------- Additional Comments From pcarlini at suse dot de  2005-08-31 10:06 -------
Agreed, not a bug. Thanks

PS: notice that according to 23.1.2/8, no iterators are invalidated due to the
insertion, and im2 is perfectly ok to use, just gets "updated" to the new
M.rbegin() ;) Last remark: being libstdc++-v3 free software, submitter is
encouraged to have a look to class reverse_iterator in stl_iterator.h, in
particular its comments and the (conforming, 24.4.1.3.3) implementation of
operator*!


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |INVALID


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