乐趣区

关于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(...):插入一个或多个元素。该函数参数较简单,此处省略。

总结

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