STL模板库

一、模板

1、什么是模板

C++语言中提供一种自动生成代码的技术，这种技术可以让程序员在编程时不需要考虑数据类型，而专注思考业务逻辑和算法，程序员只需要编写好代码的整体框架，具体的数据类型由使用者提供，这就叫模板技术，也被称为泛型编程技术。

2、为什么使用模板

1、C、C++是一种静态编程语言，这种语言的特点是，需要把代码经历 预处理-> 编译-> 汇编-> 连接 -> 生成可执行文件 过程最后才能执行所编写好的代码，这种编程语言最大的优点就是执行速度快，缺点是在程序执行过程中只能按照预先设计好的路线执行，并且在程序执行过程中，数据的类型不能发生变化，这种特点就需要程序员预先把所有可能性都考虑清楚，所以C、C++的程序员一直为实现通用型的代码而努力（通用指针、回调函数、宏函数、函数重载、运算符重载）。

2、使用void类型的指针配合回调函数实现通用型代码（qsort排序函数为代表），该方法的缺点是既危险，实现难度大，使用麻烦。

3、使用宏函数实现通用型的代码，不会对数据进行检查，最重要的是没有返回值，还会造成冗余以及代码段增大。

4、借助函数重载，为各种数据类型的参数都实现一遍功能相同的代码，需要耗费大量的人力，并且会使代码段增大，但无法预料所有的数据类型，无法解决未知的数据类型。

5、基于以上原因，C++之父设计了模板技术，程序员只需要把模具制作好，然后调用者给模具提供原料（数据类型），然后生产出"产品"，也就是符合我们预期的代码，最终再调用该代码完成任务。

3、函数模板

定义函数模板：

template <typename T1,typename T2,...>
T3 函数名(T1 arg1,T2,arg2)
{T3 ret = arg1+arg2;return ret;
}

可以给未知的类型取任何名字，但约定俗成使用T。

函数模板的原理：

函数模板会经历两次编译：

1、编译器会检查模板的代码是否有语法错误，此时函数模板仅仅是生成代码的工具，并不会产生二进制指令。

2、使用模板，编译器会根据使用者提供的类型参数生成相关代码，并且会再次编译生成的代码，如果没有语法错误，就会生成二进制的指令，然后把二进制的指令存储在代码段。

函数模板的调用：

自动提供类型参数：

模板需要的类型参数，都可以根据函数的参数列表自动提取。

