文档介绍：STL就是Standard Template Library(C++标准模板库),下面是关于STL中的各种内容
STL中的几个基本概念:
:可容纳各种数据类型的数据结构。
可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结构。
容器分为三大类:
(1) 顺序容器
vector:后部插入/删除,直接访问 deque:前/后部插入/删除,直接访问 list:双向链表,任意位置插入/删除
1) vector 头文件<vector>
实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。
2) deque 头文件<deque>
也是个动态数组,随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。
3) list 头文件<list>
双向链表,在任何位置增删元素都能在常数时间完成。不支持随机存取。
上述三种容器称为顺序容器,是因为元素的插入位置同元素的值无关。
( 2)关联容器
set:快速查找,无重复元素 multiset :快速查找,可有重复元素 map:一对一映射,无重复元素,基于关键字查找 multimap :一对一映射,可有重复元素,基于关键字查找,前2者合称为第一类容器
关联式容器内的元素是排序的,插入任何元素,都按相应的排序准则来确定其位置。关联式容器的特点是在查找时具有非常好的性能。
1) set/multiset: 头文件<set>
set 即集合。set中不允许相同元素,multiset中允许存在相同的元素。
2) map/multimap: 头文件<map>
map与set的不同在于map中存放的是成对的key/value。
并根据key对元素进行排序,可快速地根据key来检索元素
map同multimap的不同在于是否允许多个元素有相同的key值。
上述4种容器通常以平衡二叉树方式实现,插入和检索的时间都是 O(logN)
(3)容器适配器
stack:LIFO queue:FIFO priority_queue:优先级高的元素先出
对象被插入容器中时,被插入的是对象的一个复制品。
许多算法,比如排序,查找,要求对容器中的元素进行比较,所以,放入容器的对象所属的类,还应该实现== 和< 运算符。
1) stack :头文件<stack>
栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则
2) queue :头文件<queue>
队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。
3)priority_queue :头文件<queue>
优先级队列。最高优先级元素总是第一个出列
所有标准库容器共有的成员函数:
相当于按词典顺序比较两个容器大小的运算符: =, < , <= , > , >=, == , !=
empty : 判断容器中是否有元素
max_size: 容器中最多能装多少元素
size: 容器中元素个数
swap: 交换两个容器的内容
只在第一类容器中的函数:
begin 返回指向容器中第一个元素的迭代器
end 返回指向容器中最后一个元素后面的位置的迭代器
rbegin 返回指向容器中最后一个元素的迭代器
rend 返回指向容器中第一个元素前面的位置的迭代器
erase 从容器中删除一个或几个元素
clear 从容器中删除所有元素
:可依次存取容器中元素的东西
用于指向第一类容器中的元素。有const 和非 const两种。
通过迭代器可以读取它指向的元素,通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。
定义一个容器类的迭代器的方法可以是:
容器类名::iterator 变量名;
或:
容器类名::const_iterator 变量名;
访问一个迭代器指向的元素:
* 迭代器变量名
迭代器上可以执行++ 操作, 以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面,则迭代器变成past-the-end值。
使用一个past-the-end值的迭代器来访问对象是非法的,就好像使用NULL或未初始化的指针一样。
算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。
函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。
比如,数组int array[100]就是个容器,而 int * 类型的指针变量就可以作