STL(标准模板库)

1. STL概述

• 标准模板库是C++标准库的核心组成部分，包括一系列的类模板和函数模板，强大，方便，好用，高效。
• 主要包括六大组件： 迭代器、容器、适配器(容器适配器)、通用算法、仿函数、内存分配器

2. 迭代器

2.1. 概念;

• 容器是用于保存对象的对象，例如：数组就是简单的容器。
• 迭代器是用于表示容器中的位置的对象，例如：数组的迭代器就是指针。
• 迭代器是对指针的封装，指针就是简单的迭代器。
• 迭代器和容器的关系，相当于指针和数组的关系就。
• 每种容器都定义了自己的迭代器类型iterator，是容器的内部类。
• 迭代器的类型为：容器类型名::iterator，类似int*
• 所有容器都可以用迭代器来访问容器中的元素。
• 容器的.begin( )返回指向容器第一个对象的迭代器，.end( )返回指向容器的最后一个对象的下一个位置的迭代器。

  2.2. 迭代器的分类及其支持的运算符：

  | 分类 | 支持的运算符 | | —- | —- | | 前向迭代器 | = ++ * -> == != | | 双向迭代器 | “前向”支持的运算 — | | 随机迭代器 | “双向”支持的运算符 [ ] +n -n > >= < <= |

2.3. 示例代码：

#include <iostream>
using namespace std;
void print(int* arr, int n){
    /*
    for(int i = 0; i < n; i++){
    cout << arr[i] << " ";
    }
    cout << endl;
    */
    for(int* p = arr; p < arr + n; p++){
        cout << *p << " ";
    }
    cout << endl;
}
template <typename I>
void print(I begin, I end){
    for(I p = begin; p != end; p++){
        cout << *p << " ";
    }
    cout << endl;
}
int main(){
    int arr[4] = {9, 5, 2, 7};
    print(arr, 4);
    print(arr, arr + 4);
    double arrd[4] = {9.1, 5.1, 2.1, 7.1};
    print(arrd, arrd + 4);
    char arrc[4] = {'j', 'w', 'e', 'q'};
    print(arrc, arrc + 4);
    return 0;
}

2.4. 参考资料：

• 一文读懂C++五种常见的迭代器

3. 容器

3.1. 容器的概念

• 容器用于存储和处理同一类型的多个对象
• 数组就是简单的容器，对应的迭代器就是指针
• STL中的容器是对多种数据结构的实现
• STL中的容器可以分为序列容器，关联容器

3.2. 序列容器

3.2.1. 序列容器的特点

• 底层的数据结构是个序列（表）

• 元素在容器中的位置取决于插入的次序，与元素的值有关。

  3.2.2. 常见的序列容器

• list，双向链表，头文件

• vector，向量，又叫动态数组，头文件

• deque，双端队列(double-end-queue)，头文件

  3.3. 关联容器

  3.3.1. 关联容器的特点

• 底层的数据结构是平衡排序二叉树（简称，平衡树）

  • 左子树小于根，右子树大于根，左右子树高度差不超过1
• 元素在容器中的位置取决于元素的键值（key），与插入的次序无关。
• 插入的时候会自动根据值进行排序，通常是升序。

• 不能直接修改元素的直接，因为这会打乱原有的排序。

  3.3.2. 常见的关联容器

• set，集合，保存的是键，按照键排序，键唯一，头文件为

• multiset，多重集合，支持重复键，头文件也是
• map，映射，是键值对的集合，保存的是键值对，按照键排序，键唯一，头文件是
• multimap，多重映射，支持重复键，头文件也是

3.4.1. 容器的共用方法

3.4.1.1. 构造函数

• 无参构造
• 拷贝构造

• 初值列表构造（自C++11起），list<int> intList{1,2,3};

  3.4.1.2. 返回迭代器的方法

• .begin() : 前向iterator，返回指向第一元素位置的迭代器

• .end() : 返回指向最后一个元素的下一个位置的迭代器

• 注意：

  • 迭代器在插入或者删除元素之后可能会失效，因为可能会重新分配内存。
  • 如果插入或者删除过，需用.begin()和.end()重新获取迭代器。

    3.4.1.3. 插入

• .insert(pos, element)： pos为迭代器，在pos之前插入element，返回指向element的迭代器

  3.4.1.4. 删除

• .erase(pos) : 清除容器里位置为pos的元素

• .clear() : 清除容器里所有的元素

  3.4.1.5. 大小

• .size() : 实际元素数目

• .max_size() : 最大可能元素数据

  3.4.1.6. 交换

• .swap(c) : c代表一个容器，交换两个容器的内容

  3.4.1.7. 赋值

• =

  3.4.1.8. 比较

• ==

