STL标准库：

#include<iostream>：

• 输入输出流标准库（流：一个字符序列），其中std::cout、std::cin（是一个对象或者可看作操作符）。

• <<表示输出运算符；>>表示输入运算符。运算符重载，相当于一个函数（第一个参数：cin/cout对象；第二个参数：输入或输出）。

  定义的<<运算符，返回的是一个写入了给定值的cout对象： ostream &std::cout.operator<<()。

• std::endl;（模板函数名，相当于函数指针），作用：

  1. 输出换行符\n；
  2. 强制刷新缓冲区（输出缓冲区，相当于一段内存）。

• cout，本质上是给缓冲区输入内容。强制刷新输出缓冲区，并把内容输出到屏幕上，的三种方式：

  1. 缓冲区满了；
  2. 程序执行到了main中的return语句；
  3. 调用std::endl;。

#include<iomanip>：

• 保留三位有效数字：cout << setprecision(3) << ...;
• 保留小数点后，三位有效数字：cout << fixed << setprecision(3) << ...;
• 小数点后三位有效数字的科学计算：cout << scientific << setprecision(3) << ...;

#include<cstdlib>：

• 随机数发生器rand：

  rand()产生的随机数是相同的（伪随机数）：0~99：int num = rand() % 100;、0~1：int num = (rand() % 100) * 0.01;

• 初始化随机数发生器srand()：用来设置rand产生随机数时的随机数种子。

  格式：void srand(unsigned int seed);

  注意：若随机数种子相同，则每次产生的随机数相同。

• srand和rand一般要同时使用：srand用来初始化随机数种子；rand用来产生随机数。

#include<cmath>：

• exp(x)、pow(x, y)、sqrt(x)：x必须是实数，如果为整数，要使用x*1.0；
• fabs(x)：求绝对值；
• log(x) – In(x)、log10(x) – lg(x)；
• sin(x)、cos(x)，其中x表示弧度；

#include<tuple>：

类模板 std::tuple 是固定大小的异类值汇集，是 std::pair 的推广。

注：利用的是可变参数模板，借助“递归继承”实现参数包的展开。

利用可变参数模板，借助“递归继承”或“递归组合”实现参数包的展开：

#include <iostream>
using namespace std;namespace _nmsp1
{// 通过“递归继承”的方式，展开参数包template <typename... Values> class tuple {};template <>class tuple<>{public:tuple(){cout << "tuple<>::tuple()执行了，this = " << this << endl;}};template <typename Head, typename... Tail>class tuple<Head, Tail...> : private tuple<Tail...>{typedef tuple<Tail...> inherited;protected:Head m_head;public:tuple() {}tuple(Head val, Tail... valTail) : m_head(val), inherited(valTail...) {}auto head()->decltype(m_head){return m_head;}inherited& tail(){return *this;}};void test(){tuple<int, float, string> t(41, 6.3, "hello");// type(t) ==> _nmsp::tuple<int, float, string>tuple<int, float, string> t_1 = t;cout << t.head() << endl;                 // 41// type(t.tail()) ==> _nmsp::tuple<float, string>tuple<float, string> t_2 = t.tail();cout << t.tail().head() << endl;          // 6.3// type(t.tail().tail()) ==> _nmsp::tuple<string>tuple<string> t_3 = t.tail().tail();cout << t.tail().tail().head() << endl;   // "hello"}
} namespace _nmsp2
{// 通过“递归组合”的方式，展开参数包template <typename... Args> class tuple;template <>class tuple<>{public:tuple(){cout << "tuple对象的首地址：" << this << endl;}};template <typename Head, typename... Args>class tuple<Head, Args...>{typedef tuple<Args...> Composited;protected:Head m_head;Composited composition;public:tuple() {}tuple(Head val, Args... args) : m_head(val), composition(args...) { }Head head() { return m_head; }Composited& tail() { return composition; }};void test(){tuple<int, double, float, string> t(41, 5.44, 6.3f, "hello");// type(t) ==> _nmsp::tuple<int, double, float, string>tuple<int, double, float, string> t_1 = t;cout << t.head() << endl;                 // 41// type(t.tail()) ==> _nmsp::tuple<double, float, string>tuple<double, float, string> t_2 = t.tail();cout << t.tail().head() << endl;          // 5.33// type(t.tail().tail()) ==> _nmsp::tuple<float, string>tuple<float, string> t_3 = t.tail().tail();cout << t.tail().tail().head() << endl;   // 6.3// type(t.tail().tail().tail()) ==> _nmsp::tuple<string>tuple<string> t_4 = t.tail().tail().tail();cout << t.tail().tail().head() << endl;   // "hello"}
}int main()
{_nmsp1::test(); _nmsp2::test();return 0;
}

通过“tuple（元组：一堆各种类型数据的组合）和递归调用”，展开参数包：

#include <iostream>
#include <tuple>
using namespace std;/* 通过tuple和递归调用展开参数包 */
/* 
这种展开参数包的方式，需要写类的特化版本（有一定难度）
实现思路：计数器IDX从零开始计数，每处理一个参数，IDX+1，直到所有参数都处理完；最后，用一个模板偏特化作为递归调用的结束
*/// 1）泛化版本
template<int IDX, int MAX, typename ...T>
class myClassT3
{
public:static void mySFunc(const tuple<T...>& t){cout << get<IDX>(t) << (IDX + 1 == MAX ? "" : ", ");myClassT3<IDX + 1, MAX, T...>::mySFunc(t);}
};// 2）偏特化版本，用于结束递归调用
template<int MAX, typename ...T>
class myClassT3<MAX, MAX, T ...>       
{
public:static void mySFunc(const tuple<T...> &t){cout << "结束tuple元组的遍历" << endl;}
};// 3）可变参函数模板
template<typename ...T>
void myFuncT(const tuple<T...> &t)   
{myClassT3<0, sizeof...(T), T...>::mySFunc(t);
}int main()
{ tuple<float, int, int> mytuple(1.2f, 1, 2);// 调用可变函数模板，并用标准库中get<位置>(对象名)，获取元组参数包的元素cout << get<0>(mytuple) << endl;cout << get<1>(mytuple) << endl;cout << get<2>(mytuple) << endl;cout << "..................." << endl;// 通过tuple（元组：一堆各种类型数据的组合），调用可变函数模板-->类模板-->偏特化版本（结束调用的标志），进而展开参数包myFuncT(mytuple); return 0;
}

正序输出参数列表，用重载<<的方式实现：

#include <iostream>
#include <tuple>
using namespace std;namespace _nmsp
{/* 通过tuple和递归调用展开参数包 *//* 这种展开参数包的方式，需要写类的特化版本（有一定难度）实现思路：计数器IDX从零开始计数，每处理一个参数，IDX+1，直到所有参数都处理完；最后，用一个模板偏特化作为递归调用的结束。*/// 1）泛化版本template<int IDX, int MAX, typename ...T>class PRINT_TUPLE{public:static void mySFunc(ostream& os, const tuple<T...>& t){os << get<IDX>(t) << (IDX + 1 == MAX ? "" : ", ");PRINT_TUPLE<IDX + 1, MAX, T...>::mySFunc(os, t);}};// 2）偏特化版本，用于结束递归调用template<int MAX, typename ...T>class PRINT_TUPLE<MAX, MAX, T ...>       {public:static void mySFunc(ostream& os, const tuple<T...> &t){// 结束tuple元组的遍历}};// 3）可变参函数模板template<typename... T>ostream& operator<<(ostream& os, const tuple<T...> &t)   {os << "[";PRINT_TUPLE<0, sizeof...(T), T...>::mySFunc(os, t);os << "]";return os;} void PrintTuple(){tuple<float, int, int> mytuple(1.2f, 1, 2);cout << mytuple; }
}int main()
{ // 通过tuple（元组：一堆各种类型数据的组合）//，调用可变函数模板-->类模板-->偏特化版本（结束调用的标志），进而展开参数包_nmsp::PrintTuple();return 0;
}

#include<string>：

string是字符容器，内部维护了一个动态的字符数组。相比于普通的字符数组，string容器的优缺点如下：

• 优点：

  1）使用时，不需要考虑内存分配和释放的问题；

  2）动态管理内存，即可扩展；

  3）提供了大量的操作容器的API；

• 缺点：效率略有点低。

string类是std::basic_string类模板的一个具体化版本的别名。

using std::string = std::basic_string<char, std::char_traits<char>, std::allocator<char>>

c风格的字符串NBTS：null-terminated string，即以空字符\0结尾的字符串。string是以字节为最小存储单位的动态容器，用于存放字符串（不存放空字符’\0’），即用于存放数据的内存空间（缓冲区）。

