Assume we have this:
std::list<Typelist1(10, 1), list2(20, 2);
std::list<Type>::iterator iter = list1.end();
list1.swap(list2);
What happens here, according to the standard?
1) 'iter' still points to list1::end().
2) 'iter' now points to list2::end().
3) Undefined behavior.
11  4136 
Juha Nieminen wrote:
Assume we have this:
std::list<Typelist1(10, 1), list2(20, 2);
std::list<Type>::iterator iter = list1.end();
list1.swap(list2);
What happens here, according to the standard?
1) 'iter' still points to list1::end().
2) 'iter' now points to list2::end().
3) Undefined behavior.
Since 'swap' is required to invalidate *no iterators*, I believe the '2'
is correct. Iterators by definition "point to elements". There is an
imaginary element "one past the end of the collection". It sits right
after the last one. Since the "one past the last" in list1 follows "the
last one" in list1, and that element _migrates_ to 'list2' (and becomes
its "last one"), then it's logical to conclude that the iterator that
pointed to the end of list1 after swapping will point to the end of the
list2...
V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
On Jul 25, 2:22*pm, Victor Bazarov <v.Abaza...@comAcast.netwrote:
Juha Nieminen wrote:
* Assume we have this:
std::list<Typelist1(10, 1), list2(20, 2);
std::list<Type>::iterator iter = list1.end();
list1.swap(list2);
* What happens here, according to the standard?
1) 'iter' still points to list1::end().
2) 'iter' now points to list2::end().
3) Undefined behavior.
Since 'swap' is required to invalidate *no iterators*, I believe the '2'
is correct. *Iterators by definition "point to elements". *There is an
imaginary element "one past the end of the collection". *It sits right
after the last one. *Since the "one past the last" in list1 follows "the
last one" in list1, and that element _migrates_ to 'list2' (and becomes
its "last one"), then it's logical to conclude that the iterator that
pointed to the end of list1 after swapping will point to the end of the
list2...
Tricky area. The definition of "invalidate" is probably a little
fuzzier than it should be. Certainly if an iterator is not
invalidated then (if it was dereferenceable) if you dereference it you
should get the same thing. But if you increment or decrement it
should you get an iterator pointing to the same sibling?
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. But the neighbors of
these spliced elements (found via increment or decrement of the
outstanding iterators) are not necessarily the same as before the
splice.
In the case of end(), invalidation is particularly ill-defined. One
can not dereference end() to ensure that it is still pointing to the
same place. All one can do is associate it with its predecessor by
decrementing it. Thus detecting "invalidation" of end() is
problematic at least by current definition (or lack thereof) of
"invalidation".
In the case of list, the OP's question is quite relevant to this area
as there are two implementation techniques of list where the OP
detects the difference in implementations (which is probably what
prompted the post in the first place).
std::list<Typelist1(10, 1), list2(20, 2);
std::list<Type>::iterator iter = list1.end();
list1.swap(list2);
What happens here, according to the standard?
1) 'iter' still points to list1::end().
2) 'iter' now points to list2::end().
Some implementations will satisfy (1), while others will satisfy (2).
And there are good reasons for both implementations.
In the early days, all implementations satisfied (2). These
implementations worked by creating a "ghost node" for end() to point
to on the heap. This node was just like all of the other nodes in the
list except that it held a spot for T which was simply never
constructed. The implications of this is that even the default
constructor of list needed to allocate a "ghost node" so that end()
would have something to point to. Naturally under swap, two lists
would swap "ghost nodes" and thus any outstanding end() iterators
would be swapped (exactly analogous to vector).
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. This
has a couple of advantages:
1. The default constructor no longer needs to allocate an end node on
the heap. end() simply points to within the list class itself.
2. In C++0X this design means that the list move constructor can be
nothrow since no resources need be left behind in the moved-from
source.
A few years later the FSF (gcc) independently developed this same
design. But with this design, end() is not swapped when the lists are
swapped.
Now we have multiple and widespread STL implementations with both (1)
and (2) behaviors. A LWG issue is not out of the question on this
subject (you can open a LWG issue by emailing me). My preferred
resolution would be to say that one can not detect invalidation of an
end() iterator, at least after a swap or splice. At the very least, I
do not want to make illegal the "embedded end node" implementation for
node based containers such as list (and map, set, etc.). Nothrow
default constructors and nothrow move constructors serve clients very
well imho. They are wicked fast compared to constructors which must
allocate memory.
-Howard
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<intalloc1(1); // Use allocation strategy 1
MyAllocator<intalloc2(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.
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?
AFAIK it's not only the 'int' element which must be re-allocated, but
the entire list node structure (the one which contains the prev and next
pointers). Thus a simple re-allocation and assignment of the 'int' value
itself will not be enough.
If the new standard really demands for iterators pointing to spliced
elements to not to be invalidated, then it must put some constraints on
what kind of allocators you can use with a std::list. This would seem a
bit odd.
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. In other words, space can be allocated
for it, but the list element inside it doesn't need to be constructed.
There may be cases where constructing such an extra element would be
counter-productive, if not outright hindering (for example if the
element constructor always allocates an enormous array, for instance,
something the user might not want the list data container doing for no
reason).
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.)
On Jul 26, 4:11 am, Juha Nieminen <nos...@thanks.invalidwrote:
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<intalloc1(1); // Use allocation strategy 1
MyAllocator<intalloc2(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:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze wrote:
On Jul 26, 4:11 am, Juha Nieminen <nos...@thanks.invalidwrote:
>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<intalloc1(1); // Use allocation strategy 1
MyAllocator<intalloc2(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.)
They create new copies of the elements, if the allocators compare
unequal.
Pretty useless, but with a smaller support problem than crashing. :-)
Bo Persson
On 2008-07-26 05:26:38 -0400, James Kanze <ja*********@gmail.comsaid:
On Jul 26, 4:11 am, Juha Nieminen <nos...@thanks.invalidwrote:
>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.)
When the allocators don't compare equal, you have to copy the elements.
--
Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
( www.petebecker.com/tr1book)
Pete Becker wrote:
When the allocators don't compare equal, you have to copy the elements.
That's what I thought, and that's why it sounded odd that the new
standard requires for iterators pointing to spliced elements to not to
be invalidated.
If there were an additional condition "unless the allocators in both
lists compare unequal", then it would make sense.
James Kanze wrote:
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.
Do you mean that you have a BaseNode object as member (as the end
node), but an iterator pointing to it would have a DerivedNode type
pointer pointing to this BaseNode type object? Is this even allowed?
On Jul 26, 1:17 pm, Juha Nieminen <nos...@thanks.invalidwrote:
Pete Becker wrote:
When the allocators don't compare equal, you have to copy
the elements.
Actually, you don't, because...
That's what I thought, and that's why it sounded odd that the
new standard requires for iterators pointing to spliced
elements to not to be invalidated.
If there were an additional condition "unless the allocators
in both lists compare unequal", then it would make sense.
At least in the latest draft, there is a statement: "The
behavior of splice operations is undefined if get_allocator() !=
x.get_allocator()." Which means that anything the application
does in this case is OK. (And so it doesn't have to copy---it
could reformat the hard disk instead, for example. Although
from a QoI point of view, I'd prefer the deep copy. Or better
yet, an assertion failure.)
--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On Jul 26, 1:23 pm, Juha Nieminen <nos...@thanks.invalidwrote:
James Kanze wrote:
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.
Do you mean that you have a BaseNode object as member (as the
end node),
Yes.
but an iterator pointing to it would have a
DerivedNode type pointer pointing to this BaseNode type
object?
No. All pointers are always to the BaseNode; the element()
function of my iterator (which corresponds more or less to the
operator*() of a standard iterator) used a static_cast (actually
a C style cast, back then) to convert the pointer, e.g.:
return static_cast< DerivedNode* >( myPtr )->data ;
Is this even allowed?
Having a pointer to base which actually points to a derived is
certainly allowed:-). And templates (actually <generic.h>, back
then) guarantee the type, so the static_cast downcast is
guaranteed (unless you're at the end, of course).
--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On 2008-07-26 07:17:15 -0400, Juha Nieminen <no****@thanks.invalidsaid:
Pete Becker wrote:
>When the allocators don't compare equal, you have to copy the elements.
That's what I thought, and that's why it sounded odd that the new
standard requires for iterators pointing to spliced elements to not to
be invalidated.
If there were an additional condition "unless the allocators in both
lists compare unequal", then it would make sense.
You snipped too much context. I was replying to the question of what
Dinkumware's implementation does, not to what the next revision of the
standard will require. Under the current standard the behavior when
allocators don't compare equal, for implementations that support this,
is implementation-defined.
--
Pete
Roundhouse Consulting, Ltd. ( www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
( www.petebecker.com/tr1book) This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Mike Pemberton |
last post by:
I'm sure there's a good explanation for this effect, but I get rather
a strange output from this little test:
#include <iostream>
#include <list>
int main()
{
std::list<int> int_list;
|
by: JustSomeGuy |
last post by:
I need to write an new class derived from the list class.
This class stores data in the list to the disk if an object
that is added to the list is over 1K in size.
What methods of the std stl...
|
by: Glen Able |
last post by:
Without further ado, here's some code:
std::list<int> things;
things.push_back(1);
things.push_back(2);
things.push_back(3);
std::list<int>::iterator it;
int test;
|
by: velthuijsen |
last post by:
I tried taking a list and pass it through std::sort like the following:
sort(Unsorted.begin(), Unsorted.end());
I got an error back stating that the list iterator doesn't have a
binary...
|
by: sandwich_eater |
last post by:
I want to know how to set an std::list iterator variable to make it
null or nil. If this is not possible what is the value of an
uninitialised std::list iterator and is it ok to assign this value...
| | |
by: Markus Svilans |
last post by:
Hi,
There seems to be some functionality missing from the STL.
I am iterating through a linked list (std::list) using a reverse
iterator and attempting to erase certain items from the list. It...
|
by: desktop |
last post by:
Are there any case where iterators in a std::list gets invalidated
besides from the iterator pointing to an element thats deleted?
It seems that its only the std::vector that invalidates...
|
by: Juha Nieminen |
last post by:
If I'm not completely mistaken, the only reason why std::list::size()
may be (and usually is) a linear-time operation is because they want
std::list::splice() to be a constant-time operation, and...
|
by: lallous |
last post by:
#include <conio>
#include <list>
typedef std::list<intint_list_t;
typedef std::list<int_list_t::iteratorint_list_iterator_list_t;
void print_list(int_list_t &L)
{
for (int_list_t::iterator...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| | |
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated ...
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...
| |
