顺序容器操作 | 彩潭有鲤的札记

type

status

date

slug

summary

向顺序容器添加元素

除 array 外，所有标准库容器都提供灵活的内存管理，在运行时可以动态添加或删除元素。

当使用这些操作时，必须记得不同容器使用不同的策略来分配元素空间，而这些策略直接影响性能。在一个vector或string的尾部之外的任何位置，或是一个deque的首尾之外的任何位置添加元素，都需要移动元素。而且，向一个vector或string添加元素可能引起整个对象存储空间的重新分配。重新分配一个对象的存储空间需要分配新的内存，并将元素从旧的空间移动到新的空间中。

使用push_back

push_back 将一个元素追加到容器尾部，push_front 将元素插入容器头部。除 array 和 forward_list 之外，每个顺序容器（包括 string 类型）都支持 push_back。

对push_back的调用在container尾部创建了一个新的元素，将container的size增大了1。该元素的值为word的一个拷贝。container的类型可以是list、vector或deque。

关键概念：容器元素是拷贝的

当使用对象来初始化容器，或者插入一个对象到容器中时，放入容器中的是哪个对象值的拷贝，不是对象本身。这就像传递一个对象给非引用参数是一样的，容器中的元素与这个对象没有任何关系。接下来如果改变了元素的值并不会影响到原始值，反之亦然。

使用push_front

除了push_back，list、forward_list和deque容器还支持push_front操作，将元素插入到容器头部：

注：deque像 vector一样提供了随机访问元素的能力，但它提供了vector所不支持的push_front。deque保证在容器首尾进行插入和删除元素的操作都只花费常数时间。与vector一样，在 deque首尾之外的位置插入元素会很耗时。

在容器的特定位置添加元素

insert 将元素插入到迭代器指定的位置之前。一些不支持 push_front 的容器可以使用 insert 将元素插入开始位置。

vector、deque、list和string都支持insert成员，forward_list提供了特殊版本的insert成员

将元素插入到 vector、deque 或 string 的任何位置都是合法的，但可能会很耗时。

插入元素范围

insert 除了第一个参数后的参数的模式与构造函数具有相同的参数模式。

其中一个版本 insert 以元素数目和值作为参数，将添加指定数目的同一元素到给定的位置：

这段代码添加 10 个元素到 svec 的尾部，每个元素的值都是 "Anna"。

还有一个版本的 insert 以一对迭代器或者一个初始值列表作为参数，将给定范围内的值插入到指定位置：

当以一对迭代器作为拷贝源时，这些迭代器一定不能指向将要插入元素的容器。

在新标准库中，接受元素个数或范围的 insert 版本返回指向第一个新加入元素的迭代器，而旧版本中这些操作返回 void。如果范围为空，不插入任何元素，insert 会返回第一个参数。

使用 insert 的返回值

通过使用insert的返回值，可以在容器中一个特定位置反复插入元素：

在循环之前，将iter初始化为lst.begin ()。第一次调用insert会将刚刚读入的string插入到iter所指向的元素之前的位置。insert返回的迭代器恰好指向这个新元素。将此迭代器赋予iter并重复循环，读取下一个单词。只要继续有单词读入，每步 while循环就会将一个新元素插入到iter之前，并将iter改变为新加入元素的位置。此元素为（新的）首元素。因此，每步循环将一个新元素插入到list首元素之前的位置。

使用 emplace 操作

新标准库增加了三个直接构造而不是拷贝元素的操作：emplace_front、emplace_back 和 emplace，其分别对应 push_front、push_back 和 insert。当调用 push或insert 时，元素对象被拷贝到容器中。而调用 emplace 时，则是将参数传递给元素类型的构造函数，直接在容器的内存空间中构造元素。

传递给 emplace 的参数必须与元素类型的构造函数相匹配。

forward_list 有特殊版本的 insert 和 emplace 操作，且不支持 push_back 和 emplace_back。vector 和 string不支持 push_front 和 emplace_front。

emplace 函数在容器中直接构造元素。传递给 emplace 函数的参数必须与元素类型的构造函数相匹配。

访问元素

顺序容器的元素访问操作：

每个顺序容器都有一个 front 成员函数，而除了 forward_list 之外的顺序容器还有一个 back 成员函数。这两个操作分别返回首元素和尾元素的引用。

迭代器 end 指向的是容器尾元素之后的(不存在的)元素。为了获取尾元素，必须首先递减此迭代器

在调用front和back之前(或解引用 begin 和 end 返回的迭代器)之前，要确保容器非空

访问成员函数返回的是引用

在容器中访问元素的成员函数（即front、back、下标和at）都返回引用类型。如果容器是 const 对象，则返回 const 引用，否则返回普通引用。可以使用其来改变元素的值：

如果使用auto变量来保存这些函数的返回值，并且希望使用此变量来改变元素的值，必须记得将变量定义为引用类型