#include <iostream>
#include <cstring>
using namespace std;int main()
{struct Girl{int age;char name[30];double weight;char* memo;   // 在结构体中占8字节用来存放指向的字符数组的地址// 如果memo改成string类型，用memset初始化整个结构体可能存在内存泄露的危险//因nullptr空指针区域，并不一定是0x00000所在的区域，而memset会将string类中的start_、end_、finish_三者置零} girl;cout << "struct Girl占用的字节数：" << sizeof(struct Girl) << endl;string buffer;  // 创建一个空的string容器buffer// 生成10个Girl结构体的信息，并存入buffer中for (int i = 0; i < 10; ++i){memset(&girl, 0, sizeof(struct Girl));girl.age = i + 1;sprintf(girl.name, "name%02d", i);girl.weight = 150 + i;girl.memo = (char*)"lililili";buffer.append((char*)&girl, sizeof(struct Girl));}cout << "buffer.capacity() = " << buffer.capacity() << endl;cout << "buffer.size() = " << buffer.size() << endl;for (int i = 0; i < 10; ++i){memset(&girl, 0, sizeof(struct Girl));memcpy(&girl, buffer.data() + i * sizeof(struct Girl), sizeof(struct Girl));// 等价于buffer.copy(&girl, sizeof(struct Girl), buffer.data() + i * sizeof(struct Girl));cout << girl.age << "," << girl.name << "," << girl.weight << "," << girl.memo << endl;}return 0;
}

注意：内存空间就是内存空间，只有不同类型的指针指向它时才有不同的解释。

#include <iostream>
#include <cstring>
using namespace std;int main()
{char items[8];   // 栈上分配8字节的内存空间// 该8字节的内存空间用于存放字符串strcpy(items, "hello");cout << items << endl;// 该8字节的内存空间用于存放整数int *a, *b;a = (int*)items;b = (int*)items + 4;*a = 1;*b = 2;cout << *((int*)items) << "," << *((int*)items + 4) << endl;// 该8字节的内存空间用于存放doubledouble* d = (double*)items;*d = 2.2;cout << *((double*)items) << endl;// 将8字节的内存空间用于存放结构体struct people{int age;char name[4];} *person;person = (struct people*)items;person->age = 20;strcpy(person->name, "yoyo");cout << ((struct people*)items)->age << "," << ((struct people*)items)->name << endl;// 不同类型的指针指向这块内存，将会给该段内存空间不同的解释int* items1 = (int*)malloc(8);double* items1 = (double*)malloc(8);char* items1 = (char*)malloc(8);return 0;
}

string内部的三个指针：

char* start_    // 动态分配内存块开始的地址
char* end_      // 动态分配内存块最后的地址
char* finish    // 已使用空间的最后的地址
// 有finish的存在故不需要'\0'作为结束标志

string中的七个构造函数，c++11新增了两个：

// 1. 默认构造函数：
string()                    // 创建一个长度为0的string对象，即
string str1;// 2. 转换函数：
string(const char* s)       // 将string对象初始化为s指向的NBTS
string str2 = "I love China!";    // 把等号右边的字符串内容拷贝到str2代表的一段内存中，不包括'\0'
// 等价于，string str2("I love China!");// 3. 拷贝构造函数：
string(const string& str)   // 将string对象初始化为str 
string str3 = str2;               // 将str2中的内容拷贝到str3代表的一段内存空间中
// 等价于，string str3(str2);// 4. 创建一个由n个字符组成的string对象
string(size_t n, char ch)
string str4(6, 'a');       // 把str4初始化为有num个字符a组成的字符串
// 缺点：会在系统内部创建临时对象，故会较低效率（不推荐）// 5. 将string对象初始化为s指向的NBTS的前n个字符，即使超过了NBTS结尾
string(const char* s, size_t n) 
string s4("hello world", 10);
string s4("hello world", 20) // 结尾会有一些乱码的东西，因为n超过了char*的结尾'\0'// 6. 将string对象初始化为s指向的NBTS的从pos位置开始的npos个字符
string(const char* s, size_t pos = 0, size_t = npos)：
string s4("hello world",  1, 5);// 7. 创建一个string对象初始化为指针[begin,end)所指的区间内的字符
template<class T> 
string(T begin, T end)  // c++11新增的两个构造函数：
// 8. 移动构造函数
string(string&& str) noexpect   // 将一个string对象初始化为string对象str，并可能修改str
// 9. 将string对象初始化为初始化列表init_list中的字符串
string(initializer_list<char> init_list)
string str = {'h', 'e', 'l', 'l', 'o' , ' ' , 'w', 'o', 'r', 'l', 'd'};

string对象上的操作：

// 判断字符串是否为空
empty()   // 返回布尔类型的值// 返回当前对象分配的存储空间能保存的字符数量
capacity() // 返回字节数，即字符串容器的大小
size()// 返回字符数量，代表该字符串的字符个数，即字符串长度
length()// 把容器中的实际大小置为len，如果len<实际大小则截断多出的部分，len>实际的大小则用字符c填充
resize(int len, char c = 0)char& operator[](int n)                // 可读可修改
const char& operator[](int n) const    // 只读
char& at(int n)                        // 可读可修改
const char& at(int n) const            // 可读
/*[]和at()的对比：1、str[n]（n是个整型值）：返回str的第n个字符（n代表位置，0~(size(n)-1)）2、at()函数提供范围检查，当越界时，会抛出out_of_range异常，但operator[]不提供范围检查
*/// 返回容器中动态数组的首地址
const char* c_str() const   // 返回的是一个指针常量const char*，也就是以\0结尾的
// 该函数的引入是为了兼容C语言（因为C语言中没有string类型），通过string对象的c_str()成员函数，把string对象转换为C语言中的字符串样式
const char* data() const // 把当前容器中的内容，从pos开始的n个字节拷贝到s中，返回实际拷贝的数目
int copy(char* s, int n, int pos = 0) const// 当前容器与str交换，如果数据量小则交换的是动态数组的内容，数据量大则直接交换动态数组的地址
void swap(string& str)
/*#include <iostream>
using namespace std;int main()
{string s1 = "...................................";string s2 = "......111111111111111111111........";cout << "before the swap：" << endl;cout << (void*)s1.data() << endl; cout << (void*)s2.data() << endl;s1.swap(s2);cout << "after the swap：" << endl;cout << (void*)s1.data() << endl; cout << (void*)s2.data() << endl; return 0;
}*/// 返回pos开始的n个字节组成的子容器
string substr(size_t pos = 0, size_t = npos) const// 字符串的连接：str1+str2，返回连接后的结果，会得到一个新的string对象
// 注意：两个字符串不能直接相加，必须在中间夹一个string对象
string str = "abc";
string str2 = "adc" + str + "def";// 字符串对象赋值
str2 = str1     // 用str2中的内容代替str1中的内容// 判断两个字符串是否相等（长度和字符全部相等） 
str1 == str2
// 判断两个字符串是否不等
str1 != str2

范围for语句，针对string的使用：

// auto：变量类型推断为char
for (auto c : str)
{cout << c;
}
cout << endl;string str = "I love China!";
// 因为c是引用，所以形参c的改变会影响实参str
for (auto &c : str)
{// toupper()函数，会将所有字符转换为大写的字符c = toupper(c);
}
cout << str << endl;

string结合了c++的新特性，更安全和方便；适合对性能要求不高的场景。

string的实现：

#include <iostream>
#include <cstring>
using namespace std;// static data members、data members
// 类中的静态变量，需要在类内声明、类外定义
// static function members、function members
// 1、类的每个非静态成员函数，第一个形参都隐含为this指针
// 2、类的静态成员函数，不会隐含this指针作为参数，故其只能处理静态成员变量
// 3、静态成员函数的调用方式：①通过对象调用、②通过“类名::静态成员函数名”调用
class String 
{
public:String(const char* cstr = 0);// 拷贝构造函数String(const String& str);// 拷贝赋值函数String& operator=(const String& str);~String();char* get_c_str() const { return this->m_data; } 
private:char* m_data;
};String::String(const char* cstr)
{if (cstr == 0){m_data = new char[1];m_data[0] = '\0';return;}m_data = new char[strlen(cstr) + 1];strcpy(m_data, cstr);return;
}String::String(const String& str)
{m_data = new char[strlen(str.m_data) + 1];strcpy(m_data, str.m_data);
}// 这里之所以要返回String&，是为了很好的适应，出现多个连续的赋值操作，如str1 = str2 = str3
String& String::operator=(const String& str)
{if (this == &str)  // 检测并避免自我赋值{return *this;}delete[] m_data;m_data = new char[strlen(str.m_data) + 1];strcpy(m_data, str.m_data);return *this;
}String::~String()
{delete[] m_data;	
}ostream& operator<<(ostream& out, const String& str)
{out << str.get_c_str();return out;
}int main()
{String* str = new String("hello");  // 调用String(const char* cstr = 0);cout << *str << endl;               // 调用ostream& operator<<(ostream& out, const String& str);cout << str->get_c_str() << endl; return 0;
}

STL（standard template library）标准模板库：

使用泛型编程的编码方式，所写的一套供我们非常方便使用的一套库。

算法与数据结构：

数据结构（栈（后进先出）、队列（先进先出）、数组、链表（每个节点都包含数据和下一个节点的地址）、散列表（哈希表）、树、图）：研究数据如何存、取。

STL基础认识：

• 学习阶段：使用、认识、良好使用、扩充C++标准库。
• c++中STL以的head files形式呈现，且都在namespaces "std"中，故一般要在.cpp写using namespace std。

c++设计标准库时，有意让标准容器间共享接口，来发挥模板多态的特性：

常见的构造函数：

ContainerType c(num);
ContainerType c(num, x);
ContainerType c(beg, end);

相关的方法：

int size = c.size()
c.resize(num) / c.resize(num, x)
bool flag = c.empty()
c.clear()

STL的六大组成部分：

容器Container（类模板），分为三大类：

1. 顺序容器（sequence container）：放进去在哪里，元素就排在哪里，比如：array数组、vector动态数组、deque双端队列、list双向链表、forward_list单向链表。
2. 关联容器（associative container）（用树（红黑树）或哈希表实现）：元素是 键/值对，特别适合查找，比如：set、multiset、map、multimap。
3. 无序容器（unordered container）（用哈希表实现）：只关心元素是否在容器中，比如：unordered_set、unordered_multiset、unordered_map、unordered_multimap。

容器之间的继承关系：

迭代器Iterator（遍历、访问或修改容器（除const_iterator）中的元素）（类模板）：

迭代器是访问容器中元素的通用方法，是一种对指针的抽象。

迭代器支持的操作：赋值=、解引用*（*迭代器名，就表示迭代器指向的元素）（通过非常量迭代器，还能修改其指向的元素）、比较==/!=、从左向右遍历++。

有些容器中迭代器是指针，有些容器中迭代器是模板类。

不是所有的容器都有迭代器：stack、queue、priority_queue等容器就不支持迭代器，遍历可以通过front()/top()/pop()搭配使用。

划分不同的迭代器：

目的：针对不同类型迭代器设计不同的算法，以便更好地解决“容器–算法”的依赖。

注：因存在继承关系，故父类迭代器的功能，子类也拥有。

正/反/常量迭代器：（vector容器的迭代器）

c++中，string、vector、deque、array等容器，能用[ ]访问，但更多的是通过迭代器访问。

正向迭代器iterator的begin()、end()操作：

vector<int> vctor = { . . . };
// 类型：vector<int>::iterator；迭代器：变量iter或者pos
vector<int>::iterator iter/pos;        // 定义迭代器
iter = vctor.begin();   // 迭代器指向容器中的第一个元素，相当于iter指向vctor[0]
iter = vctor.end();     // 迭代器指向容器中的一个不存在的元素（容器中最后一个元素的下一个位置）

• 容器名<元素类型>::iterator 迭代器名
• iterator begin()、iterator end()
• 正向迭代器，只能通过++遍历容器，且每次沿容器向右移动一个元素。
• 如果容器为空，则begin()、end()返回的迭代器相同。

反向迭代器reverse_iterator的rbegin()、rend()操作：

// 用反向迭代器，反向遍历容器中的元素
for (vector<int>::reverse_iterator riter = vctor.begin(); riter != vctor.end(); riter++)
{cout << *riter << endl;
}

• 容器名<元素类型>::reverse_iterator 迭代器名

• reverse_iterator rbegin()、reverse_iterator rend()

  rbegin()：返回的一个反向迭代器，指向容器的最后一个元素的位置。

  rend()：返回一个反向迭代器，指向容器的第一个元素的下一个位置。

• 用来反向遍历容器中的元素。

常量迭代器const_iteration的cbegin()、cend()操作：

vector<int> vctor = { . . . };
for (auto citer = vctor.cbegin(); citer = vctor.cend(); citer++)
{// *citer = 4;     // 报错，在操作常量迭代器的过程中，不能改变容器的中元素的值// cbegin()：返回的是常量迭代器cout << *citer << endl;
}

• 容器名<元素类型>::const_iterator 迭代器名

• const_iterator cbegin()、const_iterator cend()，返回首尾的常量迭代器（类似于常量指针）。

• 迭代器指向的元素值是不变的，但是迭代器可以不断指向下一个元素，即只能从该容器中读取元素不能改变元素值（类似于常量指针）。

• 如果容器中的变量是常量，则必须用常量迭代器遍历容器中的元素，否则会报错。

  vector<int> vctor = { . . . };
  vector<int>::const_iterator citer;  // 定义迭代器citer// 如果容器中的变量是常量，必须用常量迭代器遍历容器中的元素，否则会报错
  const vector<int> cvctor  = { . . . };
  vector<int>::const_iterator citer;  // 定义迭代器citer
  

迭代器运算符：

1. *iter：返回迭代器iter所指向的元素的引用（必须保证这个迭代器指向的是有效的容器元素）。

2. iter++、++iter：让迭代器指向容器的下一个元素；如果已经指向了end()，则不能再++。

3. iter--、--iter：让迭代器指向容器的上一个元素；如果已经指向了begin()，则不能再–。

4. iter1 != iter2、iter1 == iter2：判断两个元素是否相等，指向的同一个元素即是相等。

5. 引用结构体或类中的成员：

   // 如何引用结构体或类中的成员
   struct Student
   {int num;char name;
   }
   vector<Student> stuVctor;
   Student myStu;
   myStu.num = 100;
   stuVctor.push_back(myStu);vector<Student>::iterator iter;
   iter = stuVctor.begin()
   cout << (*iter).num << endl; 
   // 等价于cout << iter->num << endl;
   

6. 迭代器失效：

   灾难程序1：

   vector<int> vctor = { . . . };
   vector<int>::iterator beg = vctor.begin();
   auto end = vctor.end();
   while(beg != end)
   {vctor.insert(beg, val);break;    // 最明智的防止迭代器失效的方法++beg;
   }beg = vctor.begin();
   end = vctor.end();
   while(beg != end)
   {cout << *beg << endl;++beg;
   }
   

   灾难程序2：

   vector<int> vctor = { . . . };
   vector<int>::iterator beg = vctor.begin();
   auto end = vctor.end();
   while(beg != end)
   {beg = vctor.erase(beg);
   }// 等价于上述函数
   while(!vctor.empty())
   {auto beg  = vctor.begin();  vctor.erase(beg);         // erase()函数，移除iter位置上的元素，返回下一个元素位置
   }
   

   resize()、reverse()、assign()、push_back()、pop_back()、insert()、erase()等函数，都会引起vector容器的动态数组发生变化，故可能导致vector的迭代器失效。

基于能够进行的运算类型，将迭代器分类（依据的是 迭代器的移动特性 和 能够做的操作）（每个分类都对应一个struct）：

所有迭代器都支持“*解引用运算符*”和“自增运算符++”。不同的容器的迭代器不同，实现难度也不同。

按顺序逐层进行继承，其中输入型迭代器是最底层父类。

输出型迭代器（output iterator）：

• 向前写入，提供者ostream、inserter，仅支持单次写入。
• *iter = val，将val写入该迭代器指向的位置。
• ++iter：向前步进，返回新的位置；iter++ ：向前步进，返回旧的位置。

输入型迭代器（input iterator）：

• 向前读取一次，提供者istream，支持*、++、==、!=、单次读取、->。
• *iter （iter->member）：读取元素。
• ++iter：向前步进，返回新的位置；iter++：向前步进，返回旧的位置。
• iter1 == / != iter2：用来判断两个迭代器是否相等。

前向迭代器（forward iterator）：

• 向前读取，提供者forward list、unordered_containers。
• 继承了直接父类input iterator的所有功能。
• 在input iterator的基础上，支持重复访问及读写、赋值=。

双向迭代器（bidirectional iterator）：

• 向前和向后读取，提供者list、set、mulitset、map、multimap。
• 继承了直接父类forward iterator的所有功能。
• 在forward iterator的基础上，支持自减运算符–（–iter（步退并返回新的位置）；iter–（步退并返回旧的位置））。

随机访问迭代器（random_access iterator）：

• 以随机的方式读取，提供者array、vector、deque、string。与普通的指针功能相同。

• 继承了直接父类bidirectional iterator的所有功能。

• 在birdirectional iterator的基础上，支持[]、+、+=、-、-=、>、<、<=、>=运算符（与普通指针功能相同）：

  iter[n]       // 访问索位置为n的元素
  iter += n      // 前进n个元素（n为负，则回退）
  iter -= n      // 回退n个元素（n为负，则前进）
  iter + n     // 返回iter之后的第n个元素
  iter - n     // 返回iter之前的第n个元素
  iter1 - iter2  // 返回iter1与iter2之间的距离
  iter1 </>/<=/>= iter2   // 用来判断iter1与iter2之间的相对位置
  

#include<iterator>中，有迭代器的辅助函数，即用于操作迭代器的三个函数模板：

// 使迭代器 p 向后移动 n 个元素
advance(p, n)  // c++11中，next(iter, n=1) / prev(iter, n=1)，返回“iter+/-n”对应的迭代器// 计算两个迭代器之间的距离，即迭代器 p 经过多少次 ++ 操作后与迭代器 q 相等
distance(p, q)
// 注意：如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。// 用于交换两个迭代器 p、q 指向的值		 
iter_swap(p, q)

std::iterator_traits：

迭代器的iterator_category：

#include <iostream> 
#include <vector>
#include <list>
#include <iterator>
using namespace std; // 经常把实现细节，隐藏于细致的命名空间 
namespace implementation_details 
{template<class BDIter>void alg(BDIter, BDIter, std::bidirectional_iterator_tag){std::cout << "alg() called for bidirectional iterator\n";}template <class RAIter>void alg(RAIter, RAIter, std::random_access_iterator_tag){std::cout << "alg() called for random-access iterator\n";} 
}template< class Iter >
void alg(Iter first, Iter last)
{implementation_details::alg(first, last, typename std::iterator_traits<Iter>::iterator_category());// 这里的第三个参数是产生了的临时对象，同时也是一个类型名
}int main()
{vector<int> vctor{1,2,3}; alg(vctor.begin(), vctor.end());list<int> list_{1,2,3};alg(list_.begin(), list_.end());return 0;
}

迭代器的value_type、difference_type：

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;template<typename BirIter>
void m_reverse(BirIter first, BirIter last)
{typedef typename iterator_traits<BirIter>::difference_type diff_type;typedef typename iterator_traits<BirIter>::value_type value_type;diff_type n = std::distance(first, last);while (n > 0){value_type tmp = *first;*(first++) = *(--last); *last = tmp;n -= 2;}
}int main()
{vector<int> vctor{1,2,3,4,5};m_reverse(vctor.begin(), vctor.end()); for_each(vctor.begin(), vctor.end(), [](int val) { cout << val << ", "; }); cout << endl;list<int> m_list{1,2,3,4,5,6};m_reverse(m_list.begin(), m_list.end());for_each(vctor.begin(), vctor.end(), [](int val) { cout << val << ", "; }); cout << endl; return 0;
}

算法Algorithm（全局函数/全局函数模板，如sort、search、copy等）：

常见的算法概念：

仿函数/函数对象（是一个类）：

• 重载函数调用操作符的类，其对象常被称为函数对象/仿函数；
• 本质：重载了"()"操作符，使类对象可像函数那样调用；

谓词（可作为一个判断式）：

• 普通函数 或 重载operator，返回值是bool类型的函数对象；

• operator接受一个参数，则为一元谓词；接受两个参数则是二元谓词；

  // 一元谓词：
  struct GreaterThanFive
  {bool opeartor()(int num){return num > 5;}
  };
  find_if(vtr.begin(), vtr.end(), GreaterThanFive());// 二元谓词：
  struct MyCompare
  {// 降序bool opeartor()(int num1, int num2){return num1 > num2;}
  };
  sort(vtr.begin(), vtr.end(), MyCompare());
  

内建函数对象：

• 基本用法：

  // 这些仿函数产生的对象，用法与一般函数相同
  greater<int> gtInt;
  gtInt(1, 2);// 可产生无名的临时对象来履行函数功能
  sort(vtr.begin(), vtr.end(), greater<int>());
  

• #include<functional>内建函数对象：

  大致分为：算法类函数对象、关系运算类函数对象、逻辑运算类仿函数。

  

  注意：还有很多其他的函数对象。

函数对象适配器：

• 函数适配器bind1st（将参数绑定为函数对象的第一个参数）、bind2nd（将参数绑定为函数对象的第二个参数），会将将二元函数对象转为一元函数对象：

  class MyPrint : public binary_function<int, int, bool>
  {
  public:void operator()(int v1, int v2){cout << v1 << ", " << v2 << endl;}
  };for_each(vtr.begin(), vtr.end(), bind1st(MyPrint(), x));
  for_each(vtr.begin(), vtr.end(), bind2nd(MyPrint(), x));
  

• 取反适配器not1（对一元函数对象取反）、not2（对二元函数对象取反）：

  class GreaterThanFive : public unary_function<int, bool>
  {
  public:bool operator()(int v) const {return v > 5;}
  };find_if(vtr.begin(), vtr.end(), GreaterThanFive());
  find_if(vtr.begin(), vtr.end(), not1(GreaterThanFive()));
  find_if(vtr.begin(), vtr.end(), not1(bind2nd(greater<int>(), 5)));
  

• 函数指针适配器ptr_fun：

  void MyPrint(int v1, int v2)
  {cout << v1 + v2 << endl;
  }for_each(vtr.begin(), vtr.end(), bind2nd(ptr_fun(MyPrint), 5));
  

• 成员函数适配器mem_fun_ref或mem_fun：

  class Person
  {
  public:Person(string name, int age) : m_name(name), m_age(age){ }void showPerson(){cout << m_name << ", " << m_age << endl;} 
  };/* 利用 mem_fun_ref 将Person内部成员函数适配 */
  // 如果容器中存放的是对象实体，那么用mem_fun_ref
  vector<Person> vtr;
  for_each(vtr.begin(), vtr.end(), mem_fun_ref(&Person::showPerson));// 如果容器存放的是对象指针，那么用mem_fun
  vector<Person*> vtr;
  for_each(vtr.begin(), vtr.end(), mem_fun(&Person::showPerson));
  

STL中算法大致分为四类（包含于<algorithm><numeric><functional>中）：

• 非可变序列算法：指不直接修改其所操作的容器内容的算法。
• 可变序列算法：指可以修改它们所操作的容器内容的算法。
• 排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
• 数值算法：对容器内容进行数值计算。

最常用的算法：查找、排序和通用算法，排列组合算法、数值算法、集合算法等算法。泛型算法：

• 非变易算法Non-mutating Algorithms
• 变易算法Mutating Algorithms
• 排序Sorting
• 泛型数值算法Generalized Numeric Algorithms

*算法的前两个形参的类型：一般都是迭代器类型，表示容器中元素所在的区间（前闭后开）。

算法，是一种搭配迭代器使用的全局函数，与具体的容器没有关联，故只需根据迭代器来开发不同的算法。

for_each：

template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
{for (; first != last; ++first) {f(*first);}return f; // C++11 起隐式移动
}
// 注意：for_each的返回值为UnaryFunction这个函数模板参数。

/* for_each()函数的工作原理：perform function for each element [first, last) */
template<class InputInterator, class Function>
void for_each(InputInterator first, InputInterator last, Function f)
{for (; first != last; first++){f(*first);           // 是可调用对象}return f;    // （重点）返回的是Function类型
}/* 不断地迭代并将找到的每个元素传入函数func() */
auto f = for_each(vctor.begin(), vctor.end(), func)    // 其中，func是一个可调用对象（函数、lambda表达式、重载operator()类对象（仿函数），调用时传入的是类对象countevent或匿名对象CountEvent()）

void myfunc(int i)
{cout << i << endl;
}
void func()
{vector<int> intvctor = { 10, 20, 30, 40 };for_each(intvctor.begin(), intvctor.end(), myfunc);
}class CountEven
{
public:CountEven(int &count) : count_(count){cout << "调用了CountEven的有参构造函数" << endl;}CountEven(const CountEven &tempCountEven) : count_(tempCountEven.count_){cout << "调用了CountEven的拷贝构造函数" << endl;}void operator()(int val){cout << "调用了CountEven的重载()运算符" << endl;if (val % 2 == 0){++count_;}}
public:int &count_;   
};void classObj()
{std::vector<int> vctor = { 1, 2, 3, 4, 5, 6 };int even_count = 0;    // 记录std::vector<int>容器中的偶数的个数CountEven counteven(even_count);// 返回的func1是类对象auto func1 = for_each(vctor.begin(), vctor.end(), counteven);                     // 调用了有参构造函数和拷贝构造函数、六次重载()运算符、拷贝构造函数cout << func1.count_ << endl;   cout << "..................." << endl;/* 推荐使用：相比上述使用，减少了一次拷贝构造函数的调用！！！ */even_count = 0;auto func2 = for_each(vctor.begin(), vctor.end(), CountEven(even_count));         // 调用了有参构造函数、六次重载()运算符、拷贝构造函数cout << func2.count_ << endl;cout << "..................." << endl;for (vector<int>::iterator iter = vctor.begin(); iter != vctor.end(); iter++)    // 仅仅调用了六次重载()运算符{counteven.operator()(*iter);}cout << "..................." << endl;
}void lambdaExpress()
{even_count = 0;// lambda 表达式的价值在于，就地封装短小的“（功能）闭包”，可以极其方便地表达出我们希望执行的具体操作，并让上下文结合得更加紧密for_each(vctor.begin(), vctor.end(), [&even_count](int val)                      // 并没有调用类成员函数{if (val % 2 == 0){++even_count;}});cout << even_count << endl;  
}

find/find_if、count/count_if：

容器带/不带该两种成员函数：

• 不带：array、vector、list、deque、forward_list。

  注意：具体容器中不含有find函数时，统一可使用全局的find函数！！！

  // vector容器没有特定的find()函数
  void func1()
  {vector<int> intvctor = { 10, 20, 30, 40 };vector<int>::iterator iter = find(intvctor.begin(), intvctor.end(), 40);if (iter != intvctor.end()) {cout << "be found" << endl;} else {cout << "not found" << endl;}
  }
  

• 带：set/multi_set、map/multimap、unordered_set/unordered_multiset、unordered_map/unordered_multimap

find、find_if，本质是“遍历”进行查找：

// map容器中的find()函数
void func2()
{map<int, string> m_map;m_map.insert(std::make_pair(1, "s"));m_map.insert(std::make_pair(2, "ss"));auto iter = m_map.find(2);if (iter != m_map.end()) {cout << "be found" << endl;} else {cout << "not found" << endl;}
}// find_if()：要查找的东西，取决于该函数的第三个参数
void func3()
{map<int, string> m_map;m_map.insert(std::make_pair(1, "s"));m_map.insert(std::make_pair(2, "ss"));// lambda表达式也是可调用对象，且不“引用或者值传入任何外部变量”auto result = find_if(m_map.begin(), m_map.end(), [](pair<int, string> tmp_pair) {if (tmp_pair.first == 2){return true;}return false;});if (result != m_map.end()) {cout << "be found" << endl;cout << result->first << "\t" << result->second << endl;} else {cout << "not found" << endl;} 
}

count、count_if

#include<iostream>
#include<numeric>
#include<algorithm>
using namespace std;int main()
{int arr1[] = { 1, 2, 3, 4, 5 };int arr2[] = { 1, 2, 3, 4, 5 };int results[5];// transform(first1, last1, first2, out, func)的用法：transform(arr1, arr1 + 5, arr2, results, std::plus<int>());for_each(results, results + 5, [](int val) { std::cout << val << " "; });std::cout << endl;// count()函数的用法：int result_len = sizeof(results) / sizeof(results[0]);std::cout << count(results, results + result_len, 6) << endl;     // 统计results中，==6的元素个数// count_if()函数的用法：int counts = count_if(results, results + result_len, [](int val) { // 统计results中，4<=val<=8的元素个数if (val >= 4 && val <= 8) { return true;} return false;});std::cout << counts << endl;return 0;
}

transform：

版本一：

template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op)
{while (first1 != last1) {*d_first++ = unary_op(*first1++);}return d_first;
}

版本二：

template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op)
{while (first1 != last1) {*d_first++ = binary_op(*first1++, *first2++);}return d_first;
}

