************ 写在前面*************

这是我在学习过程中的总结，代码只写了关键部分，直接复制可能运行不了，还需要额外补充main和头文件等一些东西。可能会有不全或者错误的地方，欢迎大家指出来，共同进步。

1、STL的概念

STL（Standard Template Library），即标准模板库，是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构。

STL有两个极为重要的特点。1、它不是面向对象的。2、数据结构和算法分离。为了实现泛型编程和更好的通用性，STL依赖于模板而不是OOP的三要素（继承、封装和多态）。

STL从广义上分为：容器、算法和迭代器。容器和算法之间通过迭代器进行无缝连接，STL几乎所有的代码都采用了模板类和模板函数，使得一个数据结构或者算法可以适用于多种类型的数据。

2、STL的内容

STL中有六大组件：

• 容器（Container）：是一种数据结构，以模板类的方式存放数据。例如vector、list等。
• 算法（Algorithm）：是一种模板函数，用于操作容器内的数据元素。例如排序算法sort()，查找函数find()。函数与其具体操作的数据结构和类型无关。
• 迭代器（Iterator）：是一个类，类中封存了指向容器内部的对象的指针。由于容器和算法是分开编写的，为了使其能够搭配起来使用，便将迭代器作为容器和算法之间沟通的桥梁。容器提供自己的迭代器，算法接收迭代器，即可操作容器内的数据元素。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。
• 仿函数（Functor）：在STL中采用的名称是函数对象，其本质就是类重载了一个operator()，创建一个行为类似函数的对象。所以有两点特点：1、仿函数不是函数，本质是一个类； 2、仿函数重载了()运算符，使得它可以像函数那样调用（代码的形式好像是在调用函数）。
• 适配器（Adaptor）：简单理解就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。
• 分配器（Allocator）

2.1、容器

STL中的容器分类序列式容器和关联式容器。
（1）序列式容器，顾名思义就是有顺序的容器，这种顺序与元素的具体的值无关，由其进入容器的顺序有关。例如vector、list、的确等。
（2）关联式容器，顾名思义就是元素之间具有某种关联，这种所谓的“关联”就是容器内各个元素排序的“规则”，与元素的插入顺序无关。例如元素大小顺序就是一种排序规则。例如set、multiset、map、multimap等。

2.2、迭代器

要访问容器中的元素，需要通过“迭代器（iterator）”进行。迭代器是一个变量，相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。从这一点上看，迭代器和指针类似。
迭代器重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；常见的一些迭代器类型：正向迭代器（iterator）、常量正向迭代器（const_iterator）、反向迭代器（reverse_iterator）和常量反向迭代器（const_reverse_iterator）。

2.3、算法

STL定义了一组泛型算法：因为它们是操作数据元素实现某种目的，所以称之为“算法”；而“泛型”指的是它们可以适用于多种容器类型，不但可以作用于标准库类型，也可以用于内置类型。
使用算法需要包含头文件<algorithm>，<numeric>和<functional>。其中<algorithm>是所有STL头文件中最大的一个，是由一大堆模版函数组成的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
<numeric>只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
<functional>中定义了一些模板类，用以声明函数对象。

STL中算法大致分为四类：
非可变序列算法：指不直接修改其所操作的容器内容的算法。
可变序列算法：指可以修改它们所操作的容器内容的算法。
排序算法：对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
数值算法：对容器内容进行数值计算。

具体分类及使用方法如下：
（1）常用查找算法

• find(iterator begin, iterator end, value)：在指定区间进行查找，若找到返回对应的位置的迭代器，否则返回end()。注意：因为find内部比较是用的双等号==操作符，所以如果查找的是对象，需要对此进行重载。

bool operator==(const 类名& p) const
{
    
	return 0;
}

