std :: list迭代器和交换 [英] std::list iterators and swapping
问题描述
假设我们有这个：
std :: list< Typelist1（10,1），list2（20,2）;
std :: list< Type> :: iterator iter = list1.end（）;
list1.swap（list2）;
根据标准，这里会发生什么？
1）''iter''仍然指向list1 :: end（）。
2）''iter''现在指向list2： ：end（）。
3）未定义的行为。
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.
推荐答案
Juha Nieminen写道：
Juha Nieminen wrote:
假设我们有这个：
std :: list< Typelist1（10,1），list2（20,2）;
std :: list< Type> :: iterator iter = list1.end（）;
list1.swap（list2）;
会发生什么在这里，根据标准？
1）''iter''仍然指向list1 :: end（）。
2）''iter' 'now指向list2 :: end（）。
3）未定义的行为。
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.
由于''swap''需要使* no iterators *无效，我相信'''''
是正确的。根据定义，迭代器指向元素。有一个
虚构元素一个超过集合的末尾。它位于最后一个之后的
。由于一个过去的最后一个在list1中跟随
最后一个在list1中，那个元素_migrates_到''list2''（并且变成
，它的最后一个），那么从逻辑上得出结论是这个迭代器是
指向交换后list1的结尾将指向
list2的结尾...
V
-
请在通过电子邮件回复时删除资金''A'
我没有回复最热门的回复，请不要问
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
7月25日下午2：22 * pm，Victor Bazarov< v.Abaza ... @ comAcast.netwrote：
On Jul 25, 2:22*pm, Victor Bazarov <v.Abaza...@comAcast.netwrote:
Juha Nieminen写道：
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）;
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''仍然指向list1 :: end（）。
2）''iter ''现在指向list2 :: end（）。
3）未定义的行为。
1) ''iter'' still points to list1::end().
2) ''iter'' now points to list2::end().
3) Undefined behavior.
由于''swap''需要使* no iterators *无效，我相信'''''
是正确的。 *根据定义的迭代器指向元素。 *有一个
虚构元素超过集合结尾的一个。 *它位于最后一个之后的
。 *自过去一次以来在list1中跟随
最后一个在list1中，那个元素_migrates_到''list2''（并且变成
，它的最后一个），那么从逻辑上得出结论是这个迭代器是
指向交换后list1的结尾将指向
list2的结尾...
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...
棘手的区域。 无效的定义可能比它本应有点模糊一点。当然如果迭代器不是
无效，那么（如果它是可解除引用的）如果你取消引用它你就会得到同样的东西。但是如果你增加或减少它
你应该得到一个指向同一个兄弟的迭代器吗？
拼接示例指向我之前的一个反例
声明。如果你从一个列表拼接到另一个列表，迭代器是
并没有真正失效。 C ++ 03说它们是，但是C ++ 0X工作草案
说它们不是。在所有现有的实现中，引用拼接元素的
优秀迭代器继续指向拼接元素，现在在另一个列表中。但
的邻居这些拼接元素（通过增加或减少
杰出迭代器找到）不一定与之前的
相同splice。
在end（）的情况下，失效特别不明确。一个
不能取消引用end（）以确保它仍然指向
相同的位置。所有人都可以做的是将它与它的前任联系起来，减去它的价值。因此，检测无效。 of end（）至少是因为当前定义（或缺乏）
无效而有问题。
在列表的情况下，OP的问题与这个领域非常相关
因为有两种列表实现技术，其中OP
检测到实现的差异（这可能是什么
首先提示帖子）。
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）;
根据标准，这里会发生什么？
1）''iter''仍然指向list1 :: end（）。
2） ''iter''现在指向list2 :: end（）。
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().
有些实现将满足（1），而其他实现将满足（2）。
两种实现都有充分的理由。
在早期，所有实施都满意（2）。这些
实现通过创建ghost节点来实现。 for end（）指向
到堆上。这个节点就像
列表中的所有其他节点一样，除了它为T保留了一个点，这根本就不是构建的
。这意味着即使是列表的默认值，也需要分配一个鬼节点。所以结束（）
会有一些指向。自然地在交换下，两个列表
将交换鬼节点。因此任何未完成的end（）迭代器
都会被交换（完全类似于向量）。
在2000年代早期的Metrowerks''CodeWarrior切换
到嵌入式终端节点。这有点类似于短
字符串优化。它不是在
堆上分配端节点，而是在列表类本身中作为成员分配。这个
有几个优点：
1.默认构造函数不再需要在
上分配一个终端节点堆。 end（）只是指向列表类本身。
2.在C ++ 0X中，这个设计意味着列表移动构造函数可以是
nothrow，因为没有资源需要被移动的
来源。
几年后，FSF（gcc）独立开发了这个相同的
设计。但是使用这种设计，当列表被交换时，不会交换end（）。
现在我们有多个广泛使用的STL实现（1）
和（2）行为。 LWG问题对于这个
主题并不是不可能的（你可以通过电子邮件给我打开LWG问题）。我的首选
分辨率是说，至少在交换或拼接之后，无法检测到
end（）迭代器的失效。至少，我不希望使嵌入式终端节点变为非法。基于节点的容器（例如list（和map，set等））的实现。 Nothrow
默认构造函数和nothrow移动构造函数非常适合客户
井imho。与构造函数相比，它们是快速的，它们必须分配内存。
-Howard
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写道：
Howard Hinnant wrote:
splice示例指向我之前的
语句的反例。如果你从一个列表拼接到另一个列表，迭代器是
并没有真正失效。 C ++ 03说它们是，但是C ++ 0X工作草案
说它们不是。在所有现有的实现中，引用拼接元素的
优秀迭代器继续指向拼接元素，现在在另一个列表中。
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.
无法满足要求（即拼接永远不会使迭代器失效）
理论上会导致自定义分配器出现问题？
假设：
MyAllocator< intalloc1（1）; //使用分配策略1
MyAllocator< intalloc2（2）; //使用分配策略2，
//与1完全不同
std :: list< int，MyAllocator< int list1（10,1 ，alloc1）;
std :: list< int，MyAllocator< int list2（20,2，alloc2）;
list1.splice（list1.begin （），list2）;
现在的问题是：std :: list只需将
list2的最后一个元素与list1的第一个元素链接起来然后抓住list2的第一个
元素（并使list2为空），因为list1和list2是使用*不同*分配器的
（即使它们属于相同的类型）？
如果它这样做，它会使用一个不同的分配器来自己分配不同的元素，并且当它被例如销毁时，它将使用错误的分配器释放拼接元素。
显然，如果list1和list2中的分配器不同，list1必须
在拼接过程中重新分配元素使用分配器
到list1。问题是：这可以在没有使
迭代器指向拼接元素的情况下完成吗？
AFAIK它不仅仅是''int''必须重新分配的元素，但
整个列表节点结构（包含prev和next
指针的那个）。因此，简单的重新分配和分配''int''值
本身是不够的。
如果新标准真的需要迭代器指向拼接
元素不被无效，那么它必须对
施加一些限制你可以使用std :: 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.
在2000年代早期，Metrowerks的'CodeWarrior切换了
到嵌入式端节点。这有点类似于短
字符串优化。它不是在
堆上分配端节点，而是在列表类本身中作为成员分配。
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.
在堆上分配终端节点的一个好处是它不需要构造
。换句话说，空间可以为它分配
，但是里面的列表元素不需要构造。
可能存在构造这样的情况的情况额外的元素将是
适得其反，如果不是完全阻碍（例如，如果
元素构造函数总是分配一个巨大的数组，例如，
用户可能不希望列表数据容器做什么没有
原因。
或者，换一种方式：你可以分配一个 ;结束节点它有
" prev"和下一个指针，但元素本身没有被不必要地构造（因为它不用于任何东西，并且取消引用指向结束节点的迭代器的
未定义）行为
无论如何）。
是否有可能与班级成员达成同样的目的？
（我会感兴趣知道诀窍，如果存在诀窍。）
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.)
这篇关于std :: list迭代器和交换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