• !=

  3.4.1.9. 示例代码

  ```cpp

  ifndef TOOLH

  define TOOLH

using namespace std;

include

include

template ostream& operator<<(ostream& out, const pair& pr){ out << “(“ << pr.first << “, “ << pr.second << “)” ; return out; }

template void print(I begin, I end){ for(I it = begin; it != end; it++){
cout << *it << “ “; } cout << endl; }

endif

```cpp
#include <iostream>
#include <list>
#include "tool.h"
using namespace std;
int main(){
    // 定义容器
    list<int> intList;
    list<int> intList1{9, 5, 2, 7};
    // 定义迭代器对象
    list<int>::iterator it; // int*
    /*
    for(it = intList1.begin(); it != intList1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(intList1.begin(), intList1.end());
    intList.insert(intList.begin(), 2);
    intList.insert(intList.begin(), 0);
    intList.insert(intList.begin(), 1);
    intList.insert(intList.begin(), 9);
    intList.insert(intList.end(), 88);
    print(intList.begin(), intList.end());
    it = intList.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    intList.erase(it);
    print(intList.begin(), intList.end());
    //intList.clear();
    print(intList.begin(), intList.end());
    cout << intList.size() << endl;
    cout << intList.max_size() << endl;
    intList.swap(intList1);
    print(intList.begin(), intList.end());
    print(intList1.begin(), intList1.end());
    intList = intList1;
    print(intList.begin(), intList.end());
    print(intList1.begin(), intList1.end());
    cout << (intList == intList1) << endl;
    return 0;
}

3.4.2. 序列容器的共有方法

3.4.2.1. 插入

• .insert(pos,n,element) : 在pos之前插入n个element

  3.4.2.2. 赋值

• .assign(pos_beg, pos_end) : 将其他容器中的一段赋值给当前容器

  3.4.2.3. 调整大小

• .resize(n,element=0) : 改变当前容量的大小为n，新增元素的值为element

  3.4.2.4. 首尾

• .front() : 返回头元素的引用

• .back() : 返回尾元素的引用

  3.4.2.5. 尾部增删

• .push_back(element) : 从尾部增加一个元素

• .pop_back() : 从尾部删除一个元素，返回void

  3.4.2.6. 示例代码

  ```cpp

  include

  include

  include “tool.h”

  using namespace std;

int main(){ // 定义容器 list intList; list intList1{9, 5, 2, 7};

cout << "----------container" << endl;
// 定义迭代器对象
list<int>::iterator it; // int*
/*
for(it = intList1.begin(); it != intList1.end(); it++){
    cout << *it << " ";
}
cout << endl;
*/
print(intList1.begin(), intList1.end());
intList.insert(intList.begin(), 2);
intList.insert(intList.begin(), 0);
intList.insert(intList.begin(), 1);
intList.insert(intList.begin(), 9);
intList.insert(intList.end(), 88);
print(intList.begin(), intList.end());
it = intList.begin();
for(int i = 0; i < 2; i++){
    it++;
}
intList.erase(it);
print(intList.begin(), intList.end());
//intList.clear();
print(intList.begin(), intList.end());
cout << intList.size() << endl;
cout << intList.max_size() << endl;
intList.swap(intList1);
print(intList.begin(), intList.end());
print(intList1.begin(), intList1.end());
intList = intList1;
print(intList.begin(), intList.end());
print(intList1.begin(), intList1.end());
cout << (intList == intList1) << endl;
cout << "----------sequentialContainer" << endl;
intList.insert(intList.begin(), 3, 99);
print(intList.begin(), intList.end());
intList.assign(intList1.begin(), intList1.end());
print(intList.begin(), intList.end());
intList.resize(6, 66);
print(intList.begin(), intList.end());
cout << intList.front() << endl;
cout << intList.back() << endl;
intList.push_back(77);
print(intList.begin(), intList.end());
intList.pop_back();
print(intList.begin(), intList.end());
return 0;

}

<a name="LAj95"></a>
### 3.4.3. 序列容器的特有方法
<a name="gOBz1"></a>
#### 3.4.3.1. list的个性方法
<a name="bEYZH"></a>
##### 3.4.3.1.1. 增删
- `.push_front(element)`     :   从前面插入
- `.pop_front()  `      :    从前面删除
- `.remove(element)`  :  删除值为element的元素
<a name="DRjJL"></a>
##### 3.4.3.1.2. 除重
- `.unique()  `    :   相邻的重复元素只保留一个
<a name="lYYT9"></a>
##### 3.4.3.1.3. 排序
- `.sort() `         :   默认用于小于符号比较，从小到大排序
<a name="X1R2q"></a>
##### 3.4.3.1.4. 倒置
- `.reverse()`
<a name="h1cir"></a>
##### 3.4.3.1.5. 归并已排序list
- `.merge(list1)`    :  将 list1和当前的list合并
<a name="tHRSh"></a>
##### 3.4.3.1.6. 示例代码
```cpp
#include <iostream>
#include <list>
#include "tool.h"
using namespace std;
int main(){
    // 定义容器
    list<int> intList;
    list<int> intList1{9, 5, 2, 7};
    cout << "----------container" << endl;
    // 定义迭代器对象
    list<int>::iterator it; // int*
    /*
    for(it = intList1.begin(); it != intList1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(intList1.begin(), intList1.end());
    intList.insert(intList.begin(), 2);
    intList.insert(intList.begin(), 0);
    intList.insert(intList.begin(), 1);
    intList.insert(intList.begin(), 9);
    intList.insert(intList.end(), 88);
    print(intList.begin(), intList.end());
    it = intList.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    intList.erase(it);
    print(intList.begin(), intList.end());
    //intList.clear();
    print(intList.begin(), intList.end());
    cout << intList.size() << endl;
    cout << intList.max_size() << endl;
    intList.swap(intList1);
    print(intList.begin(), intList.end());
    print(intList1.begin(), intList1.end());
    intList = intList1;
    print(intList.begin(), intList.end());
    print(intList1.begin(), intList1.end());
    cout << (intList == intList1) << endl;
    cout << "----------sequentialContainer" << endl;
    intList.insert(intList.begin(), 3, 99);
    print(intList.begin(), intList.end());
    intList.assign(intList1.begin(), intList1.end());
    print(intList.begin(), intList.end());
    intList.resize(6, 66);
    print(intList.begin(), intList.end());
    cout << intList.front() << endl;
    cout << intList.back() << endl;
    intList.push_back(77);
    print(intList.begin(), intList.end());
    intList.pop_back();
    print(intList.begin(), intList.end());
    cout << "----------list" << endl;
    intList.push_front(77);
    print(intList.begin(), intList.end());
    intList.pop_front();
    print(intList.begin(), intList.end());
    intList.remove(9);
    print(intList.begin(), intList.end());
    intList.unique();
    print(intList.begin(), intList.end());
    intList.reverse();
    print(intList.begin(), intList.end());
    intList.sort();
    print(intList.begin(), intList.end());
    intList1.sort();
    print(intList1.begin(), intList1.end());
    intList.merge(intList1);
    print(intList.begin(), intList.end());
    return 0;
}

3.4.3.2. vector的个性方法

3.4.3.2.1. 当前容量

• .capacity() ：返回当前可以容纳的元素的个数，当插入的元素个数超过capacity时，capacity会翻倍。

  3.4.3.2.2. 预定容量

• .reserve(n) ：增加容量到n，如果n小于或等于当前容量则不起作用。

  3.4.3.2.3. 下标

• .operator[](i) ： 不检查越界

• .at(i) ：这个函数做越界检测，越界会抛出异常

  3.4.3.2.4. 示例代码

  ```cpp

  include

  include

  include “tool.h”

  using namespace std;