• adjacent_find(iterator begin, iterator end, _callback)：在指定区间进行查找相邻重复元素，若找到返回相邻元素的第一个位置的迭代器，否则返回end()
• binary_search(iterator begin, iterator end, value)：二分查找，仅适用于有序序列，返回值是bool
• find_if(iterator begin, iterator end, _callback)：条件查找，若找到返回对应的位置的迭代器，否则返回end()
• count(iterator begin, iterator end, value)：统计元素个数，返回次数
• count_if(iterator begin, iterator end, _callback)：返回满足条件_callback的个数

（2）常用遍历算法

• for_each(iterator begin, iterator end, _callback)：遍历让容器元素，返回容器对象
• transform(iterator begin1, iterator end1, iterator begin2, _callback)：将制定容器内的元素搬运到另一个容器中。返回目标容器迭代器

（3）常用删除和替换算法

• copy(iterator begin1, iterator end1, iterator begin2)：复制序列
• copy_backward(iterator begin1, iterator end1, iterator)：与copy相同，不过元素是以相反顺序被拷贝。
• replace：将指定范围内所有与给定值相等的值替换为另一个值
• swap：换存储在两个容器中的值
• remove：删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数

2.4、仿函数

2.4.1、概述

重载函数调用操作符“()”的类，其对象称之为函数对象（function object），即它们是香行为类似函数的对象，也叫仿函数（functor），其实就是重载“()”操作符，使得类对象可以像函数那样调用。

注意：

1. 函数对象（仿函数）本质是一个类，不是一个函数。
2. 函数对象（仿函数）重载了“()”操作符使得它可以像函数一样调用，类似函数却不是函数，所以叫仿函数。
3. 函数对象可以用参数和返回值。
4. 函数对象超出函数概念，可以保存函数调用状态。比如要计算一个函数调用的次数，普通函数需要通过全局变量保存，而因为函数对象是一个类，可以用成员变量来保存。
5. 函数对象可以作为参数和返回值。
6. 根据operator()重载需要的参数个数，有“一元仿函数”和“二元仿函数”。

2.4.2、仿函数的使用

1. 使用回调函数实现仿函数

int sortFunc(int v1, int v2)
{
    
	return v1 > v2;
}

void main()
{
    
	//实现vector的降序排列
	vector<int> v = {
     54, 21, 11, 67, 22 };
	sort(v.begin(), v,end(), sortFunc);
}

2. 重载“()”实现仿函数

class MyCompare
{
    
public:
	bool operator()(int v1, int v2)
	{
    
		return v1 > v2;
	}
};

void main()
{
    
	//实现vector的降序排列
	vector<int> v = {
     54, 21, 11, 67, 22 };
	MyCompare mycompare;
	sort(v.begin(), v.end(), mycompare);
}

2.4.3、内建仿函数

STL内建了一些仿函数，分为：1）算数类仿函数，2）关系运算类仿函数，3）逻辑运算类仿函数。要使用这些内建仿函数，需要包含头文件头文件是<functional>。

1. 算数类仿函数：
   -加：plus<T>
   -减：minus<T>
   -乘：multiplies<T>
   -除：divides<T>
   -取模：modulus<T>
   -取反：negate<T>

例子：

int main()
{
    
	cout << plus<int>()(3, 5) << endl;//3+5
	cout << multiplies<int>()(3, 5) << endl;//3*5
}

2. 关系运算类仿函数
   -等于：equal_to<T>
   -不等于：not_equal_to<T>
   -大于：greater<T>
   -大于等于：greater_equal<T>
   -小于：less<T>
   -小于等于：less_equal<T>

例子：

int main()
{
    
	vector<int> v = {
     54, 21, 11, 67, 22 };
	//降序排列
	sort(v.begin(), v.end(), greater<int>());
}

3. 逻辑运算类仿函数
   -逻辑与：logical_and<T>
   -逻辑或：logical_or<T>
   -逻辑否：logical_no<T>

2.5、适配器

（函数对象）适配器是完成一些配接工作，这些配接工作包括绑定（bind），否定（negate）以及对一般函数或成员的修饰，使其成为函数对象：

