您的位置: 首页  >  文章  >  C++ 标准模板库STL

C++ 标准模板库STL

分类: 文章 • 2024-10-15 18:48:22

1.STL简介

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。

C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

2.STL容器

简单的理解容器，它就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法（也就是数据结构）。STL 提供有 3 类标准容器，分别是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器。它们各自的含义如表 1 所示。
STL容器分为三大类
序列容器
vector deque list
关联容器
set multiset map multimap
容器适配器
stack queue priority_queue

（1） 序列容器

所谓序列容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。

需要注意的是，序列容器只是一类容器的统称，并不指具体的某个容器，序列容器大致包含以下几类容器：
array<T,N>（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
vector（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；

deque（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；

list（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。

forward_list（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

容器结构图

C++ 标准模板库STL



（2）关联式容器

STL一共实现了两种不同结构的关联式容器：树形结构和哈希结构。

树形结构的容器主要有四种：map、set、multimap、multiset。

它们的共同点：使用平衡搜索树（红黑树）座位其底层结构。

map容器介绍：

  1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值
    key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，
    为其取别名称为pair:
    typedef pair value_type;
  3. 在内部，map中的元素总是按照键值key进行比较排序的。
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行
    直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
  5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
  6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

（3）容器适配器

容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。

3 种容器适配器，分别是 stack、queue、priority_queue：
stack<T>：是一个封装了 deque 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack 模板定义在头文件 stack 中。

queue<T>：是一个封装了 deque 容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。可以为它指定一个符合确定条件的基础容器。queue 模板定义在头文件 queue 中。

priority_queue<T>：是一个封装了 vector 容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。priority_queue 模板定义在头文件 queue 中。



参考资料：http://c.biancheng.net/view/409.html

相关推荐