int main(){ // 定义容器 vector intVector; vector intVector1{9, 5, 2, 7};

cout << "----------container" << endl;
// 定义迭代器对象
vector<int>::iterator it; // int*
/*
for(it = intVector1.begin(); it != intVector1.end(); it++){
    cout << *it << " ";
}
cout << endl;
*/
print(intVector1.begin(), intVector1.end());

intVector.insert(intVector.begin(), 2);
intVector.insert(intVector.begin(), 0);
intVector.insert(intVector.begin(), 1);
intVector.insert(intVector.begin(), 9);
intVector.insert(intVector.end(), 88);
print(intVector.begin(), intVector.end());

it = intVector.begin();
for(int i = 0; i < 2; i++){
    it++;
}
intVector.erase(it);
print(intVector.begin(), intVector.end());

//intVector.clear();
print(intVector.begin(), intVector.end());

cout << intVector.size() << endl;
cout << intVector.max_size() << endl;

intVector.swap(intVector1);
print(intVector.begin(), intVector.end());
print(intVector1.begin(), intVector1.end());

intVector = intVector1;
print(intVector.begin(), intVector.end());
print(intVector1.begin(), intVector1.end());

cout << (intVector == intVector1) << endl;

cout << "----------sequentialContainer" << endl;
intVector.insert(intVector.begin(), 3, 99);
print(intVector.begin(), intVector.end());

intVector.assign(intVector1.begin(), intVector1.end());
print(intVector.begin(), intVector.end());

intVector.resize(6, 66);
print(intVector.begin(), intVector.end());

cout << intVector.front() << endl;
cout << intVector.back() << endl;

intVector.push_back(77);
print(intVector.begin(), intVector.end());
intVector.pop_back();
print(intVector.begin(), intVector.end());

cout << "--------vector" << endl;
cout << intVector.capacity() << endl;

intVector.reserve(9);
intVector.insert(intVector.end(), 3, 88);
print(intVector.begin(), intVector.end());
cout << intVector.capacity() << endl;

cout << "[] : " << intVector[3] << endl;
//cout << "at() : " << intVector.at(19) << endl;


return 0;

}

<a name="oRipk"></a>
#### 3.4.3.3. deque的个性方法
<a name="AWnsA"></a>
##### 3.4.3.3.1. 下标

- `.operator[](i)`   ：不检查越界
- `.at(i) `                 ：越界抛异常
<a name="Bm2AZ"></a>
##### 3.4.3.3.2. 增删