• bind1st：将参数绑定为函数对象的第一个参数
• bind2nd：将参数绑定为函数对象的第一个参数
• not1：对一元函数对象取反
• not2：对一二函数对象取反
• ptr_fun：将普通函数修饰成函数对象
• mem_fun：修饰成员函数
• mem_fun_ref：修饰成员函数

例子：

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


//---------------------绑定适配器bind1st bind2nd---------------------
class MyPrint : public binary_function<int,int,void>
{
    
public:
	void operator()(int v, int val) const
	{
    
		cout << v + val << " ";
	}
};

void test01()
{
    
	vector<int> v;
	for (int i = 0; i < 20; i++)
	{
    
		v.push_back(i);
	}	 
	//绑定适配器bind2nd，将两个参数绑定为一个参数
	int addnum = 100;
	for_each(v.begin(), v.end(), bind2nd(MyPrint(),addnum));
	//假设要使vector的每个值加一个值addnum后输出，需要用到bind2nd适配器
	//操作步骤：
	//1、仿函数public继承一个类binary_function<参数一类型，参数二类型，返回类型>
	//（MyPrint有两个参数，所以binary_function有两个参数类型+返回类型void）
	//2、operator()加入const修饰符

	//bind1st和bind2nd的区别？
	//bind1st，将addnum绑定为第一个参数
	//bind2nd，将addnum绑定为第二个参数
}


//-------------------------取反适配器not1 not2----------------------------
class MyCompare : public binary_function<int, int, bool>
{
    
public:
	bool operator()(int v1, int v2) const
	{
    
		return v1 > v2;
	}
};

void test02() 
{
    
	vector<int> v;
	for (int i = 0; i < 20; i++)
	{
    
		v.push_back(i);
	}
	//使vector降序排列
	sort(v.begin(), v.end(), MyCompare());
	//对MyCompare取反，使得vector升序排列
	sort(v.begin(), v.end(), not2(MyCompare()));
	//将函数对象取反
	//操作步骤：
	//1、public继承类binary_function<参数一类型，参数二类型，返回类型>
	//（MyCompare有两个参数，所以binary_function有两个参数类型+返回类型bool）
	//2、operator()加入const修饰符

	//not1 和 not2 的区别
	//对二元函数对象取反，用not2
	//对一元函数对象取反，用not1
	//用not1时，继承的类是unary_function

}
//---------------------普通函数转函数对象ptr_fun----------------------
void MyPrint(int val, int val2) 
{
    
	cout << val << " ";
	cout << "增加的参数：" << val2 << " ";
}
void test03() 
{
    
	vector<int> v;
	for (int i = 0; i < 20; i++)
	{
    
		v.push_back(i);
	}
	for_each(v.begin(), v.end(), MyPrint);
	//上面for_each调用的是普通函数MyPrint，不是函数对象不能进行绑定
	//使用ptr_fun将普通函数转成函数对象，然后可以绑定参数
	//此时，MyPrint函数可以增加一个参数
	for_each(v.begin(), v.end(), bind2nd(ptr_fun(MyPrint),10));
}


//-----------------成员函数适配器mem_fun mem_fun_ref---------------------
class Person
{
    
public:
	Person(int age, int id) :age(age), id(id) 
	{
    
	}
	void show() 
	{
    
		cout << "age: " << age << " id: " << id << endl;
	}

private:
	int age;
	int id;
};

void test04()
{
    
	//如果容器中存放着对象或者对象指针，我们可以在for_each中调用对象自己提供的打印函数
	vector<Person> v;
	Person p1(10, 20), p2(30, 40), p3(50, 60);
	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);

	//使用mem_fun_ref可以调用对象内部的成员函数
	//使用格式：
	//mem_fun_ref(&类名::函数名)
	for_each(v.begin(), v.end(), mem_fun_ref(&Person::show));

	//mem_fun_ref 和 mem_fun 的区别？
	//存放的是对象，使用mem_fun_ref
	//存放的是对象指针，用mem_fun

	vector<Person*> v1;
	v1.push_back(&p1);
	v1.push_back(&p2);
	v1.push_back(&p3);
	for_each(v1.begin(), v1.end(), mem_fun(&Person::show));
}