#include <iostream>
using namespace std;
​
template <typename T>
void show_arr(T arr[],int len)
{for(int i=0; i<len; i++){cout << arr[i] << " ";}   cout << endl;
}
int main(int argc,const char* argv[])
{double arr[9] = {0,1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8};show_arr(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}

练习1：使用模板技术，实现通用的排序函数，可使用任何排序算法。

template <typename T>
void mySort(T arr[],size_t len)
{for(size_t i=0; i<len-1; i++){size_t m = i;for(int j=i+1; j<len; j++){if(arr[j] < arr[m])m = j;}if(m != i)swap(arr[m],arr[i]);}
}

练习2：设计一个学生类，定义学生数组，使用模板排序算法对学生数组进行排序（以成绩为排序标准）。

class Student
{string name;char sex;short age;float score;
public:Student(const string& name="",char sex=0,short age=0,float score=0):name(name),sex(sex),age(age),score(score){} 
​bool operator<(const Student& that){return score < that.score;}
​friend ostream& operator<<(ostream& os,const Student& s){return os << s.name << " "<< s.sex << " "<< s.age << " "<< s.score;}
};

手动提供类型参数：

未知的类型没有出现参数列表，就需要调用者手动提供类型参数。

函数名<类型>(实参);

template <typename T>
T strToNumber(const string& str)
{T num;if(typeid(T) == typeid(int))sscanf(str.c_str(),"%d",&num);else if(typeid(T) == typeid(short))sscanf(str.c_str(),"%hd",&num);else if(typeid(T) == typeid(float))sscanf(str.c_str(),"%f",&num);else sscanf(str.c_str(),"%lf",&num);return num;
}
​
int main(void)
{string str = "12345";cout << strToNumber<int>(str) << endl;str = "12";cout << strToNumber<short>(str) << endl;string str = "3.14";cout << strToNumber<float>(str) << endl;
}

注意：需要手动提供的类型参数尽量放在最左边，这样使用者可以只提供部分类型即可。

默认形参：

template <typename T3=float,typename T2,typename T1>
T3 avg(T1 n1,T2 n2)
{if(typeid(T3) == typeid(float) || typeid(T3)== typeid(double))return n1/2.0+n2/2.0;elsereturn (n1+n2)/2;
}

给模板的类型参数，设置默认值，当使用者不提供类型参数时，使用默认类型，但该语法只有C++11标准才支持。

思考：字符串数组能不使用模板排序算法，如果不能该怎么办？

const char* arr[] = {"hehe1","hehe2","hehe3"};
mySort(arr,5);
​

模板的特化：

当有一些特殊类型，不能使用通用操作时，就需要为它提供一个特殊版本的函数(真正的函数），编译器会优先调用真正的函数，而不会再调用模板生成的函数，这就叫模板的特化。

注意：一般char* 类型都需要进行特化。

#include <iostream>
#include <string.h>
using namespace std;
template <typename T>
void bullue_sort(T arr[],int len)
{bool flag = true;for(int i=len-1; flag && i>0; i--){   flag = false;for(int j=0; j<i; j++){if(arr[j] > arr[j+1]){swap(arr[j],arr[j+1]);flag = true;}}}   cout << "sort：";for(int i=0; i<len; i++){   cout << arr[i] << " ";}   cout << endl;
}
​
void bullue_sort(const char* arr[],int len)
{bool flag = true;for(int i=len-1; flag && i>0; i--){   flag = false;for(int j=0; j<i; j++){if(0 < strcmp(arr[j],arr[j+1])){swap(arr[j],arr[j+1]);flag = true;}}}   cout << "sort：";for(int i=0; i<len; i++){   cout << arr[i] << " ";}   cout << endl;
}
​
int main(int argc,const char* argv[])
{int arr1[] = {1,3,5,7,9,2,4,6,8,10};bullue_sort(arr1,sizeof(arr1)/sizeof(arr1[0]));
​const char* arr2[] {"abc","cba","bba","aab","bab"};  bullue_sort(arr2,sizeof(arr2)/sizeof(arr2[0]));return 0;
}

练习1：通用的变量交换函数。

练习2：通用的求数组最大值、最小值函数。

4、类模板

什么是类模板：

使用到了未知的类型来设计一种类（模板类在使用时，必须需要提供类型参数）。

template <typedef M,typedef T,typedef R>
class Test
{M num;
public:Test(T t) {}R func(void){R ret;return ret;}
};

类模板的使用：

由于创建类对象时可以不提供参数（无参构造），所以必须手动提供类模板的类型参数。

类名<类型参数> 对象;

注意：在构造函数执行前，对象必须先创建出来（分配内存），所以必须先提供模板的类型参数，让模板类先完成实例化，然后再创建对象、调用构造，具体过程如下：

1、类名+类型参数 -> 模板实例化->生成类

2、类再实例化对象 -> 分配内存

3、父类构造，成员构造，自己的构造

注意：模板类的声明与定义不能分开实现，必须在头文件中完成，模板类和模板函数预先编译成二进制没有意义，它们只是生成代码的工具。

练习、实现一个 链式队列 类模板。

类模板的静态成员变量：

类模板的静态成员变量与普通成员变量一样都需要在类内存声明，类外定义，但静态成员定义时就需要提供类型参数了。

一般类模板的设计者只负责声明静态成员变量，而由类模板的使用定义静态成员。

template<> 类型 类名<类型参数>::静态成员 = 初始化数据;

#include <iostream>
using namespace std;
​
template <typename T>
class Test
{T num;
public:static T static_num;Test(T t):num(t){cout << num << endl;}
};
​
template<> int Test<int>::static_num = 34;
int main(int argc,const char* argv[])
{Test<int> t(1234);cout << t.static_num << endl;return 0;   
}

类模板可以递归创建：

什么类型都以是类模板的类型参数，包含类模板。

类< 类<类型> > 对象;

Array<Array<int> > arr; // 二维数组

类模板的默认形参：

类模板也可以像函数模板一样设置默认形参，规则与函数模板一样。

template <typename T1,typename T2=int>
class Test
{T1 val;
public:Test(T2 val){}
};

类的局部特化：

当类模板的成员函数不能支持所有的类型时，可以为这个成员函数实现一个特殊版本。

// 需要在类外定义：
template<> 返回值类型 类名<特殊类型>::函数名(参数列表)
{
​
}

#include <iostream>
#include <string.h>
using namespace std;
​
template <typename T>
class Array
{T* ptr;size_t cnt;const size_t cap;
public:Array(size_t cap):cap(cap){ptr = new T[cap];cnt = 0;}~Array(void){delete[] ptr;}// 满bool full(void){return cnt >= cap;}// 空bool empty(void){return 0 == cnt;}// 添加void back(const T& t){if(full())throw invalid_argument("满了");ptr[cnt++] = t;}// 插入void insert(size_t index,const T& t){if(full() || index >= cnt)throw invalid_argument("满了");
​for(int i=cnt; i>index; i--){ptr[i] = ptr[i-1];}
​ptr[index] = t;cnt++;}
​// 删除void remove(size_t index){if(index >= cnt)throw invalid_argument("空了");
​for(int i=index; i<cnt-1; i++){ptr[i] = ptr[i+1];}cnt--;}
​// 查找int query(const T& key){for(int i=0; i<cnt; i++){if(key == ptr[i])return i;}return -1;}
​// 排序void sort(void){for(int i=0; i<cnt-1; i++){int min = i;for(int j=i+1; j<cnt; j++){if(ptr[j] < ptr[min])min = j;}if(min != i)swap(ptr[min],ptr[i]);}}
​// 遍历void show(void){cout << "array：";for(int i=0; i<cnt; i++){cout << ptr[i] << " ";}cout << endl;}
};// 类的局部特化
template<> void Array<const char*>::sort(void)
{for(int i=0; i<cnt-1; i++){int min = i;for(int j=i+1; j<cnt; j++){if(-1 == strcmp(ptr[j],ptr[min]))min = j;}if(min != i)swap(ptr[min],ptr[i]);}
}
template<> int Array<const char*>::query(const char* const & key)
{for(int i=0; i<cnt; i++){if(0 == strcmp(ptr[i],key))return i;}return -1;
}
int main(int argc,const char* argv[])
{const char* str[] = {"B","C","A","Z","F","E"};Array<const char*> arr(10);for(int i=0; i<6; i++){arr.back(str[i]);}
​arr.show();arr.sort();arr.show();string s = "Z";cout << arr.query(s.c_str()) << endl;return 0;
}

