STL基本概念

STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

STL 最初由惠普实验室开发，于 1998 年被定为国际标准，正式成为 C++ 程序库的重要组成部分。

STL的从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。几乎所有的代码都采 用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

STL细说六大件：

​ – 容器（Container）

​ – 算法（Algorithm）

​ – 迭代器（Iterator）

​ – 仿函数（Function object）

​ – 适配器（Adaptor）

​ – 空间配制器（allocator）

在C++标准中，STL被组织为下面的13个头文 件：\、\、\、\、\、\、\

说了这么多，使用STL有什么好处呢？

1）STL是C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。

2）STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但是这种分离确实使得STL变得非常通用。

3） 程序员可以不用思考STL具体的实现过程，只要能够熟练使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。

4） STL具有高可重用性，高性能，高移植性，跨平台的优点。

高可重用性：STL中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。关于模板的知识，已经给大家介绍了。

高性能：如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。(红黑树是平横二叉树的一种)

高移植性：如在项目A上用STL编写的模块，可以直接移植到项目B上。

跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译。

5） 了解到STL的这些好处，我们知道STL无疑是最值得C++程序员骄傲的一部分。每一个C＋＋程序员都应该好好学习STL。只有能够熟练使用STL的程序员，才是好的C++程序员。

6） 总之：招聘工作中，经常遇到C++程序员对STL不是非常了解。大多是有一个大致的映像，而对于在什么情况下应该使用哪个容器和算法都感到比较茫然。STL是C++程序员的一项不可或缺的基本技能，掌握它对提升C++编程大有裨益。

Alexander Stepanov

容器

一些封装数据结构的模板类，简单来说，就是存储数据的结构

序列式容器：特点是不会对存储的元素进行排序，元素排列的顺序取决于存储它们的顺序。

关联式容器：在存储元素时会为每个元素在配备一个键，整体以键值对的方式存储到容器中，可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素键值的大小做升序排序。

迭代器

用来遍历容器中的元素的类型，类中类(可以理解为指针)，扮演着容器和算法之间的胶合剂

算法

解决问题的方法

容器、迭代器、算法分离案例

#include<iostream>
using namespace std;
//算法：求数组元素个数
int mcount(int *begin,int *end,int arr[])
{
	int num=0;
	while (begin != end)
	{
		num++;
		begin++;
	}
	return num;
}
int main()
{
    //容器
	int arr[] = { 7,1,2,5,4,7,5 };
    //迭代器
	int *begin = arr;
	int *end = &arr[sizeof(arr) / sizeof(arr[0])];
	cout<<mcount(begin,end,arr);

	while (1);
	return 0;
}

string容器

string概念

• string是STL的字符串类型，通常用来表示字符串。而在使用string之前，字符串通常是用char表示的。string与char都可以用来表示字符串，那么二者有什么区别呢。

string和char*的比较

• string是一个类, char*是一个指向字符的指针。

  ​ string封装了char\，管理这个字符串，是一个char*型的容器*

• string不用考虑内存释放和越界。

  ​ string管理char所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。*

• string提供了一系列的字符串操作函数（这个等下会详讲）

     *查找find，拷贝copy，删除erase，替换replace，插入insert*
  

string的构造函数

• 默认构造函数：

  ​ string(); //构造一个空的字符串string s1。

• 拷贝构造函数：

  ​ string(const string &str); //构造一个与str一样的string。如string s1(s2)。

• 带参数的构造函数

    string(const char *s);   //用字符串s初始化
  

  string(int n,char c); //用n个字符c初始化

string的存取字符操作

• char &operator[] (int n);

• char &at(int n);

• operator[]和at()均返回当前字符串中第n个字符，但二者是有区别的。

  主要区别在于at()在越界时会抛出异常，[]在刚好越界时会返回‘\0’，再继续越界时，程序直接中断。如果你的程序希望可以通过try,catch捕获异常，建议采用at()。

从string取得const char*

• const char *c_str() const; //返回一个以’\0’结尾的字符串的首地址
• const char *data() const; //同上

把string拷贝到char*指向的内存空间的操作

• int copy(char *s, int n, int pos=0) const;

  把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中，返回实际拷贝的数目。注意要保证s所指向的空间足够大以容纳当前字符串，不然会越界。

string str("maye");
char arr[10] = "";
str.copy(arr, 2);

string的长度

• int length() const; //返回当前字符串的长度。长度不包括字符串结尾的’\0’。

• int size() const; //同上

• bool empty() const; //当前字符串是否为空

string的赋值

• string &operator=(const string &s);//把字符串s赋给当前的字符串

• string &assign(const char *s); //把字符串s赋给当前的字符串

• string &assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串

• string &assign(const string &s); //把字符串s赋给当前字符串

• string &assign(int n,char c); //用n个字符c赋给当前字符串

• string &assign(const string &s,int start, int n); //把字符串s中从start开始的n个字符赋给当前字符串

string字符串连接

• string &operator+=(const string &s); //把字符串s连接到当前字符串结尾

• string &operator+=(const char *s);//把字符串s连接到当前字符串结尾

• string &append(const char *s); //把字符串s连接到当前字符串结尾

• string &append(const char *s,int n); //把字符串s的前n个字符连接到当前字符串结尾

• string &append(const string &s); //同operator+=()