int main() 
{
    
	test01();
	test02();
	test03();
	test04();	
}

2.6、分配器

3、常用容器

3.1、string容器

3.1.1、跟char*型的字符串作对比：

• string是一个类，char* 是一个指针；
  -string内部封装了char* ，管理这个字符串，是一个char*型 的容器
• string封装了很多成员方法；
  -查找find，拷贝copy，删除delete，替换replace，插入insert）
• 不用考虑内存释放和越界；
  -string管理char* 所分配的内存，每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等问题

3.1.2、与char*型的相互转换：

char* 转 string：

• 方式1：

const char* ch = "abc"; 
//或者 char ch[] = "abc";
string str1(ch);//调用构造函数
string str2 = ch;

• 方式2：

char* ch = "abc";
string str(ch, ch + strlen(ch)); 

string 转 char*：

• 方式1

string str;
char* ch = const_cast<char*>(str.c_str());

• 方式2

string str;
char* ch = &str[0];

3.1.3、string的使用

1. 初始化、

string str1;
string str2(10, 'a');
string str3("abc");
string str4(str3);

2. 赋值

string str1;
string str2("abc");
str1 = "abc";
str1 = str2;
str1 = 'a';
str1.assign("abc");

//重载[]操作符
for(int i = 0; i < str1.size(); i++)
{
    
	cout << str1[i] << endl;
}
//at成员函数
for(int i = 0; i < str1.size(); i++)
{
    
	cout << str1.at(i) << endl;
}
//[]和at区别：
//越界时，[]会崩溃；at会抛异常out_of_range

3. 拼接

//重载+=操作符
string str1("abc");
str1 += "def";
//append函数
string str2;
str2.append(str1);

4. 查找

//find函数，从前往后查找，返回第一次查找到的位置
string str("abcdefghfg");
int pos = str.find("fg"); //5
//rfind函数，从后往前查找，返回第一次查找到的位置
int rpos = str.rfind("fg");//8

5. 替换

//replace
string str("abcdefg");
str.replace(3,2,"111");//从3位置用111替换2个字符，答案abc111fg

6. 比较

//compare 根据ASCII码比较
// > 时返回1
// < 时返回-1
// == 时返回 0
string str("bbb");
int ret; // a b c ASCII码依次是97 98 99
ret = str.compare("aaa");// 1
ret = str.compare("bbb");// 0
ret = str.compare("ccc");// -1

7. 子串

string str("abcdef");
string subs = str.substr(1,3);//从位置1开始的3个字符，答案bcd

8. 插入与删除

//insert
string str("abcdef");
str.insert(2,"111");//从位置2插入111
str.insert(2,3,'h');//从位置2插入3的字符h
str.erase(3,2);//从位置3开始删除2个字符

3.2、vector（向量）

3.2.1、vector的底层结构

vector，动态数组，可以根据元素的数量实现数组长度的动态增长，也是一个单口数组，一般是从数组一端（数组尾部）进行插入和删除，效率很高，如果在中间位置插入，会引起大量数据的移动，效率偏低。

3.2.2、vector的使用

1. 初始化

//1.
vector<int> v1;
vector<int> v2 = {
    1,2,3.0,4,5,6,7};
vector<int> v3 {
    1,2,3.0,4,5,6,7};
//2.
vector<int> v4(v2.begin(), v2.end());//复制区间
vector<int> v5 = v2;
vector<int> v6(v2);//复制构造函数
vector<int> v7(7);//7个缺省值的初始化
vector<int> v8(20,1);//用20个1初始化

2. 插入

//插入
vector<int> v;
v.push_back(1);//尾部增加一个元素
v.insert(v.begin(),2);//开始迭代器增加一个元素
v.insert(v.begin(),5,3);//开始迭代器位置增加5个相同的元素3

3. 存取

