C++编程学习（十二） STL

一、简介

　标准模板库STL，是一组模板类和函数。提供了：

　　1、容器。用于存储信息。

　　2、迭代器。用于访问容器中的信息。

　　3、算法。操作容器内容。

1、容器

　　STL有两种类型的容器类：

（1）顺序容器

　　std::vector。动态数组。

　　std::deque。和vector类似。

　　　　【vector和deque区别】

　　　　① deque使用不止一块内存（而vector必须使用一块连续内存），所以传地址需要注意

　　　　② 除了头尾两端，在任何地方安插或删除元素，都将导致指向deque元素的所有pointers、references、iterators失效。

　　　　③ deque的动态数组头尾都开放，允许在开头插入或者删除元素。

　　std::list。双向链表。

　　std::forward_list。单向链表。

（2）关联函数

　　std::set。存储各不相同的值，并在插入时候进行排序。复杂度为对数。

　　std::unordered_set。功能等同于set。但复杂度为常数。(C++11新增)

　　std::multiset。存储值，并在插入时候进行排序。但是值可以是相同的，即值不需要唯一。

　　std::unordered_multiset。与unordered_set类似，但是允许存储多个值相同的项，即值不需要唯一。(C++11新增)

　　std::map。存储键值对，并根据唯一的键排序。复杂度为对数。

　　std::unordered_map。存储键值对，并根据唯一的键排序。复杂度为对数。(C++11新增)

　　std::multimap。与map类似，但是键不要求唯一。

　　std::unordered_multimap。与unordered_map类似，但是键不要求唯一。(C++11新增)

此外还提供了：

（3）容器适配器。

　　std::stack。后进先出。在栈顶压入或者弹出元素。

　　std::queue。先进先出。可以删除最先插入的元素。

　　std::priority_queue。优先级队列，优先级最高的元素排在队列开头。

2、迭代器

　　最简单的迭代器是指针。STL迭代器可以理解为模板类的一部分，是一种泛型指针。算法为模板函数，迭代器让模板函数能够无缝地处理容器。

（1）输入迭代器

　　通过对输入迭代器解除引用，它将引用对象。

（2）输出迭代器

　　执行写入操作。

3、算法

　　常用的STL算法如下：

　　std::find。在集合中查找值。

　　std::find_if。根据条件查找值。

　　std::reverse。反转顺序。

　　std::remove_if。根据条件反转顺序。

　　std::transform。根据用户定义的变换函数对容器中的元素进行变换。

除了上面的，STL还提供了一个操纵字符串的模板类std::basic_string<T>。具体化为std::string和std::wstring。

巴特西