当前位置：首页 > article >正文

【C++】顺序容器（二）：顺序容器操作

article 2024/11/27 12:16:07

9.3 顺序容器操作

9.3.1 向顺序容器添加元素

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

使用 push_back

除 array 和 forward_list 之外，每个顺序容器（包括 string 类型）都支持 push_back。

如：

string word;
while(cin >> word) {
	container.push_back(word);
}

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

使用 push_front

list、forward_list 和 deque 容器还支持名为 push_front 的类似操作。来将元素插入到容器的头部。

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

push_back 和 push_front 操作提供了一种方便地在顺序容器头部和尾部插入单个元素的方法。insert 成员提供了更加一般的添加功能，它允许我们在容器中任意位置插入 0 个或多个元素。

每个 insert 函数都接受一个迭代器作为其第一个参数。迭代器指出了在容器中什么位置存放新元素。它还可以指向容器中的任何位置，包括容器尾部之后的下一个位置。由于迭代器可能指向容器为不之后不存在的元素的位置，而且在容器开始位置插入元素是很有用的功能，所以 insert 函数将元素插入到实参迭代器所指向的元素位置之前：

slist.insert(iter, "Hello!");

将一个值为”Hello!"的 string 对象插入到 iter 指向的元素之前的位置。

WARNING: 将元素插入到 vector、deque 和 string 中的任何位置都是合法的。然而这样做将会很耗时。

插入范围内元素

除了第一个迭代器参数之外，insert 函数还可以接受更多的参数，这与容器构造函数类似。

其中的一个版本接受一个元素数目和一个值，它将指定数量的元素添加到指定位置之前，这些元素都按给定值初始化：

svec.insert(svec.end(), 10, "Anna");

上述代码将 10 个元素插入到 svec 末尾，并将元素初始化为 string “Anna”。

接受一对迭代器或一个初始化列表的 insert 版本将给定范围中的元素插入到指定位置之前：

vector<string> v = {"quasi", "simba", "frollo", "scar"};
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will", "go", "at", "the", "end"});
slist.insert(slist.begin(), slist.begin(), slist.end()); // 运行时错误❌: 迭代器
														 // 表示要拷贝的元素范围, 不能
														 // 指向与目的位置相同的容器

使用 insert 返回值

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

list<string> lst;
auto iter = lst.begin();
while(cin >> word) {
	iter = lst.insert(iter, word);	// 等价于调用 push_front
}

insert 返回的迭代器恰好指向插入的新元素。

使用 emplace 操作

C++ 11 标准引入了三个新成员—— emplace_front、emplace 和 emplace_back，这些操作构造而不是拷贝元素。上述三个操作对应的分别是 push_front、insert 和 push_back。

当调用 push 或 insert 成员函数时，我们将元素类型的对象传递给它们，这些对象拷贝到容器当中。而当我们调用一个 emplace 成员函数时，则是将参数传递给元素类型的构造函数。emplace 成员使用这些参数在容器管理的内存空间中直接构造元素。

例如，假定容器 c 要保存一个 Sales_data 的对象：

// 在 c 的末尾构造一个 Sales_data 对象
// 使用三个参数的 Sales_data 构造函数
c.emplace_back("978-0590353403", 25, 15.99); // 正确👌, 调用三个实参版本的 Sales_data 构造函数构造临时对象
											 // 并将临时对象保存到 c 的末尾
// 👇 以下是一个错误的例子
c.push_back("978-0590353403", 25, 15.99); // 错误❌, 没有接受三个参数的 push_back 对象
c.push_back(Sales_data("978-0590353403", 25, 15.99)); // 正确: 创建了一个临时的 Sales_data 对象

在调用 emplace_back 时，会在容器管理的内存空间中直接创建对象。而调用 push_back 则会创建一个局部临时对象，并将其压入容器中。

emplace 函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配。

9.3.2 访问元素

以下是一些常用的顺序容器中访问元素的操作：