//存取元素
vector<int> v;
int front = v.front();//第一个元素
int back = v.back();//最后一个元素
//重载[]操作符
for(int i = 0; i < v.size(); i++)
{
    
	cout << v[i] << endl;
}
//at成员函数
for(int i = 0; i < v.size(); i++)
{
    
	cout << v.at(i) << endl;
}
//[]和at区别：
//越界时，[]会崩溃；at会抛异常out_of_range

4. 删除

//删除
v.erase(v.begin()+2);//删除begin+2位置的元素
v.erase(v.begin()+3, v.end());//删除从begin+3位置到end之间的元素
v.pop_back();//删除最后一个元素
v.clear();//清空

5. 大小

vector<int> v;
int size = v.size();//目前已有的元素个数
int capacity = v.capacity();//可以容纳的元素个数
int ret = v.empty();//容器是否为空


//resize 改变当前使用的容器的大小
//如果比当前容量大，则填充默认值
//否则删除多余的元素
vector<int> v;
v.resize(10);//默认10个0
v.resize(2);//删除后面的8个0
//reserve 改变当前vecotr所分配空间的大小
v.reserve(10);//申请了容量为10的大小的空间
//区别：
//1、
//resize的空间中存在对象，可以直接访问
//reserve的不存在对象，在push_back/insert之前不能访问
//2、
//resize改变size和capacity
//reserve只改变capacity
int vv1, vv2;
int size, capacity;
vv1.resize(20);
size = vv1.size();//20
capacity = vv1.capacity();//20
vv2.reserve(20);
size = vv2.size();//0
capacity = vv2.capacity();//20

6. 巧用swap压缩vector空间
   当数据增长时，size和capacity都会跟着增长，但是当减少元素时会改变size的大小，却不会改变capacity的大小。

//压缩capacity
vector<int> (v).swap(v);

3.3、deque（双端队列）

3.3.1、deque的底层结构

deque是一个双端数组，即本身是一个数组，而且可以从数组头部和尾部进行插入和删除，效率较高，如果从中间位置插入，也会引起大量数据的移动，效率较低。

与vector的不同之处：

1. deque允许常数时间内在队头和队尾进行添加和删除元素
2. deque没有capacity的概念，因为它是动态的分段的连续空间组合而成的，随时可以增加一段新的空间并链接起来。换句话说，像vector那样“因旧空间不足而重新申请一段更大的控件，然后再复制元素，释放旧空间”这样的情况不会发生在deque上，也因此deque没有必要提供所谓的空间保留功能。

3.3.2、deque的使用

1. 初始化、赋值

//1、
deque<int> d1;
deque<int> d2(d1.begin(), d1.end());
deque<int> d3(10,3);//10个3初始化
deque<int> d4(d2);//拷贝构造
//2、
deque<int> d;
d.assign(d2.begin(), d2.end());
d.assign(10, 3);//10个3赋值
d = d2;//=运算符
d.swap(d2);//与d2的元素交换

2. 大小操作

deque<int> d;
int size = d.size();
int ret = d.empty();//是否为空
//用法与vector的resize相同
d.resize(10);//10个默认元素指定deque的大小
d.resize(10, 3);//10个3指定deque的大小

3. 插入、删除

deque<int> d;
d.push_back(1);//尾部添加
d.push_front(2);//头部添加
d.insert(d.begin(),2);//开始位置增加一个元素
d.insert(d.begin(),5,3);//开始位置增加5个相同的元素3
d.pop_back();//删除最后一个元素
d.pop_front();//删除第一个元素

4. 存取

//存取元素
deque<int> d;
int front = d.front();//第一个元素
int back = d.back();//最后一个元素
//重载[]操作符
for(int i = 0; i < d.size(); i++)
{
    
	cout << d[i] << endl;
}
//at成员函数
for(int i = 0; i < d.size(); i++)
{
    
	cout << d.at(i) << endl;
}
//[]和at区别：
//越界时，[]会崩溃；at会抛异常out_of_range

3.4、list（列表）

3.4.1、list的底层结构