二分查找函数：

• std::lower_bound：用来查询不降序列中首个不小于给定值的元素。

• std::upper_bound：用来查询不降序列中首个严格大于给定值的元素。

• std::binary_search：用来查询不降序列中是否存在等价于给定值的元素。

  #include<iostream>
  #include<numeric>
  #include<algorithm>
  using namespace std;int main()
  {int arr1[] = { 1, 2, 3, 4, 5 };int arr2[] = { 1, 2, 3, 4, 5 };int results[5];// transform(first1, last1, first2, out, func)的用法：transform(arr1, arr1 + 5, arr2, results, std::plus<int>());for_each(results, results + 5, [](int val) { std::cout << val << " "; });std::cout << endl;// count()函数的用法：int result_len = sizeof(results) / sizeof(results[0]);std::cout << binary_search(results, results + result_len, 8) << endl;   // 二分查找results中等于8的元素个数
  }
  

• std::equal_range：查询不降序列中等价于给定值的元素范围。返回lower_bound和upper_bound的pair。

sort对区间[first,last)内元素排序：

bool myfunc(int i, int j)
{return i > j;   // 降序//return i < j;   // 升序
}
class A
{
public:bool operator()(int i, int j){return i < j;}
};
void func1()
{vector<int> intvctor = { 20, 10, 30, 40 };// 函数作为可调用对象sort(intvctor.begin(), intvctor.end(), myfunc);   // 匿名对象（仿函数）作为可调用对象sort(intvctor.begin(), intvctor.end(), A());        
}void func2()
{list<int> intlist = { 20, 10, 30, 40 };intlist.sort(myfunc);   // 函数作为可调用对象
}

