C++笔记(12) 标准模板库STL

STL提供了一组表示容器、迭代器、函数、函数对象和算法的模板。STL不是面向对象的编程，而是一种不同的编程模式——泛型编程。

• 容器：与数组类似的单元，可以存储若干个值，存储的值的类型相同；
• 算法：完成特定任务（如对数组进行排序或在链表中查找特定值）的处方；
• 迭代器：能供用来遍历容器的对象，与能够遍历数组的指针类似，是广义指针；
• 函数对象：类似于函数的对象，可以是类对象或函数指针（包括函数名，因为函数名被用作指针）。

容器

通用容器分为3类：顺序容器、关联容器、容器适配器。

 1. 顺序容器

（1）vector：数组的一种类表示，提供自动内存管理功能，可以动态地改变对象长度；

提供对元素的随机访问，在尾部之外的位置插入或者删除元素可能很慢。

（2）deque：双端列表，支持随机访问，从deque对象开始位置插入和删除元素的时间固定。

（3）list：双向链表，可以双向遍历列表，任意位置插入和删除元素时间固定，不支持数组表示法和随机访问。

（4）array：在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。(C++11标准新加)

在使用上，它比普通数组更安全（原因后续会讲），且效率并没有因此变差。

array 容器的大小是固定的，因此无法借由增加或移除元素而改变其大小，它只允许访问或者替换存储的元素。

（5）forward_list : 单向链表。只支持单向顺序访问。在链表的任何位置进行插入、删除操作都很快。(C++11标准新加)

2. 关联容器

关联容器将值与键关联在一起，并使用键来查找值。关联容器的优点在于，它提供了对元素的快速访问。与序列相似，关联容器也允许插入新元素，但不能指定元素的插入位置。原因是关联容器通常有用于确定数据放置位置的算法，以便能够快速检索信息。

关联容器通常是使用树实现的。树是一种数据结构，其根节点链接到一个或两个节点，而这些节点又链接到一个或两个节点，从而形成分支结构，与链表相比，树的查找速度更快。

（1）set：值和键的类型相同，键是唯一的，值就是键。

（2）multiset：类似于set，只是可能又多个值的键相同。

（3）map：键与值类型不同，键是唯一的，每个键只对应一个值。

（4）multimap：类似于map，只是一个键可以和多个值相关联。

//由于此处初始化时指示了对键进行排序的比较函数，因此下面的set_union也需要加，不然会异常

#include <set>
#include <string>
#include <iterator>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {

    set<int,greater<int>> A{ 1,2,3,4,5,6,9,9 };
    set<int, greater<int>> B{ 6,5,4,3,2,1 };//由于此处初始化时指示了对键进行排序的比较函数，因此下面的set_union也需要加，不然会异常

    ostream_iterator<int, char> out(cout, " ");
    cout << "set A:"; 
    copy(A.begin(), A.end(), out);
    cout << "\nset B:";
    copy(B.begin(), B.end(), out);
    cout << "\n" << "Union of A and B:";
    set_union(begin(A), A.end(), B.begin(), B.end(),out, greater<int>());
    return 0;
}

 无序关联容器

（1）unordered_map ： 用哈希函数组织的map

（2）unordered_set : 用哈希函数组织的set

（3）unordered_multimap ： 哈希组织的map;关键字可以重复出现

（4）unordered_multiset : 哈希组织的set;关键字可以重复出现

从上面的容器名称可以看出：允许重复关键字的容器名字都包含multi；而使用哈希技术的容器名字都以unordered开头。

3. 适配器

容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。 

（1）queue：封装了 deque 容器，不允许随机访问队列元素，不允许遍历队列。可以添加元素到队尾push()，删除队首pop()，size()，以及empty();

（2）priority_queue:封装了 vector 容器，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。

（3）stack：封装了 deque 容器，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。

容器操作

size()——返回容器中元素数目

swap()——交换两个容器的内容

begin()——返回一个指向容器中第一个元素的迭代器

end()——返回一个表示超多容器尾的迭代器

push_back()——将元素添加到矢量末尾

erase()——删除矢量中给定区间的元素（函数接受两个迭代器参数，第一个迭代器指向区间的起始处，第二个迭代器位于区间终止处的后一个位置）

insert()——在给定区间插入元素（函数接受3个迭代器参数，第一个参数指定了新元素的插入位置，第二个和第三个迭代器参数定义了被插入区间，该区间是另一个容器的一部分）

迭代器