list的底层结构是一个双向链表，既然是链表，那么在任意位置插入和删除效率很高，遍历效率很差。同时，由于需要保存前驱和后继节点的关系，相较于数组而言，需要额外的空间。

3.4.2、list的使用

1. 初始化

list<int> list1;//默认构造
list<int> list2(list1.begin(), list1.end());//以list1的begin到end初始化
list<int> list3(10, 3);//10个3初始化
list<int> list4(list2);//拷贝构造

2. 赋值

list<int> list1;
list<int> list2;
list2.assign(list1.begin(), list1.end());
list2.assign(10, 3);//10个3赋值
list2 = list1;//重载=操作·操作符
list2.swap(list1);//两个list内的元素交换

3. 插入、存取、删除

//插入
list<int> lisT;
lisT.push_back(1);//在尾部插入元素
lisT.push_front(2);//在头部插入元素
lisT.insert(3,5);//在位置3插入元素5
//存取
int front = lisT.front();//头部第一个元素
int back = lisT.back();//尾部第一个元素 
//删除
lisT.pop_back();//删除尾部的第一个元素
lisT.pop_front();//删除头部的第一个元素
lisT.erase(3);//删除位置3的元素
lisT.erase(2,4);//删除位置2到4之间的元素
lisT.remove(5);//删除list中所有的5

4. 大小操作

list<int> lisT;
int size = lisT.size();//元素个数
int ret = lisT.empty();//是否为空
lisT.resize(10);//重置大小为10
//打印所有的元素
for(list<int>::iterator it = lisT.begin(); it < lisT.end(); it++)
{
    
	cout << *it << " " << endl;
}

5. 翻转与排序

list<int> lisT;
lisT.sort();//排序。成员函数，不是算法。默认升序
lisT.reverse();//翻转（逆序）

//如何使list降序排序？
//使用回调函数
bool MyCompare(int v1, int v2)
{
    
	return v1 > v2; 
}
lisT.sort(MyCompare);

6. 算法中sort和list中的成员函数sort的区别？
   -支持随机存取迭代器的（连续存储空间）vector、deque(双向存取vector)使用STL的sort函数；
   不支持随机存取迭代器的（链式非连续存储空间）list(双向链表)、slist(单向链表forward_list)，不能使用STL的sort函数，因此需要在类中定义sort()成员函数。

3.5、stack（栈）

3.5.1、stack的底层结构

栈是一种很重要的数据结构，具有“先进后出”的规则，只能在一端进行插入和删除。因为这个规则，栈没有提供迭代器，不能进行元素的遍历和随机访问。如果想要取得最底层的元素，需要从栈顶元素开始依次弹出。

3.5.2、stack的使用

1. 初始化、赋值

//初始化
stack<int> s1;//默认构造
stack<int> s2(s1);//拷贝构造
//赋值
stack<int> s3;
s3 = s2;//重载等号运算符

2. 插入、删除

stack<int> s;
s.push(1);//压栈（进栈）
s.push(2);

//删除
int top = s.top();//取得栈顶元素
s.pop();//删除（弹出）栈顶元素

3. 大小操作

stack<int> s;
int size = s.size();//栈内元素的个数
int ret = s.empty();//栈是否为空
//打印栈内所有的元素
while(!s.empty())
{
    
	cout << s.top() << " " << endl;
	s.top();
}

3.6、queue（队列）

3.6.1、queue的底层结构

queue的规则是“先进先出”，在一端（队尾）进行插入，在另一端（队头）进行删除。队列同样不提供迭代器，不支持元素的遍历和随机访问。

3.6.2、queue的使用

1. 初始化、赋值

queue<int> q1;//默认构造
queue<int> q2(q1);//拷贝构造

queue<int> q3;
q3 = q2;//重载=运算符

2. 插入、删除

queue<int> q;
q.push(1);
q.push(2);//队尾插入元素
int front = q.front();//返回队头的第一个元素
int back = q.back();//返回队尾的第一个元素
q.pop();//删除队头的第一个元素

3. 大小操作

