营销型网站建设案例,电子商城网站,东莞网站建设网站推广,网站建设制作设计惠州参考资料#xff1a;
《C Primer》第5版《C Primer 习题集》第5版
C 中的容器可以分为 3 类#xff1a;顺序容器、关联容器、无序关联容器。
9.1 顺序容器概述#xff08;P292#xff09;
所有顺序容器都提供了快速顺序访问的能力#xff0c;但在以下方面的性能有所不…参考资料
《C Primer》第5版《C Primer 习题集》第5版
C 中的容器可以分为 3 类顺序容器、关联容器、无序关联容器。
9.1 顺序容器概述P292
所有顺序容器都提供了快速顺序访问的能力但在以下方面的性能有所不同
向容器添加、删除元素非顺序访问容器中的元素 除了固定大小的 array 外其他容器提供高效、灵活的内存管理。不同的存储管理策略将会影响容器操作的效率以及是否支持特定操作
string 和 vector 将元素保存在连续的空间中所以支持随机访问但在中间位置添加或删除元素就非常耗时。添加一个元素可还需要分配额外的存储空间此时容器中的每个元素都将移动到新的存储空间中。list 和 forward_list 可以快速在任何位置添加或删除元素但不支持随机访问。这两个容器的额外内存开销也较大。deque 支持快速随机访问在中间位置添加或删除元素代价高但在两端添加或删除元素的速度与 list 和 forward_list 相当。
forward_list 和 array 是 C 新标准新添加的类型。array 是比内置数组更安全、更易使用的数组类型forward_list 的设计目标是达到与最好的手写单向链表相当的性能所以其没有 size 操作因为这会产生额外开销。 新标准库的容器性能很高所以现在 C 程序应该更多地使用标准库容器 确定使用哪种顺序容器
选择容器的基本原则
除非有很好的理由选择其他容器否则选择 vector 。如果你的程序有很多小的元素且空间开销很重要则不要使用 list 或 forward_list 。如果程序要求随机访问元素使用 vector 或 deque 。如果程序要求在中间插入或删除元素使用 list 或 forward_list 。如果程序要求在头尾插入或删除元素使用 deque 。
9.2 容器库概览P294
本小节介绍的操作对所有容器都适用。
对容器可以保存的元素类型的限制
虽然顺序容器几乎可以保存任何元素类型但某些容器操作需要对元素类型有特殊要求。例如顺序容器的构造函数的一个版本接受容器大小参数它使用了元素的默认构造函数但如果某个类没有默认构造函数我们可以定义这个类的顺序容器但不能适用这个版本的构造函数
// noDefault是一个没有默认构造函数的类型
vectornoDefault v1(10); // 错误9.2.1 迭代器P296
迭代器范围
一个迭代器范围iterator range由一对迭代器表示这两个迭代器通常被称为 begin 和 end 并满足如下要求
它们指向同一个容器中的元素或容器的尾后位置。可以通过大于等于 0 次的递增运算使 begin 到达 end 。
迭代器范围是一个左闭右开区间。
适用左闭合范围蕴含的编程假定
左闭合范围有一些方便的性质
如果 begin 和 end 相等则范围为空。如果 begin 和 end 不等则范围中至少包含一个元素且 begin 指向范围中的首元素。我们可以对 begin 递增若干次使得 begin end 。
9.2.2 容器类型成员97
每个容器都定义了很多类型如 size_type 、iterator 、const_iterator 。大多数容器还提供反向迭代器执行 操作会得到上一个元素。
每个容器还定义了很多类型别名如 value_type 、reference 或 const_reference 。
为了使用这些类型我们必须显式使用类名
liststring::iterator iter;
vectorint::difference_type count;9.2.3 begin和end成员P298
不以 c 开头的 begin 和 end 函数都是被重载过。例如实际上存在两个名为 begin 的成员一个是 const 的返回 const_iterator 另一个不是常量返回 iterator 。
以 c 开头的版本是 C 新标准引入的用以支持 auto 与 begin 和 end 结合使用
vectorint vi(5);
auto it1 a.begin();
auto it2 a.cbegin();练习
9.10 下面四个对象分别是什么类型
vectorint v1;
const vectorint v2;
auto it1 v1.begin(), it2 v2.end();
auto it3 v1.cbegin(), it4 v2.cend();答第一条 auto 语句显然是不正确的第二条 auto 语句解析出的类型是 vectorint::const_iterator 。
9.2.4 容器定义和初始化P299 将一个容器初始化为另一个容器的拷贝
将一个容器初始化为另一个容器的拷贝的方式有两种直接拷贝整个容器、 array 除外拷贝由一对迭代器指定的元素范围。
直接拷贝整个容器时需保证容器类型和元素类型完全相同范围拷贝只要求能将被拷贝的元素类型转换成目标类型即可
liststring ls { hello, hi, world };
vectorconst char * vcc { a, an, the };liststring ls1(ls); // 正确
dequestring ds(ls); // 错误容器类型不相同
vectorstring vs(vcc); // 错误元素类型不相同
forward_liststring fls(vcc.begin(), vcc.end()); // 正确范围初始化用被拷贝容器中的元素对目标容器中的对应元素进行初始化。 列表初始化
在新标准中我们可以对一个容器进行列表初始化。对于除 array 之外的容器类型外初始化列表还隐含指定了容器的大小。
与顺序容器大小相关的构造函数
只有顺序容器的构造函数才接受大小参数。
标准库array具有固定大小
定义一个 array 容器时除了要指定元素类型外还要指定容器大小
arrayint, 42 ai;大小是 array 类型的一部分
arrayint, 10::size_type i;
arrayint::size_type j; // 错误与内置数组不同的是array 支持拷贝、赋值操作此时要求容器类型、元素类型、元素个数都一样。
9.2.5 赋值和swapP302 赋值操作 c1 c2 将 c1 中的元素替换为 c2 中元素的拷贝要求 c1 和 c2 必须具有相同的类型容器类型、元素类型array 还额外要求元素数量。
使用assign仅顺序容器
assign 允许我们从一个不同但相同的类型赋值
liststring ls { hello, hi, world };
vectorconst char * vcc { a, an, the };ls vcc; // 错误
ls.assign(vcc.begin(), vcc.end()); // 正确使用swap
swap 可以交换两个相同类型容器的内容
vectorstring svec1(10);
vectorstring svec2(20);
swap(svec1, svec2);单独提起“相同类型容器”其实就等价于容器类型相同、元素类型相同、元素数量相同仅 array。 除 array 外swap 并不会真的交换元素本身所以效率很高可以在常数时间完成。由于元素不会被移动除 string 外指向容器的迭代器、引用、指针在 swap 操作后不会失效它们仍然指向原来的元素但这些元素已经不属于原来的容器了。
array 的 swap 操作会真正交换元素所需时间与元素数量成正比。swap 操作后迭代器、引用、指针扔指向原来的元素但元素值已经进行了交换 建议使用非成员版本的 swap 。 9.2.6 容器大小操作P304
除 forward_list 外每个容器都支持 size 、empty 、max_size forward_list 只支持前两个。
9.2.7 关系运算符P304
每个容器类型都支持 和 ! 除无序关联容器外的所有容器都支持 、 、 、 。关系运算符要求左右两边对象有相同的容器类型。
两个容器的比较实际上是元素的逐对比较
逐个比较元素一旦遇到不相等的情况就用这对不相等元素的比较结果作为容器的比较结果。如果没有遇到不相等的情况此时用元素数量的比较结果作为容器的比较结果。
容器的关系运算符使用元素的关系运算符完成
容器的 和 ! 实际上是使用元素的 实现的其他运算符是使用元素的 实现的。