下标操作和安全的随机访问

可以快速随机访问的容器（string、vector、deque 和 array）都提供下标运算符，下标运算符接受一个下标参数，返回容器中该位置的元素的引用。

保证下标有效是程序员的责任。如果希望确保下标合法，可以使用 at 成员函数。at 类似下标运算，但如果下标越界，at 会抛出 out_of_range 异常。

删除元素

顺序容器的元素删除操作：

删除元素的成员函数并不检查其参数。删除元素前，程序员必须确保目标元素存在。

pop_front 和 pop_back 成员

pop_front 和 pop_back 分别移除首尾元素。就像 vector 和 string 没有 push_front 一样，它们也没有 pop_front 。类似的 forward_list 没有 pop_back 成员。就像元素访问成员一样，不要将 pop 操作用于空的容器。

这些操作返回 void，如果需要被 pop 的值，需要在 pop 之前先将其存储起来：

在容器的中间部分移除元素

erase 函数删除指定位置的元素。可以删除由一个迭代器指定的单个元素，也可以删除由一对迭代器指定的范围内的所有元素。两种形式的 erase 都返回指向删除元素（最后一个）之后位置的迭代器。也就是说如果j是元素i之后的元素，那么 erase(i) 将会返回指向 j的迭代器。

移除多个元素

为了删除容器中的所有元素，可以调用clear或者将begin和end传给erase ：

特殊的forward_list操作

为了理解为何 forward_list 有特别的添加和移除元素操作的版本，需要知道从单向链表中移除元素将会发生什么：

为了移除 elem3 必须改变 elem2 ，使得其 next 重新指向 elem4

给单链表添加或删除元素时，被增加或删除的元素的之前那个元素的 next 改变了。所以，为了添加或移除元素，需要访问其前置元素，从而才能更新那个元素的 next 连接。然而，对于 forward_list 这种单链表来说很难获得一个元素的前置元素。基于这个原因，在 forward_list 中的添加或移除元素操作改变的是给定元素后面的那个元素。这样总能访问到由于改变而影响到的元素。

由于这些操作在 forward_list 上的不同表现，forward_list 没有定义 insert 、 emplace 和 erase ，相反它定义 insert_after emplace_after 和 erase_after，如为了移除 elem3 ，可以在 elem2 的迭代器上调用 erase_after，为了支持这些操作，forward_list 定义了 before_begin 返回首前迭代器（off-the-beginning iterator）。这个迭代器允许我们在一个首元素之前的不存在的元素之后添加或移除一个元素。

forward_list 的插入和删除操作：

改变容器大小

除了 array 的容器可以使用resize操作来使得容器更大或更小。如果当前大小比请求的尺寸大的话，元素将从后面开始删除；如果当前大小比新的尺寸小的话，元素将被添加到容器的尾部，以下是顺序容器支持的改变大小的操作：

resize 操作以一个可选的元素值作为参数，用于初始化添加到容器中的元素。如果没有这个参数，添加的元素将是值初始化的。如果容器中的元素是类类型，那么当 resize 添加元素时，要么提供初始值要么元素类型有一个默认构造函数。

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

向容器中添加或删除元素可能会使指向容器元素的指针、引用或迭代器失效。失效的指针、引用或迭代器不再表示任何元素，使用它们是一种严重的程序设计错误。

向容器中添加元素后：

如果容器是 vector 或 string 类型，且存储空间被重新分配，则指向容器的迭代器、指针和引用都会失效。如果存储空间未重新分配，指向插入位置之前元素的迭代器、指针和引用仍然有效，但指向插入位置之后元素的迭代器、指针和引用都会失效
如果容器是 deque 类型，添加到除首尾之外的任何位置都会使迭代器、指针和引用失效。如果添加到首尾位置，则迭代器会失效，而指针和引用不会失效。
如果容器是 list 或 forward_list 类型，指向容器的迭代器、指针和引用仍然有效。

从容器中删除元素后，指向被删除元素的迭代器、指针和引用失效：

如果容器是 list 或 forward_list 类型，指向容器其他位置的迭代器、指针和引用仍然有效。
如果容器是 deque 类型，删除除首尾之外的任何元素都会使迭代器、指针和引用失效。如果删除尾元素，则尾后迭代器失效，其他迭代器、指针和引用不受影响。如果删除首元素，这些也不会受影响。
如果容器是 vector 或 string 类型，指向删除位置之前元素的迭代器、指针和引用仍然有效。但尾后迭代器总会失效。

使用失效的迭代器、指针或引用是严重的运行时错误。

建议：管理迭代器

当使用迭代器（或指向容器元素的引用或指针）时，最小化要求迭代器必须保持有效的程序片段是一个好的方法。由于向迭代器添加元素和从迭代器删除元素的代码可能会使选代器失效，因此必须保证每次改变容器的操作之后都正确地重新定位迭代器。这个建议对 vector、string 和 deque 尤为重要。