类的全局特化:

如果类的大部分操作都不支持特殊类型，就需要为特殊类型实一个特殊的类模板。

template <>
class Test<特殊类型>
{// 实现类的所有功能
};

二、STL模板库

1、什么是STL模板库

STL是 Standard Template Library 缩写，也就是C++标准模板库。

C++标准库是C++标准委员会为C++语言提供的一些基础类库，相当于C语言标准库。

STL库是惠普公司以模板技术为基础，而实现的一些常用的数据结构和算法的函数模板和类模板，由于该库的质量比较高，被C++标准委员会认可，所以被包含中C++标准库中。

该模板库主要有三部分内容：

函数模板：常用的算法有，sort、find、 search、max、min、copy、remove。

类模板：常用的数据结构有，也叫容器，vector，deque，list，priority_queue，queue、stack、set、multiset、map，multimap，bitset。

迭代器iterator：是一种辅助使用容器的工具，把它当作指针使用即可（指向着容器中的数据元素），它支持*、->，*.，++、--，it+n,it-n运算。

iterator begin(); 
const_iterator begin() const;
功能：返回一个正向迭代器，指向数据结构中的第一个元素
​
iterator end();
const_iterator end() const;
功能：返回一个正向迭代器，指向数据结构中的最后一个元素的下一位置
​
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
功能：返回一个逆向迭代器，指向数据结构中的最后一个元素
​
reverse_iterator rend();
const_reverse_iterator rend() const;
功能：返回一个逆向迭代器，指向数据结构中的第一个元素的上一个位置

2、STL中为什么要使用迭代器？

1、迭代器能加快、方便链式容器的访问（相当于建立了索引）。

2、能适用于大部分的容器（除了stack、queue），给所有的容器提供一种统一的遍历接口。

3、保护容器类的封装性。

for(auto it=容器.begin(); it!=容器.end(); it++)
{it->成员函数|成员变量;*it.成员函数|成员变量;
}

3、vector容器

构造函数：

// 无参构造
vector();
// 拷贝构造 
vector(const vector &from);
// 有参构造
vector(size_type num, const TYPE &val);num：数组的长度val：各元素的初始化
// 使用迭代器来构造
vector(input_iterator start, input_iterator end);
功能：使用一个数据结构的迭代器来构造vectorstart：迭代器的开头end：迭代器的末尾，end只是边界，它指向的元素不会插入进当前容器

支持的运算符：

TYPE& operator[]( size_type index );
const TYPE& operator[]( size_type index ) const;
功能：访问元素，不检查下标，速度快但有安全隐患
​
vector operator=(const vector& c2);
功能：赋值函数bool operator==(const vector& c1, const vector& c2);
bool operator!=(const vector& c1, const vector& c2);
bool operator<(const vector& c1, const vector& c2);
bool operator>(const vector& c1, const vector& c2);
bool operator<=(const vector& c1, const vector& c2);
功能：比较两个vector的内容，以全局运算符函数实现

成员函数：