什么是迭代器？它是一个广义指针，也可以是一个对其执行类似指针的操作——如解除引用operator*()和递增operator++()的对象。通过将指针广义化为迭代器，让STL能够为各种不同的容器类提供统一的接口。每个容器类都定义了一个合适的迭代器，该迭代器的类型是一个名为iterator的typedef，其作用域为整个类。比如：

vector<double>::iterator pd;
vector<double> scores;
pd = scores.begin();//使pd指向第一个元素
*pd = 22.3;//解除引用并赋值
++pd;//使pd指向下一个元素

算法

算法用来处理群集内的元素，可以出于不同目的搜寻、排序、修改、使用那些元素。所有容器的迭代器都提供一致的接口，通过迭代器的协助，算法程序可以用于任意容器。常见的算法如下：

• for_each()——可以代替for循环

例如：

vector<int>::iterator pr;
for (pr = a.begin(); pr != a.end(); pr++) {
    show(*pr);
}

可以替换为：

for_each(a.begin(), a.end(), show);

• random_shuffle()——随机排列区间中的元素

函数接受两个指定区间的迭代器参数，并随机排列该区间中的元素

random_shuffle(a.begin(), a.end());

• sort()——排序

第一个版本，接受两个定义区间的迭代器参数，并使用（为存储在容器中的类型元素定义的）<运算符，对区间中的元素进行操作。

如果容器元素是自定义的对象，要使用sort()，必须定义该对象的operate<()函数，例如：

class Person {
public:
    Person(int a, int h) :age(a), height(h) {};
    int age;
    int height;
};
bool operator<(const Person& p1, const Person& p2) {
    if (p1.age < p2.age)
        return true;
    else if (p1.age == p2.age && p1.height < p2.height)
        return true;
    else
        return false;
}

排序：

Person p1(11, 150); Person p2(12, 160); Person p3(11, 160);
vector<Person> ps({ p1,p2,p3 });
sort(ps.begin(), ps.end());

上面是以全局函数的形式实现对 < 运算符的重载，还可以使用成员函数或者友元函数的形式实现。其中，当以成员函数的方式重载 < 运算符时，该成员函数必须声明为 const 类型，且参数也必须为 const 类型：

bool operator<(const Person& temp) {
    if (this->age < temp.age)
        return true;
    else if (this->age == temp.age && this->height < temp.height)
        return true;
    else
        return false;    
}

同样，如果以友元函数的方式重载 < 运算符时，要求参数必须使用 const 修饰：

//类中友元函数的定义
friend bool operator <(const myString &a, const myString &b);

//类外部友元函数的具体实现
bool operator <(const myString &stra, const myString &strb) {
    //以字符串的长度为标准比较大小
    return stra.str.length() < strb.str.length();
}

第二个版本，如果不是想升序，想降序，或者其他的排序方法，就定义一个函数：

bool fun(const Person& p1, const Person& p2) {
...
}
sort(ps.begin(), ps.end(), fun);

用lamda表达式后：

sort(v.begin(), v.end(), [](const int& a, const int& b) { return a > b; });

函数对象（仿函数）

一般来说，如果我们列出一个对象，而它的后面又跟有由括号包裹的参数列表，就像f(arg1, arg2, ...)，这个对象就被称为函数对象。

注意：函数对象使一个类，不是一个函数，函数对象重载了“（）”操作符使得它可以像函数一样调用。比如：

class Add
{
public:
    int operator()(int a, int b)
    {
        return a + b;
    }
};
Add add; // 定义函数对象  
cout << add(3, 2); // 5 

函数指针版本为：

int AddFunc(int a, int b)  
{  
　　return a + b;  
}  
typedef int (*Add) (int a, int b);  
Add add = &AddFunc;  
cout << add(3,2); 

既然C++函数对象与函数指针在使用方式上没什么区别，那为什么要用函数对象呢？很简单，函数对象可以携带附加数据，而指针就不行了。比如：

class  less 
{
    public : 
    less(int  num) : n(num) {} 
    bool operator()(int  value) 
    {
        return  value  < n;
    } 
    private : 
    int n;
};

使用时：

const int SIZE = 5;  
int array[SIZE] = { 50, 30, 9, 7, 20};  
// 找到小于数组array中小于10的第一个数的位置  
int * pa = std::find_if(array, array + SIZE, less(10)); 
// pa 指向 9 的位置  

// 找到小于数组array中小于40的第一个数的位置  
int * pb = std::find_if(array, array + SIZE, less(40));　
// pb 指向 30 的位置 

参考文献：

1. 《C++ Primer Plus》第16章

2. C++ STL关联式容器自定义排序规则

3. 干货分享：什么是C++STL？掌握C++ STL的核心很重要！

4.【C++】什么是函数对象和函数对象的用处