欢乐C++ —— 7. 顺序容器概览

欢乐C++ —— 7. 顺序容器概览

简述

简单说一下C++的容器，这节主要介绍常见的顺序容器的操作。

STL 标准库

C++ 语言的核心优势之一就是便于代码的重用。C++ 中有两个方面体现重用：

一是面向对象的继承和多态机制；二是通过模板的概念实现了对泛型程序设计的支持。

C++ 的标准模板库（Standard Template Library，STL）是泛型程序设计最成功应用的实例。STL 是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。有了 STL，程序员就不必编写大多数常用的数据结构和算法。而且 STL 是经过精心设计的，运行效率很高，比水平一般的程序员编写的同类代码速度更快。

容器

容器（container）用于存放数据的类模板。可变长数组、链表、平衡二叉树等数据结构在 STL 中都被实现为容器。

C++ 的容器总的可以分为两类：

顺序容器：容器中的元素是按照它们在容器中的位置顺序来保存和访问的。关联容器：容器中的元素是按照关键字来保存和访问。关联容器内的元素是排序的。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。默认情况下，关联容器中的元素是从小到大排序的，而且用<运算符比较元素或关键字大小。因为是排好序的，所以关联容器在查找时具有非常好的性能。容器适配器：通过对上面两类容器进行限制一部分操作STL 在两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能，实现了三种容器适配器：栈 stack、队列 queue、优先级队列 priority_queue。这些容器适配器底层没有自己的数据结构，依靠其它的容器。其本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。

底层

我的是MSVC 14.16 版本。

vector 动态扩容数组deque 底层为map 和多个小数组list 双向循环链表forward_list 单向链表array 固定大小数组string 动态扩容数组map set multimap multiset 红黑树unordered_map unordered_set unordered_mulitimap unordered_mulitiset 哈希链表stack queue 底层为 dequepriority_queue 底层为 vector

顺序容器

它们之所以被称为顺序容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插入，元素就会位于什么位置。

该选择那种顺序容器？

以下是一些准则：

如果程序要求随机访问，那就 vector 或 deque如果程序要求经常插入：如果是头尾插入：deque在中间插入：list 或 forward_list如果既需要随机访问，又需要中间访问，测试vector deque 与 list forward_list 的相对性能。如果程序中有很多小元素，且对空间要求较高，那就不要使用 list 或 forward_list

总之，结合各个容器的特性，按照使用使用场景进行筛选。

一些常见操作

添加元素

push_back() … insert() … 拷贝构造元素emplace() … 新构造元素。

访问元素

back() front() 返回容器中最后一个 / 第一个元素的引用。重载运算符[] 和 at() 返回特定下标位置的元素的引用。

这些保证索引有效是调用者的责任。

删除元素

pop_back() … erase() … clear()

删除时小心迭代器失效。

容器空间大小

• reserve() resize()

  两者区别在于前者只给元素分配空间，而后者是分配空间并构造元素。

  empty()	size()	capacity()
  resize(10)	false	10	10
  reserve(10)	true	0	10

  在reserve 之后，不能使用下标访问vector ，因为此时vector 中没有元素。reserve 和resize 都可能导致容器扩容，元素搬家。

• max_size() shrink_to_fit()

  前者是返回当前环境最大存放元素的个数。后者使容器大小空间大小缩至和size() 相等。

赋值相关

assign()给一个容器对象赋值。有多种重载版本，可以拷贝别的元素类型相同的容器的元素，或者使用列表，或者指定某个元素及其数量。都将会调用拷贝构造函数。swap()在绝大部分容器中，swap 只是交换底层的数据结构，所以开销与容器所含的元素个数无关。但在array 中 swap 会老老实实交换元素。列表初始化与赋值先将元素拷贝到 initializer_list 可变形参类中，然后再从这个类拷贝到容器中。

迭代器

四种类型begin() cbegin() rbegin() crbegin()

迭代器默认的范围是左闭右开 即 [begin , end)

迭代器底层是指针，所以在容器中添加，删除等操作可能使得迭代器失效。

string 容器的额外操作

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。