忧郁的大能猫

好奇的探索者，理性的思考者，踏实的行动者。

Table of Contents:

STL 是一些常用数据结构和算法的模板的集合，于 1998 年被加入 C++ 标准

C++容器（STL容器）

容器（container）中可以存放基本类型的变量，也可以存放对象。对象或基本类型的变量被插入容器中时，实际插入的是对象或变量的一个复制品
但是不能放引用，因为：
The component type of containers like vectors must be assignable. References are not assignable (you can only initialize them once when they are declared, and you cannot make them reference something else later).
Other non-assignable types are also not allowed as components of containers, e.g. vector<const int> is not allowed.

STL 中的许多算法（即函数模板），如排序、查找等算法，在执行过程中会对容器中的元素进行比较。这些算法在比较元素是否相等时通常用运算符进行，比较大小通常用<运算符进行，因此，被放入容器的对象所属的类最好重载==和<运算符，以使得两个对象用==和<进行比较是有定义的。

顺序容器

顺序容器有以下三种：可变长动态数组 vector、双端队列 deque、双向链表 list。
它们之所以被称为顺序容器，是因为将元素插入容器时，指定在什么位置（尾部、头部或中间某处）插入，元素就会位于什么位置。
顺序容器和关联容器还有以下成员函数：
 begin()：返回指向容器中第一个元素的迭代器。
 end()：返回指向容器中最后一个元素后面的位置的迭代器。
 rbegin()：返回指向容器中最后一个元素的反向迭代器。
 rend()：返回指向容器中第一个元素前面的位置的反向迭代器。
 erase(...)：从容器中删除一个或几个元素。该函数参数较复杂，此处省略。
 clear()：从容器中删除所有元素。
顺序容器还有以下常用成员函数：
 front()：返回容器中第一个元素的引用。
 back()：返回容器中最后一个元素的引用。
 push_back()：在容器末尾增加新元素。
 pop_back()：删除容器末尾的元素。
* insert(...)：插入一个或多个元素。该函数参数较复杂，此处省略。

关联容器

关联容器有以下四种：set、multiset、map、multimap。关联容器内的元素是排序的。插入元素时，容器会按一定的排序规则将元素放到适当的位置上，因此插入元素时不能指定位置。
默认情况下，关联容器中的元素是从小到大排序（或按关键字从小到大排序）的，而且用<运算符比较元素或关键字大小。因为是排好序的，所以关联容器在查找时具有非常好的性能。

除了以上两类容器外，STL 还在两类容器的基础上屏蔽一部分功能，突出或增加另一部分功能，实现了三种容器适配器：
栈 stack、队列 queue、优先级队列 priority_queue。
容器适配器 stack、queue 和 priority_queue 没有迭代器。容器适配器有一些成员函数，可以用来对元素进行访问

C++迭代器（STL迭代器）iterator详解

要访问顺序容器和关联容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以1.读写它指向的元素,2.通过递减或递增来改变指向。从这一点上看，迭代器和指针类似。
iterator const_iterator  reverse_iterator const_reverse_iterator  move_iterator

迭代器的功能分类

1. 正向迭代器(不支持大于小于比较)
2. 双向迭代器(不支持大于小于比较)
3. 随机访问迭代器(可以比较，可以随机访问)

迭代器的辅助函数

 advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。
 distance(p, q)：计算两个迭代器之间的距离，如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。
* iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

STL算法

STL 提供能在各种容器中通用的算法，如插入、删除、查找、排序等。算法就是函数模板。
算法通过迭代器来操纵容器中的元素
STL 中的大部分常用算法都在头文件 algorithm 中定义。此外，头文件 numeric 中也有一些算法。
有的算法会改变其所作用的容器。例如：
 copy：将一个容器的内容复制到另一个容器。
 remove：在容器中删除一个元素。
 random_shuffle：随机打乱容器中的元素。
 fill：用某个值填充容器。
有的算法不会改变其所作用的容器。例如：
 find：在容器中查找元素。
 count_if：统计容器中符合某种条件的元素的个数。

