std::vector<int> ints;
// ... fill ints with random values
for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
if(*it < 10)
{
*it = ints.back();
ints.pop_back();
continue;
}
it++;
}
This code is not working because when pop_back() is called, it is invalidated. But I don't find any doc talking about invalidation of iterators in std::vector::pop_back().
此代码无效,因为调用pop_back()时,它无效。但是我没有找到任何关于std :: vector :: pop_back()中迭代器失效的文档。
Do you have some links about that?
你有相关的链接吗?
11 个解决方案
#1
10
The call to pop_back() removes the last element in the vector and so the iterator to that element is invalidated. The pop_back() call does not invalidate iterators to items before the last element, only reallocation will do that. From Josuttis' "C++ Standard Library Reference":
对pop_back()的调用将删除向量中的最后一个元素,因此该元素的迭代器无效。 pop_back()调用不会使最后一个元素之前的项的迭代器无效,只有重新分配才会这样做。来自Josuttis的“C ++标准库参考”:
Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.
插入或删除元素会使引用,引用和迭代器无效,这些引用,引用和迭代器引用以下元素。如果插入导致重新分配,则会使所有引用,迭代器和指针无效。
#2
12
Here is your answer, directly from The Holy Standard:
以下是您的答案,直接来自The Holy Standard:
23.2.4.2 A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the optional sequence requirements (23.1.1).
23.1.1.12 Table 68 expressiona.pop_back() return typevoid operational semantics a.erase(--a.end()) containervector, list, deque
Notice that a.pop_back is equivalent to a.erase(--a.end()). Looking at vector's specifics on erase:
请注意,a.pop_back等同于a.erase( - a.end())。看看矢量的擦除细节:
23.2.4.3.3 - iterator erase(iterator position) - effects - Invalidates all the iterators and references after the point of the erase
Therefore, once you call pop_back, any iterators to the previously final element (which now no longer exists) are invalidated.
因此,一旦调用pop_back,任何先前最终元素(现在不再存在)的迭代器都将失效。
Looking at your code, the problem is that when you remove the final element and the list becomes empty, you still increment it and walk off the end of the list.
查看您的代码,问题是当您删除最后一个元素并且列表变为空时,您仍然会增加它并离开列表的末尾。
#3
4
(I use the numbering scheme as used in the C++0x working draft, obtainable here
(我使用C ++ 0x工作草案中使用的编号方案,可在此处获得
Table 94 at page 732 says that pop_back (if it exists in a sequence container) has the following effect:
第94页的表94说pop_back(如果它存在于序列容器中)具有以下效果:
{ iterator tmp = a.end();
--tmp;
a.erase(tmp); }
23.1.1, point 12 states that:
23.1.1,第12点指出:
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.
除非另有说明(显式或通过根据其他函数定义函数),调用容器成员函数或将容器作为参数传递给库函数不应使迭代器无效或更改该容器中对象的值。 。
Both accessing end() as applying prefix-- have no such effect, erase() however:
访问end()作为应用前缀 - 都没有这样的效果,erase()但是:
23.2.6.4 (concerning vector.erase() point 4):
23.2.6.4(关于vector.erase()第4点):
Effects: Invalidates iterators and references at or after the point of the erase.
效果:在擦除点处或之后使迭代器和引用无效。
So in conclusion: pop_back() will only invalidate an iterator to the last element, per the standard.
总而言之:pop_back()只会根据标准使最后一个元素的迭代器无效。
#4
3
Here is a quote from SGI's STL documentation (http://www.sgi.com/tech/stl/Vector.html):
以下是SGI的STL文档(http://www.sgi.com/tech/stl/Vector.html)的引用:
[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.
[5]当重新分配内存时,向量的迭代器无效。此外,在向量中间插入或删除元素会使指向插入或删除点后面的元素的所有迭代器无效。因此,如果使用reserve()预分配与向量将使用的内存一样多的内存,并且所有插入和删除都在向量的末尾,则可以防止向量的迭代器失效。
I think it follows that pop_back only invalidates the iterator pointing at the last element and the end() iterator. We really need to see the data for which the code fails, as well as the manner in which it fails to decide what's going on. As far as I can tell, the code should work - the usual problem in such code is that removal of element and ++ on iterator happen in the same iteration, the way @mikhaild points out. However, in this code it's not the case: it++ does not happen when pop_back is called.
我认为,pop_back只会使指向最后一个元素和end()迭代器的迭代器失效。我们确实需要查看代码失败的数据,以及它无法确定发生了什么的方式。据我所知,代码应该可行 - 这种代码中的常见问题是在迭代器上删除元素和++会在同一次迭代中发生,就像@mikhaild指出的那样。但是,在这段代码中并非如此:调用pop_back时不会发生++。
Something bad may still happen when it is pointing to the last element, and the last element is less than 10. We're now comparing an invalidated it and end(). It may still work, but no guarantees can be made.
当它指向最后一个元素时,仍然会发生一些不好的事情,最后一个元素小于10.我们现在正在比较一个无效的和end()。它可能仍然有效,但不能保证。
#5
1
Iterators are only invalidated on reallocation of storage. Google is your friend: see footnote 5.
迭代器仅在重新分配存储时失效。谷歌是你的朋友:见脚注5。
Your code is not working for other reasons.
您的代码因其他原因无效。
#6
1
pop_back() invalidates only iterators that point to the last element. From C++ Standard Library Reference:
pop_back()仅使指向最后一个元素的迭代器无效。从C ++标准库参考:
Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.
插入或删除元素会使引用,引用和迭代器无效,这些引用,引用和迭代器引用以下元素。如果插入导致重新分配,则会使所有引用,迭代器和指针无效。
So to answer your question, no it does not invalidate all iterators.
所以回答你的问题,不,它不会使所有迭代器无效。
However, in your code example, it can invalidate it when it is pointing to the last element and the value is below 10. In which case Visual Studio debug STL will mark iterator as invalidated, and further check for it not being equal to end() will show an assert.
但是,在您的代码示例中,当它指向最后一个元素并且值低于10时,它可以使它无效。在这种情况下,Visual Studio调试STL会将迭代器标记为无效,并进一步检查它是否等于end( )将显示一个断言。
If iterators are implemented as pure pointers (as they would in probably all non-debug STL vector cases), your code should just work. If iterators are more than pointers, then your code does not handle this case of removing the last element correctly.
如果迭代器被实现为纯指针(就像它们可能在所有非调试STL向量的情况下那样),那么你的代码应该可以工作。如果迭代器不仅仅是指针,那么您的代码不会处理正确删除最后一个元素的情况。
#7
0
Error is that when "it" points to the last element of vector and if this element is less than 10, this last element is removed. And now "it" points to ints.end(), next "it++" moves pointer to ints.end()+1, so now "it" running away from ints.end(), and you got infinite loop scanning all your memory :).
错误是当“it”指向vector的最后一个元素时,如果此元素小于10,则删除最后一个元素。现在“它”指向ints.end(),接着“it ++”将指针移动到ints.end()+ 1,所以现在“它”从ints.end()运行,并且你得到了无限循环扫描所有你的记忆:)。
#8
0
The "official specification" is the C++ Standard. If you don't have access to a copy of C++03, you can get the latest draft of C++0x from the Committee's website: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf
“官方规范”是C ++标准。如果您无法访问C ++ 03的副本,可以从委员会的网站获取最新的C ++ 0x草案:http://www.open-std.org/jtc1/sc22/wg21/文档/文件/ 2008 / n2723.pdf
The "Operational Semantics" section of container requirements specifies that pop_back() is equivalent to { iterator i = end(); --i; erase(i); }. the [vector.modifiers] section for erase says "Effects: Invalidates iterators and references at or after the point of the erase."
容器需求的“操作语义”部分指定pop_back()等效于{iterator i = end(); - 一世;擦除(ⅰ); }。擦除的[vector.modifiers]部分说“效果:在擦除点或之后使迭代器和引用无效”。
If you want the intuition argument, pop_back is no-fail (since destruction of value_types in standard containers are not allowed to throw exceptions), so it cannot do any copy or allocation (since they can throw), which means that you can guess that the iterator to the erased element and the end iterator are invalidated, but the remainder are not.
如果你想要直觉参数,pop_back是不失败的(因为标准容器中的value_types的破坏不允许抛出异常),所以它不能进行任何复制或分配(因为它们可以抛出),这意味着你可以猜到擦除元素和结束迭代器的迭代器无效,但其余部分则无效。
#9
0
pop_back() will only invalidate it if it was pointing to the last item in the vector. Your code will therefore fail whenever the last int in the vector is less than 10, as follows:
pop_back()只有在指向向量中的最后一项时才会使它失效。因此,只要向量中的最后一个int小于10,您的代码就会失败,如下所示:
*it = ints.back(); // Set *it to the value it already has
ints.pop_back(); // Invalidate the iterator
continue; // Loop round and access the invalid iterator
* it = ints.back(); //将*设置为已有的值ints.pop_back(); //使迭代器无效; //循环并访问无效迭代器
#10
0
You might want to consider using the return value of erase instead of swapping the back element to the deleted position an popping back. For sequences erase returns an iterator pointing the the element one beyond the element being deleted. Note that this method may cause more copying than your original algorithm.
您可能需要考虑使用erase的返回值,而不是将后退元素交换到已删除的位置。对于序列,erase返回一个迭代器,指向要删除的元素之外的元素。请注意,此方法可能会导致比原始算法更多的复制。
for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
if(*it < 10)
it = ints.erase( it );
else
++it;
}
std::remove_if could also be an alternative solution.
std :: remove_if也可以作为替代解决方案。
struct LessThanTen { bool operator()( int n ) { return n < 10; } };
ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );
std::remove_if is (like my first algorithm) stable, so it may not be the most efficient way of doing this, but it is succinct.
std :: remove_if(就像我的第一个算法一样)是稳定的,所以它可能不是最有效的方法,但它很简洁。
#11
-1
Check out the information here (cplusplus.com):
查看此处的信息(cplusplus.com):
Delete last element
删除最后一个元素
Removes the last element in the vector, effectively reducing the vector size by one and invalidating all iterators and references to it.
移除向量中的最后一个元素,有效地将向量大小减小一个,并使所有迭代器和对它的引用无效。
#1
10
The call to pop_back() removes the last element in the vector and so the iterator to that element is invalidated. The pop_back() call does not invalidate iterators to items before the last element, only reallocation will do that. From Josuttis' "C++ Standard Library Reference":
对pop_back()的调用将删除向量中的最后一个元素,因此该元素的迭代器无效。 pop_back()调用不会使最后一个元素之前的项的迭代器无效,只有重新分配才会这样做。来自Josuttis的“C ++标准库参考”:
Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.
插入或删除元素会使引用,引用和迭代器无效,这些引用,引用和迭代器引用以下元素。如果插入导致重新分配,则会使所有引用,迭代器和指针无效。
#2
12
Here is your answer, directly from The Holy Standard:
以下是您的答案,直接来自The Holy Standard:
23.2.4.2 A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the optional sequence requirements (23.1.1).
23.1.1.12 Table 68 expressiona.pop_back() return typevoid operational semantics a.erase(--a.end()) containervector, list, deque
Notice that a.pop_back is equivalent to a.erase(--a.end()). Looking at vector's specifics on erase:
请注意,a.pop_back等同于a.erase( - a.end())。看看矢量的擦除细节:
23.2.4.3.3 - iterator erase(iterator position) - effects - Invalidates all the iterators and references after the point of the erase
Therefore, once you call pop_back, any iterators to the previously final element (which now no longer exists) are invalidated.
因此,一旦调用pop_back,任何先前最终元素(现在不再存在)的迭代器都将失效。
Looking at your code, the problem is that when you remove the final element and the list becomes empty, you still increment it and walk off the end of the list.
查看您的代码,问题是当您删除最后一个元素并且列表变为空时,您仍然会增加它并离开列表的末尾。
#3
4
(I use the numbering scheme as used in the C++0x working draft, obtainable here
(我使用C ++ 0x工作草案中使用的编号方案,可在此处获得
Table 94 at page 732 says that pop_back (if it exists in a sequence container) has the following effect:
第94页的表94说pop_back(如果它存在于序列容器中)具有以下效果:
{ iterator tmp = a.end();
--tmp;
a.erase(tmp); }
23.1.1, point 12 states that:
23.1.1,第12点指出:
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.
除非另有说明(显式或通过根据其他函数定义函数),调用容器成员函数或将容器作为参数传递给库函数不应使迭代器无效或更改该容器中对象的值。 。
Both accessing end() as applying prefix-- have no such effect, erase() however:
访问end()作为应用前缀 - 都没有这样的效果,erase()但是:
23.2.6.4 (concerning vector.erase() point 4):
23.2.6.4(关于vector.erase()第4点):
Effects: Invalidates iterators and references at or after the point of the erase.
效果:在擦除点处或之后使迭代器和引用无效。
So in conclusion: pop_back() will only invalidate an iterator to the last element, per the standard.
总而言之:pop_back()只会根据标准使最后一个元素的迭代器无效。
#4
3
Here is a quote from SGI's STL documentation (http://www.sgi.com/tech/stl/Vector.html):
以下是SGI的STL文档(http://www.sgi.com/tech/stl/Vector.html)的引用:
[5] A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use reserve() to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end.
[5]当重新分配内存时,向量的迭代器无效。此外,在向量中间插入或删除元素会使指向插入或删除点后面的元素的所有迭代器无效。因此,如果使用reserve()预分配与向量将使用的内存一样多的内存,并且所有插入和删除都在向量的末尾,则可以防止向量的迭代器失效。
I think it follows that pop_back only invalidates the iterator pointing at the last element and the end() iterator. We really need to see the data for which the code fails, as well as the manner in which it fails to decide what's going on. As far as I can tell, the code should work - the usual problem in such code is that removal of element and ++ on iterator happen in the same iteration, the way @mikhaild points out. However, in this code it's not the case: it++ does not happen when pop_back is called.
我认为,pop_back只会使指向最后一个元素和end()迭代器的迭代器失效。我们确实需要查看代码失败的数据,以及它无法确定发生了什么的方式。据我所知,代码应该可行 - 这种代码中的常见问题是在迭代器上删除元素和++会在同一次迭代中发生,就像@mikhaild指出的那样。但是,在这段代码中并非如此:调用pop_back时不会发生++。
Something bad may still happen when it is pointing to the last element, and the last element is less than 10. We're now comparing an invalidated it and end(). It may still work, but no guarantees can be made.
当它指向最后一个元素时,仍然会发生一些不好的事情,最后一个元素小于10.我们现在正在比较一个无效的和end()。它可能仍然有效,但不能保证。
#5
1
Iterators are only invalidated on reallocation of storage. Google is your friend: see footnote 5.
迭代器仅在重新分配存储时失效。谷歌是你的朋友:见脚注5。
Your code is not working for other reasons.
您的代码因其他原因无效。
#6
1
pop_back() invalidates only iterators that point to the last element. From C++ Standard Library Reference:
pop_back()仅使指向最后一个元素的迭代器无效。从C ++标准库参考:
Inserting or removing elements invalidates references, pointers, and iterators that refer to the following element. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.
插入或删除元素会使引用,引用和迭代器无效,这些引用,引用和迭代器引用以下元素。如果插入导致重新分配,则会使所有引用,迭代器和指针无效。
So to answer your question, no it does not invalidate all iterators.
所以回答你的问题,不,它不会使所有迭代器无效。
However, in your code example, it can invalidate it when it is pointing to the last element and the value is below 10. In which case Visual Studio debug STL will mark iterator as invalidated, and further check for it not being equal to end() will show an assert.
但是,在您的代码示例中,当它指向最后一个元素并且值低于10时,它可以使它无效。在这种情况下,Visual Studio调试STL会将迭代器标记为无效,并进一步检查它是否等于end( )将显示一个断言。
If iterators are implemented as pure pointers (as they would in probably all non-debug STL vector cases), your code should just work. If iterators are more than pointers, then your code does not handle this case of removing the last element correctly.
如果迭代器被实现为纯指针(就像它们可能在所有非调试STL向量的情况下那样),那么你的代码应该可以工作。如果迭代器不仅仅是指针,那么您的代码不会处理正确删除最后一个元素的情况。
#7
0
Error is that when "it" points to the last element of vector and if this element is less than 10, this last element is removed. And now "it" points to ints.end(), next "it++" moves pointer to ints.end()+1, so now "it" running away from ints.end(), and you got infinite loop scanning all your memory :).
错误是当“it”指向vector的最后一个元素时,如果此元素小于10,则删除最后一个元素。现在“它”指向ints.end(),接着“it ++”将指针移动到ints.end()+ 1,所以现在“它”从ints.end()运行,并且你得到了无限循环扫描所有你的记忆:)。
#8
0
The "official specification" is the C++ Standard. If you don't have access to a copy of C++03, you can get the latest draft of C++0x from the Committee's website: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf
“官方规范”是C ++标准。如果您无法访问C ++ 03的副本,可以从委员会的网站获取最新的C ++ 0x草案:http://www.open-std.org/jtc1/sc22/wg21/文档/文件/ 2008 / n2723.pdf
The "Operational Semantics" section of container requirements specifies that pop_back() is equivalent to { iterator i = end(); --i; erase(i); }. the [vector.modifiers] section for erase says "Effects: Invalidates iterators and references at or after the point of the erase."
容器需求的“操作语义”部分指定pop_back()等效于{iterator i = end(); - 一世;擦除(ⅰ); }。擦除的[vector.modifiers]部分说“效果:在擦除点或之后使迭代器和引用无效”。
If you want the intuition argument, pop_back is no-fail (since destruction of value_types in standard containers are not allowed to throw exceptions), so it cannot do any copy or allocation (since they can throw), which means that you can guess that the iterator to the erased element and the end iterator are invalidated, but the remainder are not.
如果你想要直觉参数,pop_back是不失败的(因为标准容器中的value_types的破坏不允许抛出异常),所以它不能进行任何复制或分配(因为它们可以抛出),这意味着你可以猜到擦除元素和结束迭代器的迭代器无效,但其余部分则无效。
#9
0
pop_back() will only invalidate it if it was pointing to the last item in the vector. Your code will therefore fail whenever the last int in the vector is less than 10, as follows:
pop_back()只有在指向向量中的最后一项时才会使它失效。因此,只要向量中的最后一个int小于10,您的代码就会失败,如下所示:
*it = ints.back(); // Set *it to the value it already has
ints.pop_back(); // Invalidate the iterator
continue; // Loop round and access the invalid iterator
* it = ints.back(); //将*设置为已有的值ints.pop_back(); //使迭代器无效; //循环并访问无效迭代器
#10
0
You might want to consider using the return value of erase instead of swapping the back element to the deleted position an popping back. For sequences erase returns an iterator pointing the the element one beyond the element being deleted. Note that this method may cause more copying than your original algorithm.
您可能需要考虑使用erase的返回值,而不是将后退元素交换到已删除的位置。对于序列,erase返回一个迭代器,指向要删除的元素之外的元素。请注意,此方法可能会导致比原始算法更多的复制。
for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
if(*it < 10)
it = ints.erase( it );
else
++it;
}
std::remove_if could also be an alternative solution.
std :: remove_if也可以作为替代解决方案。
struct LessThanTen { bool operator()( int n ) { return n < 10; } };
ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );
std::remove_if is (like my first algorithm) stable, so it may not be the most efficient way of doing this, but it is succinct.
std :: remove_if(就像我的第一个算法一样)是稳定的,所以它可能不是最有效的方法,但它很简洁。
#11
-1
Check out the information here (cplusplus.com):
查看此处的信息(cplusplus.com):
Delete last element
删除最后一个元素
Removes the last element in the vector, effectively reducing the vector size by one and invalidating all iterators and references to it.
移除向量中的最后一个元素,有效地将向量大小减小一个,并使所有迭代器和对它的引用无效。