GLIBCXX_DEBUG bug in list::merge?

GLIBCXX_DEBUG bug in list::merge?

[David Greene]

The code below triggers what I think is a bogus assert in GLIBCXX_DEBUG
mode.  According to  http://www.sgi.com/tech/stl/List.html iterators
remain valid after a merge operation.  I don't have a copy of the
standard.  Does it say the same?

If so, I believe list::merge needs to update the _M_sequence members of
the safe iterators merged into the list.

I've filed bug 35969.

                             -Dave

include <list>
#include <iostream>

int main(void)
{
   std::list<int> list1;
   std::list<int> list2;

   for(int i = 0; i < 10; ++i) {
     list1.push_back(i);
     list2.push_back(10-i);
   }

   list1.sort();
   list2.sort();

   std::list<int>::iterator node_of_interest = list2.begin();

   // Ok, preserves iterator and updates iterator owner in
   // GLIBCXX_DEBUG mode
   list1.splice(list1.begin(), list2, node_of_interest);

   // Ok, preserves iterator and updates iterator owner in
   // GLIBCXX_DEBUG mode
   list2.splice(list2.begin(), list1, node_of_interest);

   // Oops, does not appear to update iterator owner in GLIBCXX_DEBUG
   // mode
   list1.merge(list2, std::less<int>());

   // Triggers GLIBCXX_DEBUG error: "attempt to splice an iterator from
   // a different container."  Is node_of_interest still a valid
   // iterator according to the standard?
   list2.splice(list2.begin(), list1, node_of_interest);

   std::cout << "list1:\n";
   for(std::list<int>::iterator i = list1.begin();
       i != list1.end();
       ++i) {
     std::cout << *i << "\n";
   }

   std::cout << "list2:\n";
   for(std::list<int>::iterator i = list2.begin();
       i != list2.end();
       ++i) {
     std::cout << *i << "\n";
   }

   return 0;
}

Re: GLIBCXX_DEBUG bug in list::merge?

[David Greene]

David Greene wrote:
> The code below triggers what I think is a bogus assert in GLIBCXX_DEBUG
> mode.  According to  http://www.sgi.com/tech/stl/List.html iterators
> remain valid after a merge operation.  I don't have a copy of the
> standard.  Does it say the same?
> 
> If so, I believe list::merge needs to update the _M_sequence members of
> the safe iterators merged into the list.
> 
> I've filed bug 35969.

Knowing that the SGI docs are very old, I looked at the 1998 draft
standard at:

http://www.kuzbass.ru:8086/docs/isocpp/lib-containers.html#lib.sequences

According to this document, a splice invalidates iterators for the
elements being spliced.  So according to that document the testcase is
invalid and GLIBCXX_DEBUG mode should cause an assert at the second 
splice due to an invalid iterator being passed to it.  But it does not.

Perhaps this was changed in the final standard.  I don't have access to
that document.  It surprises me that splice and merge would invalidate
iterators since a prime motivator for using std::list is iterator
stability and these two operations don't destroy any sequence values,
they just move them around.

No books on the standard library that I've found address iterator
stability for std::list splice and merge operations, which leads
the reader to assume that iterators remain valid.

                                    -Dave

Re: GLIBCXX_DEBUG bug in list::merge?

[me22]

On Fri, Apr 18, 2008 at 12:21 AM, David Greene <greened@obbligato.org> wrote:
>
>  Perhaps this was changed in the final standard.  I don't have access to
>  that document.  It surprises me that splice and merge would invalidate
>  iterators since a prime motivator for using std::list is iterator
>  stability and these two operations don't destroy any sequence values,
>  they just move them around.
>
>  No books on the standard library that I've found address iterator
>  stability for std::list splice and merge operations, which leads
>  the reader to assume that iterators remain valid.
>

void splice(iterator position, list<T,Allocator>& x)
23.2.2.4/4 Effects: Inserts the contents of x before position and x
becomes empty. Invalidates all iterators and references to the list x.

I think the rationale is that the end iterator associated with the
iterators change, so they are invalidated, even if the representation
of a typical iterator would not actually change.

HTH,
~ Scott