关于c++:C-STL标准库概述容器

一、定义

STL，英文全称 sdard template library，中文可译为规范模板库或者泛型库，其蕴含有大量的模板类和模板函数，是 C++ 提供的一个根底模板的汇合，用于实现诸如输出 / 输入、数学计算等性能。简略来讲，STL 是一些容器、算法和其余一些组件的汇合。

二、组成构造

STL 是由容器、算法、迭代器、函数对象、适配器、内存分配器这 6 局部形成，其中前面 4 局部是为前 2 局部服务的，它们各自的含意如下图所示。

C++ 规范中，STL 被组织为 13 个头文件。

三、容器

 容器（container）是用于存放数据的类模板。可变长数组、链表、均衡二叉树等数据结构在 STL 中都被实现为容器。容器中能够寄存根本类型的变量，也能够寄存对象。对象或根本类型的变量被插入容器中时，理论插入的是对象或变量的一个复制品。容器分为两大类, 即程序容器和关联容器；也能够分为三大类：序列容器、排序容器和哈希容器。

1、程序容器（序列容器）

 程序容器或序列容器，其特点就是元素在容器中的地位同元素的值无关，即容器不会对存储的元素进行排序。将元素插入容器时，指定在什么地位（尾部、头部或两头某处）插入，元素就会位于什么地位。STL 规范库中所有的序列式容器，包含 array、vector、deque、list 和 forward_list。

2、关联容器（排序容器、有序关联容器）

 关联容器分为 set（汇合）和 map（映射表）两大类，及其衍生体 multiset 和 multimap。这些容器的底层机制均以 RB-tree（红黑树）实现，均衡二叉树中的一种（还包含 AVL-tree、AA-tree）。RB-tree 也是一个独立容器，但并不凋谢应用。SGI STL 还提供一个不在规范规格的关联式容器 hash_table（散列表），以及以 hash_table 为底层机制而实现的 hash_set 散列汇合、hash_map 散列映射表、hash_multiset 散列多键汇合、hash_multimap 散列多键映射表。关联容器中每个元素都有一个键值 key 和一个实值 value。关联容器内的元素是排序的。插入元素时，容器会按肯定的排序规定将元素放到适当的地位上，因而插入元素时不能指定地位。默认状况下，关联容器中的元素是从小到大排序（或按关键字从小到大排序）的，而且用 `<` 运算符比拟元素或关键字大小。因为是排好序的，所以关联容器在查找时具备十分好的性能。

3、无序关联容器（哈希容器）

无序关联式容器，它们常被称为“无序容器”、“哈希容器”或者“无序关联容器”。无序容器是 C++ 11 规范才正式引入到 STL 规范库中的，如果要应用该类容器，则必须抉择反对 C++ 11 规范的编译器。和关联式容器一样，无序容器也应用键值对（pair 类型）的形式存储数据。然而它们有着实质上的不同：关联式容器的底层实现采纳的树存储构造，更确切的说是红黑树结构；无序容器的底层实现采纳的是哈希表的存储构造。C++ STL 底层采纳哈希表实现无序容器时，会将所有数据存储到一整块间断的内存空间中，并且当数据存储地位发生冲突时，解决办法选用的是“链地址法”（又称“开链法”）。基于底层实现采纳了不同的数据结构，因而和关联式容器相比，无序容器具备以下 2 个特点：①无序容器外部存储的键值对是无序的，各键值对的存储地位取决于该键值对中的键；②和关联式容器相比，无序容器善于通过指定键查找对应的值（均匀工夫复杂度为 O(1)）；但对于应用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。和关联式容器一样，无序容器只是一类容器的统称，其蕴含有 4 个具体容器，别离为 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。这 4 种无序容器的名称，仅是在关联式容器名称的根底上，增加了 "unordered_"。以 map 和 unordered_map 为例，其实它们仅有一个区别，即 map 容器内存会对存储的键值对进行排序，而 unordered_map 不会。也就是说，C++ 11 规范的 STL 中，在已提供有 4 种关联式容器的根底上，又新增了各自的“unordered”版本（无序版本、哈希版本），进步了查找指定元素的效率。理论场景中如果波及大量遍历容器的操作，倡议首选关联式容器；反之，如果更多的操作是通过键获取对应的值，则应首选无序容器。留神，因为哈希容器直到 C++ 11 才被正式纳入 C++ 规范程序库，而在此之前，“民间”流传着 hash_set、hash_multiset、hash_map、hash_multimap 版本，不过该版本只能在某些反对 C++ 11 的编译器下应用（如 VS），有些编译器（如 gcc/g++）是不反对的。

4、容器适配器

除了以上两类容器外，STL 还在两类容器的根底上屏蔽一部分性能，突出或减少另一部分性能，实现了三种容器适配器：栈 stack、队列 queue、优先级队列 priority_queue。容器适配器是一个封装了序列容器的类模板，它在个别序列容器的根底上提供了一些不同的性能。之所以称作适配器类，是因为它能够通过适配容器现有的接口来提供不同的性能。1.  stack<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack<T> 模板定义在头文件 stack 中。2.  queue<T>：是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。能够为它指定一个合乎确定条件的根底容器。queue<T> 模板定义在头文件 queue 中。3.  priority_queue<T>：是一个封装了 vector<T> 容器的适配器类模板，默认实现的是一个会对元素排序，从而保障最大元素总在队列最后面的队列。priority_queue<T> 模板定义在头文件 queue 中。适配器类在根底序列容器的根底上实现了一些本人的操作，显然也能够增加一些本人的操作。它们提供的劣势是简化了公共接口，而且进步了代码的可读性。

四、成员办法

所有容器都有以下两个成员函数：①int size()：返回容器对象中元素的个数。②bool empty()：判断容器对象是否为空。程序容器和关联容器还有以下成员函数：* begin()：返回指向容器中第一个元素的迭代器。* end()：返回指向容器中最初一个元素前面的地位的迭代器。* rbegin()：返回指向容器中最初一个元素的反向迭代器。* rend()：返回指向容器中第一个元素后面的地位的反向迭代器。* erase(...)：从容器中删除一个或几个元素。该函数参数较简单，此处省略。* clear()：从容器中删除所有元素。注：如果一个容器是空的，则 begin() 和 end() 的返回值相等，rbegin() 和 rend() 的返回值也相等。程序容器还有以下罕用成员函数：* front()：返回容器中第一个元素的援用。* back()：返回容器中最初一个元素的援用。* push_back()：在容器开端减少新元素。* pop_back()：删除容器开端的元素。* insert(...)：插入一个或多个元素。该函数参数较简单，此处省略。

总结

 以上几种容器的存储形式齐全不同，因而应用不同容器实现雷同操作的效率也大不相同。所以在理论应用时，要长于依据想实现的性能，抉择适合的容器。