- `.push_front(element)`    ：从前插入
- `.pop_front() `                 ：从前删除
<a name="VtOsb"></a>
##### 3.4.3.3.3. 示例代码
```cpp
#include <iostream>
#include <deque>
#include "tool.h"
using namespace std;

int main(){
    // 定义容器
    deque<int> intDeque;
    deque<int> intDeque1{9, 5, 2, 7};

    cout << "----------container" << endl;
    // 定义迭代器对象
    deque<int>::iterator it; // int*
    /*
    for(it = intDeque1.begin(); it != intDeque1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(intDeque1.begin(), intDeque1.end());

    intDeque.insert(intDeque.begin(), 2);
    intDeque.insert(intDeque.begin(), 0);
    intDeque.insert(intDeque.begin(), 1);
    intDeque.insert(intDeque.begin(), 9);
    intDeque.insert(intDeque.end(), 88);
    print(intDeque.begin(), intDeque.end());

    it = intDeque.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    intDeque.erase(it);
    print(intDeque.begin(), intDeque.end());

    //intDeque.clear();
    print(intDeque.begin(), intDeque.end());

    cout << intDeque.size() << endl;
    cout << intDeque.max_size() << endl;

    intDeque.swap(intDeque1);
    print(intDeque.begin(), intDeque.end());
    print(intDeque1.begin(), intDeque1.end());

    intDeque = intDeque1;
    print(intDeque.begin(), intDeque.end());
    print(intDeque1.begin(), intDeque1.end());

    cout << (intDeque == intDeque1) << endl;

    cout << "----------sequentialContainer" << endl;
    intDeque.insert(intDeque.begin(), 3, 99);
    print(intDeque.begin(), intDeque.end());

    intDeque.assign(intDeque1.begin(), intDeque1.end());
    print(intDeque.begin(), intDeque.end());

    intDeque.resize(6, 66);
    print(intDeque.begin(), intDeque.end());

    cout << intDeque.front() << endl;
    cout << intDeque.back() << endl;

    intDeque.push_back(77);
    print(intDeque.begin(), intDeque.end());
    intDeque.pop_back();
    print(intDeque.begin(), intDeque.end());

    cout << "-----------deque" << endl;
    cout << "[] : " << intDeque[3] << endl;
    //cout << "at() : " << intDeque.at(19) << endl;

    intDeque.push_front(77);
    print(intDeque.begin(), intDeque.end());
    intDeque.pop_front();
    print(intDeque.begin(), intDeque.end());

    return 0;
}

3.4.4. 关联容器的共用方法

3.4.4.1. 查找

• .find(key) ：返回键等于key的第一个元素的迭代器，找不到则返回end()

  3.4.4.2. 区间

• .lower_bound(key) ：返回一个迭代器，指向首个大于或等于key的元素，作为区间的下界

• .upper_bound(key) ：返回一个迭代器，指向首个大于给定key的元素，作为区间的上届

  3.4.4.3. 统计

• .count(key) ：统计键等于key的元素的个数

  3.4.4.4. 插入

• .insert(element) ：插入元素element，返回指向element的迭代器

  3.4.4.5. 删除

• .erase(key) ：删除键等于key的所有元素

  3.4.4.6. 示例代码

  ```cpp

  include

  include

  include “tool.h”

  using namespace std;

int main(){ // 定义容器 set intSet; set intSet1{9, 5, 2, 7};

// 定义迭代器对象
set<int>::iterator it; // int*
/*
for(it = intSet1.begin(); it != intSet1.end(); it++){
    cout << *it << " ";
}
cout << endl;
*/
print(intSet1.begin(), intSet1.end());

intSet.insert(intSet.begin(), 2);
intSet.insert(intSet.begin(), 0);
intSet.insert(intSet.begin(), 1);
intSet.insert(intSet.begin(), 9);
intSet.insert(intSet.end(), 88);
print(intSet.begin(), intSet.end());

it = intSet.begin();
for(int i = 0; i < 2; i++){
    it++;
}
intSet.erase(it);
print(intSet.begin(), intSet.end());

//intSet.clear();
print(intSet.begin(), intSet.end());

cout << intSet.size() << endl;
cout << intSet.max_size() << endl;

intSet.swap(intSet1);
print(intSet.begin(), intSet.end());
print(intSet1.begin(), intSet1.end());

intSet = intSet1;
print(intSet.begin(), intSet.end());
print(intSet1.begin(), intSet1.end());

cout << (intSet == intSet1) << endl;

cout << "-----------associativeContainer" << endl;
print(intSet.begin(), intSet.end());
it = intSet.find(9);
cout << *it << endl;

intSet.insert(intSet.begin(), 16);
intSet.insert(intSet.begin(), 18);
intSet.insert(intSet.begin(), 8);
print(intSet.begin(), intSet.end());

it = intSet.lower_bound(2);
cout << "lower_bound: " << *it << endl;

it = intSet.upper_bound(17); // 指向落入区间的最后一个元素的下一个元素
cout << "upper_bound: " << *it << endl;

cout << "count : " << intSet.count(9) << endl;

intSet.insert(24);
print(intSet.begin(), intSet.end());

intSet.erase(9);
print(intSet.begin(), intSet.end());

return 0;

}

<a name="PcowQ"></a>
### 3.4.5. 关联容器的特有方法
<a name="jTBVH"></a>
#### 3.4.5.1. map的个性方法
<a name="rxw1N"></a>
##### 3.4.5.1.1. 随机存取

