Re: std::list iterators and swapping
On Jul 26, 4:11 am, Juha Nieminen <nos...@thanks.invalid> wrote:
Howard Hinnant wrote:
The splice example points to a counter example of my
previous statement. If you splice from one list to another,
the iterators are not really invalidated. C++03 says they
are, but C++0X working draft says they aren't. And in all
existing implementations, the outstanding iterators
referring to spliced elements continue to point to the
spliced elements, now in another list.
Couldn't such a requirement (ie. splicing never invalidates
iterators) theoretically cause problems with custom
allocators?
Assume this:
MyAllocator<int> alloc1(1); // Use allocation strategy 1
MyAllocator<int> alloc2(2); // Use allocation strategy 2, which
// is completely different from 1
std::list<int, MyAllocator<int> > list1(10, 1, alloc1);
std::list<int, MyAllocator<int> > list2(20, 2, alloc2);
list1.splice(list1.begin(), list2);
The question is now: Can std::list simply link the last
element of list2 with the first element of list1 and then take
hold of the first element of list2 (and make list2 empty),
given that list1 and list2 are using *different* allocators
(even though they are of the same type)?
If it did that, it would own elements allocated differently,
using a different allocator, and when it's for example
destroyed, it will attempt to deallocate the spliced elements
with the wrong allocator.
That's probably worth a defect report, if there isn't already
one. I don't see off hand how you can implement splice if the
allocators compare unequal. (Does anyone know what Dinkumware
does? I believe they claim to support unequal allocators.)
Obviously if the allocators in list1 and list2 differ, list1
must re-allocate the elements during the splicing using the
allocator given to list1. The question is: Can this be done
without invalidating iterators pointing to the spliced
elements?
Can it be done in constant time: splice is required to have
constant time (and is uninteresting if it doesn't).
In the early part of the 2000 decade Metrowerks' CodeWarrior
switched to an "embedded end node". This is somewhat
analogous to the "short string optimization". Instead of
the end node being allocated on the heap, it was allocated
within the list class itself as a member.
One advantage of allocating the end node on the heap is that it
doesn't need to be constructed.
Yes and no. Whether the node is on the heap or part of the
object doesn't change anything here: the pointers in the node
need to be initialized, but the data element doesn't need to be
constructed (and can't be constructed, because the class has no
initial element to copy, and it doesn't have to support default
construction). In pre-standard GB_DLList, the memory for the
data element wasn't even allocated.
Or, put in another way: You can allocate an "end node" which
has its "prev" and "next" pointers, but where the element
itself has not been needlessly constructed (because it's not
used for anything, and dereferencing an iterator pointing to
the end node is undefined behavior anyways).
Is it possible to achieve this same thing with a class
member? (I would be interested in knowing the trick, if
there exists one.)
Obviously, it's possible, since the all of the implementations
which have the node as a class member do it. And are required
to, by the standard.
The simplest solution (in my mind, anyway) uses inheritance: you
have a BaseNode with the pointers, and a DerivedNode which
contains the memory for the data. In my pre-standard
implementation, an "unsigned char buffer[ sizeof( T ) ]", with
some additional tricks to ensure alignment. I think the
standard more or less requires this as well, since the
implementation is required to use the allocator, and the
allocator separates allocation and initialization. And since
dereferencing the end iterator is undefined behavior, it can be
a simple BaseNode, without even the memory for the data.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34