Closed csbdong closed 9 years ago
问题出在,insert
操作之后,vector
的空间恰好发生了再分配,使 iter
无效。导致 while 无法正常结束。
在 while 循环前面加上这么一句:
iv.reserve(iv.size() * 2);
即可解决。
@pezy
在9.3.1节提到了向一个vector、string或者deque插入元素会使得所有只想容器的迭代器、引用和指针失效。
我的疑问是
1.在vector<int>::iterator iter=iv.begin()
进行第一次赋值之后,进入while循环,然后只要插入元素,那么iter的值就会失效吗??? 是不是说如果mid=iv.insert(mid,2*some_val);
改为iv.insert(mid,2*some_val);
那么mid的值也会失效???
2.为什么代码如下修改:
#include <iostream>
#include <vector>
using std::vector;
int main()
{
//修改1
vector<int> iv={0,1,2,3,4,5,6,7,8,9};
vector<int>::iterator iter=iv.begin(),mid=iv.begin()+iv.size()/2;
//修改2
int some_val=4;
while(iter!=mid)
{
if(*mid==some_val)
mid=iv.insert(mid,2*some_val);
else --mid;
}
return 0;
}
就无返回值错误的问题了??而不要加上iv.reserve(iv.size() * 2);
在vector
::iterator iter=iv.begin() 进行第一次赋值之后,进入while循环,然后只要插入元素,那么iter的值就会失效吗???
insert 导致失效,有两种情况:
据此,如果是第二种情况,iter
是不会失效的。而第一种情况,肯定失效。
是不是说如果mid=iv.insert(mid,2_some_val); 改为iv.insert(mid,2_some_val); 那么mid的值也会失效???
是的,因为 insert 是在 mid 之前插入,mid 在插入点后面,无论哪种情况都会失效。但如果被赋值为返回值,那是指向插入元素的迭代器,显然是有效的。
就无返回值错误的问题了??而不要加上iv.reserve(iv.size() * 2);
这属于第二种情况。不同机器、不同编译器都会有不同的空间增长策略,所以是否会发生重分配,都是不一定的。你上面所谓没问题的代码,在我这跑就会出现错误。
你可以试试下面的代码:
#include <iostream>
#include <vector>
using std::vector;
int main()
{
vector<int> iv = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size() / 2;
std::cout << iv.capacity() << std::endl;
int some_val = 4;
while (iter != mid) {
if (*mid == some_val)
mid = iv.insert(mid, 2 * some_val);
else --mid;
}
std::cout << iv.capacity() << std::endl;
return 0;
}
看看两行输出是否一致,来验证上述的分析。
@pezy
我说下我现在的理解,不知道是不是正确,如果有误,还请指出。
我测试了你刚刚给我的代码。结果是10,20
而我将代码对应的vector<int> iv = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
改为vector<int> iv = {0, 1, 2, 3, 4};
结果就是5,5
我有三点理解:
capacity()函数:指出最少要多少元素才会使其容量重新分配,即是重新分配内存空间的条件。
1.对于第一次结果10,20。容器的内存原有空间够分配。执行前需重新分配的临界点大小是10,空间有余,执行后是20,所以元素可以在原位置之后继续放置,不需要重新分配,迭代器有效,正常执行。(这个说法不知道对不对)
2.对于第二次结果5,5。证明容器的内存原有空间不够分配执行前大小是5,空间正好塞满元素,执行后还是5,所以元素无法在原位置放置,所以进行了重新分配,导致迭代器失效,所以返回值错误,即while无法合理跳出。
3.加上了iv.reserve(iv.size() * 2);
用reserve(size_type)扩大capacity值。使得在循环前后内存空间都是充足的,因此在insert元素位置之前的迭代器均有效,所以iter有效,mid被赋值也有效。因此执行无误。
@csbdong
capacity()函数:指出最少要多少元素才会使其容量重新分配,即是重新分配内存空间的条件。
说法不准确,准确定义如下:
Returns the number of elements that the container has currently allocated space for.
即,目前分配的内存空间所能容纳最多的元素个数。
我上面的代码,是希望用 capacity
的变化来说明空间的重分配。而你貌似理解有偏差,那么,请自行在插入循环之后,输出容器中的所有元素,以供分析。
@pezy
我在你发布的代码里面输出容器中的所有元素,无错误。
但是我下面的代码,返回值仍不对。
#include <iostream>
#include <vector>
using std::vector;
int main()
{
vector<int> iv = {0,1,2,3,4,5};
vector<int>::iterator iter = iv.begin(), mid = iv.begin() + iv.size()/2;
for (auto i: iv)
std::cout <<i<< " ";
std::cout <<std::endl;
std::cout << iv.capacity() << std::endl;
int some_val = 3;
iv.reserve(iv.size()*2);
while (iter != mid)
if (*mid == some_val)
mid = iv.insert(mid, 2 * some_val);
else --mid;
for (auto j: iv)
std::cout <<j<< " ";
std::cout <<std::endl;
std::cout << iv.capacity() << std::endl;
return 0;
}
@csbdong
从你给出的代码来看,你或许还没理解迭代器失效的根本原因。
iv.reserve(iv.size()*2);
这句话会对产生什么影响?
请见 reserve
函数的说明:
Increase the capacity of the container to a value that's greater or equal to new_cap. If new_cap is greater than the current capacity(), new storage is allocated, otherwise the method does nothing.
If new_cap is greater than capacity(), all iterators and references, including the past-the-end iterator, are invalidated. Otherwise, no iterators or references are invalidated.
也就是说,这句话会 导致容器空间的重分配,从而导致迭代器皆失效。
那么在这句话之前定义的 iter
和 mid
显然都会失效,后面的操作也就不用说了。
如何修正?将 iv.reserve(iv.size()*2);
紧随 vector<int> iv = {0,1,2,3,4,5};
后面即可。
@pezy 谢谢,明白了,我之前想当然的认为空间重新分配,原有迭代器失效的同时,迭代器会进行新的绑定。。。 。。。 唉,不能想当然了。
一小段代码
运行时候返回值出问题了。
不知道问题出在哪里。感觉逻辑应该不错的。