queue<int> q;
int size = q.size();//队列元素的个数
int ret = q.empty();//队列是否为空
//打印队列内所有的元素
while(!q.empty())
{
    
	cout << q.front() << " " << endl;
	q.pop();
}

3.7、set/mulitset（集合/多重集合）

3.7.1、set/mulitset的底层结构

set/mulitset的特性是所有元素会根据元素的值进行自动排序，其底层结构是红黑树（RB-tree）。set不允许两个元素有相同的值。不能通过set的迭代器去修改set元素，因为这样操作会打破原有的顺序。multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是一种高效的平衡二叉树，即红黑树（Red-Black Tree）。

3.7.2、set/mulitset的使用

1. 初始化、赋值

set<int> s;//默认构造
mulitset<int> ms;//默认构造
set<int> s2(s);//拷贝构造

set<int> s3;
s3 = s2;//重载=运算符

s3.swap(s1);//交换元素

2. 插入、删除

set<int> s;
s.insert(1);
s.insert(2);

s.erase(2);//删除set中值为2的元素
s.erase(2,4);//删除位置2到4之间的元素
s.erase(s.begin());//删除第一个元素

s.clear();//清空所有元素

3. 查找

set<int> s;
//查找，若找到就返回该元素的迭代器，否则返回s.end()
set<int>::iterator ret = s.find(2);
//返回第一个大于等于2的迭代器
set<int>::iterator it1 = s.lower_bound(2);
//返回第一个大于2的迭代器
set<int>::iterator it2 = s.upper_bound(2);
//返回lower_bound和upper_bound的迭代器
pair<set<int>::iterator, set<int>::iterator> mypair = s.equal_range(2);
//通过mypair.first和mypair.second来访问pair中的两个迭代器

4. 利用仿函数更改set默认排序方式

//1、基本数据类型
class MyCompare
{
    
public:
	bool operator()(int v1, int v2)
	{
    
		return v1 > v2;
	}
};
set<int, MyCompare> s; //升序排序

//2、自定义数据类型
class Person
{
    
public:
	Person(int id, int age):id(id), age()age{
    }
public:
	int id;
	int age;	
};
class MyCompare02
{
    
public:
	bool operator()(Person p1, Person p2)
	{
    
		return p1.id > p2.id;
	}
};
set<Person, MyCompare02> s; //按照id升序排序自定义数据类型
Person p1(10,20), p2(30,40);
s.insert(p1);
s.insert(p2);
//！！！！！！！注意！！！！！！！！！！
Person p3(10,40);
s.find(p3);//可以查找到，查找的结果是p1的迭代器
//原因：由于person是根据id排序的，因此查找的时候也会跟id来找。
//

5. 大小操作

set<int> s;
int size = s.size();
int ret = s.empty();//是否为空
//打印所有元素
for(set<int>::iterator it = s.begin(); s < it.end(); it++)
{
    
	cout << *it << " " << endl;
}

3.8、map/mulitmap（映射/多重映射）

3.8.1、map/mulitmap的底层结构

C++中map提供的是一种键值对容器，里面的数据都是成对出现的,如下图：每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。
Map是STL的一个关联容器，它提供一对一（其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个可能称为该关键字的值）的数据 处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。相对于set区别，map具有键值和实值。map内部自建一颗红黑树，这颗树根据key对数据进行自动排序，所以在map内部所有的数据都是有序的。
map与multimap的不同之处在于，map的键值key不可重复，而multimap可以，也正是由于这种区别，map支持[ ]运算符，multimap不支持[ ]运算符。在用法上没什么区别。

3.8.2、map/mulitmap的使用

1. 初始化

map<int, int> m1;//默认构造
mulitmap<int, int> mm;//默认构造
map<int, int> m2(m1);//拷贝构造

map<int, int> m3;
m3 = m2;//重载=运算符

m3.swap(m1);//交换元素

2. 插入、删除