void assign(input_iterator start, input_iterator end);
功能：使用一个迭代器区间给当前容器中元素赋值
​
void assign(size_type num, const TYPE &val);
功能：给当前对容器中的前num个元素，赋值为val,如果容器中元素不足num个，会自动往里添加TYPE& at(size_type loc);
const TYPE& at(size_type loc) const;
功能：使用loc作为下标访问成员，它比[]访问更安全，会检查loc是否会法，如果超出范围会抛出std::out_of_range异常。TYPE& back();
const TYPE& back() const;
功能：获取容器对象的最后一个元素，如果容器为空则会产生段错误，应该通过size()确保容器中有元素。size_type capacity() const;
功能：获取当前容器的容量，当vector容器的容量为空时，它会自动把存储容量扩展一倍void clear();
功能：清空容器中的所有元素bool empty() const;
功能：判断当前容器是否为空iterator erase(iterator loc);
iterator erase(iterator start, iterator end);
功能：使用迭代器，删除容器中的元素
返回值：所删除元素下个位置的迭代器TYPE& front();
const TYPE& front() const;
功能：获取容器的第一个元素，如果容器为空则会产生段错误iterator insert( iterator loc, const TYPE& val );
功能：在迭代器loc指向的元素前面插入一个值为val的元素
void insert( iterator loc, size_type num, const TYPE& val );
功能：在迭代器loc指向的元素前面插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
功能：在迭代器loc指向的元素前面插入一个区别的元素size_type max_size() const;
功能：计算出当前容器能存储多个元素，它与所存储元素的类型有关。void pop_back();
功能：删除容器的最后一个元素，如果容器为空则段错误。void push_back(const TYPE& val);
功能：在容器的末尾添加一个元素void reserve(size_type size);
功能：调整当前容器空间，让它能容纳size个元素的空间，如果capacity() > reserve()则不执行任何操作。void resize(size_type num, const TYPE& val = TYPE());
功能：设置容器的元素数量为numnum > size() 扩充元素，并对扩充的元素初始化num < size() 删除尾部的size-num个元素void swap(container& from);
功能：交换两个容器的元素

4、list容器

list容器与vector最大的区别是底层的存储结构不同，vector采用的是顺序存储相当于数组，而list容器采用链式存储也就是数据结构讲过的双向链表，所以list插入、删除速度较快，但随机访问速度较慢，所以不支持[]、at函数，只能使用迭代器遍历。

与vector功能参数相同的成员函数：

// 无参、拷贝、有参、迭代器构造
list();
list( const list& c );
list( size_type num, const TYPE& val = TYPE() );
list( input_iterator start, input_iterator end );
​
// 赋值与关系运算符
list operator=(const list& c2);
bool operator==(const list& c1, const list& c2);
bool operator!=(const list& c1, const list& c2);
bool operator<(const list& c1, const list& c2);
bool operator>(const list& c1, const list& c2);
bool operator<=(const list& c1, const list& c2);
bool operator>=(const list& c1, const list& c2);
​
// 批量赋值
void assign( size_type num, const TYPE& val );
void assign( input_iterator start, input_iterator end );
​
// 获取尾部元素
TYPE& back();
const TYPE& back() const;
​
// 清空与判断是为空 比vector慢
void clear();
bool empty() const;
​
// 基于迭代器的删除，按位置、区间 比vector快
iterator erase( iterator loc ); 
iterator erase( iterator start, iterator end );
​
// 头部元素
TYPE& front();
const TYPE& front() const;
​
// 最大元素数量
size_type max_size() const;
​
// 调整链表长度 比vector慢
void resize( size_type num, const TYPE& val = TYPE());
​
// 获取链表长度 可能比vector慢
size_type size() const;
​
//头删除与头添加 比vector快
void pop_front(); 
void push_front( const TYPE& val );
​
// 尾删除与尾添加 相同
void pop_back()
void push_back( const TYPE &val );
​
// 插入元素 比vector快
iterator insert( iterator loc, const TYPE& val );
功能：在指定的位置前插入一个元素
void insert( iterator loc, size_type num, const TYPE& val );
功能：在指定的位置前插入num个元素
void insert( iterator loc, input_iterator start,input_iterator end );
功能：在指定的位置前插入一个区间的元素void swap( container& from )

list新增的成员函数：

void merge( list &lst );
功能：合并两个链表，会按照从小到大的顺序进行合并，如果之前链表是无序则合并的结果是不确定的，所以在调用前最好对链表进行排序，所有的容器只要有排序的功能则成员必须支持 < 运算符函数。
注意：作为参数的lst链表，合并完成后会被清空。void merge( list &lst, BinPred compfunction );
功能：合并两个链表
compfunction：比元素回调用函数
// 成员是int的可以用比较函数
bool comper(int t1,int t2) 
{return t1 > t2; 
}void remove( const TYPE &val );
功能：删除所有与val相等的元素void remove_if( UnPred pr );
功能：按条件删除
pr：判断元素是符合删除的条件
// 成员是int的判断函数
bool is_check(int ele)
{   return ele > 2 && ele < 8;
}
​
void reverse();
功能：链表逆序
​
void sort();
功能：对链表进行排序，此时会使用元素的 < 运算符，自定义的类型需要重载<运算函数。
void sort( BinPred p );
功能：对链表进行排序，此时使用回调用函数对元素进行比较并排序BinPred函数原型：bool xxxcmp(const T&,const T&);void splice( iterator pos, list& lst );
功能：把lst链表的所有元素插入到当前链表的pos位置void splice( iterator pos, list& lst, iterator del );
功能：把lst链表的del指向的元素，插入到当前链表的pos位置void splice( iterator pos, list& lst, iterator start, iterator end );
功能：把lst链表的[start,end)范围的元素，插入到当前链表的pos位置
​
void unique();
功能：删除链表中值相同的元素，默认使用 < 判断元素是否相等，只保留一个。
void unique( BinPred pr );
功能：删除链表中值相同的元素，使用回调用函数pr判断元素是否相等，只保留一个。       