书写改变容器大小的循环

给 vector 、string 和 deque 添加或删除元素的循环程序必须考虑的一个事实是：迭代器、引用和指针可能会失效。程序必须保证每次循环之后迭代器、引用和指针都会更新。如果循环调用的是 insert 或 erase 的话，更新迭代器将会很简单。这些操作都会返回迭代器，从而可以用于重置迭代器

避免存储由 end 返回的迭代器

当在 vector 和 string中添加和删除元素后，或者在 deque 中添加元素或者移除非首元素时，其 end 返回的迭代器将总是失效。所以添加和移除元素的循环需要总是调用 end 而不是将获取到的迭代器存起来。部分由于这个原因，C++标准库将 end() 调用实现为一个很快的操作。

考虑这样一个循环，它处理容器中的每个元素，在其后添加一个新元素。我们希望循环能跳过新添加的元素，只处理原有元素。在每步循环之后，我们将定位迭代器，使其指向下一个原有元素。如果试图优化后这个循环，在循环之前保存end() 返回的迭代器，一直用作容器末尾，就会导致一场灾难。

上面代码的行为是未定义的，在很多标准库实现上会导致无限循环。问题是我们将end操作返回的迭代器保存在一个名为end的局部变量中。在循环体中，我们向容器中添加了一个元素，这个操作是保存在end中的迭代器失效了。这个迭代器不再指向v中的任何元素，或是v中尾元素之后的位置。

注：不要在会往 deque 、string 或 vector 中插入或删除元素的循环中缓存 end() 返回的迭代器。

必须在每次插入操作后重新调用end() ，而不能再循环开始前保存它返回的迭代器：

vector对象是如何增长的

为了支持快速随机访问，vector 的元素是连续存储的，每个元素都毗邻前一个元素。通常，不必关心标准库类型是如何实现的，只需要关心如何使用。然而，对于 vector 和 string ，其部分实现渗透到了接口中。

如果元素是连续的，而容器的大小是可变的，想象一下当添加元素到 vector 和 string 中会发生什么：如果没有用于存储新元素的空位置，容器必须要分配新的内存并将所有元素移动到新位置，并且添加新元素，然后释放掉旧的内存。如果 vector 每次添加元素分配和释放内存，那么性能将会很差。

为了避免这种消耗，库实现使用一种分配策略来减少容器需要重新分配内存的次数。当需要获取新的内存时，vector 和 string实现通常会分配超出其所直接需要的内存。容器将保留这部分内存用于存储新添加的元素。这样容器就不需要每次添加一个新元素就重新分配内存。

这种分配策略比每次添加一个元素都重新分配更加高效。事实上，vector的性能甚至比 list 或 deque 更加好，即便 vector 每次重新分配内存时都需要移动其所有元素。

管理容量的成员

vector 和 string 类型提供了一些成员用于与内存分配部分的实现进行交互。capacity 操作告知我们容器在不扩张内存空间的情况下可以容纳多少个元素。reserve 操作则允许我们告知容器准备让它准备保存多少个元素

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

只有当需要的内存空间超过当前容量时，reserve 才会真正改变容器容量，分配不小于需求大小的内存空间。当需求大小小于当前容量时，reserve 并不会退回内存空间。因此在调用 reserve 之后，capacity 会大于或等于传递给 reserve 的参数。

在C++11中可以使用 shrink_to_fit 函数来要求 deque、vector 和 string 退回不需要的内存空间（并不保证退回）。

每个 vector 实现都可以选择自己的内存分配策略。但是必须遵守的一条原则是：只有当迫不得已时才可以分配新的内存空间。

capacity 和 size

size 是容器中已经拥有的元素的数目，capacity是这个容器在重新分配内存之前可以容纳多少元素。

刚创建一个空的容器时，size和capacity都是 0，随着不断添加元素，capacity总是大于等于size。容器只有在必须要分配内存时才会重新分配，而且似乎目前实现的策略是将容量扩大为原来的两倍，不过这是由实现决定的。

每个实现都需要实现一种分配策略从而保证 push_back 元素到 vector 中是高效的。通过在一个原本是空的 vector 上调用 push_back n 次创建一个具有 n 个元素的 vector 的执行时间不应该超过一个常量乘以 n 。

可以调用shrink_to_fit来要求vector将超出当前大小的多余内存退回系统

每个vector实现都可以选择自己的内存分配策略，必须遵守的一条原则是：只有当迫不得已时才可以分配新的内存空间

只有在执行insert操作时size与capacity相等，或者调用resize或reserve时给定的大小超过当前capacity，vector才可能重新分配内存空间。会分配多少超过给定容量的额外空间，取决于具体实现。