STL中“大”、“小”和“相等”的概念

在 STL 中，默认情况下，比较大小是通过<运算符进行的，和>运算符无关
y比x大意味着x<y为真，而不是y>x为真。y>x的结果如何并不重要，甚至y>x是没定义的都没有关系。
综上所述，使用 STL 中的关联容器和许多算法时，往往需要对<运算符进行适当的重载，使得这些容器和算法可以用<运算符对所操作的元素进行比较。

STL vector（可变长的动态数组）

STL list（双向链表）

STL 中的算法 sort 可以用来对 vector 和 deque 排序，它需要随机访问迭代器的支持。因为 list 不支持随机访问迭代器，所以不能用算法 sort 对 list 容器排序。因此，list 容器引入了 sort 成员函数以完成排序。

STL deque（双向队列详解）

deque 也是顺序容器的一种，同时也是一个可变长数组。所有适用于 vector 的操作都适用于 deque。
优点:头尾增删元素都具有较好的性能

C++函数对象详解

如果一个类将()运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。函数对象其实就是重载了()的对象，是一个更加面向对象的函数指针，它可以用很多面相对象的很多特性。

class CAverage
{
public:
    double operator()(int a1, int a2, int a3)
    { //重载()运算符
        return (double)(a1 + a2 + a3) / 3;
    }
};
int main()
{
    CAverage average; //能够求三个整数平均数的函数对象
    cout << average(3, 2, 3); //等价于 cout << average.operator(3, 2, 3);
    return 0;
}

STL关联容器

关联容器内部的元素都是排好序的，有以下四种。
 set：排好序的集合，不允许有相同元素。
 multiset：排好序的集合，允许有相同元素。
 map：每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的。不允许有多个元素的关键字相同。
 multimap：和 map 类似，差别在于元素的关键字可以相同。
不能修改 set 或 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 set 或 multiset 容器中某个元素的值，
正确的做法是先删除该元素，再插入新元素。
同理，也不能修改 map 和 multimap 容器中元素的关键字。
使用关联容器的目的也就在于快速查找。当一个元素被插入关联容器时，该元素会和已有的元素进行比较，最终被插入一个合适的位置。
关联容器一般是用平衡二叉树实现的。

STL pair类模板

在学习关联容器之前，首先要了解 STL 中的 pair 类模板，因为关联容器的一些成员函数的返回值是 pair 对象
STL 中还有一个函数模板 make_pair，其功能是生成一个 pair 模板类对象

pair<int,double> p1;
pair<string,int> p2("this",20);
pair<int,int> p3(pair<char,char>('a','b'));
pair<int,string> p4 = make_pair(200,"hello");

STL multiset

multiset 是关联容器的一种，是排序好的集合（元素已经进行了排序），并且允许有相同的元素。

<运算符必须经过适当重载，才可以向 multiset <A>容器中插人元素。

#include <set>
using namespace std;
class A{};
int main(){
    multiset <A> a;
    a.insert( A() ); //编译出错，因为不能用“<”运算符比较两个A对象
}

typedef multiset<A> MSET1; //用“<”运算符比较大小
MSET1::iterator pp = m1.find(19);
if (pp != m1.end())
{
    cout << "found" << endl; //本行会被执行，输出 found
    cout << *m1.lower_bound(22)
    << "," << *m1.upper_bound(22) << endl; //输出 22,33

}
pp = m1.erase(m1.lower_bound(22), m1.upper_bound(22));

STL set

set 是关联容器的一种，是排序好的集合（元素已经进行了排序）。set 和 multiset 类似，它和 multiset 的差别在于 set 中不能有重复的元素。multiset 的成员函数 set 中也都有。
由于不能有重复元素，所以 set 中插入单个元素的 insert 成员函数与 multiset 中的有所不同，其原型如下：

pair<iterator, bool> insert(const T & val);

如果 set 的 insert 成员函数的返回值是 pair 模板类对象 x，如果 x.second 为 true，则说明插入成功，此时 x.first 就是指向被插入元素的迭代器；
如果 x.second 为 false，则说明要插入的元素已在容器中，此时 x.first 就是指向原有那个元素的迭代器。