• 容器带/不带该全局sort成员函数
  不带：通过自然遍历即可获取排序后的结果：set/multi_set、map/multimap、unordered_set/unordered_multiset、unordered_map/unordered_multimap

  带：list、forward_list（不能进行随机访问）、vector、deque、array

• 关联容器（红黑树）和无序容器（哈希表），会对容器中的元素进行自定义的排序，即只有sort()成员函数没有全局sort()成员函数。

• list/forward_list容器，没有全局的sort()函数，只有各自的sort()成员函数。

• 主要适用于vector，string、deque等容器也可以但没有必要。

• STL中的sort算法，
  1）数据量大的时候采用QuickSort，分段归并排序；

  2）一旦分段后数据量小于某个门槛，为避免QuickSort的递归调用带来的过大的额外负荷，就改用InsertSort；如果递归层数太深就改用HeapSort；

STL提供了很多处理容器的函数模板，它们的设计是相同的，特点如下：

1. 用迭代器表示要处理数据的区间（左开右闭）。

2. 接受一个可调用对象（又称函数符）（函数指针、仿函数：匿名对象/类对象/函数对象、lambda表达式），用于处理数据。

   • 生成器generator：不用参数就可以调用的可调用对象；

   • 一元函数unary function：用一个参数就可以调用的可调用对象；

   • 二元函数binary function：用两个参数就可以调用的可调用对象；

   • 改进的概念：

     1）一元谓词predicate：返回bool值的一元函数；

     2）二元谓词binary predicate：返回bool值的二元函数；

3. 返回迭代器放置处理数据的结果。

使用要领：

• 若容器中有成员函数则优先使用成员函数，没有则考虑用STL算法函数；
• 若打算使用某算法函数，则必须搞清楚它的原理，关注它的效率；

空间配置器Allocator（内存分配器）（类模板）：

分配器的使用：

allocator<int>是一个类模板，内部封装有allocate()成员函数，用来自定义的分配一段连续的内存空间；使用完后要调用deallocate()成员函数析构掉内存对象占用的空间。

allocator隐藏在其他组件中默默工作，且allocator的分析可以体现c++性能和资源管理上优化的思想。容器中自动填补的缺省的分配器std::allocator<int>，底层实现仍然是使用malloc（内存分配不是连续的），并没有采取内存池等技术。

STL库中的二级内存分配器，作用：

通过大量减少malloc的使用，节省了内存且提高了效率（类似于内存池的概念，因为每次malloc都会占用超出的内存用来管理申请的内存，从而会造成内存的浪费）。

详细参考本人写的内存池的文章。

自定义分配器：内存池相关（嵌入式指针）

内存池：

• 作用：提前预留一大块内存空间、提高分配效率和速度、减少内存碎片。

• 一个类的内存池简单实现（没有提到内存块释放的问题）：

  //#define NO_MEM_POOLclass mem_pool
  {
  public:mem_pool() {  }void* operator new(size_t size);void operator delete(void* ptrDelete); 
  private:static int m_sMallocCount; // malloc一次，则加一static int m_sNewCount;    // new一次，则加一static mem_pool* m_freeLink;       // 始终指向空闲内存块组成的链表的首地址static int m_sTrunkCount;   // 一次性分配多少倍的mem_pool的内存空间mem_pool* next;     // 用来指向下一个mem_pool内存块 
  };mem_pool* mem_pool::m_freeLink = nullptr;
  int mem_pool::m_sMallocCount = 0;
  int mem_pool::m_sNewCount = 0;
  int mem_pool::m_sTrunkCount = 10;
  

  void* operator new(size_t size)中的实现原理：

  

  void* mem_pool::operator new(size_t size)
  {
  #ifdef NO_MEM_POOL// 不考虑内存池分配时，代码如下：A* tmpA = (A*)malloc(size);return tmpA; 
  #endifmem_pool* tmpLink = nullptr;/* 表示此时内存池并没有可分配的空间，则重新申请 m_sTrunkCount * size（size==sizeof(mem_pool)） 的内存空间，并用链表将各个空间连接起来 */if (m_freeLink == nullptr)    {// 重新申请 m_sTrunkCount * size 的内存空间m_freeLink = reinterpret_cast<mem_pool*>(new char[m_sTrunkCount * size]);// 用链表将各个空间连接起来tmpLink = m_freeLink;for (; tmpLink != &m_freeLink[m_sTrunkCount - 1]; ++tmpLink){tmpLink->next = tmpLink + 1;}tmpLink->next = nullptr; ++m_sMallocCount;} /* 表示此时内存池有可分配的内存空间，则只需将m_freeLink中的首个内存空间分配出去，并调整tmpLink和m_freeLink的位置 */tmpLink = m_freeLink;   m_freeLink = tmpLink->next;  ++m_sNewCount;return tmpLink;
  } 
  

  void operator delete(void* pDelete)中的实现原理：

  

  void mem_pool::operator delete(void* pDelete)
  {
  #ifdef NO_MEM_POOL// 不考虑内存池分配时，代码如下：free(pDelete); return;
  #endif (static_cast<mem_pool*>(pDelete))->next = m_freeLink;m_freeLink = static_cast<mem_pool*>(pDelete);
  }
  

嵌入式指针Embedded Pointer：

嵌入式指针使用的前提条件：类对象的sizeof()不小于4bytes。

工作原理：当类对象对应的内存块空闲时，暂时借用类对象的前4bytes用来链住空闲的内存块。

一旦内存块被分配出去了，就不再需要这4bytes，即这4bytes可被正常使用。

内存池代码的改进：引入嵌入式指针

namespace _MemoryPool
{// 因内部使用了“嵌入式指针”，故要求类最少占用4bytesclass Allocator{public:void* alllocator(size_t size){EP* tmpLink = nullptr;/* 表示此时空闲链表为空，即没有可分配的空闲的内存块，故需要重新申请m_sTrunkCount个内存块并挂在m_freeLink后等待被分配 */if (m_freeLink == nullptr){// 重新申请m_sTrunkCount个内存块m_freeLink = (EP*)malloc(m_sTrunkCount * size);tmpLink = m_freeLink;// 并挂在m_freeLink后等待被分配for (int i = 0; i < m_sTrunkCount - 1; ++i){tmpLink->next = (EP*)((char*)tmpLink + size);    // 每个内存块的大小是size，且前4bytes暂时被嵌入式指针用来链接空闲内存块tmpLink = tmpLink->next;}tmpLink->next = nullptr;}/* 表示此时空闲链表中，有可分配的空闲的内存块，故只需从m_freeLink中分配并调整m_freeLink指向的位置即可 */tmpLink = m_freeLink;m_freeLink = tmpLink->next;return tmpLink;}void deallocator(void* pDelete){// 回收内存块时，只需将其重新挂到m_freeLink上即可，并调整m_freeLink指向的位置 */((EP*)pDelete)->next = m_freeLink;m_freeLink = ((EP*)pDelete)->next;}private:// 嵌入式指针，只能在类内使用，且该类对象必须大于4bytesstruct EP{EP* next;};int m_sTrunkCount = 10;     // 记录要申请的内存块的个数（每个内存块的大小为sizeof(allocator)）EP* m_freeLink = nullptr;   // 空闲内存块组成的链表的首地址};class A  // 因需要通过内存池Allocator来进行A类对象的内存分配，故要求类A不能小于4bytes{public:int m_i; int m_j;public:static Allocator alloc_;   // 声明静态成员变量alloc_void* operator new(size_t size){return alloc_.alllocator(size);}void operator delete(void* pDelete){alloc_.deallocator(pDelete);return;}};Allocator A::alloc_;          // 定义静态成员变量alloc_void test(){/* 这样通过内存池Allocator来分配30个A类对象，则会出现3个独立的连续内存空间（每个内存空间由10个内存块组成，故共30个元素） */A* arr[30];for (int i = 0; i < 30; ++i){arr[i] = new A();(*(arr + i))->m_i = i;(arr[i])->m_j = i + 1;printf("%p\n", arr[i]);}for (int i = 0; i < 30; ++i){delete arr[i];}}
}int main()
{_MemoryPool::test(); return 0;
}

仿函数Functor/函数对象（类模板）：

仿函数概念：

一般不会单独使用，主要用来和STL算法配合使用，用来实现一些功能。

template <typename T>
class PrintContainer
{ 
public:ostream& os;  // 此处必须是引用类型
public:PrintContainer(ostream& os_) : os(os_){ }void operator()(const int& t){ os << t << " "; }
};void test()
{vector<int> vctor = vector<int>({ 1,2,3,4,5 });for_each(vctor.begin(), vctor.end(), PrintContainer<int>(std::cout));
}

为什么要用仿函数而不普通的函数指针作为算法的行为参数？

• 函数对象（仿函数）可内联编译，性能好，但函数指针几乎不可能；
• 函数指针无法满足STL对抽象性的要求，无法与STL中其他组件搭配使用。

本质：

类重载了一个operator()，创建一个行为类似函数的对象。

应用举例：仿函数可作为模板实参用于定义对象的某种默认行为，

• 以某种顺序对元素进行排序的容器，其中的排序规则（仿函数）就是一个模板实参；
• 注意：同一种有序容器，以两种不同的顺序对元素进行排序，则它们进行 “赋值” 或 “==判断” 会导致错误。