- `[key]`  ：访问key对应的值的引用，如果key 不存在就新增一个key
- `.at(key)`    ：返回key对应的值的引用，如果key不存在则抛出异常
<a name="axhkK"></a>
##### 3.4.5.1.2. 示例代码
```cpp
#include <iostream>
#include <map>
#include "tool.h"
using namespace std;

int main(){
    // 定义容器
    map<string, int> siMap;
    map<string, int> siMap1{{"tom", 9}, {"jerry", 5}, {"bluce", 2}, {"rose", 7}};

    // 定义迭代器对象
    map<string, int>::iterator it; // int*
    /*
    for(it = siMap1.begin(); it != siMap1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(siMap1.begin(), siMap1.end());

    siMap.insert(siMap.begin(), pair<string, int>("a", 2));
    siMap.insert(siMap.begin(), pair<string, int>("b", 0));
    siMap.insert(siMap.begin(), pair<string, int>("c", 1));
    siMap.insert(siMap.begin(), pair<string, int>("d", 9));
    siMap.insert(siMap.end(), pair<string, int>("e", 88));
    print(siMap.begin(), siMap.end());

    it = siMap.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    siMap.erase(it);
    print(siMap.begin(), siMap.end());

    //siMap.clear();
    print(siMap.begin(), siMap.end());

    cout << siMap.size() << endl;
    cout << siMap.max_size() << endl;

    siMap.swap(siMap1);
    print(siMap.begin(), siMap.end());
    print(siMap1.begin(), siMap1.end());

    siMap = siMap1;
    print(siMap.begin(), siMap.end());
    print(siMap1.begin(), siMap1.end());

    cout << (siMap == siMap1) << endl;

    cout << "-----------associativeContainer" << endl;
    print(siMap.begin(), siMap.end());
    it = siMap.find(string("b"));
    cout << *it << endl;

    siMap.insert(siMap.begin(), pair<string, int>("H", 16));
    siMap.insert(siMap.begin(), pair<string, int>("Q", 18));
    siMap.insert(siMap.begin(), pair<string, int>("R", 8));
    print(siMap.begin(), siMap.end());

    it = siMap.lower_bound(string("Q"));
    cout << "lower_bound: " << *it << endl;

    it = siMap.upper_bound(string("d")); // 指向落入区间的最后一个元素的下一个元素
    cout << "upper_bound: " << *it << endl;

    cout << "count : " << siMap.count(string("a")) << endl;

    siMap.insert(pair<string, int>("jack", 10));
    print(siMap.begin(), siMap.end());

    siMap.erase(string("e"));
    print(siMap.begin(), siMap.end());

    cout << "-------------map" << endl;
    cout << siMap[string("jack")] << endl;
    print(siMap.begin(), siMap.end());

    cout << siMap[string("rose")] << endl;
    print(siMap.begin(), siMap.end());

    cout << siMap.at(string("jack")) << endl;
    print(siMap.begin(), siMap.end());

    //cout << siMap.at(string("huluwa")) << endl;

    siMap.insert(pair<string, int>("jack", 10));
    print(siMap.begin(), siMap.end());

    return 0;
}

3.4.5.2. multimap的个性方法

没有特有方法

3.4.5.2.1. 示例代码

#include <iostream>
#include <map>
#include "tool.h"
using namespace std;

int main(){
    // 定义容器
    multimap<string, int> siMap;
    multimap<string, int> siMap1{{"tom", 9}, {"jerry", 5}, {"bluce", 2}, {"rose", 7}};

    // 定义迭代器对象
    multimap<string, int>::iterator it; 
    /*
    for(it = siMap1.begin(); it != siMap1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(siMap1.begin(), siMap1.end());

    siMap.insert(siMap.begin(), pair<string, int>("a", 2));
    siMap.insert(siMap.begin(), pair<string, int>("b", 0));
    siMap.insert(siMap.begin(), pair<string, int>("c", 1));
    siMap.insert(siMap.begin(), pair<string, int>("d", 9));
    siMap.insert(siMap.end(), pair<string, int>("e", 88));
    print(siMap.begin(), siMap.end());

    it = siMap.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    siMap.erase(it);
    print(siMap.begin(), siMap.end());

    //siMap.clear();
    print(siMap.begin(), siMap.end());

    cout << siMap.size() << endl;
    cout << siMap.max_size() << endl;

    siMap.swap(siMap1);
    print(siMap.begin(), siMap.end());
    print(siMap1.begin(), siMap1.end());

    siMap = siMap1;
    print(siMap.begin(), siMap.end());
    print(siMap1.begin(), siMap1.end());

    cout << (siMap == siMap1) << endl;

    cout << "-----------associativeContainer" << endl;
    print(siMap.begin(), siMap.end());
    it = siMap.find(string("b"));
    cout << *it << endl;

    siMap.insert(siMap.begin(), pair<string, int>("H", 16));
    siMap.insert(siMap.begin(), pair<string, int>("Q", 18));
    siMap.insert(siMap.begin(), pair<string, int>("R", 8));
    print(siMap.begin(), siMap.end());

    it = siMap.lower_bound(string("Q"));
    cout << "lower_bound: " << *it << endl;

    it = siMap.upper_bound(string("d")); // 指向落入区间的最后一个元素的下一个元素
    cout << "upper_bound: " << *it << endl;

    cout << "count : " << siMap.count(string("a")) << endl;

    siMap.insert(pair<string, int>("jack", 10));
    print(siMap.begin(), siMap.end());

    siMap.erase(string("e"));
    print(siMap.begin(), siMap.end());

    siMap.insert(pair<string, int>("jack", 10));
    print(siMap.begin(), siMap.end());
    cout << "-------------multimap" << endl;
    // 没有特有方法

    return 0;
}

3.4.5.3. set的个性方法

没有特有方法

3.4.5.3.1. 示例代码

#include <iostream>
#include <set>
#include "tool.h"
using namespace std;

int main(){
    // 定义容器
    set<int> intSet;
    set<int> intSet1{9, 5, 2, 7};

    // 定义迭代器对象
    set<int>::iterator it; // int*
    /*
    for(it = intSet1.begin(); it != intSet1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(intSet1.begin(), intSet1.end());

    intSet.insert(intSet.begin(), 2);
    intSet.insert(intSet.begin(), 0);
    intSet.insert(intSet.begin(), 1);
    intSet.insert(intSet.begin(), 9);
    intSet.insert(intSet.end(), 88);
    print(intSet.begin(), intSet.end());

    it = intSet.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    intSet.erase(it);
    print(intSet.begin(), intSet.end());

    //intSet.clear();
    print(intSet.begin(), intSet.end());

    cout << intSet.size() << endl;
    cout << intSet.max_size() << endl;

    intSet.swap(intSet1);
    print(intSet.begin(), intSet.end());
    print(intSet1.begin(), intSet1.end());

    intSet = intSet1;
    print(intSet.begin(), intSet.end());
    print(intSet1.begin(), intSet1.end());

    cout << (intSet == intSet1) << endl;

    cout << "-----------associativeContainer" << endl;
    print(intSet.begin(), intSet.end());
    it = intSet.find(9);
    cout << *it << endl;

    intSet.insert(intSet.begin(), 16);
    intSet.insert(intSet.begin(), 18);
    intSet.insert(intSet.begin(), 8);
    print(intSet.begin(), intSet.end());

    it = intSet.lower_bound(2);
    cout << "lower_bound: " << *it << endl;

    it = intSet.upper_bound(17); // 指向落入区间的最后一个元素的下一个元素
    cout << "upper_bound: " << *it << endl;

    cout << "count : " << intSet.count(9) << endl;

    intSet.insert(24);
    print(intSet.begin(), intSet.end());

    intSet.erase(9);
    print(intSet.begin(), intSet.end());

    cout << "-------------set" << endl;
    // 没有特有方法

    return 0;
}

3.4.5.4. multiset的个性方法

没有特有方法

3.4.5.4.1. 示例代码

#include <iostream>
#include <set>
#include "tool.h"
using namespace std;

int main(){
    // 定义容器
    multiset<int> intMultiset;
    multiset<int> intMultiset1{9, 5, 2, 7};

    // 定义迭代器对象
    multiset<int>::iterator it; 
    /*
    for(it = intMultiset1.begin(); it != intMultiset1.end(); it++){
        cout << *it << " ";
    }
    cout << endl;
    */
    print(intMultiset1.begin(), intMultiset1.end());

    intMultiset.insert(intMultiset.begin(), 2);
    intMultiset.insert(intMultiset.begin(), 0);
    intMultiset.insert(intMultiset.begin(), 1);
    intMultiset.insert(intMultiset.begin(), 9);
    intMultiset.insert(intMultiset.end(), 88);
    print(intMultiset.begin(), intMultiset.end());

    it = intMultiset.begin();
    for(int i = 0; i < 2; i++){
        it++;
    }
    intMultiset.erase(it);
    print(intMultiset.begin(), intMultiset.end());

    //intMultiset.clear();
    print(intMultiset.begin(), intMultiset.end());

    cout << intMultiset.size() << endl;
    cout << intMultiset.max_size() << endl;

    intMultiset.swap(intMultiset1);
    print(intMultiset.begin(), intMultiset.end());
    print(intMultiset1.begin(), intMultiset1.end());

    intMultiset = intMultiset1;
    print(intMultiset.begin(), intMultiset.end());
    print(intMultiset1.begin(), intMultiset1.end());

    cout << (intMultiset == intMultiset1) << endl;

    cout << "-----------associativeContainer" << endl;
    print(intMultiset.begin(), intMultiset.end());
    it = intMultiset.find(9);
    cout << *it << endl;

    intMultiset.insert(intMultiset.begin(), 9);
    intMultiset.insert(intMultiset.begin(), 1);
    intMultiset.insert(intMultiset.begin(), 8);
    print(intMultiset.begin(), intMultiset.end());

    it = intMultiset.lower_bound(2);
    cout << "lower_bound: " << *it << endl;

    it = intMultiset.upper_bound(17); // 指向落入区间的最后一个元素的下一个元素
    cout << "upper_bound: " << *it << endl;

    cout << "count : " << intMultiset.count(9) << endl;

    intMultiset.insert(24);
    print(intMultiset.begin(), intMultiset.end());

    intMultiset.erase(9);
    print(intMultiset.begin(), intMultiset.end());

    cout << "------------multiset" << endl;
    // 没有特有方法

    return 0;
}

3.5. 容器特点总结

4. 容器适配器

4.1. 简介

• 容器适配器是对容器进行改造，通过限制底层容器的接口，使底层容器能够满足特殊需求。

• 容器适配器不支持迭代器，所以无法使用print函数模板。

  4.2. 常见的容器适配器

• stack，栈，后进先出

• queue，队列，先进先出

• priority_queue，优先队列，优先级大的先出，默认是数值大的优先

4.3. 常见的容器适配器用法

4.3.1. 头文件：

• <stack>

• <queue>(包含queue和priority_queue)

  4.3.2. 容器适配器的共用方法

  4.3.2.1. 压入元素

• .push(element) ：压入元素，返回void
  

  4.3.2.2. 弹出元素

• .pop() ：弹出下一个元素，返回void

  4.3.2.3. 判断容器是否为空

• .empty() ：判断容器是否为空，空则返回true。移除或者返回元素前应该先检测容器是否为空，否则导致不确定结果。

  4.3.2.4. 获取容器中元素数目

• .size() ：返回容器中的元素数目

  4.3.2.5. 示例代码

  ```cpp

  include

  include

  using namespace std;

