Chapter 11 Containers – A Tour of C++

11.2 vector

可能标准库中最为有用的容器就是vector了。一个vector就是一组给定类型的元素。而这些元素存储在连续的内存中。一般来说,vector由几个部分组成,首先是一个handle,其保存了指向第一个元素的指针;最后一个元素之后的元素;最后一个元素之后的元素的分配空间。

此外,vector还将拥有一个allocator(也就是上图中的alloc),通过该变量,vector能够为其中的元素去拿到内存空间。默认的allocator使用new与delete来取得或者释放内存。

如果你的class层级关系与多态需要通过class的虚函数来实现,那么我们最好不将对象直接存储在容器中。相反,我们应该存储指针或者智能指针。

vector<Shape> vs;               // No!!! 我们无法使用Shape的子类,例如Circle或者Smiley
vector<Shape*> vps;             // Better
vector<unique_ptr<Shape>> vups; // Ok

11.3 list

标准库提供了一种双重链表,其被称为list。

当我们想要插入或者删除某些元素,但又不希望改变其他元素的序列时,我们会使用list。当我们使用链表时,不能通过类似vector中的标记位来读取list中的元素。相反,我们可能需要遍历整个list。

11.4 map

如果我们使用pair类型的list来保存name和与之对应的number,那么在该list中查询name将会非常繁琐。此外,线性搜索方式的效率也非常低,除非list的长度较短。因此标准库提供了binary search tree,其被称为map。

11.5 unordered_map

在map中进行查询的开销是O(log(n)),其中n表示map中元素的数量。例如,map中有1,000,000个元素,那么我们只需要进行20次对比与迂回就能找到某个元素。但是,在许多情况下,我们可以通过使用hash查询来进行优化。标准库中的hash容器都带有“unordered”,这是因为它们不需要排序函数。

11.7 Advice

[01] 使用vector作为你的默认容器。

[06] 千万不要简单地认为reserve()函数能提升效率。

[12] 元素都是拷贝至一个容器。

[13] 为了保证元素的多态,存储其指针。

[15] 如果你的序列常常是空序列,那么使用forward_list。

[19] 通过引用来传递容器,通过值来返回容器。

[20] 对于一个容器,使用()来初始化容器的size,使用{}来初始化容器的元素。

[21] 遍历整个list的开销相对较高。

[22] 如果你需要在一大堆数据中进行搜索,那么使用unordered容器。

[25] 如果容器中元素的类型没有自然顺序(大于小于),那么使用unordered容器。

 

 

留下评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据