不同的函数对象/仿函数：

函数：

#include<iostream>
#include<algorithm>
using namespace std;// 函数方式实现：
bool MySort(int a, int b)
{return a < b;
}void Display(int a)
{cout << a << " ";
}int main()
{int arr[] = { 4,3,2,1,7,6 };// 函数方式实现：sort(arr, arr + 5, MySort);for_each(arr, arr + 5, Display);return 0;
}

模板函数：

// 泛型编程（模板函数）：
template<typename T>
inline bool MySort(const T& a, const T& b)  // 使用内联函数，来利用空间换取时间
{return a < b;
}template<typename T>
inline void Display(const T& a)
{cout << a << " ";
}int main()
{int arr[] = { 4,3,2,1,7,6 };// 泛型编程（模板函数）：sort(arr, arr + 5, MySort<int>);for_each(arr, arr + 5, Display<int>);return 0;
}

函数对象（仿函数）：

// 仿函数：
class MySort
{
public:bool operator()(int a, int b){return a < b;}
};class Display
{
public:void operator()(int a){cout << a << " ";}
};int main()
{int arr[] = { 4,3,2,1,7,6 };// 函数对象（仿函数）：作为参数，又称匿名函数sort(arr, arr + 5, MySort());for_each(arr, arr + 5, Display());return 0;
}

模板类：

// 仿函数（模板）：
template<typename T>
struct MySort
{bool operator()(const T& a, const T& b) const{return a < b;}
};
template<typename T>
struct Display
{void operator()(const T& a) const{cout << a << " ";}
};int main()
{int arr[] = { 4,3,2,1,7,6 };// 仿函数（模板）：sort(arr, arr + 5, MySort<int>());for_each(arr, arr + 5, Display<int>());return 0;
}				

lambda表达式：

[传入的外部变量](形参列表)->返回值类型 { 函数体 
};		

#include<functional>标准库，包含有现成的函数对象：

// 四则运算：
plus<type>()        // param1 + param2
minus<type>()       // param1 - param2
multiplies<type>()  // param1 * param2
divides<type>()     // param1 / param2
modulus<type>()     // param1 % param2
negate<type>()      // -param// 判断是否相等
equal_to<type>()      // param1 == param2
not_equal_to<type>()  // param1 != param2// 比较大小
greater<type>()        // param1 > param2
less<type>()           // param1 < param2
greater_equal<type>()  // param1 >= param2
less_equal<type>()     // param1 <= param2// 逻辑运算
logical_and<type>()  // param1 && param2
logical_or<type>()   // param1 || param2
logical_not<type>()  // !param// 位操作
bit_and<type>()   // param1 & param2
bit_or<type>()    // param1 | param2				

适配器Adapter（转接头）（类模板）：

概念：

通过限制模型的功能以让它满足另一个模型的功能，相当于改变了接口，但实现不变。

三种适配器：

适配器都是通过“组合”的方式，而非继承的方式，获取其他类的方法并加以改造。

*容器适配器Container Adapters：

stack、queue的底层实现，都是deque（双端都能够进或出），即可以用deque对象直接初始化stack、queue对象：

• stack堆栈，只允许一个端口进或者出，即先进后出。通过头指针和尾指针，来实现元素的进出。
• queue队列，只允许两个端口分别进行进或者出。通过头指针（头指针不是必须的，可以用计数器来替代）和尾指针，来实现元素的进出。

priority_queue优先队列。

*仿函数适配器Functor Adapters：最经典的是绑定器bind（也存在bind1st、bind2nd、mem_fun、mem_fun_ref但已被std::bind替代）

目的：将无法匹配的仿函数 “套接” 成可以匹配的型别。

#include<iostream>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std;class A
{
public:bool operator()(int val){return 6 < val;}
};class Add
{
public:int operator()(const int& a, const int&b){return a + b;}
};void Print(int a)
{cout << a << ", ";
}void func()
{vector<int> intVector;intVector.push_back(10);intVector.push_back(5);intVector.push_back(11);intVector.push_back(6);for_each(intVector.begin(), intVector.end(), Print); cout << endl;/* count1、count2都是得出，intVector中比6大的元素个数 */// A作为可调对象，并调用了重载()函数int count1 = count_if(intVector.begin(), intVector.end(), A()); /* std::placeholders命名空间中定义了一系列所谓的占位符。占位符的目的是限制函数的参数。 */// ，其中placeholders::_1，表示将[intVector.begin(), intVector.end())中的参数，放到可调用对象中重载()的函数的第2个形参中，即第一个参数已经被占用 int count2 = count_if(intVector.begin(), intVector.end(), std::bind(less<int>(), 6, std::placeholders::_1));/* count3、count4都是得出，intVector中比6小的元素个数 */int count3 = count_if(intVector.begin(), intVector.end(), std::bind(less<int>(), std::placeholders::_1, 6));int count4 = count_if(intVector.begin(), intVector.end(), std::bind2nd(less<int>(), 6));cout << count1 << "," << count2 << "," << count3 << "," << count4 << endl;
}int main()
{func();return 0;
}

bind绑定函数functions

#include<iostream>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std;int divide_(const int& a, const int&b)
{return a / b;
}int main()
{// bind绑定函数auto result = std::bind(divide_, 10, 3);cout << result() << endl;auto resultUnaryFunc = std::bind(divide_, std::placeholders::_1, 3);cout << resultUnaryFunc(10) << endl;auto resultBinaryFunc_1 = std::bind(divide_, std::placeholders::_1, std::placeholders::_2);cout << resultBinaryFunc_1(10, 3) << endl;auto resultBinaryFunc_2 = std::bind(divide_, std::placeholders::_2, std::placeholders::_1);cout << resultBinaryFunc_2(10, 3) << endl;return 0;
}

bind绑定函数对象function objects

int count3 = count_if(intVector.begin(), intVector.end(), std::bind(less<int>(), std::placeholders::_1, 6));int count4 = count_if(intVector.begin(), intVector.end(), std::bind2nd(less<int>(), 6));// 这两个是相互等价的，即功能相同，都是找出intVector中小于6的元素个数

bind绑定成员变量member variables/成员函数member functions（必须是成员变量或成员函数的地址）

#include<iostream>
#include<functional>
#include<algorithm>
#include<vector>
using namespace std; struct Divide_1
{  double operator()(const double& a, const double&b){return a / b;}
};class Divide_2
{
public:double a, b;
public:Divide_2(double m_a, double m_b) : a(m_a), b(m_b) { }double my_divide(){return a / b;}
}; int main()
{// bind绑定匿名对象auto result = std::bind(Divide_1(), 10, 3);cout << result() << endl;auto resultUnaryFunc = std::bind(Divide_1(), std::placeholders::_1, 3);cout << resultUnaryFunc(10) << endl;auto resultBinaryFunc_1 = std::bind(Divide_1(), std::placeholders::_1, std::placeholders::_2);cout << resultBinaryFunc_1(10, 3) << endl;auto resultBinaryFunc_2 = std::bind(Divide_1(), std::placeholders::_2, std::placeholders::_1);cout << resultBinaryFunc_2(10, 3) << endl;cout << "......................" << endl;// bind绑定成员变量Divide_2 divide_obj{ 10, 3 };auto resultMemberVar_1 = std::bind(&Divide_2::a, divide_obj);cout << resultMemberVar_1() << endl;auto resultMemberVar_2 = std::bind(&Divide_2::b, std::placeholders::_1);cout << resultMemberVar_2(divide_obj) << endl;// bind绑定成员函数，成员函数隐含了一个参数thisauto resultMemberFunc = std::bind(&Divide_2::my_divide, std::placeholders::_1);cout << resultMemberFunc(divide_obj) << endl;return 0;
}

迭代器适配器Iterator Adapters：

正向迭代器，容器类名::iterator 迭代器名;
常量正向迭代器，容器类名::const_iterator 迭代器名;
常量反向迭代器，容器类名::const_reverse_iterator 迭代器名;
反向迭代器，容器类名::reverse_iterator 迭代器名;

inserter：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <set>int main()
{std::vector<int> d {100, 200, 300};std::vector<int> l {1, 2, 3, 4, 5};// 插入顺序容器是，插入点前进，因为每次std::copy(d.begin(), d.end(), std::inserter(l, std::next(l.begin())));for (int n : l){ std::cout << n << ' '; }std::cout << '\n';
}// 1 100 200 300 2 3 4 5

ostream_iterator：

istream_iterator：

STL容器的使用时机：

vector的使用场景：如软件历史操作记录的存储（经常要查看历史记录，但很少会去删除记录）。

deque的使用场景：如排队购票系统（支持头端的快速移除，尾端的快速添加）。

vector和deque比较：

• vector.at()和deque.at()效率高，如vector.at(0)是固定位置，但deque位置不固定。
• 如果大量释放，vector花费的时间更少，这与两者内部实现有关。
• deque支持头部的快速插入和快速移除。

list的使用场景：如公交车乘客的存储（支持频繁的不确实位置元素的移除插入）。

set的使用场景：如对手机游戏的个人得分记录的存储（存储要求从高分到低分的顺序排列）。

map的使用场景：如按ID号存储十万个用户（快速要通过ID查找对应的用户）。

#include<array>：

一个顺序容器（本质是一个数组），即内存空间连续、大小固定（由申请的时大小决定），故无法动态的扩展或收缩，且只允许访问或者替换存储的元素。

初始化：

array<typename T, size_t N> m_array = { . . . };  // 默认零初始化

访问array容器中单个元素：

#include <iostream>
#include <array>
using namespace std;template<typename T>void tranverse2DArr(const T& arr){int m = arr.size(), n = arr[0].size();for (int i = 0; i < m; ++i){for (int j = 0; j < n; ++j){cout << arr[i][j] << ",";}cout << endl;}}int main()
{// 创建两行三列的二维数组，默认值是0  array<array<int, 3>, 2> arr = {(array<int, 3>){1,1,1}, (array<int, 3>){2,2,2}};   tranverse2DArr(arr);
}

成员函数：

// 容器名[] 的方式直接访问和使用容器中的元素（与 C++ 标准数组访问元素的方式相同）
// 注意：由于没有做任何边界检查，所以即便使用越界的索引值去访问或存储元素，也不会被检测到。
T& operator[](size_t n)
const T& operator[](size_t n) const// 能够有效地避免越界访问的情况
T& at(size_t n)     // 可以通过随机访问迭代器，访问元素。但常规的数组更方便，能用数组作为模板参数。// 通过调用该函数可以得到指向容器首个元素的指针（进而可以获得容器中的各个元素）
T* data() 
const T* data() const // 返回第一个/最后一个元素
T& front() 
const T& front() 
T& back() 
const T& back()// 能够获取到容器的第 n 个元素
get<n>   // 模板函数
// 注意：该模板函数中，参数的实参必须是一个在“编译时可以确定的常量表达式”，所以它不能是一个循环变量。// 给数组填充元素
void fill(const T& val)   

底层实现代码：

#include<vector>：

性质：

• Sequence Container
• Random_access iterator
• 随机访问：operator[]、at(x)、front()、back()
• 代表集合/动态数组的容器（可以将若干个“对象”放在其中，故称容器），且内存空间是连续的。
• 当vector容器的内存不够时，要重新申请一块更大的内存（原来的两倍大小）并将原有数据拷贝到新的内存空间同时删除原有的内存空间。解决方法：通过reserve()预留出一定的vector内存空间，避免反复拷贝导致的程序效率的下降。

vector类模板的声明：

template<class T, class Alloc=allocator<T>>  // allocator分配器，即使用那个分配器对象来管理内存。可选的模板参数，若省略则使用默认的allocator<T>，即用new和delete分配和释放内存。
class vector
{
private:T* start_;T* end_;T* finish_;...
}

定义vector类类型：

vector<int> vctor;
vector<string> vctor;
vector<Student> vctor;
vector<int*> vctor;
// 注意：不能在容器中装引用，引用是别名不是对象，故不能放在vector容器中。

构造函数：