• string &append(const string &s,int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾

• string &append(int n, char c); //在当前字符串结尾添加n个字符c

string比较

int compare(const string &s) const; //与字符串s比较

int compare(const char *s) const; //与字符串s比较

compare函数在>时返回 1，<时返回 -1，==时返回 0。此外还支持>、>=、<、<=、==直接比较

string的子串

string substr(int pos=0, int n=npos) const; //返回由pos开始的n个字符组成的子字符串

string的查找和替换

查找

int find(char c,int pos=0) const; //从pos开始查找字符c在当前字符串的位置

int find(const char *s, int pos=0) const; //从pos开始查找字符串s在当前字符串的位置

int find(const string &s, int pos=0) const; //从pos开始查找字符串s在当前字符串中的位置

find函数如果查找不到，就返回-1

int rfind(char c, int pos=npos) const; //从pos开始从后向前查找字符c在当前字符串中的位置

int rfind(const char *s, int pos=npos) const;

int rfind(const string &s, int pos=npos) const;

//rfind是反向查找的意思，如果查找不到， 返回-1

替换

string &replace(int pos, int n, const char *s);//删除从pos开始的n个字符，然后在pos处插入串s

string &replace(int pos, int n, const string &s); //删除从pos开始的n个字符，然后在pos处插入串s

void swap(string &s2); //交换当前字符串与s2的值

String的区间删除和插入

string &insert(int pos, const char *s);

string &insert(int pos, const string &s);

//前两个函数在pos位置插入字符串s

string &insert(int pos, int n, char c); //在pos位置 插入n个字符c

string &erase(int pos=0, int n=npos); //删除pos开始的n个字符，返回修改后的字符串

vector容器

Vector容器简介

vector是将元素置于一个动态数组中加以管理的容器。

vector可以随机存取元素（支持索引值直接存取， 用[]操作符或at()方法，这个等下会详讲）

vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时

vector的构造函数

vector采用模板类实现，vector对象的默认构造形式

vector\ vecT; //尖括号内还可以设置任意的数据类型。

存放对象的时候值得注意：由于容器元素的存放是按值复制的方式进行的，所以此时类必须提供对象的拷贝构造函数，以保证对象间拷贝正常。

vector(begin,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。(能取begin的值，不能取end的值)

vector(n,elem); //构造函数将n个elem拷贝给本身。

vector(const vector &vec); //拷贝构造函数

int  iArray[] = { 0,1,2,3,4 };
vector<int> vecIntA(iArray, iArray + 5);
vector<int> vecIntB(vecIntA.begin(), vecIntA.end());  //用构造函数初始化容器vecIntB 
vector<int> vecIntB(vecIntA.begin(), vecIntA.begin() + 3);
vector<int> vecIntC(3, 9); //容器vecIntB存放3个元素，每个元素的值是9。
vector<int> vecIntD(vecIntA);

vector的赋值

vector.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。

vector.assign(n,elem); //将n个elem拷贝赋值给本身。

vector& operator=(const vector &vec); //重载等号操作符

vector.swap(vec); // 将vec与本身的元素互换。

vector<int> vecIntA, vecIntB, vecIntC, vecIntD;
int  iArray[] = { 0,1,2,3,4 };
vecIntA.assign(iArray, iArray + 5);		//把iArray全部赋值给vecIntA
vecIntB.assign(vecIntA.begin(), vecIntA.end());   //用其它容器的迭代器作参数。
vecIntC.assign(3, 9);//容器vecIntB存放3个元素，每个元素的值是9。
vector<int> vecIntD;
vecIntD = vecIntA;
vecIntA.swap(vecIntD);//交换vecIntA和vecIntD的数据

vector的大小

vector.size(); //返回容器中元素的个数

vector.empty(); //判断容器是否为空

vector.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

vector.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

vector末尾的添加移除操作

vector.push_back(data);//在尾部添加一个元素

vector.pop_back();//删除尾部元素

vector的数据存取

vec.at(index); //返回索引index所指的数据，如果index越界，抛出out_of_range异常。

vec[index]; //返回索引index所指的数据，越界时，运行直接报错

deque容器

Deque简介

deque是“double-ended queue”的缩写，和vector一样都是STL的容器，deque是双端数组，而vector是单端的。

deque在接口上和vector非常相似，在许多操作的地方可以直接替换。

deque可以随机存取元素（支持索引值直接存取， 用[]操作符或at()方法，这个等下会详讲）。

deque头部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比较费时。

include

deque对象的默认构造

deque采用模板类实现，deque对象的默认构造形式：deque deqT;

deque deqInt; //一个存放int的deque容器。

deque deq Float; //一个存放float的deque容器。

deque deq String; //一个存放string的deque容器。

…

//尖括号内还可以设置指针类型或自定义类型。

deque对象的带参数构造

deque(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。

deque(n,elem); //构造函数将n个elem拷贝给本身。

deque(const deque &deq); //拷贝构造函数。

deque末尾的添加移除操作

deque.push_back(elem); //在容器尾部添加一个数据

deque.push_front(elem); //在容器头部插入一个数据

deque.pop_back(); //删除容器最后一个数据

deque.pop_front(); //删除容器第一个数据

deque的数据存取

deque.at(idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range。

deque[idx]; //返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。

deque.front(); //返回第一个数据。

deque.back(); //返回最后一个数据

deque的赋值

deque.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。

deque.assign(n,elem); //将n个elem拷贝赋值给本身。

deque& operator=(const deque &deq); //重载等号操作符

deque.swap(deq); // 将vec与本身的元素互换

deque的大小

deque.size(); //返回容器中元素的个数

deque.empty(); //判断容器是否为空

deque.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

deque.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

deque的插入

deque.insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。

deque.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。

deque.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

deque的删除

deque.clear(); //移除容器的所有数据

deque.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。

deque.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

迭代器基本原理

• 代器是一个“可遍历STL容器内全部或部分元素”的对象。

• 迭代器指出容器中的一个特定位置。

• 迭代器就如同一个指针。

• 迭代器提供对一个容器中的对象的访问方法，并且可以定义了容器中对象的范围。

迭代器的类别

输入迭代器：也有叫法称之为“只读迭代器”，它从容器中读取元素，只能一次读入一个元素向前移动，只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列。

输出迭代器：也有叫法称之为“只写迭代器”，它往容器中写入元素，只能一次写入一个元素向前移动，只支持一遍算法，同一个输出迭代器不能两遍遍历一个序列。

正向迭代器：组合输入迭代器和输出迭代器的功能，还可以多次解析一个迭代器指定的位置，可以对一个值进行多次读/写。

双向迭代器：组合正向迭代器的功能，还可以通过++操作符向后移动位置。

随机访问迭代器：组合双向迭代器的功能，还可以向前向后跳过任意个位置，可以直接访问容器中任何位置的元素。

迭代器的操作

迭代器	操作
所有迭代器	it++、++it
输入迭代器	*it、it1=it2、it1==it2、it1！=it2
输出迭代器	*it、it1=it2
正向迭代器	提供输入输出迭代器的所有功能
双向迭代器	it—、—it
随机迭代器	+=、-=、+、-、[]、<、<=、>、>=

这里用到的容器，都支持双向迭代器或随机访问迭代器，下面将会详细介绍这两个类别的迭代器。

容器	对应迭代器类型
array	随机访问迭代器
vector	随机访问迭代器
deque	随机访问迭代器
list	双向迭代器
set / multiset	双向迭代器
map / multimap	双向迭代器
forward_list	前向迭代器
unordered_map / unordered_multimap	前向迭代器
unordered_set / unordered_multiset	前向迭代器
stack	不支持迭代器
queue	不支持迭代器

迭代器实现

template<typename Data>
class Vector
{
public:
	Vector() :Array(nullptr), curSize(0), capacity(0) {}
	Vector(int size) :curSize(0), capacity(size)
	{
		Array = new Data[size];
	}
	Vector(Vector& arr) :curSize(arr.curSize), capacity(arr.capacity)
	{
		Array = new Data[capacity];
		for (int i = 0; i < arr.curSize; i++)
		{
			this->Array[i] = arr.Array[i];
		}
	}
	void push(Data data)
	{
		if (curSize < capacity)
		{
			Array[curSize] = data;
			curSize++;
			return;
		}
		cout << "数组越界" << endl;
	}
	void arrMul(int mulNum)
	{
		for (int i = 0; i < curSize; i++)
		{
			Array[i] *= mulNum;
			//要确保存的数据类型，能够相乘
		}
	}
	void operator=(Vector& arr)
	{
		//判断当前对象和arr的关系
		if (capacity < arr.curSize)
		{
			delete[] Array;
			capacity = arr.capacity;
			curSize = arr.curSize;
			Array = new Data[capacity];
		}
		for (int i = 0; i < arr.curSize; i++)
		{
			this->Array[i] = arr[i];
			//要确保，存的类型能够相互赋值
		}
		curSize = arr.curSize;
	}
	Data& operator[](int index)
	{
		if (index >= 0 && index < capacity)
		{
			return Array[index];
		}
		cout << "数组访问越界" << endl;
	}
	friend ostream& operator<<(ostream& out, Vector& Array)
	{
		for (int i = 0; i < Array.curSize; i++)
		{
			out << setw(5) << setiosflags(ios::left) << Array[i];
		}
		return out;
	}
	~Vector()
	{
		delete[] Array;
	}
	//迭代器
	Data* begin()
	{
		return Array;
	}
	Data* end()
	{
		return &Array[curSize];
	}
	class iterotar
	{
	public:
		iterotar(Data *begin=nullptr)
		{
			pmove = begin;
		}
		~iterotar()
		{

		}
		bool operator!=(Data* end)
		{
			return pmove != end;
		}
		Data* operator++(int)
		{
			Data* temp = pmove;
			this->pmove++;
			return temp;
		}
		//一定要返回引用，否则匿名对象不接受会出错
		Data& operator*()
		{
			return *pmove;
		}
		Data* operator->()
		{
			return pmove;
		}
	private:
		Data* pmove;
	};
protected:
	Data* Array;		//数组指针
	int curSzie;	//数组当前大小
	int capacity;	//数组最大容量
};

initializer_list聚合初始化

前面给大家讲过数组可以用聚合的方式初始化，int arr[]={1,3,1,4,5,2,0};那么咱们自己写的vector能用聚合初始化吗？

答案是否定的，那么怎么做才能使用聚合形式进行初始化呢？

C++11提供的新模板类型initializer_list,有了它之后咱们就可以使用聚合进行初始化啦！

用法：

void show(initializer_list<int> ls)
{
	for (int i : ls)
	{
		cout << i << " ";
	}
}

show({ 1,3,1,4,5,2,0 });//输出

同理，在类中我们可以提供一个initializer_list类型的构造函数

//构造聚合初始化
Vector(initializer_list<Data> ls)
{
	_capacity = ls.size();
	_curSize = 0;
	_Array = new Data[_capacity];
	for (const Data& temp : ls)
	{
		this->push_back(temp);
	}
}

list容器

list简介

list是一个双向链表容器，可高效地进行插入删除元素。

list不可以随机存取元素，所以不支持at.(pos)函数与[]操作符。It++(ok) it+5(err)

list对象的默认构造

list采用采用模板类实现,对象的默认构造形式：list lsT; 如：

list lstInt; //定义一个存放int的list容器。

list lstFloat; //定义一个存放float的list容器。

list lstString; //定义一个存放string的list容器。

…

//尖括号内还可以设置指针类型或自定义类型。

list头尾的添加移除操作

list.push_back(elem); //在容器尾部加入一个元素

list.pop_back(); //删除容器中最后一个元素

list.push_front(elem); //在容器开头插入一个元素

list.pop_front(); //从容器开头移除第一个元素

list的数据存取

list.front(); //返回第一个元素。

list.back(); //返回最后一个元素。

list与迭代器

list.begin(); //返回容器中第一个元素的迭代器。

list.end(); //返回容器中最后一个元素之后的迭代器。

list.rbegin(); //返回容器中倒数第一个元素的迭代器。

list.rend(); //返回容器中倒数最后一个元素的后面的迭代器。

list对象的带参数构造

list(beg,end); //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。

list(n,elem); //构造函数将n个elem拷贝给本身。

list(const list &lst); //拷贝构造函数。

list的赋值

list.assign(beg,end); //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。

list.assign(n,elem); //将n个elem拷贝赋值给本身。

list& operator=(const list &lst); //重载等号操作符

list.swap(lst); // 将lst与本身的元素互换。

list的大小

list.size(); //返回容器中元素的个数

list.empty(); //判断容器是否为空

list.resize(num); //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

list.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

list的插入

list.insert(pos,elem); //在pos位置插入一个elem元素的拷贝，返回新数据的位置。

list.insert(pos,n,elem); //在pos位置插入n个elem数据，无返回值。

list.insert(pos,beg,end); //在pos位置插入[beg,end)区间的数据，无返回值。

list的删除

list.clear(); //移除容器的所有数据

list.erase(beg,end); //删除[beg,end)区间的数据，返回下一个数据的位置。

list.erase(pos); //删除pos位置的数据，返回下一个数据的位置。

lst.remove(elem); //删除容器中所有与elem值匹配的元素。

当使用一个容器的insert或者erase函数通过迭代器插入或删除元素”可能”会导致迭代器失效，因此我们为了避免危险，应该获取insert或者erase返回的迭代器，以便用重新获取的新的有效的迭代器进行正确的操作

list<int> ls;
for (int i = 0; i < 10; i++)
{
	ls.push_back(i);
}
list<int>::iterator it;
for (it = ls.begin(); it != ls.end(); it++)
{
	if (*it == 5)
	{
		it=ls.erase(it);
	}
	cout << *it << " ";
}

list的反序排列

lst.reverse(); //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。

小结

一、容器deque的使用方法

​ 适合在头尾添加移除元素。使用方法与vector类似。

二、容器queue,stack的使用方法

​ 适合队列，堆栈的操作方式。

三、容器list的使用方法

​ 适合在任意位置快速插入移除元素

stack容器

Stack简介

stack是堆栈容器，是一种“先进后出”的容器。

stack是简单地装饰deque容器而成为另外的一种容器。

include

stack对象的默认构造

stack采用模板类实现， stack对象的默认构造形式： stack stkT;

stack stkInt; //一个存放int的stack容器。

stack stkFloat; //一个存放float的stack容器。

stack stkString; //一个存放string的stack容器。

…

//尖括号内还可以设置指针类型或自定义类型。

stack元素获取与删除

stack.push(elem); //往栈头添加元素

stack.pop(); //从栈头移除第一个元素

stack.top(); //返回最栈顶元素

stack对象的拷贝构造与赋值

stack(const stack &stk); //拷贝构造函数

stack& operator=(const stack &stk); //重载等号操作符

stack的大小

stack.empty(); //判断堆栈是否为空

stack.size(); //返回堆栈的大小

Queue容器

Queue简介

queue是队列容器，是一种“先进先出”的容器。

queue是简单地装饰deque容器而成为另外的一种容器。

include

queue对象的默认构造

queue采用模板类实现，queue对象的默认构造形式：queue queT; 如：

queue queInt; //一个存放int的queue容器。

queue queFloat; //一个存放float的queue容器。

queue queString; //一个存放string的queue容器。

…

//尖括号内还可以设置指针类型或自定义类型。

queue的数据存取

queue.push(elem); //往队尾添加元素

queue.pop(); //从队头移除第一个元素

queue.back(); //返回最后一个元素

queue.front(); //返回第一个元素

queue对象的拷贝构造与赋值

queue(const queue &que); //拷贝构造函数

queue& operator=(const queue &que); //重载等号操作符

queue的大小

queue.empty(); //判断队列是否为空

queue.size(); //返回队列的大小

set/multiset容器

set/multiset的简介

set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。

set不可以直接存取元素。（不可以使用at.(pos)与[]操作符）。

multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。

不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。

include

set/multiset对象的默认构造

set setInt; //一个存放int的set容器。

set setFloat; //一个存放float的set容器。

set setString; //一个存放string的set容器。

multiset mulsetInt; //一个存放int的multi set容器。

multi set multisetFloat; //一个存放float的multi set容器。

multi set multisetString; //一个存放string的multi set容器。

set的插入

set.insert(elem); //在容器中插入元素。

Set集合的元素排序

set > setIntA; //该容器是按升序方式排列元素。

set> setIntB; //该容器是按降序方式排列元素。

set 相当于 set>。

less与greater中的int可以改成其它类型，该类型主要要跟set容纳的数据类型一致。

疑问1： less<>与greate< >是什么？

疑问2：如果set<>不包含int类型，而是包含自定义类型，set容器如何排序？

要解决如上两个问题，需要了解容器的函数对象，也叫伪函数，英文名叫functor。

下面将讲解什么是functor以及用法。

使用stl提供的函数对象

set> setIntB;

setIntB.insert(3);

setIntB.insert(1);

setIntB.insert(5);

setIntB.insert(2);

此时容器setIntB就包含了按顺序的5,3,2,1元素

函数对象functor的用法

尽管函数指针被广泛用于实现函数回调，但C++还提供了一个重要的实现回调函数的方法，那就是函数对象。

functor，翻译成函数对象，伪函数，算符，是重载了“()”操作符的普通类对象。从语法上讲，它与普通函数行为类似。

greater<>与less<>就是函数对象。

下面举出greater的简易实现原理。

class greater
{
public:
	bool operator()(const int& iLeft, const int& iRight)
	{
		return iLeft > iRight;  //如果是实现less<int>的话，这边是写return (iLeft<iRight);
	}
};

容器就是调用函数对象的operator()方法去比较两个值的大小。

仿函数练习

学生包含学号，姓名属性，现要求任意插入几个学生对象到set容器中，使得容器中的学生按学号的升序排序。

解：

#include<iostream>
#include<set>
using namespace std;
//学生类
class CStudent
{
public:
	CStudent(int iID, string strName)
	{
		m_iID = iID;
		m_strName = strName;
	}
	//private:
	int m_iID;		//学号
	string m_strName; 	//姓名
};
//为保持主题鲜明，本类不写拷贝构造函数，不类也不需要写拷贝构造函数。但大家仍要有考虑拷贝构造函数的习惯。
//函数对象
struct StuFunctor
{
	bool operator()(const CStudent& stu1,const CStudent& stu2) const
	{
		return (stu1.m_iID < stu2.m_iID);
	}
};

int main()
{
	set<CStudent, StuFunctor> setStu;
	setStu.insert(CStudent(3, "小张"));
	setStu.insert(CStudent(1, "小李"));
	setStu.insert(CStudent(5, "小王"));
	setStu.insert(CStudent(2, "小刘"));
	for (auto i : setStu)
	{
		cout << i.m_iID << " ";
	}
	return 0;
}

set对象的拷贝构造与赋值

set(const set &st); //拷贝构造函数

set& operator=(const set &st); //重载等号操作符

set.swap(st); //交换两个集合容器

set的大小

set.size(); //返回容器中元素的数目

set.empty();//判断容器是否为空

set的删除

set.clear(); //清除所有元素

set.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

set.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

set.erase(elem); //删除容器中值为elem的元素。

set的查找

set.find(elem); //查找elem元素，返回指向elem元素的迭代器。

set.count(elem); //返回容器中值为elem的元素个数。对set来说，要么是0，要么是1。对multiset来说，值可能大于1。

set.lower_bound(elem); //返回第一个>=elem元素的迭代器。

set.upper_bound(elem); // 返回第一个>elem元素的迭代器。

set.equal_range(elem); //返回一对迭代器，这两个迭代器分别用于发现set中其键大于指定键的第一个元素，以及集中其键等于或大于指定键的第一个元素。

以上函数返回两个迭代器，而这两个迭代器被封装在pair中。

pair

以下讲解pair的含义与使用方法。

pair的使用

pair译为对组，可以将两个值视为一个单元。

pair存放的两个值的类型，可以不一样，如T1为int，T2为float。T1,T2也可以是自定义类型。

pair.first是pair里面的第一个值，是T1类型。

pair.second是pair里面的第二个值，是T2类型。

小结

一、容器set/multiset的使用方法；

​ 红黑树的变体，查找效率高，插入不能指定位置，插入时自动排序。

二、functor的使用方法；

      类似于函数的功能，可用来自定义一些规则，如元素比较规则。

三、pair的使用方法。

​ 对组，一个整体的单元，存放两个类型(T1,T2，T1可与T2一样)的两个元素。

map\multimap容器

map/multimap的简介

map是标准的关联式容器，一个map是一个键值对序列，即(key,value)对。它提供基于key的快速检索能力。

map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。

map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。

map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。

multimap与map的区别：map支持唯一键值，每个键只能出现一次；而multimap中相同键可以出现多次。multimap不支持[]和at操作。

include

map/multimap对象的默认构造

map mapTT;

multimap multimapTT;

map的插入与迭代器

map.insert(…); //往容器插入元素，返回pair

在map中插入元素的三种方式：

假设 map mapStu;

一、通过pair的方式插入对象

mapStu.insert( pair(3,”小张”) );

二、通过pair的方式插入对象

mapStu.inset(make_pair(-1, “校长-1”));

三、通过value_type的方式插入对象

mapStu.insert( map::value_type(1,”小李”) );

四、通过数组的方式插入值(multimap不支持)

mapStu[3] = “小刘”;

mapStu.at(4) = “小王”；

map<int, string> chess;
chess.insert(pair<int,string>(1,"将"));
chess.insert(make_pair(2, "士"));
chess.insert(map<int, string>::value_type(3, "像"));
chess.at(3) = "马";
chess[4] = "車";

前三种方法，采用的是insert()方法，该方法返回值为pair

第四种方法非常直观，但存在一个性能的问题。插入3时，先在mapStu中查找主键为3的项，若没发现，则将一个键为3，值为初始化值的对组插入到mapStu中，然后再将值修改成“小刘”。若发现已存在3这个键，则修改这个键对应的value。

string strName = mapStu[2]; //取操作或插入操作

只有当mapStu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。

函数对象functor的用法

map > mapA; //该容器是按键的升序方式排列元素。未指定函数对象，默认采用less函数对象。

map> mapB; //该容器是按键的降序方式排列元素。

less与greater 可以替换成其它的函数对象functor。

可编写自定义函数对象以进行自定义类型的比较，使用方法与set构造时所用的函数对象一样。

map对象的拷贝构造与赋值

map(const map &mp); //拷贝构造函数

map& operator=(const map &mp); //重载等号操作符

map.swap(mp); //交换两个集合容器

map的大小

map.size(); //返回容器中元素的数目

map.empty();//判断容器是否为空

map的删除

map.clear(); //删除所有元素

map.erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器。

map.erase(beg,end); //删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。

map.erase(keyElem); //删除容器中key为keyElem的对组。

map的查找

map.find(key); 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();

map.count(keyElem); //返回容器中key为keyElem的对组个数。对map来说，要么是0，要么是1。对multimap来说，值可能大于1。

map.equal_range(keyElem); //返回容器中key与keyElem相等的上下限的两个迭代器。上限是闭区间，下限是开区间，如[beg,end)。

以上函数返回两个迭代器，而这两个迭代器被封装在pair中。

Multimap 案例:

//1个key值可以对应多个value = 分组

//公司有销售部 sale （员工2名）、技术研发部 development （1人）、财务部 Financial （2人）

//人员信息有：姓名，年龄，电话、工资等组成

//通过 multimap进行 信息的插入、保存、显示

//分部门显示员工信息

STL容器共性机制

STL容器所提供的都是值（value）寓意，而非引用（reference）寓意，也就是说当我们给容器中插入元素的时候，容器内部实施了拷贝动作，将我们要插入的元素再另行拷贝一份放入到容器中，而不是将原数据元素直接放进容器中，也就是说我们提供的元素必须能够被拷贝。

• 除了queue和stack之外，每个容器都提供可返回迭代器的函数，运用返回的迭代器就可以访问元素。

• 通过STL不会抛出异常，需要使用者传入正确参数。

• 每个容器都提供一个默认的构造函数和默认的拷贝构造函数。

• 大小相关的构造方法：

  • （1）size()返回容器中元素的个数；
  • （2）empty()判断容器是否为空。

  | | vector | deque | list | set | multiset | map | multimap |
  | —————— | ———— | ———— | ———— | ——— | ———— | ——————- | ——————- |
  | 内存结构 | 单端数组 | 双端数组 | 双向链表 | 二叉树 | 二叉树 | 二叉树 | 二叉树 |
  | 可随机存取 | 是 | 是 | 否 | 否 | 否 | 对key而言：是 | 否 |
  | 元素查找速度 | 慢 | 慢 | 非常慢 | 快 | 快 | 对key而言：快 | 对key而言：快 |
  | 元素添加移除 | 尾端 | 头尾两端 | 任何位置 | - | - | - | - |

各容器使用场景

在实际使用过程中，到底选择这几种容器中的哪一个，应该根据遵循以下原则：

１、如果需要高效的随机存取，不在乎插入和删除的效率，使用vector；

2、如果需要大量的插入和删除元素，不关心随机存取的效率，使用list；

3、如果需要随机存取，并且关心两端数据的插入和删除效率，使用deque；

4、如果打算存储数据字典，并且要求方便地根据key找到value，一对一的情况使用map，一对多的情况使用multimap；

5、如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用set，不唯一存在的情况使用multiset。

6、如果要求很快的查找速度，根据情况选择使用unordered_map或unordered_set。

STL算法

sort()排序函数

该函数专门用来对容器或普通数组中指定范围内的元素进行排序，排序规则默认以元素值的大小做升序排序，除此之外我们也可以选择标准库提供的其它排序规则（比如std::greater<T>降序排序规则），甚至还可以自定义排序规则。

需要注意的是，sort() 函数受到底层实现方式的限制，它仅适用于普通数组和部分类型的容器。换句话说，只有普通数组和具备以下条件的容器，才能使用 sort() 函数：

1. 容器支持的迭代器类型必须为随机访问迭代器。这意味着，sort() 只对 array、vector、deque 这 3 个容器提供支持。

2. 如果对容器中指定区域的元素做默认升序排序，则元素类型必须支持<小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；

   sort()函数有两种用法：

   //对 [first, last) 区域内的元素做默认的升序排序
   void sort (first, last);
   //按照指定的 comp 排序规则，对 [first, last) 区域内的元素进行排序
   void sort (first, last, Compare comp);

transform()转换函数

将指定范围内的元素进行转换，并将结果存储在从result开始的范围中。

Iterator transform (first, last,result, const T& val);
transform(maye.begin(), maye.end(), maye.begin(), toupper);//转大写
transform(maye.begin(), maye.end(), maye.begin(), tolower);//转小写

find()查找函数

该函数专门用来对容器或普通数组中，指定范围内查找和目标元素值相等的第一个元素。

find()函数用法：

Iterator find (first, last, const T& val);

find_if()查找

使用自定义的比较函数代替find函数默认的 == 比较操作。

bool cmp(int i)
{
	return i == 1;
}

void fun_find_if()
{
	vector<int> v = { 9,8,7,6,5,1,2,3,4 };
	auto temp=find_if(v.begin(), v.end(), cmp);
	if (temp != v.end())
	{
		cout << *temp ;
	}
}

adjacent_find()

指定范围内查找连续的两个连续相等的元素，并返回第一个元素的迭代器，如果没有找到，返回end迭代器。

bool cmp(int i, int j)
{
	return i == j;
}

void fun_adjacent_find()
{
	vector<int> v = { 9,8,7,6,5,1,2,3,4 };
	auto temp=adjacent_find(v.begin(), v.end(), cmp);
	if (temp != v.end())
	{
		cout << *temp;
	}
}

count()统计函数

该函数专门用来对容器或普通数组中，指定范围内查找和目标元素值相等的所有元素。

int count(first,last,const T& val);

for_each函数

该函数专门用来对容器或普通数组中指定范围内的元素进行处理，把处理功能用函数封装。返回一个函数对象

用法：

FUNC for_each(first, last, 函数对象);

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

int arr[] = { 1,2,4,5,6,4 };
for_each(&arr[0], &arr[6], show);

copy()函数

把一个容器指定范围内的元素，拷贝到另一个容器中（目标容器必须内存足够）。返回一个迭代器，指向目标容器被拷贝元素范围的末尾

Iterator count(first,last,destit);

void fun_copy()
{
	vector<int> v = { 9,8,7,6,5,1,2,3,4 };
	vector<int> v1(v.size());
	//list<int> v1(v.size()+10);
	cout << *copy(v.begin(), v.end(), v1.begin()) << endl;;
	for (auto i : v1)
	{
		cout << i << " ";
	}
}

更多算法

C++参考手册

仿函数

为什么要有仿函数？

从一个非常简单的问题入手，来了解为什么要有仿函数。

假设我们现在有一个数组，数组中存有任意数量的数字，我们希望能够统计出这个数组中大于 10 的数字的数量(按照容器、迭代器、算法分离来实现)

一般这么写：

typedef bool FUNC(int);
int arrNum(int* first, int* last, FUNC func)
{
	int _count = 0;
	while (first != last)
	{
		if (func(*first))
		{
			_count++;
		}
		first++;
	}
	return _count;
}
bool isRight(int num)
{
	return num > 10;
}
int main()
{
	int arr[] = { 1,2,3,4,5,68,5,1,6,45,3,164,6,1,64 };
	//求出数组中大于5的元素个数
	int len = sizeof(arr) / sizeof(arr[0]);
	int num=arrNum(arr, arr + len, isRight);
	cout << "共有..个：" <<num << endl;

	return 0;
}

arrNum()函数的第三个参数是一个函数指针，用于回调，而 isRight() 函数也是外部定义好的，它只接受一个参数的函数。如果此时希望将判定的阈值也作为一个变量传入，变为如下函数就不可行了：

bool isRight(int num,int threshold)
{
	return num > threshold;
}

虽然这个函数看起来可以，但是它不能满足已经定义好的函数指针参数的要求，因为函数指针参数的类型是bool (*)(int)，与函数arrNum()的类型不兼容。如果一定要完成这个任务，按照以往的经验，我们可以考虑如下途径：
（1）阈值作为函数的局部变量。局部变量不能在函数调用中传递，故不可行；
（2）函数传参。这种方法我们已经讨论过了，多个参数不适用于已定义好的 arrNum() 函数。
（3）全局变量。我们可以将阈值设置成一个全局变量。这种方法虽然可行，但是不优雅，且非常容易引入 Bug，比如全局变量容易同名，造成命名空间污染。

那么有什么好的处理方法呢？仿函数应运而生。

仿函数的定义

仿函数（Functor）又称为函数对象（Function Object）是一个能行使函数功能的类。仿函数的语法几乎和我们普通的函数调用一样，不过作为仿函数的类，都必须重载 operator() 运算符。因为调用仿函数，实际上就是通过类对象调用重载后的 operator() 运算符。

如果编程者要将某种“操作”当做算法的参数，一般有两种方法：
（1）一个办法就是先将该“操作”设计为一个函数，再将函数指针当做算法的一个参数。上面的实例就是该做法；
（2）将该“操作”设计为一个仿函数（就语言层面而言是个 class），再以该仿函数产生一个对象，并以此对象作为算法的一个参数。

很明显第二种方法会更优秀，因为第一种方法扩展性较差，当函数参数有所变化，则无法兼容旧的代码，具体在第一小节已经阐述。正如上面的例子，在我们写代码时有时会发现有些功能代码，会不断地被使用。

这时就可以使用仿函数了，写一个简单类，除了维护类的基本成员函数外，只需要重载 operator() 运算符 。这样既可以免去对一些公共变量的维护，也可以使重复使用的代码独立出来，以便下次复用。

STL 中也大量涉及到仿函数，有时仿函数的使用是为了函数拥有类的性质，以达到安全传递函数指针、依据函数生成对象、甚至是让函数之间有继承关系、对函数进行运算和操作的效果。比如 STL 中的容器 set 就使用了仿函数 less ，而 less 继承的 binary_function，就可以看作是对于一类函数的总体声明，这是函数做不到的。

所以使用仿函数之后可以这样写：

struct isRight
{
	isRight(int res=0):res(res) {}
	bool operator()(int num)
	{
		return num > res;
	}
private:
	int res;
};
using FUNC = isRight;
int arrNum(int* first, int* last, FUNC func)
{
	int _count = 0;
	while (first != last)
	{
		if (func(*first))
		{
			_count++;
		}
		first++;
	}
	return _count;
}
int main()
{
	int arr[] = { 1,2,3,4,5,68,5,1,6,45,3,164,6,1,64 };
	//求出数组中大于5的元素个数
	int len = sizeof(arr) / sizeof(arr[0]);
	int num = arrNum(arr, arr + len, isRight(10));
	cout << "共有..个：" << num << endl;
	return 0;
}

谓词

谓词是指普通函数或重载的operator()返回值是bool类型的函数对象(仿函数)。如果
operator接受一个参数，那么叫做一元谓词,如果接受两个参数，那么叫做二元谓词，谓词
可作为一个判断式

函数对象适配器

函数对象适配器是完成一些配接工作，这些配接包括绑定(bind)，否定(negate),以及对一
般函数或成员函数的修饰，使其成为函数对象，重点掌握函数对象适配器(红色字体):

bind1st 将参数绑定为函数对象的第一个参数

bind2nd 将参数绑定为函数对象的第二个参数

not1 对一元函数对象取反

not2 对二元函数对象取反

ptr_fun 将普通函数修饰成函数对象

mem_fun 修饰成员函数(容器里存的是对象)

mem_fun_ref 修饰成员函数(容器里存的是指针)

bind1st

将一个二元函数转换成一个一元函数。（绑定到第一个参数）

其他同下

bind2nd

template <class Operation, class T>
  binder2nd<Operation> bind2nd (const Operation& op, const T& x);

将一个二元函数转换成一个一元函数。（绑定到第二个参数）

struct CTest :public binary_function<int, int, void>
{
	void operator()(int i, int val) const
	{
		cout << i << " + " << val <<" = "<<i+val<< endl;
	}
};

void obj3()
{
	vector<int> v = { 9,8,7,6,5,1,2,3,4 };
	for_each(v.begin(), v.end(), bind2nd(CTest(), 10));
	//for_each(v.begin(), v.end(), bind1st(CTest(),10));
}

not1

一元函数取反适配器

struct Mycmp1:public unary_function<int,bool>
{
	bool operator()(int v1)const
	{
		return v1 > 5;
	}
};

void fun_not1()
{
	vector<int> v = { 9,8,7,6,5,1,2,3,4 };
	auto it = find_if(v.begin(), v.end(), not1(Mycmp1()));
	if (it != v.end())
	{
		cout << *it << endl;
	}
}

not2

二元函数取反适配器

struct MCMP1 :public binary_function<int, int, bool>
{
public:
	bool operator()(int a, int b) const
	{
		return a == b;
	}
};

void fun_not2()
{
	vector<int> v = { 50,4,1,2,4,5,5,7,8,2 };
	auto it = adjacent_find(v.begin(), v.end(), not2(MCMP1()));
	cout << *it << endl;
	for (auto i : v)
	{
		cout << i << " ";
	}
}

ptr_fun

把普通函数转成仿函数

bool mycmp2(int v1)
{
	return v1 > 5;
}

void fun_not1()
{
	vector<int> v = { 9,8,7,6,5,1,2,3,4 };
	auto it = find_if(v.begin(), v.end(),not1(ptr_fun(mycmp2)));
	if (it != v.end())
	{
		cout << *it << endl;
	}
}

mem_fun

把类的成员函数转成仿函数

class Person
{
public:
	Person(int age,int id):_age(age),_id(id){}
	void show()
	{
		cout << "id: " << _id << "age: " << _age << endl;
	}
private:
	int _age;
	int _id;
};
void fun_cref()
{
	Person p1(1, 2), p2(3, 4), p3(5, 6);
	vector< Person*> v = { &p1,&p2,&p3 };
	for_each(v.begin(), v.end(), mem_fun(&Person::show));
}

mem_fun_ref

同上，把类的成员函数转成仿函数

class Person
{
public:
	Person(int age,int id):_age(age),_id(id){}
	void show()
	{
		cout << "id: " << _id << "age: " << _age << endl;
	}
private:
	int _age;
	int _id;
};
void fun_cref()
{
	Person p1(1, 2), p2(3, 4), p3(5, 6);
	vector< Person> v = { p1,p2,p3 };
	for_each(v.begin(), v.end(), mem_fun_ref(&Person::show));
}

mem_fun和mem_fun_ref的区别在哪？

当存的是对象时使用mem_fun_ref

存放的是对象的指针时使用mem_fun