int main(){ stack intStack;

intStack.push(9);
intStack.push(5);
intStack.push(2);
intStack.push(7);

intStack.pop();

cout << intStack.empty() << endl;
cout << intStack.size() << endl;

return 0;

}

<a name="Hema6"></a>
### 4.3.3. 容器适配器的特有方法
<a name="I1agR"></a>
#### 4.3.3.1. stack的个性方法
<a name="mMNJL"></a>
##### 4.3.3.1.1. 获取栈顶元素引用

-  `.top()`   ：返回栈顶元素的引用
<a name="BBg5z"></a>
##### 4.3.3.1.2. 示例代码
```cpp
#include <iostream>
#include <stack>
using namespace std;

int main(){
    cout << "---------adapter" << endl;
    stack<int> intStack;

    intStack.push(9);
    intStack.push(5);
    intStack.push(2);
    intStack.push(7);

    intStack.pop();

    cout << intStack.empty() << endl;
    cout << intStack.size() << endl;

    cout << "---------stack" << endl;
    while(intStack.empty() == 0){
        cout << intStack.top() << endl;
        intStack.pop();
    }

    return 0;
}

4.3.3.2. queue的个性方法

4.3.3.2.1. 获取队首元素引用

• .front() ：返回队首元素的引用

  4.3.3.2.2. 获取队尾元素引用

• .back() ：返回队尾元素的引用

  4.3.3.2.3. 示例代码

  ```cpp

  include

  include

  using namespace std;