常见的面试问题：顺序存储结构与链式存储结构的优缺点，vector和list优缺点？

5、stack容器

没有迭代器，访问受限的线性表（只有一个端口进出数据元素），底层采用链式结构存储，所以没有满的状态，但支持条件运算符（比较两栈的元素大小和顺序），所以进而存储的元素需要支持 <，== 运算符。

支持的运算符：

==  <=  >=  <  >  !=
注意：相等指栈内有相同的元素并有着相同的顺序 

bool empty() const;
功能：判断是否是空栈void pop();
功能：出栈void push( const TYPE& val );
功能：入栈size_type size() const;
功能：获取栈的元素个数TYPE& top();
功能：返回栈顶元素

练习：使用模板技术，实现一个stack容器。

6、queue

不支持运算符，也没有迭代器，访问受限的线性表，底层采用链式结构存储，所以没有满的状态。

TYPE& back();
const TYPE& back() const;
功能：返回队尾元素
​
bool empty() const;
功能：判断是否是空队
​
TYPE& front();
const TYPE& front() const;
功能：返回队头元素void pop();
功能：出队
​
void push( const TYPE& val );
功能：入队size_type size() const;
功能：获取队列的元素个数

7、priority_queue容器

priority_queue 优先队列，使用时包含#include <queue>，添加元素入队后，会按照元素值进行自动排序（从大到ih的顺序排序），出队时会按照排序后的结果进行出队，里面存储的元素必须支持 < 运算符函数，或者在创建时提供比较元素的回调函数。快速造词

priority_queue( const Compare& cmp = Compare(), const Container& c =
Container() );priority_queue( input_iterator start, input_iterator end, const
Compare& comp = Compare(), const Container& c = Container());
功能：构造优先队列时，提供比较元素的回调函数。bool empty() const;
功能：判断是否是空队void pop();
功能：出队一个优先级最高的元素void push( const TYPE& val );
功能：入队，不会直接加入队尾，而是根据优先级插入到合适的位置size_type size() const;
功能：获取队列的元素个数TYPE& top();
功能：获取队列中优先级最高的元素

练习：基于queue数据结构，实现一个优先队列模板。

8、set容器

set集合容器，里面存储元素除了同属一个容器外，没有任何关系，最大的特点就是集合中的元素不能重复，所以它的元素也需要支持 < 运算符（set容器会调用它判断元素是否相等，也就是是否重复），并且会对集合中的元素自动排序，适用于对数据进行排名的情况，底层数据结构是红黑树（平衡、有序的二叉树，基于有序二叉树的快速查询功能实现的元素不重复，数据排序只是顺带功能）。

支持的运算符：

set operator=(const set& c2);
bool operator==(const set& c1, const set& c2);
bool operator!=(const set& c1, const set& c2);
bool operator<(const set& c1, const set& c2);
bool operator>(const set& c1, const set& c2);
bool operator<=(const set& c1, const set& c2);
bool operator>=(const set& c1, const set& c2);
注意：相等指集合内有相同的元素

set容器的成员函数：

void clear();
功能：删除所有元素bool empty() const;
功能：判断集合是否是为空iterator begin();
const_iterator begin() const;
功能：返回一个正向迭代器，指向值最小的元素iterator end();
const_iterator end() const;
功能：返回一个正向迭代器，指向最大值元素的下一个位置
注意： begin与end得到的是从小到大的序列。void erase( iterator pos );
功能：删除pos指向的元素
void erase( iterator start, iterator end );
功能：删除[start,end)区间的元素
size_type erase(const key_type& key);
功能：删除所以值为key的元素
返回值：删除了多少个元素，在set容器中只有两种可能0或1size_type count( const key_type& key);
功能：统计值为key的元素个数，实际意义是判断值为key的元素是否存在，返回值只有两种可能0或1
​
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
功能：返回一个逆向迭代器，指向集合中的最大值元素     reverse_iterator rend();
const_reverse_iterator rend() const;
功能：返回一个逆向迭代器，指向集合中的最小值元素的下一个位置
注意：rbegin与rend得到的是从大到小的序列size_type size() const;
功能：获取集合中元素的个数void swap( container& from );
功能：交换两个集合iterator find( const key_type& key );
功能：查询值key的元素，并返回指向它的迭代器，如果返回的是 end()的值 则说明没有找到void insert( input_iterator start, input_iterator end);
功能：添加一个区间的元素[start,end)pair<iterator,bool> insert( const TYPE& val );
功能：添加一个值为val的元素，并返回两个值，一个指向元素的迭代器，另一个添加元素是否成功
​
size_type max_size() const;
功能：计算出该集合最多能存储多少个元素，会根据元素的字节而变化iterator lower_bound( const key_type& key );
功能：返回一个正向迭代器，指向第一个小于等于key的元素iterator upper_bound( const key_type& key );        
功能：返回一个正向迭代器，指向第一个大于key的元素。pair<iterator, iterator> equal_range(const key_type& key);
功能：返回一个对迭代器区间，获取集合中所以值为key的元素，该函数在set集合中没有意义iterator insert(iterator i, const TYPE& val );
功能：在i位置前插入一个值为val的元素，并返回一个指向新元素的迭代器。value_compare value_comp() const;
功能：获取set集合元素比较函数，但可以直接调用，s.key_comp()(k1,k2)，在set集合中与key_compare函数没有区别，在map集合中这两个函数是不同的。
​
key_compare key_comp() const;
功能：获取set集合元素比较函数，但可以直接调用，s.key_comp()(k1,k2);

