容器大小的改变以及容器操作可能使迭代器失效、vector对象的容量变化

1 改变容器的大小

我们可以使用resize来增加或缩小容器,与往常一样,array不支持resize。如果当前大小大于所要求的大小,容器后面的元素会被删除;如果当前大小小于新大小,会将新元素添加到容器后部:

 list<int> ilist(10,42);   //10个int:每个的值都是42

ilist.resize(15);   //将5个值为0的元素添加到ilist的末尾

ilist.resize(25,-1);  //将10个值为-1的元素添加到ilist的末尾

ilist.resize(5);    //从ilist末尾删除20个元素

resize操作接受一个可选的元素值参数,用来初始化添加到容器中的元素。如果调用者未提供此参数,新元素进行值初始化。如果容器保存的是类类型,且resize向容器添加新元素,则我们必须提供初始值,或者元素类型必须提供一个默认构造函数。

顺序容器大小操作

resize不适用array

c.resize(n)      调整c的大小为n个元素。若n<c.size(),则多出的元素被丢弃。若必须添加新元素,对新元素进行值初始化

c.resize(n,t)      调整c的大小为n个元素。任何新添加的元素都初始化为值t

 

注意:如果resize缩小容器,则指向被删除元素的迭代器、引用和指针都会失效;对vector、string或deque进行resize可能导致迭代器、指针和引用失效

 

容器操作可能使迭代器失效

向容器中添加元素和从容器中删除元素的操作可能会使指向容器的指针、引用或迭代器失效。一个失效的指针、引用或迭代器将不再表示任何元素。使用失效的指针、引用或迭代器是一种严重的程序设计错误,很可能引起与使用未初始化指针一样的问题

向容器添加元素后:

  • 如果容器是vector或string,且存储空间被重新分配,则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配,指向插入位置之前的元素的迭代器、指针和引用将会失效。
  • 对于deque。插入到除首尾位置之外的任何位置都会导致迭代器、指针和引用失效。如果在首尾位置添加元素,迭代器会失效,但指向存在的元素的引用和指针不会失效
  • 对于list和forward_list,指向容器的迭代器(包括尾后迭代器和首前迭代器)、指针和引用仍然有效。

当我们从一个容器中删除元素后,指向被删除元素的迭代器、指针和引用会失效。当我们删除一个元素后:

  • 对于list和forward_list,指向容器其他位置的迭代器、指针和引用仍然有效
  • 对于deque,如果在首尾之外的任何位置删除元素,那么指向被删除元素外其他元素的迭代器、引用或指针也会失效。如果是删除deque的尾元素,则尾后迭代器也会失效,但其他迭代器、引用和指针不受影响;如果是删除首元素,这些也不会受影响。
  • 对于vector和string,指向被删除元素之前元素的迭代器、引用和指针仍有效。注意:当我们删除元素时,尾后迭代器总是会失效。

 

编写改变容器的循环程序

添加/删除vector、string或deque元素的循环程序必须考虑迭代器、引用和指针可能失效的问题。程序必须保证每个循环步中都更新迭代器、引用和指针。如果循环中调用的是insert或erase,那么更新迭代器很容易。这些操作都返回迭代器,我们可以用来更新:

//傻瓜循环,删除偶数元素,复制每个奇数元素
vector<int> vi={0,1,2,3,4,5,6,7,8,9};
auto iter=vi.begin();  //调用begin而不是cbegin,因为我们要改变vi
while(iter!=vi.end()) 
{
    if(*iter%2){
        iter=vi.insert(iter,*iter);//复制当前元素
        iter+=2;   //向前移动迭代器,跳过当前元素以及插入到它之前的元素
    }
    else
        iter=vi.erase(iter);  //删除偶数元素
    //不应向前移动迭代器,iter指向我们删除的元素之后的元素
}

此程序删除vector中的偶数元素,并复制每个奇数元素。我们在调用insert和erase后都更新迭代器,因为两者都会使迭代器失效。

 

不要保存end返回的迭代器

当我们添加/删除vector或string的元素后,或在deque中首元素之外任何位置添加/删除元素后,用来end返回的迭代器总是会失效。因此,添加或删除元素的循环程序必须反复调用end,而不能在循环之前保存end返回的迭代器,一直当作容器末尾使用。

 

vector对象时如何增长的

为了支持随机访问,vector将元素连续存储——每个元素紧挨着前一个元素存储。通常情况下,我们不必关心一个标准库类型是如何实现的,而只需关心它如何使用。然而,对于vector和string,其部分实现渗透到了接口中。

假定容器中元素是连续存储的,其容器的大小是可变的,考虑向vector和string中添加元素会发生什么;如果没有空间容纳新元素,容器不可能简单地将它添加到内存中其他位置——因为元素必须连续存储。容器必须分配新的内存空间来保存已有元素和新元素,将已有元素从旧位置移动到新空间中,然后添加新元素,释放就存储空间。如果我们每添加一个新元素,vector就执行一次这样的内存分配和释放操作,性能会慢到不可接受。

 

管理容器的成员函数

vector和string类型提供了一些成员函数,允许我们与它的实现中内存分配部分互动。capacity操作告诉我们容器在不扩张内存空间的情况下可以容纳多少个元素。reserve操作允许我们通知容器它应该准备保存多少个元素。

容器大小管理操作

shrink_to_fit只适用于vector、string和deque

capacity和reserve只适用于vector和string

c.shrink_to_fit()       请将capacity减少为size相同大小

c.capacity()      不重新分配内存空间的话,c可以保存多少元素

c.reserve(n)       分配至少能容纳n个元素的内存空间

reserve并不改变容器中元素的数量,它仅影响vector预先分配多大的内存空间

只有当需要的内存空间超过当前容量时,reserve调用才会改变vector的容量。如果要求大小大于当前容量,reserve至少分配与要求一样大的内存空间(可能更大)。

如果需求大小小于等于当前空间,reserve什么也不做。特别是,当需求大小小于当前容量时,容器不会退回内存空间。因此,在调用reserve之后,capacity将会大于等于传递给reserve的参数。

这样,调用reserve永远也不会减少容器占用的内存空间。类似的,resize成员函数只改变容器中元素的数目,而不是容器的容量我们同样不能使用resize来减少容器预留的内存空间

在新标准中,我们可以调用shrink_to_fit来要求deque、vector或string退回不需要的内存空间。此函数指出我们不再需要任何多余的内存空间。但是,具体的实现可以选择忽略此请求。也就是说,调用shrink_to_fit也并不保证一定退回内存空间。

 

capacity和size

容器size是指它已经保存的元素的数目;而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。

 

上一篇:文件系统权限的管理(包括特殊权限)


下一篇:[LeetCode] 1172. Dinner Plate Stacks 餐盘栈