int main(){ cout << “————-adapter” << endl; priority_queue intPriorityQueue;

intPriorityQueue.push(9);
intPriorityQueue.push(5);
intPriorityQueue.push(2);
intPriorityQueue.push(7);

intPriorityQueue.pop(); // 出了9

cout << intPriorityQueue.empty() << endl;
cout << intPriorityQueue.size() << endl;

cout << "---------queue" << endl;
cout << intPriorityQueue.top() << endl;

return 0;

}

<a name="CT6no"></a>
#### 4.3.3.3. priority_queue的个性方法
<a name="DIou9"></a>
##### 4.3.3.3.1. 获取队列内的优先级最大的元素的const引用

- `.top `  ：返回队列内的优先级最大的元素的const引用，出的时候通过堆调整算法来实现最大的先出
<a name="yAIQx"></a>
##### 4.3.3.3.2. 示例代码
```cpp
#include <iostream>
#include <queue>
using namespace std;

int main(){
    cout << "---------adapter" << endl;
    queue<int> intQueue;

    intQueue.push(9);
    intQueue.push(5);
    intQueue.push(2);
    intQueue.push(7);

    intQueue.pop();

    cout << intQueue.empty() << endl;
    cout << intQueue.size() << endl;

    cout << "---------queue" << endl;
    cout << intQueue.front() << endl;
    cout << intQueue.back() << endl;

    return 0;
}

5. 通用算法

5.1. 概念

• 通用算法是全局函数模板，而不是容器的成员函数模板。
• 用来执行一些通用操作，比如查找、排序、拷贝、修改、数值运算等。
• 通用算法主要在头文件中声明，少数应用于数值运算的算法在头文件中声明
• 所有的算法都是用来处理一个或者多个区间内的元素。
• 区间的形式为[begin, end]，包含起始元素的迭代器，但不包含末尾元素的迭代器，end代表尾后迭代器。
• 一个算法能否应用于给定的容器，取决于该容器的迭代器是否支持该算法，比如sort不能用于list。
• 函数型参数：
  • 某些通用算法需要传入一个函数型的“操作(operation)”作为参数。
  • 操作可以是个函数或者函数指针，也可以是函数对象。
  • 容器中的每个元素都会执行这个操作
  • 返回bool的操作符称为“谓词(predicate)”。

• 通用算法VS容器的成员方法：

  • 通用算法，代码更通用。
  • 容器成员方法，效率更高

    5.2. 常用算法举例

    5.2.1. 非修改型算法

• for_each(begin, end, operation) ：operation可以是函数，函数指针

• find(begin, end, value) ：返回首个等于value的迭代器

• find_if(begin, end, predicate) ：返回首个满足predicate条件的迭代器

  5.2.2. 修改型算法

• replace(begin, end, oldValue, newValue) ：用newValue替换每个oldValue

• replace_if(begin, end, predicate, newValue) ：用newValue替换每个满足条件predicate的元素

  5.2.3. 变序型算法

• reverse(begin, end) ：逆序

  不能用于关联容器，因为关联容器已自动排序

5.2.4. 数值算法

• 头文件<numeric>

• accumulate(begin, end, initValue) ：返回区间所有元素的累加结果和initValue之和

  5.2.5. 移除型算法

• 移除型算法会改变原有元素个数。

• 未被移除的元素前移覆盖被移除的元素。
• 遍历时必须使用新的尾后迭代器

• remove(begin, end, value) ：移除所有等于value的元素，返回新序列的尾后迭代器

  5.2.6. 排序算法

• 不能用于关联容器，因为关联容器已自动排序

• sort(begin, end) ：sort要求随机迭代器，而list的迭代器仅仅是双向迭代器，所以sort不能用于list的排序

• sort(begin, end, predicate) ：predicate可以是函数，函数指针

  5.2.7. 有序区间算法

• binary_search(begin, end, value) ：判断已排序区间中是否包含value

• binary_search(begin, end, value, predicate) ：判断已排序区间中是否包含value，predicate代表排序规则(函数)

  5.3. 示例代码

  ```cpp

  include

  include

  include

  include

  include

  using namespace std;

void print(int a){ cout << a << “ “; }

bool myPredicate(int a){ return a < 5; }

bool myGreater(int a, int b){ return a > b; }