map<int, int> m;
//1、第一种方式
pair<map<int, int>::iterator, bool> ret = m.insert(pair<int, int>(10, 20));
//insert返回的是pair<iterator, bool>,可以根据第二个参数判断是否插入成功--ret.second
//2、第二种方式 
m.insert(make_pair(30, 40));
//3、第三种方式
m.insert(pair<int, int>::value_type(50, 60));
//4、第四三种方式
m[70] = 80;  

//！！！！！！注意！！！！！！
//前三种插入方式没有区别
//第四种插入方式
//如果key不存在，则会创建一个新的pair插入
//如果key存在，则会修改该key对应的实值

//如果通过[]去访问一个不存在的key，
//那么map会将这个key插入到map中，
//并且给对应的实值一个默认值

3. 利用仿函数实现自定义数据类型的排序

class MyKey()
{
    
public:
	MyKey(int index, int id):index(index),id(id){
    }
public:
	int index;
	int id;
};

class MyCompare()
{
    
public:
	bool operator()(MyKey key1, MyKey key2)
	{
    
		return key1.index > key2.index;
	}
};

map<MyKey, int, MyCompare> m;
m.insert(make_pair(MyKey(1,2),10));
m.insert(make_pair(MyKey(2,4),20));

4. 查找

map<int, int> m;
//根据键值查找，若找到就返回该元素的迭代器，否则返回m.end()
pair<map<int, int>::iterator,map<int, int>::iterator> ret = s.find(2);
//返回第一个大于等于2的迭代器
map<int, int>::iterator it1 = s.lower_bound(2);
//返回第一个大于2的迭代器
map<int, int>::iterator it2 = s.upper_bound(2);
//返回lower_bound和upper_bound的迭代器
pair<map<int, int>::iterator, map<int, int>::iterator> mypair = s.equal_range(2);

3.9、容器共性机制

容器深拷贝与浅拷贝

class Person()
{
    
public:
	Person(char* name, int age)
	{
    
		this->name = new char[strlen(name)+1];
		strcpy(this->name, name);
		this->age = age;
	}
	//需要添加拷贝构造函数和重载=操作符，否则会是浅拷贝，导致程序崩溃
	Person(const Person& p)
	{
    
		this->name = new char[strlen(p.name)+1];
		strcpy(this->name, p.name);
		this->age = p.age;
	}
	Person& operator=(const Person& p)
	{
    
		if(this->name != NULL)
		{
    
			delete[] this->name;
		}
		this->name = new char[strlen(p.name)+1];
		strcpy(this->name, p.name);
		this->age = p.age;
	}
	~Person()
	{
    
		if(this->name != NULL)
		{
    
			delete[] this->name;
		}
	}
public:
	char* name;
	int age;
};

Person p("aaa",20);
vector<Person> v;
v.push_back(p);

STL容器所提供的都是值寓意，而非引用寓意，也就是说当我们给容器中插入元素时，容器内不实现了拷贝动作，将要插入的元素拷贝一份再放入到容器中，而不是将原始原始直接放进容器中，也就是说我们所提供的元素必须能被拷贝。

• 除了queue和stack之外，每个容器都提供可返回迭代器的函数，运用迭代器就可以访问元素
• 通常STL不会抛出异常，需要使用者传入正确参数
• 每个容器都提供了一个默认构造函数和拷贝构造函数
• 大小相关的构造方法：1、size()返回容器内元素的个数；2、empty()判断容器是否为空

3.10、常用容器对比

	vector	deque	list	set	multiset	map	multimap
典型内存结构	单端数组	双端数组	双向链表	二叉树	二叉树	二叉树	二叉树
随机存取	是	是	否	否	否	对key而言是：是	否
元素搜素速度	慢	慢	非常慢	快	快	对key而言：快	对key而言：快
元素安插移除	尾部	头尾两端	任意位置	-	-	-	-

vector和deque的比较

• vector.at()比deque.at()效率高，比如vector.at(0)是固定的，deque的开始位置却是不固定的
• 由于deque内部结构是三段连续内存，因此如果有大量的释放操作，vector花的时间更少
• deque支持头部的插入和删除，这是deque的优点