at 和下标操作只适用于 string、vector、deque 和 array；
back 不适用于 forward_list；
c.back()：返回容器 c 中尾元素的引用。若 c 为空，函数行为未定义；
c.front()：返回容器 c 中首元素的引用。若 c 为空，函数行为未定义；
c[n]：返回 c 中下标为 n 的元素的引用，n 是一个无符号整数。若 n >= c.size()，则函数行为未定义；
c.at(n)：返回下标为 n 的元素的引用。如果下标越界，则抛出一 out_of_range 异常；
WARNING：对一个空容器调用 front 和 back，就像使用一个越界的下标一样，是一种严重的程序设计错误。

包括 array 在内的每一个顺序容器都有 front 成员函数，而除去 forward_list 之外的所有顺序容器都有一个 back 成员函数。

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

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

if(!c.empty()) {
	c.front() = 42;			// 将 42 赋予 c 的第一个元素
	auto &v = c.back();		// 获取指向最后一个元素的引用
	v = 1024;				// 改变 c 中的最后一个元素
	auto v2 = c.back();		// 此时, v2 不是一个引用, 它是一个 c.back() 的拷贝, 原因在于 v2 没有被声明为引用类型
	v2 = 0;					// 不改变 c 中的元素
}

下标元素和安全的随机访问

提供快速随机访问的容器也都提供下标运算符。下标运算符接受一个下标参数，返回容器中该位置的元素的引用。

给定下标必须在范围内。保证下标有效是程序员的责任，编译器将不会负责检查下标是否正确。使用越界的下标是一种严重的程序设计错误。

如果我们希望确保下标合法，可以使用 at 成员函数。at 成员函数类似下标运算符，如果下标越界，at 会抛出一个 out_of_range 异常。

9.3.3 删除元素

与添加元素的多种方法类似，（非 array）容器也有多种删除元素的方式：
（由于下述的删除操作会改变容器的大小，所以不适用于 array）

forward_list 有特殊版本的 erase，详见后面的内容；
forward_list 不支持 pop_back；vector 和 string 不支持 pop_front；
c.pop_back()：删除 c 中的尾元素；若 c 为空，则函数行为未定义。函数返回 void；
c.pop_front()：删除 c 中的首元素；若 c 为空，则函数行为未定义。函数返回 void；
c.erase§：删除迭代器 p 所指定的元素，返回一个指向被删元素之后元素的迭代器，若 p 指向尾元素，则返回尾后迭代器。若 p 是尾后迭代器，则函数行为未定义；
c.erase(b, e)：删除迭代器 b 和 e 所指定范围内的元素。返回一个指向最后一个被删元素之后的元素迭代器，若 e 本身就是尾后迭代器，则函数也返回尾后迭代器。（此处的 erase 操作删除的应该是左闭右闭的区间，返回的是最后一个被删元素之后的元素的迭代器）
c.clear()：删除 c 中的所有元素，返回 void；

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

pop_front 和 pop_back 成员函数

pop_front 和 pop_back 成员函数分别删除首元素和尾元素。vector 和 string 同样不支持 pop_front 和 pop_back。同时，forward_list 不支持 pop_back。不能对一个空容器执行弹出操作。

从容器内部删除一个元素

erase 从容器中指定位置删除元素。可以删除单个迭代器指定的单个元素，也可以返回由迭代器范围确定的左闭右闭区间内的元素。erase 返回被删除的最后一个元素之后的迭代器。

删除多个元素

9.3.4 特殊的 forward_list 操作

当在单向链表中添加或删除一个元素时，删除或添加的元素之前的那个元素的后继会发生改变。由于 forward_list 是一个单向链表，在单向链表中，没有简单的方法获取元素的前驱。因此，在 forward_list 中添加或删除元素的操作是通过改变给定元素之后的元素来完成的。

出于上述原因，forward_list 并未定义 insert、emplace 和 erase，而是定义了 insert_after、emplace_after 和 erase_after 操作。例如，对于链表 $elem_1 \rightarrow elem_2 \rightarrow elem_3 \rightarrow elem_4$ ，为了删除 $elem_3$ ，应该使用指向 $elem_2$ 的迭代器调用 erase_after。