int main(){ list intList{9, 5, 2, 7}; for_each(intList.begin(), intList.end(), print); cout << endl;

cout << *find(intList.begin(), intList.end(), 2) << endl;
cout << *find(intList.begin(), intList.end(), 3) << endl;

cout << *find_if(intList.begin(), intList.end(), myPredicate) << endl;

replace(intList.begin(), intList.end(), 2, 3);
for_each(intList.begin(), intList.end(), print);
cout << endl;

replace_if(intList.begin(), intList.end(), myPredicate, 8);
for_each(intList.begin(), intList.end(), print);
cout << endl;

reverse(intList.begin(), intList.end());
for_each(intList.begin(), intList.end(), print);
cout << endl;

cout << accumulate(intList.begin(), intList.end(), 1000) << endl;


list<int>::iterator it ;    //  <==>  int* it   but  it-> list<int> of  one element
it = remove(intList.begin(), intList.end(), 9);
for_each(intList.begin(), it, print);
cout << endl;

vector<int> intVector{9, 5, 2, 7};
for_each(intVector.begin(), intVector.end(), print);
cout << endl;

sort(intVector.begin(), intVector.end());
for_each(intVector.begin(), intVector.end(), print);
cout << endl;

bool r;
r = binary_search(intVector.begin(), intVector.end(), 7);
cout << "r = " << r << endl;

sort(intVector.begin(), intVector.end(), myGreater);
for_each(intVector.begin(), intVector.end(), print);
cout << endl;

r = binary_search(intVector.begin(), intVector.end(), 7, myGreater);
cout << "r = " << r << endl;

return 0;

}

---

<a name="Bt5LU"></a>
# 6. 仿函数
<a name="VgccY"></a>
## 6.1. 概念

- **_仿函数_** 是_重载了（）运算符的一个类模板_
- 仿函数的对象称为函数对象
- 函数对象调用（）运算符时，行为类似于函数。
- 注意（）是不定目数的运算符，可以接受任意个数的操作数。
<a name="unkYU"></a>
## 6.2. 自定义的仿函数
```cpp
template <typename T>
class Add{
public:
    T operator()(T a, T b){
        return a+b;
    }
};

Add a;
a(1, 2); // 返回3

6.3. 预定义的仿函数

• STL针对常用的算术运算，比较运算，逻辑运算定了很多仿函数

• 使用预定义的仿函数必须包含头文件<functional>

  6.3.1. 算术运算

• plus<T> ：实现x+y的仿函数

• minus<T> ：实现x-y的仿函数
• multiplies<T> ：实现x*y的仿函数
• divides<T> ：实现x/y的仿函数
• modulus<T> ：实现x%y的仿函数

• negate<T> ：实现-x的仿函数

  6.3.2. 比较(关系运算)

• equal_to<T> ：实现x==y的仿函数

• not_equal_to<T> ：实现x!=y的仿函数
• greater<T> ：实现x>y的仿函数
• less<T> ：实现x<y的仿函数
• greater_equal<T> ：实现x>=y的仿函数

• less_equal<T> ：实现x<=y的仿函数

  6.3.3. 逻辑运算

• logical_and<T> ：实现x&&y的仿函数

• logical_or<T> ：实现x||y的仿函数

• logical_not<T> ：实现!x的仿函数

  6.4. 仿函数的常用场景

  6.4.1. 用作通用算法的参数

• 某些通用算法需要传入一个”操作”或”判断”作为参数，函数对象可以充当这种参数。

• 例如：

  • for_each(begin, end, op);
  • find_if(begin, end, predicate);
  • sort(begin,end, predicate); ：predicate可以是函数，函数指针，函数对象

    6.4.2. 用作容器的参数

• 某些容器，需要传入一个仿函数作为参数

• 例如：
  • set<T , greater<T>>

6.5. 示例代码

#include <iostream>
#include <functional>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int add(int a , int b){
    return a + b;
}

void print(int a){
    cout << a << " ";
}

template <typename T>
class MyPrint{
    public:
    void operator()(T a){
        cout << a << " ";
    }
};

// 仿函数的定义
template <typename T>
class Add{
    public:
    T operator()(T a, T b){
        return a + b;
    }
};

template <typename T>
class MyPredicate{
    public:
    bool operator()(T a){
        return a < 6;
    }
};

int main(){
    cout << add(1, 2) << endl;

    // 函数对象的概念
    Add<int> a; // a称为函数对象
    cout << a(1, 2) << endl; // a.operator()(1, 2);
    cout << Add<int>()(2, 3) << endl;

    plus<int> b;
    cout << b(1, 3) << endl;
    cout << plus<int>()(2, 3) << endl;
    cout << greater<int>()(3, 2) << endl;

    // 函数对象的应用
    vector<int> intVector{9, 5, 2, 7};
    for_each(intVector.begin(), intVector.end(), MyPrint<int>());
    cout << endl;

    cout << *find_if(intVector.begin(), intVector.end(), MyPredicate<int>()) << endl;

    sort(intVector.begin(), intVector.end(), greater<int>());
    for_each(intVector.begin(), intVector.end(), MyPrint<int>());
    cout << endl;

    set<int, greater<int>> intSet{2, 0, 1, 9};
    for_each(intSet.begin(), intSet.end(), MyPrint<int>());
    cout << endl;

    return 0;
}

7. 内存分配器

• std::allocator
• 内存分配器用于封装STL容器在内存管理上的底层细节
• 默认情况下，STL使用预定义的通用分配器