9、multiset多重集合

multiset 容器与set容器最大的区别是，multiset元素可以重复，其它功能与set集合相同，它们的成员函数都相同，但有部分函数在set集合中没有意义，但multiset集合中意义重大。

size_type count( const key_type& key);
功能：计算出值为key的元素个数pair<iterator, iterator> equal_range(const key_type& key);
功能：获取一个迭代器区间，指向多重集合中值为key的元素

10、map容器

map容器在C++中被称为映射容器，里面存储的 key/value 型的对值，在其它编程语言中也被称为字典，它的存储结构、使用方法与redis数据库非常像，底层使用红黑树作为存储结构，所以它的查询效率非常高，一般存储类、结构等对象，使用对象的ID作为key，例如：学生、老师、员工等，使用学号、工号作为key。

map容器中一个key只能对应一个value，对值的key不能重复。

map会自动以key为判断条件对value进行排序(红黑树：平衡且有序的二叉树)，所以元素的key必须支持 < 运算符。

注意：该容器最大的特点就是会自动排序、键值不重复，可以根据键值快速查询value，查询的时间复杂度是O(logn）

常见面试题：map的底层数据结构是什么，为什么使用它。

二叉搜索树->平衡二叉树->AVL树->红黑树

支持的运算符：

TYPE& operator[]( const key_type& key );
注意：该运算符的功能比较多，可以查询、添加、遍历，map operator=(const map& c2);
bool operator==(const map& c1, const map& c2);
bool operator!=(const map& c1, const map& c2);
bool operator<(const map& c1, const map& c2);
bool operator>(const map& c1, const map& c2);
bool operator<=(const map& c1, const map& c2);
bool operator>=(const map& c1, const map& c2);
注意：相等指容器内有相同key的元素

与其它容器功能相同的成员函数：

iterator begin();
const_iterator begin() const;
功能：返回一个正常迭代器，指向容器中key值最小的元素，该迭代器指向 pair<key,value> 对象，first就是key，second就是value。
​
void clear();
功能：删除所有元素size_type count(const key_type& key);
功能：统计键值等于key的元素有多少个，由于map容器不能重复，所以该函数在map容器中只能返回0/1，适合与[]运算符配合使用。
​
bool empty() const;
功能：判断该容器是否为空iterator end();
const_iterator end() const;
功能：返回一个正常迭代器，指向容器中key值最在的元素的下一个位置pair<iterator, iterator> equal_range(const key_type& key);
功能：返回一个对迭代器区间，获取容器中所有键值等于key的元素，该函数在map容器中没有意义
​
void erase( iterator pos );
功能：删除pos指向的元素void erase( iterator start, iterator end );
功能：删除[start,end)区间的元素
size_type erase( const key_type& key );
功能：删除键值等于key的元素
​
iterator find(const key_type& key);
功能：返回一个正常迭代器，指向键值等于key的元素iterator insert(iterator i, const TYPE& pair );
功能：在i位置插入一个对值(key/value)
void insert( input_iterator start, input_iterator end );
功能：添加一个区间的元素[start,end)
pair<iterator,bool> insert( const TYPE& pair );
功能：往容器中添加一个对值(key/value)，如果容器中已经有key存储则添加失败make_pair(key,value);key_compare key_comp() const;
功能：获取key值的比较函数value_compare value_comp() const;
功能：获取value的比较函数iterator lower_bound( const key_type& key );
功能：返回一个正常迭代器，指向第一个键值大于等于key的元素size_type max_size() const;
功能：统计容器中最多能存储多少个元素，会根据元素的字节数而变化reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
功能：返回一个逆向迭代器，指向容器中键值最大的元素reverse_iterator rend();
const_reverse_iterator rend() const;
功能：返回一个逆向迭代器，指向容器中键值最小的元素下一个位置size_type size() const;
功能：获取容器中有多少个元素void swap( container& from );
功能：交换两个容器中的元素iterator upper_bound( const key_type& key );
功能：返回一个正常迭代器，指向第一个键值大于key的元素

#include <iostream>
#include <map>
using namespace std;
​
struct Student
{int id;string name;char sex;short age;float score;Student(int id=0,const string& name="",char sex='x',short age=0,float score=0){this->id = id;this->name = name;this->sex = sex;this->age = age;this->score = score;}friend ostream& operator<<(ostream& os,const Student& stu){os << stu.id << " ";os << stu.name << " ";os << (stu.sex?"女":"男") << " ";os << stu.age << " ";return os << stu.score << endl; }
};
​
int main(int argc,const char* argv[])
{// 创建映射/关联/字典容器map<int,Student> m;
​for(int i=0; i<10; i++){char name[20];sprintf(name,"hehe%d",i+1);Student stu(1001+i%5,name,i%2?'w':'m',18+i,rand()%100+1);// 以make(key,value)插入元素// m.insert(make_pair(stu.id,stu));// 以key = value添加元素m[stu.id] = stu;}
​// 使用正向迭代器遍历容器map<int,Student>::iterator it = m.begin();while(it != m.end()){// 由于存储的是key/value对值，所以map的迭代器有两个成员cout << it->first << " " << it->second;it++;}
​for(int i=1001; i<1010; i++){map<int,Student>::iterator it = m.find(i);if(it != m.end())cout << it->second;}
​return 0;
}

11、multimap容器

multimap 容器与map容器最大的区别是，multimap容器key可以重复，也就是说一个key可以对应多个value，所以multimap 容器不支持[]运算符，所有只能使用insert函数插入数据。

其它功能与map容器相同，它们的成员函数都相同，但有部分函数在map容器中没有意义，但multimap集合中意义重大。

size_type count(const key_type& key);
功能：键值key对应了多个valuepair<iterator, iterator> equal_range(const key_type& key);
功能：获取键值key对应的所有元素,first指向第一个键值为key的元素，second指向最后一个键值为key的元素下一个位置

#include <iostream>
#include <map>
using namespace std;
​
int main(int argc,const char* argv[])
{multimap<int,string> mm;for(int i=0; i<10; i++){char name[20];sprintf(name,"hehe%d",i+1);int class_id = 1001+i%4;//mm.insert(make_pair(class_id,name));}
​typedef multimap<int,string>::iterator mi;for(int i=1001; i<1005; i++){cout << i <<"班级中有"<< mm.count(i) << "位同学" << endl;pair<mi,mi> p = mm.equal_range(i);while(p.first != p.second){cout << p.first->first << " " << p.first->second << endl;p.first++;}}return 0;
}

练习：学校举办跳水比赛，选手的编号为：1001~1015，有10们评委老师会根据选手的表现打出成绩（随机产生）存储在multimap容器里，请你计算出每个选手的最后得分。

12、deque容器

deque容器也叫双端队列容器，但它的操作跟队列没有什么关系，使用方法与vector类似，只是比它多的头部添加和尾部添加，可以把它看作是list+vector=deque

。

支持的运算符：

TYPE& operator[]( size_type index );
const TYPE& operator[]( size_type index ) const;
​
container operator=(const container& c2);
bool operator==(const container& c1, const container& c2);
bool operator!=(const container& c1, const container& c2);
bool operator<(const container& c1, const container& c2);
bool operator>(const container& c1, const container& c2);
bool operator<=(const container& c1, const container& c2);
bool operator>=(const container& c1, const container& c2);
注意：容器对象相等，指的是容器内有相同的元素并有着相同的顺序 

deque(size_type num, const TYPE& val = TYPE());
功能：创建一个双端队列，往里面添加num个元素，每个元素初始化为valdeque(input_iterator start, input_iterator end);
功能：创建一个双端队列，往里面添加[start,end)区间的元素
​
void assign(input_iterator start, input_iterator end);
功能：使用一个迭代器区间给当前容器中元素赋值
​
void assign(size_type num, const TYPE &val);
功能：给当前对容器中的前num个元素，赋值为val,如果容器中元素不中num个，会自动往里添加TYPE& at(size_type loc);
const TYPE& at(size_type loc) const;
功能：使用loc作为下标访问成员，它比[]访问更安全，会检查loc是否会法，如果超出范围会抛出std::out_of_range异常。TYPE& back();
const TYPE& back() const;
功能：获取容器中的最后一个元素，如果容器为空则返回的就是悬空引用，会产生段错误
TYPE& front();
const TYPE& front() const;
功能：获取容器中的第一个元素，如果容器为空则返回的就是悬空引用，会产生段错误void clear();
功能：清空容器中的所有元素iterator begin();
const_iterator begin() const;
功能：返回一个正向迭代器，指向容器中的第一个元素iterator end();
const_iterator end() const;
功能：返回一个正向迭代器，指向容器中的最后一个元素的下一个位置reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
功能：返回一个逆向迭代器，指向容器中的最后一个元素
​
reverse_iterator rend();
const_reverse_iterator rend() const;
功能：返回一个逆向迭代器，指向容器中的第一个元素的下一个位置iterator erase(iterator loc);
功能：删除loc指向的元素
返回：loc的下一位置迭代器
iterator erase(iterator start, iterator end);
功能：删除迭代器区间[start,end)的元素iterator insert( iterator loc, const TYPE& val );
功能：在迭代器loc指向的元素前面插入一个值为val的元素，返回一个指向新的元素的迭代器
void insert( iterator loc, size_type num, const TYPE& val );
功能：在迭代器loc指向的元素前面插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
功能：在迭代器loc指向的元素前面插入一个区别的元素size_type max_size() const;
功能：计算出当前容器能存储多个元素，它与所存储元素的类型有关。void pop_back();
功能：删除容器的最后一个元素，如果容器为空则段错误。void push_back(const TYPE& val);
功能：在容器的末尾添加一个元素void pop_front();
功能：删除容器的第一个元素，如果容器为空则段错误。void push_front( const TYPE& val );
功能：在容器的头部添加一个元素void reserve(size_type size);
功能：让当容器预留至少共容纳size个元素的空间void resize(size_type num, const TYPE& val = TYPE());
功能：设置容器的容量为numnum > size() 扩充元素，并对扩充的元素初始化num < size() 删除尾部的size-num个元素void swap(container& from);
功能：交换两个容器的元素

13、bitset容器

bitset容器封装了二进制的位运算操作，该功能在C++语言中有点鸡肋，位运算操作常用于嵌入 式、单片机、驱动开发，但C++语言并不擅长做这类工作，所以该容器了解即可。

注意：bitset的模板参数与其它容器不同

容器名<类型> 对象名;

bitset<二进制位数> 对象名;

bitset容器的成员函数：

bitset(unsigned long val);
功能：用val的补码给容器中的二进制赋值
​
bool any();
功能：任意一位二进制为1，结果就是true，就是把二进制数据转换成bool类型的数据size_type count();
功能：计算二进制数据中有多少个1bitset<N>& flip();
功能：对容器的所有二进制位进行按位求反bitset<N>& flip(size_t pos);
功能：对第pos个二进制位进行求反(pos从低到高计算)bool none();
功能：如果没有二进制位被设为1返回真，否则返回假，相当于进行了逻辑求反运算bitset &set();
功能：设置所有二进制位都为1
bitset &set( size_t pos, int val=1 );
功能：设置指定的二进制位为val​
bitset<N>& reset();
功能：设置所有二进制位都为0
bitset<N>& reset( size_t pos );
功能：设置指定的二进制位为0size_t size();
功能：获取二进制的位数bool test( size_t pos );
功能：访问pos二进制位，为0返回false，为1返回true
​
string to_string();
功能：把二进制转换成字符串
​
unsigned long to_ulong();
功能：把二进制转换成无符号整数    

支持的运算符：

!=, == 
功能：比较二进制位是否全部相等
​
&=, ^=, |=, ~, <<=, >>= 
功能：进行二进制运算
​
[] 
功能：访问指定的二进制位

#include <iostream>
#include <bitset>
using namespace std;
​
int main(int argc,const char* argv[])
{unsigned int* ptr = 0xE0200240;/**ptr &= 0xff000fff;*ptr |= 0x00111000;*/bitset<32> bs(*ptr);bs.set(12);bs.reset(13);bs.reset(14);bs.reset(15);bs.set(16);bs.reset(17);bs.reset(18);bs.reset(19);bs.set(20);bs.reset(21);bs.reset(22);bs.reset(23);*ptr = bs.to_ulong();}

14、STL模板库总结

STL模板库就是使用C++语言的模板技术对数据结构和算法的封装，不建议在项目中大量使用类模板(容器)，因为容器中每存储一种新的类、结构编译器就需要生成一份该数据结构的相关代码，过多使用会使项目的代码段快速增大，编译速度变慢，一般大型项目的编译时间是以小时为单位。

STL模板库默认内存管理机制速度比较慢，因为new不能调整已经有的内存块大小，基本都是释放旧的，重新申请新的，如果对代码的运行速度要求比较高，建议自己实现数据结构。

STL模板库中大多数容器都支持迭代器，begin()，end()函数中有step in操作，会让程序的调试变的复杂。

我们目前对于STL模板库会用即可，如果后期工作中需要大量使用STL模板库，我个人建议你把所有的容器自己手动实现一下（STL模板源码解析-候捷）。

在C++11语法标准中已经加了Boost模块，Boost库的功能比较齐全，我个人认为是以后的发展方向。

vector、list、deque

stack、queue、p queue、

set multiset map multimap

bitset