STL multimap

multimap 是关联容器的一种，multimap 的每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的，并且允许有多个元素的关键字相同。

STL map

不允许有多个元素的关键字相同。

C++容器适配器简介

STL 中的容器适配器有 stack、queue、priority_queue 三种。它们都是在顺序容器的基础上实现的，屏蔽了顺序容器的一部分功能，突出或增加了另外一些功能。
容器适配器是没有迭代器的，因此 STL 中的各种排序、查找、变序等算法都不适用于容器适配器。

STL stack

stack的定义如下：

template < class T, class Cont == deque <T> >
class stack{
    ...
};

第二个参数表明，在默认情况下，stack 就是用 deque 实现的。当然，也可以指定用 vector 或 list 实现。

STL queue

queue 的定义如下：

template < class T, class Cont = deque<T> >
class queue{
    ...
};

priority_queue

priority_queue 是“优先队列”。它和普通队列的区别在于，优先队列的队头元素总是最大的——即执行 pop 操作时，删除的总是最大的元素；执行 top 操作时，返回的是最大元素的引用。
priority_queue 可以用 vector 和 deque 实现，默认情况下用 vector 实现。
priority_queue实现是二叉堆，特别适用于“不停地在一堆元素中取走最大的元素”

#include <queue>
#include <iostream>
using namespace std;
int main()
{
    priority_queue<double> pq1;
    pq1.push(3.2); pq1.push(9.8); pq1.push(9.8); pq1.push(5.4);
    while(!pq1.empty()) {
        cout << pq1.top() << " ";
        pq1.pop();
    } //上面输出 9.8 9.8 5.4 3.2
    cout << endl;
    priority_queue<double,vector<double>,greater<double> > pq2;
    pq2.push(3.2); pq2.push(9.8); pq2.push(9.8); pq2.push(5.4);
    while(!pq2.empty()) {
        cout << pq2.top() << " ";
        pq2.pop();
    }
    //上面输出 3.2 5.4 9.8 9.8
    return 0;
}

STL算法分类

在 STL 中，算法就是函数模板。STL 中的算法大多数是用来对容器进行操作的，如排序、 查找等。大部分算法都是在头文件 <algorithm> 中定义的，还有些算法用于数值处理，定义在头文件 <numeric> 中。
大多数重载的算法都有两个版本，其中一个用==判断元素是否相等，或用<比较大小；
而另一个版本多出来一个类型参数 Pred 以及函数形参 Pred op，该版本通过表达式op(x, y)的返回值是 true 还是 false 来判断 x 是否“等于”y 或者“小于”y。比如下面有两个版本的 min_element：

iterate min_element(iterate first, iterate last);
iterate min_element(iterate first, iterate last, Pred op);

min_element 返回区间中最小的元素。第一个版本用<比较大小，而第二个版本用自定义的比较器 op 来比较大小，op(x, y) 的值为 true，则说明 x 比 y 小。

C++ bitset类

bitset 模板类由若干个位（bit）组成，它提供一些成员函数，使程序员不必通过位运算就能很方便地访问、修改其中的任意一位。

template <size_t N>
class bitset
{
    ...
};

size_t 可看作 unsigned int。将 bitset 实例化时，N 必须是一个整型常数。例如：

bitset <40> bst;

则 bst 是一个由 40 个位组成的对象，用 bitset 的成员函数可以方便地访问其中任意一位。bitset 中的位从 0 开始编号，第 0 位是最右边的位。

C++ STL 中的 std：string 类以字符 \0结尾么

无规定，但是我认为内部没有理由不以零结尾或不预留结尾零的位置
原因在于c_str()这个函数的调用
这个函数会返回c风格的字符串，是以零结尾的。如果内部不以零结尾或不预留结尾零的位置，那么这个函数的实现会比较低效率，因为意味着要重新分配更大的缓冲区来盛放数据。因此（或还有其他原因），主流实现都会以零结尾或预留结尾零的位置。