vector()                               // 创建一个空的vector容器，即默认构造函数
explicit vector(const size_t n)        // 创建vector容器，元素个数为n（存放默认值，即零初始化后的值），容量和实际大小都是n
vector(const size_t n, const T& value) // 创建一个vector容器，元素个数为n，值均为value// 拷贝构造函数
vector(const vector<T>& v)                 // 举例：vector<string> myStr_(myStr);
// 赋值构造函数 
vector<T>& operator=(const vector<T>& v)   // 举例：vector<string> myStr_ = myStr;// 移动构造函数
vector(vector<T>&& v) // 用迭代器创建vector容器
vector(Iterator first, Iterator last) // c++11的标准，使用统一的初始化列表
vector(initializer_list<T> il)             // 举例：vector<string> myStr = { .  .  . };

注意：多种初始化的方式中，()一般表示对象中的元素数量这一概念、{}一般表示对象中的元素内容这一概念。

vector对象上的操作（大多数是，不知道vector容器的容量，需要动态的增加和减少）：

vector的很多操作，与string类似：

empty();       // 判断容器是否为空，返回的是布尔值
size();        // 返回元素的个数// vctor[n]：返回容器中第n个元素（n是整型值，n的范围是0~(size-1)）
T& operator[](size_t n)；                // 可读可修改
const T& operator[](size_t n) const;     // 只读
// at()函数提供范围检查，当越界时，会抛出out_of_range异常，但operator[]不提供范围检查
T& at(size_t n);                         // 可读可修改 
const T& at(size_t n) const;             // 只读 T& back() / T& front();     // 返回最后一个/首个元素的值T* data();                // 返回容器中动态数组的首地址，可修改其指向的内容
const T* data() const;    // 返回容器中动态数组的首地址void swap(vector<T>& v);    // 交换当前容器与v容器，即“交换动态数组的地址”
clear()    // 移除容器中的所有元素，即清空容器。但并不会释放vector所占用的内存空间，即vector的容量(capacity)保持不变
/* 可使用swap()，通过与空vector交换，来清空vector的内存 */ // 比较操作：
void operator==(const vector<T>& v) const;    
void operator!=(const vector<T>& v) const; 
vctor1 != vctor2
vctor1 == vctor2   // 判断vctor1和vctor2是否相等（相等，即元素个数和对应的元素都相等）// 插入和删除：
// 1、用于向vector容器的末尾追加一个元素
void push_back(const T& value);  
void emplace_back(...);          // 参数列表是可变参数，且可进行原地构造// 2、在pos迭代器所在的位置插入元素，并返回指向插入元素的迭代器
iterator insert(iterator pos, const T& value);  
iterator emplace(iterator pos, ...);            // 参数列表是可变参数，且可进行原地构造// 3、在pos位置插入一个区间的元素，并返回指向第一个插入元素的迭代器
iterator insert(iterator pos, iterator first, iterator last);  // 4、从容器尾部删除一个元素（尽可能不要在vector容器中间删除和添加元素，避免出现大量的拷贝动作）
void pop_back();                         // 5、删除指定位置的元素，并返回下一个有效的迭代器
iterator erase(iterator pos);                     // 6、删除一个区间的元素，并返回下一个有效的迭代器
iterator erase(iterator first, iterator last);    

使用swap()函数，清空vector容器并将其容量置为0：

// 可使用swap()，通过与空vector交换，来清空vector的内存 
std::vector<int> vec;   
std::vector<int>().swap(vec);
/* 1、swap()函数会用一个临时的空的vector和原来的vector进行交换，这样原来的vector就变为空了。2、它会释放原来vector占用的内存空间，也就是说，会使得vector的容量变为0。3、但要注意：swap()函数在执行过程中可能会抛出异常，而clear()函数不会。
*/

push_back和emplace_back的对比：

#include <iostream>
#include <string>
#include <vector>
using namespace std;class A
{
private:int m_age;string m_name;
public:A() { cout << "A()" << endl; }A(int age, string name) : m_age(age), m_name(name) { cout << "A(int age, string name)" << endl; };A(const A& a) : m_age(a.m_age), m_name(a.m_name) { cout << "A(const A& a)" << endl; }	
};int main()
{vector<A> vctor;/* 会先调用有参构造函数，再调用拷贝构造函数 *///A a(12,"lili");//vctor.push_back(a);  //vctor.emplace_back(a);/* 可以进行原地构造，即直接调用有参构造函数，即可 */vctor.emplace_back(12, "lili");   return 0;
}

capacity()：用来检查容器的容量的大小。

reserve()：定义vector容器对象后，给容器预留一定的空间，避免多次拷贝引起的程序效率的降低。

通过自定义分配器，验证reserve()的作用：

#include <cstddef>
#include <new>
#include <vector>
#include <iostream>
using namespace std;// 带调试输出的最小 C++11 分配器
template <class Tp>
struct NAlloc 
{typedef Tp value_type;NAlloc() = default;NAlloc(const NAlloc<value_type>&) {}value_type* allocate(size_t n){n *= sizeof(value_type);cout << "allocating " << n << " bytes\n";return static_cast<value_type*>(::operator new(n));}void deallocate(value_type* p, size_t n){cout << "deallocating " << n * sizeof(value_type) << " bytes\n";::operator delete(p);}
};
template <class T, class U>
bool operator==(const NAlloc<T>&, const NAlloc<U>&) { return true; }
template <class T, class U>
bool operator!=(const NAlloc<T>&, const NAlloc<U>&) { return false; }int main()
{int sz = 10;cout << "using reserve: " << endl;{vector<int, NAlloc<int>> v1;v1.reserve(sz);   // 为空容器v1预留sz字节的内存空间for(int n = 0; n < sz; ++n){ v1.push_back(n); }}cout << "\n" << "not using reserve: " << endl;{vector<int, NAlloc<int>> v1;for(int n = 0; n < sz; ++n){ v1.push_back(n); }}return 0;
}
/*
using reserve: 
allocating 40 bytes
deallocating 40 bytesnot using reserve: 
allocating 4 bytes
allocating 8 bytes
deallocating 4 bytes
allocating 16 bytes
deallocating 8 bytes
allocating 32 bytes
deallocating 16 bytes
allocating 64 bytes
deallocating 32 bytes
deallocating 64 bytes
*/

resize(size_t size, const T& value)：把容器中的实际大小置为size，如果size<实际大小则截断多出的部分，size>实际的大小则用value填充。

范围for语句：

vector<int> vctor = { . . . };
for (auto& vctor : vtr)
{vctor *= 2;       // 扩大一倍
}for (const auto &vctor : vtr)
{cout << vctor << endl;
}

• 迭代的范围可以是数组名、容器名、初始化列表或可迭代对象（支持begin()、end()、++、==）。
• 数组名传入函数后，会退化为指针，不能作为容器名。
• 如果容器中的元素是结构体和类，迭代器变量应该申明为引用，加const约束则为只读。
• for语句，函数体内，防止出现“迭代器失效”的问题。

vector容器存放指针类型，如何释放内存？

在使用new申请内存之后，要通过delete释放掉，防止内存泄漏；

struct conf
{char itemName[40];char itemContent[100];
};vector<conf*> createVector()
{conf *ptrConf1 = new conf;strcpy_s(ptrConf1->itemName, sizeof(ptrConf1->itemName), "ServerName");strcpy_s(ptrConf1->itemContent, sizeof(ptrConf1->itemContent), "1区");conf *ptrConf2 = new conf;strcpy_s(ptrConf2->itemName, sizeof(ptrConf2->itemName), "ServerID");strcpy_s(ptrConf2->itemContent, sizeof(ptrConf2->itemContent), "10000");vector<conf*> confList;confList.push_back(ptrConf1);confList.push_back(ptrConf2);return confList;
}vector<conf*> confList = createVector();
// 遍历容器中的元素并释放容器中的内存空间
for (vector<conf*>::iterator pos = confList.begin(); pos != confList.end(); pos++)
{delete(*pos);
}  
confList.clear();

#include<deque>：

特征：

Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。

双端队列（双向开口），最常用的就是作为stack、queue的底层容器。

Deque最大的工作：维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间、复制、释放的轮回，代价：

• 复杂的迭代器架构，Sequence Container、random_access iterator。

  

• Deque代码的实现，远比vector或list都多得多。

元素被进行了“分段连续保存”，物理结构：

deque容器，内部采用中央数组与数据缓冲区：

• 存储数据的空间是多段等长的连续空间（又称数据缓冲区，buffer）构成，且各段之间不连续。

• 为了管理这些连续空间的分段，deque容器用一个中控数组（map）存放着各个分段（buffer）的首地址。

  

  当访问至当前缓冲区的末尾时，需通过中控数组查找下一缓冲区的地址，再访问下一缓冲区的数据。

  注意：为了保证每次deque的头插和尾插的效率，中控数组中各段的地址，尽可能的放在其中间。

• 当deque容器push_front / push_back时，会先查看start / finish所在缓冲区是否还有剩余空间，当不存在剩余空间时，会申请额外的缓冲区并将该地址存放到中控数组（map）中，故不存在容量的概念。

  

特点：

1. 提高了“两端”插入和删除的效率，扩展空间时不需要拷贝以前的元素。
2. 在“中间”插入和删除元素的效率比vector更糟糕。
3. 随机访问的效率比vector略低。

#include<stack>（堆栈/栈）是容器适配器：

后进先出LIFO，只支持从栈顶放入元素、取出元素。

// stack的类模板的声明：
// 属于Container Adapter，需要基于某个Sequence container，底层容器可使用deque、list。
template<class T, class Container = std::deque<T>> 
class stack;
// 不能使用迭代器访问，采用push()/top()/pop()从栈顶插入、查找或者删除元素。

#include<queue>（队列）是容器适配器：

queue容器的逻辑结构是队列，物理结构可以是数组或链表，主要用于多线程之间的数据共享。

先进先出FIFO，支持从队首出，从队尾入。

// queue的类模板的声明：
// 属于Container Adapter，需要基于某个Sequence container，底层容器可使用deque、list。 
template<class T, class Container = std::deque<T>> 
class queue;
// 不能使用迭代器访问，采用push(const T& val)、emplace(...)效率更高/pop()/front()/back()从队尾插入、队首删除、获取队首/尾的元素。 

#include<priority_queue>是容器适配器：

优先队列相当于一个有权值的单向队列queue，在这个队列中，所有元素按照优先级排列。

// 容器container的选择：优先队列中的容器container=vector/deque，但都不能使用list作为容器（因为list是bidirectional iterator，而由于优先队列在pop时用到堆排序故要求random_access iterator，即不能用list作为其容器）
// 比较函数CompareFunctional的选择：根据不同的比较函数less<T>/greater<T>，可实现大顶堆/小顶堆的效果。根据比较函数获得的结果存入序列容器中，出队列时按照比较的结果出队列，即实现了优先级高的先出队列（自己设置的优先级规则）。默认是升序进行优先级的排列。
std::priority_queue<T, Container=std::vector<T>, CompareFunctional=std::less<T>> 	

比较函数CompareFunctional的实现：less/greater <–>大顶堆/小顶堆

“运算符重载”实现自定义数据类型的比较：

/* std::priority_queue<T, std::vector<T>,  std::less<T>> priQueueMaxFirst */// 自定义数据类型，Data类
class Data
{
public:Data(int i, int d) :id(i), data(d) {}~Data() {}int getId() { return id; }int getData() { return data; }friend bool operator < (const Data &a, const Data &b);      // 重载<运算符，友元函数可以访问类的私有成员
private:int id;int data;
};// 重载“<”运算符，仿函数less中需要使用
bool operator<(const Data &a, const Data &b) 
{return a.id < b.id;
}int main()
{// 该优先级队列维护一个大顶堆，因此最大的元素最先出队priority_queue<Data, vector<Data>, less<Data>> priQueMaxFirst;return 0;
}

“重写仿函数”（仿函数是通过重载()运算符来模拟函数操作的类）实现自定义数据类型的比较：

// 自定义数据类型，Data类
class Data
{
public:Data(int i, int d) :id(i), data(d) {}~Data() {}int getId() { return id; }int getData() { return data; }
private:int id;int data;
};// 重写仿函数，完成less的功能
struct cmp    
{bool operator() ( Data &a, Data &b) {return a.getId() < b.getId();}
};int main()
{// 该优先级队列维护一个大顶堆，因此最大的元素最先出队priority_queue<Data, vector<Data>, cmp> priQueMaxFirst;return 0;
}

“lambda表达式”实现比较函数：

#include <iostream>
#include <queue>
#include <vector>
#include <utility>
using namespace std;using my_pair_t = std::pair<size_t, bool>;using my_container_t = std::vector<my_pair_t>;int main()
{// 小顶堆：返回true则交换e1、e2，否则不交换auto my_comp = [](const my_pair_t& e1, const my_pair_t& e2) { return e1.first > e2.first; };std::priority_queue<my_pair_t, my_container_t, decltype(my_comp)> queue(my_comp);queue.push(std::make_pair(5, true));queue.push(std::make_pair(3, false));queue.push(std::make_pair(7, true));cout << boolalpha;while(!queue.empty()) {const auto& p = queue.top();cout << p.first << " " << p.second << "\n";queue.pop();}return 0;
}

使用规范：

• 无迭代器，即不能用迭代器进行访问/遍历。

• 优先级队列的基本操作与普通队列类似，不同的是每次获得队内的元素是优先级最高的元素（要从堆的顶部开始），故采用的操作是：push(x)插入元素、pop()删除优先级最高的元素、top()获取到优先级最高的元素后删除该元素。

  其余各种操作与queue相同。

#include<list>：

list类模板的声明：

template<class T, class Alloc = allocator<T>>
class list
{
private:iterator head;iterator tail;...
}

双向链表，不需要各个元素之间的内存连在一起；查找效率不突出，但在任意位置插入和删除非常迅速。

list的构造函数：

list()                           // 创建一个空的list容器
explicit list(const size_t n)         // 创建list容器，元素有n个
list(const size_t n, const T& value)  // 创建的list容器中，n个元素的值均为valuelist(const list<T>& v)                 // 拷贝构造函数
list<T>& operator=(const list<T>& v)   // 赋值构造函数
list(list<T>&& v)                      // 移动构造函数list(iterator first, iterator last)   // 用迭代器创建list容器list(initializer_list<T> il)          // 使用统一初始化列表

使用操作：

list中的迭代器，是双向迭代器bidirectional_iterator，只能进行++、——、==、!=等，不支持-=、+=等（属于随机访问迭代器）。

front()、back()
size()、empty()、clear()
void resize(size_t size, [const T& value])（不够则截取，超过则用value填补）
insert(iter, x)、push_back(x)、push_front(x)
erase(iter)、pop_back()、pop_front() // 交换、反转、排序、归并
void swap(list<T>& l)    // 交换当前链表和l，其中交换的是结点的地址
void reverse()           // 反转链表
/* #include<algorithm>中大部分排序算法不适合list双向链表 */
void sort()              // 链表排序
void sort(_Pr2_ _Pred)   // 对容器进行排序，排序方法由_Pred决定（二元函数）  
void merge(list<T>& l)   // 采用归并合并两个有序的list容器，且合并后仍然有序// 比较操作：
void operator==(const list<T>& v) const;    
void operator!=(const list<T>& v) const; // 插入删除操作：
// 1、vector动态数组容器中有的，list全有
// 2、list特有的：
void push_front(const T& value)   // 头插 
void emplace_front(...)    // 头插且原地构造
splice(iterator pos, const vector<T>& l)   // 将另一个链表连接到当前链表
splice(iterator pos, const vector<T>& l， iterator first, iterator last)  // 将另一个链表指定区间连接到当前链表
void remove(T& value)   // 删除所有等于value值的元素

vector和list的区别：

1. vector类似于数组，内存空间是连续的；list是双向链表，内存空间是不连续的（至少不要求内存空间是连续的）；
2. vector从中间或者开头插入元素效率较低；但list插入元素的效率高；
3. vector当内存不够时，会重新找一块内存，并将数据从原有的内存空间拷贝到新的内存空间，最后对原有内存对象做析构；list不存在内存不够的问题；
4. vector能够高效的进行随机存取，而list则需要从链表的一端开始逐个找。

简易list的实现：（内部通过环形链表维护）

namespace _nmsp
{template <class T>class list_node{public:list_node<T>* next;list_node<T>* prev;T data;explicit list_node(const T& val_) : next(nullptr), prev(nullptr), data(val_) {}explicit list_node(const T& val_, list_node<T>* prev_, list_node<T>* next_) : data(val_), prev(prev_), next(next_) {}~list_node(){next = nullptr; prev = nullptr;}};template <class T>class list_iterator{public:// explicit表示只能进行显示的类型转换explicit list_iterator() : node(nullptr) {}explicit list_iterator(list_node<T>* node_) : node(node_) {}T& operator*(){return node->data;}bool operator==(const list_iterator<T>& tmpIterator){return (node == tmpIterator.node);}bool operator!=(const list_iterator<T>& tmpIterator){return (node != tmpIterator.node);}list_iterator& operator++()  // 前置++{node = node->next;return *this;}list_iterator& operator++(int)   // 后置++{list_iterator<T> tmp_iterator(node);node = node->next;   // 或++(*this)，这回调用前置++return tmp_iterator;}list_node<T>* node;};template <class T>class List{public:typedef list_iterator<T> Iterator;typedef list_node<T> Node;public:List()    // 初始化的list双向链表，只有一个无用的节点{void* tmp_ptr = new char[sizeof(Node)];head = reinterpret_cast<Node*>(tmp_ptr);head->next = head; head->prev = head;}~List(){clear();  // 释放链表中，除head节点外的其他所有节点delete (void*)head;  head = nullptr;}void push_back(const T& val_){if (begin() == end()) { // 此时双向链表为空 Node* tmpNode = new Node(val_, head, head);head->next = tmpNode; head->prev = tmpNode; } else {                // 此时双向链表不为空 Node* tmpNode = new Node(val_, head->prev, head);head->prev->next = tmpNode;head->prev = tmpNode;} ++size_;} void push_front(const T& val_){if (begin() == end()) { // 此时双向链表为空 Node* tmpNode = new Node(val_, head, head);head->next = tmpNode; head->prev = tmpNode;} else {                // 此时双向链表不为空 Node* tmpNode = new Node(val_, head, head->next);head->next->prev = tmpNode;head->next = tmpNode;} ++size_;}bool insert(Iterator iter, const T& data){if (iter == end()){push_back(data);  return true;}// 在iter的位置插入节点Iterator insertPos;for (insertPos = begin(); insertPos != end(); ++insertPos){if (insertPos == iter){Node* tmpNode = iter.node->prev;Node* insertNode = new Node(data, iter.node->prev, iter.node);tmpNode->next = insertNode;iter.node->prev = insertNode;++size_;return true;}}return false;  // 插入失败}void pop_back(){if (size() == 1) {delete head->prev; head->prev = nullptr; head->prev = head;  head->next = head; } else if (size() > 1) {Node* tmpNode = head->prev;   // 待删除的节点tmpNode->prev->next = head;head->prev = tmpNode->prev;delete tmpNode; tmpNode = nullptr;} --size_;} void pop_front(){ if (size() == 1) {delete head->prev; head->prev = nullptr; head->prev = head; head->next = head; } else if (size() > 1) {Node* tmpNode = head->next;   // 待删除的节点tmpNode->next->prev = head;head->next = tmpNode->next;delete tmpNode; tmpNode = nullptr;}  --size_;}void clear(){if (size() == 0)   // 此时双向链表为空{return;}Node* tmpNode = head->next;while (tmpNode != head){Node* tmpNode_ = tmpNode->next;delete tmpNode;tmpNode = tmpNode_;}// 此时双向链表红，仅剩一个无用的head节点head->next = head; head->prev = head;size_ = 0;}bool empty() const { return (size == 0); }size_t size() const { return size_; }public: // 当begin() == end()时，表示此时链表为空Iterator begin() { return (Iterator)head->next; }Iterator end() { return (Iterator)head; }private:// head是用来连接双向链表的头和尾的无用节点，即双向链表在底层实现时，本质是“环形双向链表”Node* head;   size_t size_; // 记录链表中，元素的个数};
}int main()
{auto printList = [](_nmsp::List<int>& list) {for (_nmsp::List<int>::Iterator iter = list.begin(); iter != list.end(); ++iter){cout << *iter << ",";}cout << endl;};_nmsp::List<int> list;if (list.begin() == list.end()){cout << "list is empty" << endl;}list.push_back(2); list.push_back(1);list.push_front(3); list.push_front(4);cout << list.size() << endl; printList(list);list.pop_back(); list.pop_front();cout << list.size() << endl;printList(list);list.insert(list.begin(), 5);list.insert(list.end(), 1);printList(list);list.insert(++(list.begin()), 4);cout << list.size() << endl;printList(list);list.clear(); printList(list);cout << list.size() << endl; return 0;
}

#include<forward_list>：

单向链表，相较于list双向链表节省了内存空间，特别是元素多的时候。

• 只能往一个方向插入元素，即正向迭代器。
• 各种操作，与list双向链表相同。

实际的业务中，如果单链表能满足要求，则建议使用单链表而不是双链表。

pair键值对，类模板：

一般用于表示key/value数据，其实现是结构体。

pair结构体模板：

template<class T1, class T2>
struct pair
{T1 first;        // 键值对中的key键T2 second;       // 键值对中的value值pair();                                 // 默认构造函数pair(const T1& val1, const T2& val2);   // 有参构造函数pair(const pair<T1, T2>& pair_);        // 拷贝构造函数void swap(pair<T1, T2>& pair_);   // 交换两个pair
};

make_pair函数模板：

template<class T1, class T2>
pair<T1, T2> make_pair(const T1& first, const T2& second)
{return pair<T1, T2>(first, second);
}

#include<map>：

map容器封装了红黑树（元素由key、value组成，即pair键值对），不允许相同的key出现，而且会根据key进行自动排序（默认是升序）（非要key相等，则需要用multimap）。

map类模板的声明：

template<class K, class V, class cmp=less<K>, class Alloc=allocator<pair<const K, V>>>
class map
{...
};// K是pair.first即键的数据类型
// V是pair.second即值的数据类型
// cmp是排序方法，缺省的是按key升序
// Alloc分配器，缺省用new和deleteAssociative Container、bidirectional iterator

构造函数：

map()                             // 创建一个空的map容器 
map(const map<K,V>& m)            // 拷贝构造函数
map(map<K, V>&& m)                // 移动构造函数map(Iterator first, Iterator last)  // 用迭代器创建map容器map(initializer<pair<K, V>> il)     // 使用统一的初始化列表

使用操作：

// 插入元素：
insert(make_pair(element1,element2))
insert(pair<type1,type2>(element1,element2))
void insert(initializer_list<pair<K, V>> il)   // 用统一的初始化列表插入元素
// 在map中插入一个元素，返回已插入元素的迭代器和是否插入成功的结果
pair<iterator, bool> insert(const pair<K, V>& pair_)  
void insert(Iterator first, Iterator second)   // 用迭代器插入一个区间的元素
pair<iterator, bool> emplace(...)  // 将创建新键值对所需要的数据作为参数传入emplace中直接构造，效率更高map<int, Girl> map_;// 调用一次构造函数，两次拷贝构造函数map_.insert(pair<int, Girl>(8, Girl(12, "lili")));// 调用一次构造函数，两次拷贝构造函数map_.insert(make_pair<int, Girl>(8, Girl(12, "lili")));// 调用一次构造函数，两次拷贝构造函数map_.emplace(pair<int, Girl>(8, Girl(12, "lili")));// 调用一次构造函数，两次拷贝构造函数map_.emplace(make_pair<int, Girl>(8, Girl(12, "lili")));// 调用一次构造函数，一次拷贝构造函数map_.emplace(8, Girl(12, "lili")));
// []来说，key不存在则添加新的键值对，存在则读取/修改；at来说，key不存在则报错out_of_range
V& operator[](K key);   // map_[key] = value，注意：重载的[]运算符，如果不存在则会自动插入，返回值是引用。
V& at(K key);      // 遍历容器：
// 1、函数指针：
void Print(auto& info) 
{ cout << info.first << ": " << info.second << endl; 
}
for_each(iter.begin(), iter.end(), Print);   
// 2、lambda表达式：
for_each(iter.begin(), iter.end(), [](pair<T1, T2> pair_) { cout << pair_.first << "," << pair_.second << endl; 
}); 
// 3、迭代器：
for (auto iter = map_.begin(); iter != map_.end(); ++iter) 
{ cout << map_->first << ": " << map_->second << endl; 
}
// 4、范围for语句：
for(auto& pair_ : map_) 
{ cout << pair_.first << "," << pair_.second << endl;  
}// 当所查找的关键key出现时，它返回数据所在对象的位置；如果沒有，则iter = map_.end()
Iterator find(const K& key);
const_iterator find(const K& key) const;// 查找键出现的次数：
count(键值)   // 返回指定元素出现的次数（因为key值不会重复，所以只能是1 or 0）// 删除元素：
size_t erase(const K& key)       // 返回已删除的键值对的个数
Iterator erase(Iterator pos)     // 用迭代器删除元素，并返回下一个有效的迭代器

#include<multimap>：

• multimap和map的区别是：multimap允许关键字重复，而map不允许重复
• 各种操作与map相同

#include<set>、#include<multiset>：

• 底层是红黑树、Associative Container、bidirectional iterator
• set容器（只有一个元素值value），不允许相同的元素出现（非要出现，则需使用multiset）
• 各种操作与map相同

哈希表/散列表：

数组+链表：（哈希表的长度（桶bucket的个数），即数组的长度）

哈希函数：

// key % 不超过哈希表长的最大质数 
size_t hash(const T& key)    // 返回值必须小于hash表的表长
{ ... }  
// 装填因子 = 元素总数 / 表长，其值的越大，效率越低。
// 数据越散越好：避免某个桶中数据太多，降低了查询的速度。

无序容器中自定义类型的hash函数的定义和调用：

class Customer 
{
public: ...
};/* 形式一： */
struct CustomerHash_1
{ size_t operator()(const Customer& customer) const{...return ...;}
};
unordered_set<Customer, CustomerHash_1> uCustSet1;/* 形式二： */
size_t CustomerHash_2(const Customer& customer) 
{...return ...;
}
unordered_set<Customer, size_t(*)(const Customer&)> uCustSet2(20, CustomerHash_2);

万用的hash function：

// 各种底层是散列表的无序容器：
template <typename T, typename Hash=hash<T>,typename EqPred=equal_to<T>,typename Allocator=allocator<T>>
class unordered_set; template <typename T, typename Hash=hash<T>,typename EqPred=equal_to<T>,typename Allocator=allocator<T>>
class unordered_multiset;template <typename Key, typename T, typename Hash=hash<T>,typename EqPred=equal_to<T>,typename Allocator=allocator<pair<const Key, T>>>
class unordered_map;template <typename Key, typename T, typename Hash=hash<T>,typename EqPred=equal_to<T>,typename Allocator=allocator<pair<const Key, T>>>
class unordered_multimap;// 自定义类型的hash函数
namespace std   // 必须定义在std命名空间中
{template<>struct hash<SelfClass>{size_t  operator()(const SelfClass& selfClass) const{return ...;}}
}

举例：自定义类的hash函数实现，即hash code的求解。

#include <iostream>
#include <string>
#include <functional>
using namespace std;namespace _nmsp
{template <typename T>inline void _hash_combine(size_t& seed, const T& val){seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } template <typename T>inline void _hash_val(size_t& seed, const T& val){_hash_combine(seed, val); }template <typename T, typename... Args>void _hash_val(size_t& seed, const T& val, const Args&... args){_hash_combine(seed, val);_hash_val(seed, args...);}template <typename... Args>size_t _hash_val(const Args&... args){size_t seed = 0;_hash_val(seed, args...);return seed;} class Customer {friend class CustomerHash;public:Customer(string _fname, string _lname, int _age) : fname(_fname), lname(_lname), age(_age) {} private:string fname;string lname;int age; };class CustomerHash{public:size_t operator()(const Customer& c){return _hash_val(c.fname, c.lname, c.age);	}}; void test(){Customer customer("lili", "sun", 27);cout << CustomerHash()(customer) << endl; }
}int main()
{_nmsp::test();return 0;	
}

hash在后端开发中不同阶段的用处：

STL、算法:

STL：

• unordered_***：unordered_map、unordered_set
• 红黑树实现：map、set、multimap、multiset

算法：

设计类（大量数据的处理），利用hash的映射特性，实现拆分；

题目：最长不重复出现字符的子字符串。

// 用到哈希集合来存储出现过的字符
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_set<char> hashset;int result = 0;// 利用双指针left、right，分别指向找到的不含重复元素字符串的首尾int left = 0; int right = 0；for (; right < s.size(); right++) {// 当出现重复元素时，left指针不断向right指针靠近，同时不断地从hashset中剔除left指针指向的字符while (hashset.find(s[right]) != hashset.end()) {hashset.erase(s[left]);left++;}// 不重复时，则不断地给hashset中添加hashset.insert(s[right]);result = max(result, right - left + 1);}return result;}
};

数据库：

redis：通过hashtable，来组织存储的键值对，值中也有一个hash的数据结构。

mysql：关系型数据库，InnoDB存储引擎中自适应的hash索引：

• 通过等值查询触发
• 通过缓冲池的B+树页构造而来
• innodb存储引擎中，会自动根据访问频次、访问模式，来自动为某些页构建hash索引

hashtable

组成：hash()函数、数组。

hash：映射关系、强随机分布性、选择（siphash：解决了相似key的映射问题；murmurhash、city）

冲突：

• 负载因子：used_space / size

• 冲突原因

• 解决冲突：

  合理范围内：用链表将一个桶中的元素连接起来；红黑树、堆树、跳表也可以将一个桶中的元素连起来，能防止链表过长导致查找太慢。

  超出合理范围：当负载因子>1，扩容；当负载因子<0.1，缩容；rehash：即调整size后，需要重新将原hash中的数据进行重新映射。

反向代理中的负载均衡

性能优化利器 – 布隆过滤器

缓存横向扩展 – 分布式一致性hash

#include<unordered_map>：

容器封装了hash表，查找、插入和删除元素时，只需要几次比较key的值。

unordered_map类模板的声明：

template<class K, class V, class _Hasher=hash<K>, class _Keyeq=equal_to<K>, class _Alloc=allocator<pair<<const K, V>>>>
class unordered_map : public _Hash<_Umap_traits<K, V, _Uhash_compare<K, _Hasher, _Keyeq>, Alloc, false>>
// 参数的含义：
// 第一/二个模板参数：key（pair.first）、value（pair.second）
// 第三个参数_Hasher：哈希函数，默认值是std::hash<K>
// 第四个模板参数_Keyeq：比较函数，用于判断两个key是否相等，默认值是std::equal_to<K>
// 第五个参数Alloc：分配器，缺省用new和delete

构造函数：

// 定义std::unordered_map类模板的别名umap
template<class K, class V>
using umap = std::unordered_map<K, V>umap()                       // 创建一个空的umap容器
umap(size_t bucket)          // 创建一个空的umap容器，并指定桶的个数
umap(const umap<K, V>& m)       // 拷贝构造函数
umap(umap<K, V>&& m)            // 移动构造函数// 用迭代器创建umap容器
umap(Iterator first, Iterator last)                       
umap(Iterator first, Iterator last， size_t bucket_size)   // 指定桶的个数// 使用统一的初始化列表
umap(initializer_list<pair<K, V>> il)                       
umap(initializer_list<pair<K, V>> il, size_t bucket_size)   // 指定桶的个数

特性操作：

size_t size() const  // 返回容器中的元素个数
bool empty() const   // 判断容器是否为空
void clear()         // 清空容器// 返回第n个桶中第一个元素/最后一个元素尾后的迭代器
Iterator begin(size_t n)
Iterator end(size_t n) size_t bucket_count()    // 返回容器中桶的数量
void reserve(size_t n)   // 设置容器中至少有n个桶，要在创建容器后设置// “重新hash”的代价非常大，需要将全部已分配的数组和链表销毁，重新hash
void rehash(size_t n)    // 如果n大于当前容器的桶数，该方法将容器重新hash，小于则不起作用。size_t bucket_size(size_t n)  // 返回第n个桶中的元素个数，0 <= n < bucket_count()
size_t bucket(K& key)         // 返回键为key的元素对应的桶的编号float load_factor()            // 返回容器的负载因子，其值 = size() / bucket_count()
void max_load_factor(float z)  // 设置容器的最大的装填因子
float max_load_factor()        // 返回容器的“最大装填因子”，达到该值后，容器将扩容，缺省为1

#include <iostream>
#include <unordered_map>
using namespace std;template<class K, class V>
using umap = std::unordered_map<K, V>int main()
{umap<int, string> hashmap;cout << hashmap.bucket_count() << endl;hashmap.max_load_factor(5);hashmap.insert({{1,"a"},{2,"b"},{3,"c"},{4,"d"}});hashmap.insert({{11,"a"},{12,"b"},{13,"c"},{14,"d"}});hashmap.insert({{21,"a"},{22,"b"},{23,"c"},{24,"d"}});hashmap.insert({{31,"a"},{32,"b"},{33,"c"},{34,"d"}});hashmap.insert({{41,"a"},{42,"b"},{43,"c"},{44,"d"}});hashmap.insert({{51,"a"},{52,"b"},{53,"c"},{54,"d"}});hashmap.insert({{61,"a"},{62,"b"},{63,"c"},{64,"d"}});cout << hashmap.bucket_count() << endl;cout << "\ntranverse every bucket: " << endl;for (int i = 0; i < hashmap.bucket_count(); ++i){cout << "桶" << (i + 1) << " : ";for (auto iter = hashmap.begin(i); iter != hashmap.end(i); ++iter){cout << iter->first << ": " << iter->second << ", ";}cout << endl;} 	 cout << "\ntranverse total hashmap container: " << endl;for (auto iter = hashmap.begin(); iter != hashmap.end(); ++iter){cout << iter->first << ": " << iter->second << ", ";}cout << endl;return 0;
}

查找操作：

// 查找键值为key的键值对
Iterator find(const K& key)        // 可读可修改
const_Iterator find(const K& key)  // 只读// 统计键值对的个数
size_t count(const K& key) const

自定义的unordered_map，用链表法（这里用单链表）解决hash冲突的问题：

注意：重复元素key会被新的value覆盖，即<key,value>必须唯一；不重复则插入某个桶的单链表的头结点。

#include<unordered_set>、#include<unordered_multiset>、#include<unordered_multimap>：

底层是hash表。可通过增加篮子的数量，来避免某个篮子的元素太多，从而影响查找速度。

bucket_count()   // 查找容器中的篮子数量 
bucket_size(i)   // 第i个篮子中的元素个数 
find()           // 查找元素所在的位置

std::map和std::unordered_map对比：

std::map通常是由红黑树实现的，故操作复杂度是O(logn)。

std::unordered_map使用哈希/散列表hash实现，故操作复杂度是O(1)。

• 通过将key值用hash函数映射，到某个范围较小的空间，从而完成索引 — hash(key)。
• 如果要存储N条，一般应映射到容量大于N的hash表中。

• 合适的hash函数，应满足的性质：

  确定determinism：同一关键字总是被映射到同一地址

  快速efficiency：简单、计算复杂度低

  满射surjection：尽可能地覆盖整个散列空间

  均匀uniformity：关键码映射到散列表各位置的概率尽量接近，从而避免聚集clustering现象

• 对于字符串如何选取hash函数：通常采用“多项式”，将字符串中的每个字符都包含进去。

• hash冲突：当k1 != k2 且 h(k1) = h(k2)时，称这两个键产生了冲突。

  这种冲突是难以避免的。

  解决冲突是设计hash表的重要一环：

  法一：封闭散列/开放寻址。基本思路：事先为每个hash值约定一个试探链，如果当前hash值对应的桶被占用时，则沿着试探链找下一个位置，直到找到可以存放当前条目的空桶。

  法二：开放散列。当出现冲突时，通过链表，挂载到其后面，这样最终hash表中每个桶后会挂一个链表。

  缺点：每次新建指针较慢，结点的动态分配和回收需要消耗时间。通过公共溢出区来解决。

  

  法三：rehash。

boost库：

Boost库，可以与c++标准库完美共同工作，并且为其提供扩展功能。boost 更准确的说，并不是一个库，而是一个库集合。

Boost库大致分为20多类：字符串、文本处理库、容器库、算法库、函数对象、高阶编程库、综合类库、…

boost库的详细组成介绍。