一、STL的基本概念

1.什么是STL

STL (Standard Template Librany）标准准模板庠是惠普实验室开发的一系列软件的统称。现在主要出现在C++中，但在被引入C++之前该技木就已存在了很长一段吋间了。

STL的从广义上讲分为三类: algorithm (算法)、container (容器)和iterator (迭代器)，容器和算法通过迭代器可以进行无缝链接。几乎所有的代码都釆用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。在C++标准中，STL 被组织为下面的13个尖文件:<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、 <map>、<memory>、<numerio>、<queue>、<set>、 <stack> 和<utility>。

我们详细的说六大组件：

• 容器(Container)
• 算法(Algorithm)
• 迭代器(Iterator)
• 仿函数(Function object)
• 适配器(Adaptor)
• 空间配置器(allocator)

2.STL的好处

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

• STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但是这种分离确实使得STL变得非常通用。
  例如，在STL 的vector容器中，可以放入元素、 基础数据类型变量、元素的地址;
  STL的sort()函数可以用来操作vector,list等容器。

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

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

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

  高性能:如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。

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

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

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

二、容器

1.容器

在实际的开发过程中，数据结构本身的重要性不会逊于操作于数据结构的算法的重要性，当程序中存在着对时间要求很高的部分时，数据结构的选择就显得更加重要。

经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入。STL容器就为我们提供了这样的方便，它允许我们重复利用己有的实现构造自己的特定类型下的数据结构，通过设置-些模板，STL 容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。

​ 容器部分主要由头文件<vector>, <list>, <deque>, <set>, <map>, <stack>和<queue>组成。对于常用的一些容器和容器适配器(可以看作由其它容器实现的容器)，可以通过下表总结一:下它们和相应头文件的对应关系。

2.容器的分类

序列式容器(Sequence containers)

每个元素都有固定位置–取决于插入时机和地点，和元素值无关。如：vector、deque、 Iist。

关联式容器(Associated containers)

元素位置取决于特定的排序准则，和插入顺序无关。如：sset、multiset、 map、multimapu。

3.string类

string类的本质

string类本质上其实就是char*的容器，是cahr*的封装。

string类的遍历

使用[]遍历：

string str = "string_str";
for (int i = 0; i < str.length(); i++)
	cout << str[i];

使用迭代器遍历：

string str = "string_str";
for(string::iteratori=str.begin();i<str.end();i++)
	cout <<*i;

 注意这里的i是一个指向string::iterator类型的指针。

使用at()遍历：

string str = "string_str";
for (int i = 0; i < str.length(); i++)
	cout << str.at(i);

at()与[]不同的是，当访问发生越界等错误时，at()会自动抛出异常，而[]不会抛出异常而中断程序。

string解封成char*

C++为string类提供了一个专门的函数 str.c_str()，str是string类型的对象，但是需要注意的是str.c_str()返回的是一个 const char*，不能再被赋值给其他非常量指针，但是我们可以直接将str.c_str()当作char*来使用，如：str.c_str()[1]，即通过char*指针访问str中的第二个元素。

string类中一些常用函数

	函数名	作用
复制	str.copy(char *buf,int cout)	从字符串str中拷贝cout个字符到char数组buf中
连接	str.append(string strs)	将字符串strs连接到str之后，支持string和char*
查找	int str.find(char *strs,int index)	从字符串str中的第index索引开始查找strs子串或字符，返回查找到的第一个匹配值的索引，返回的索引也可以使用迭代器来接收
替换	str.replace(int index,int length,char *strs)	在字符串str中，从index索引开始用strs字符串替换length个长度的子串
删除	str.erase(int index,int length)	删除字符出str从index位置开始的length长度的字符
插入	str.insert(int index,char *strs)	从str字符串的index位置开始插入字串strs

string类中常用算法函数

string str = "string_str_io_stdsfx.h_iostream";
transform(str.begin(), str.end(), str.begin(), toupper);
cout << str << endl;

transform算法包含在#include <algorithm>头文件中

transform算法的使用：

原型：transform(first,last,result,op);

first是容器的首迭代器，last为容器的末迭代器，result为存放结果的容器，op为要进行操作的一元函数对象或sturct、class。

代码解释：str.begin()返回一个指向str首部位置的迭代器，str.end()返回一个指向str尾部位置的迭代器，因为我们把输出结果继续存放在str中，且迭代器始于容器相联系的，所以存放结果的容器也是str.begin()，而我们对str做的操作是将小写字母装换为大写，C++提供了标准的转换函数,所以操作函数为toupper。

transform算法的另一个重载形式：

原型：transform(first1,last1,first2,result,binary_op);

first1是第一个容器的首迭代 器，last1为第一个容器的末迭代器，first2为第二个容器的首迭代器，result为存放结果的容器，binary_op为要进行操作的二元函数 对象或sturct、class。

需要注意的是，两个容器first1和first2中的元素数量必须相等，否则会抛异常。

4.vector容器

• vector是将元素置于一个 动态数组中加以管理的容器
• vector支持随机存取元素，支持索引存取（[],at()）和迭代器存取
• vector在尾部添加和移除元素速度快，在中部和头部速度慢
• 使用vector容易需要包含#include<vector>头文件

vector常用方法

	函数	作用
读取与赋值	front(void)	获取容器首元素，既可以作左值也可以作右值
	back(void)	获取容器尾元素，既可以作左值也可以作右值
	push_back(T t)	在容器的尾部添加元素
	pop_back(T t)	删除容器最后一个元素
只读	begin(void)	获取容器首部迭代器
	end(void)	获取容器尾部迭代器
	rbegin(void)	获取逆序首部迭代器，实际指向容器的尾部，只能使用vector<int>::reverse_iterator逆序迭代器接收
	rend(void)	获取逆序尾部部迭代器，实际指向容器的首部，只能使用vector<int>::reverse_iterator逆序迭代器接收
删除	erase(iterator pos)	删除迭代器pos指向位置的元素
	erase(iterator begin,iterator end)	从迭代器begin指向位置开始到end指向位置结束，区间删除元素
插入	insert(iterator pos,T t)	在pos迭代器指向的位置插入元素t，insert中的迭代器pos只能是begin()或end()否则会报错，似乎不止其他的迭代器
判空	empty(void)	容器判空

### Vector浅析

vector的最重要的实现组成其实只有三个指针，上源码：

// CLASS TEMPLATE vector
template<class _Ty,class _Alloc = allocator<_Ty>>
class vector : public _Vector_alloc<_Vec_base_types<_Ty, _Alloc>>
{	
    //...
}

类体这里就省略了，如果仔细看源码就会发现vector的类体里主要实现的大多只是一些供外部调用的函数而已，而vector的最底层的一些实现其实在它的基类中就已经完成了，如_Vector_alloc类，而_Vector_alloc中也没有包含最重要的三个指针，我们在vector.cpp中搜索_Myfirst可以发现，_Myfirst,_Mylast,_Myend三个指针在_Vector_val这个类中，而_Vector_alloc中包含了对_Vector_val的操作。

// CLASS TEMPLATE _Vector_val
template<class _Val_types>
class _Vector_val : public _Container_base
{	// base class for vector to hold data
public:
	using value_type = typename _Val_types::value_type;
	using size_type = typename _Val_types::size_type;
	using difference_type = typename _Val_types::difference_type;
	using pointer = typename _Val_types::pointer;
	using const_pointer = typename _Val_types::const_pointer;
	using reference = value_type&;
	using const_reference = const value_type&;

	_Vector_val()
		: _Myfirst(),
		_Mylast(),
		_Myend()
		{	// initialize values
		}

	pointer _Myfirst;	// pointer to beginning of array
	pointer _Mylast;	// pointer to current end of sequence
	pointer _Myend;	// pointer to end of array
};

在vector中有两个关键的数字，size与capacity，其中size=_Mylast-_Myfirst，capacity=_Myend-Myfirst，三个指针指向的内存位置如下：

size的计算源码：

_NODISCARD size_type size() const noexcept
{	// return length of sequence
	return (static_cast<size_type>(this->_Mylast() - this->_Myfirst()));
}

capacity的计算源码：

_NODISCARD size_type capacity() const noexcept
{	// return current length of allocated storage
	return (static_cast<size_type>(this->_Myend() - this->_Myfirst()));
}

我们都知道vector的性能优越，而支撑着vector的优越性能的就是这两数据，size和capacity，size是vector中实际元素的个数，即vector总容量中的已用容量(used部分)，而capacity则是vector初始化时设置的总容量(等于used部分加unsed部分)，C++分配给vector的实际内存总是比定义时的要大一点，这是因为vector占用的内存是一整块连续的内存，预分配多一些内存可以降低vector之后的二次分配时的时间成本。所以capacity>=size，档capacity=size时表示容易已满，若需要继续添加元素则需要整体移动vector，此时花费的成本会较高，所以种情况应尽量避免。

5.deque容器

• deque容器是一个双端数组，在双端数组的两端均可以插入和删除元素
• 使用deque容器需要包头文件#include<deque>

deque容器可以说是vector容器的升级版，deque的用法基本和vector一致，但是deque不仅提供push_back()，pop_back()还提供 push_front() 和 pop_front()。

6.stack容器

• stack容器是一个栈模型
• 使用stack容器需要包含头文件#include<stack>

stack常用方法

函数	作用
push(T t)	元素入栈顶
pop()	栈顶元素出栈
top()	获取栈顶元素

7.queue容器

• queue容器是一个队列模型
• 使用queue容器需要包含头文件#include<queue>

queue常用方法

函数	作用
push(T t)	元素入队尾
pop()	队首元素出队
front()	获取队首元素，既可以作左值也可以作右值
back()	获取队尾元素，既可以作左值也可以作右值

8.list容器

• list容器是一个双向链表模型，可以高效的进行元素的插入和删除操作
• list容器不支持随机访问，即不支持[],at()和iterator + n(如：begin()+1)等形式的访问
• 使用list容器需要包含头文件#include<list>

list容器除了不支持随机访问外，用法和deque容器的用法基本一致，除此之外list容器还提供一个 remove(T t)函数来根据元素内容删除元素

使用list容器时有一点需要注意 list容器在使用erase删除元素时，遵循左闭右开的原则，如：

list<int> li;
for (int i = 0; i < 5; i++)
	li.push_back(i);
for (list<int>::iterator it = li.begin(); it != li.end(); it++)
	cout << *it;
cout << endl;
list<int>::iterator it1 = li.begin();//it1指向元素0
list<int>::iterator it2 = li.begin();
it2++; it2++; it2++;//此时it2指向元素3
li.erase(it1, it2);
for (list<int>::iterator it = li.begin(); it != li.end(); it++)
	cout << *it;
cout << endl;

输出结果：

01234
34

可以看到erase在删除0-3的元素时删除了0，1，2而没有删除3，即左闭右开。

list浅析

list在实现结构上和vector很类似，只是list比vector多了一个_List_buy中间层，list的实现的核心组成有两个，_List_val和_List_node前者主要与数据结构规模和头节点相关，后者主要与数据存储、prev和next相关。上_List_val的源码：

template<class _Val_types>
class _List_val : public _Container_base
{	// base class for list to hold data
public:
	using _Nodeptr = typename _Val_types::_Nodeptr;

	using value_type = typename _Val_types::value_type;
	using size_type = typename _Val_types::size_type;
	using difference_type = typename _Val_types::difference_type;
	using pointer = typename _Val_types::pointer;
	using const_pointer = typename _Val_types::const_pointer;
	using reference = value_type&;
	using const_reference = const value_type&;

	_List_val()
		: _Myhead(),
		_Mysize(0)
		{	// initialize data
		}

	_Nodeptr _Myhead;	// pointer to head node
	size_type _Mysize;	// number of elements
};

可以看到list中包含了一个指向头节点的指针_Myhead，也就是说即使我们创建的一个空list也至少包含一个空的头节点，list使用头节点的目的就是更方便的构建容器，_Mysize记录的就是list的当前元素个数。

list节点_List_node`的底层数据结构是一个结构体：

template<class _Value_type,class _Voidptr>
struct _List_node
{	// list node
	using _Nodeptr = _Rebind_pointer_t<_Voidptr, _List_node>;
	_Nodeptr _Next;	// successor node, or first element if head
	_Nodeptr _Prev;	// predecessor node, or last element if head
	_Value_type _Myval;	// the stored value, unused if head

	_List_node& operator=(const _List_node&) = delete;

	template<class _Alloc>
	static void _Freenode0(_Alloc& _Al, _Nodeptr _Ptr) noexcept
	{
		using _Alnode = _Rebind_alloc_t<_Alloc, _List_node>;
		using _Alnode_traits = allocator_traits<_Alnode>;
		_Alnode _Node_alloc(_Al);
		_Alnode_traits::destroy(_Node_alloc, _STD addressof(_Ptr->_Next));
		_Alnode_traits::destroy(_Node_alloc, _STD addressof(_Ptr->_Prev));
		_Alnode_traits::deallocate(_Node_alloc, _Ptr, 1);
	}
};

_List_node的核心组成就是_Next，_Prev，_Myval，_Next是下一个节点的指针，_Prev是指向上一个节点的指针，_Myval是存储数据的容器。

9.priority_queue容器

• priority_queue容器是一个具有优先级的队列，又叫优先级队列适配器，分为最大优先级队列和最小优先级队列两种

• priority_queue容器是一种特殊的queue容器，所以也需要包含头文件#include<queue>

默认的定义priority_queue<T> pr的优先级队列是最大优先级队列，显示定义最小优先级队列：priority_queue<int,vector<int>,less<int>> pr，less是一个谓词后面再学习，显示定义最大优先级队列：priority_queue<int,vector<int>,greater<int>> pr，其中使用greater需要包含头文件#include<functional>。

priority_queue容器的用法基本和queue一致，除此之外，priority_queue容器提供一个top()函数来获取队首元素，而queue容器没有这个方法。

示例：

priority_queue<int,vector<int>,greater<int>> pr;
pr.push(12);
pr.push(4);
pr.push(10);
pr.push(20);
cout << "最小元素：" <<pr.top() << endl;
while (pr.size() > 0)
{
	cout << pr.top() << ",";
	pr.pop();
}

输出结果：

最小元素：4
4,10,12,20,

10.set容器

• set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排序，元素的插入过程是按排序规则插入，所以不能指定位置插入
• set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树，在插入和删除操作上比vector容器速度更快
• set容器不支持[]和at()来存取元素
• set不支持直接修改容器中的元素，因为元素是自动排序的，如果希望修改一个元素值，就必须删除这个元素再插入新元素
• 要使用set容器需要包含头文件#include<set>

set容器的基本特性

默认情况下，直接定义的set容器采用最小优先排序，和priority_queue容器恰好相反，set<T> se就是隐式的set<T,less<T>> se，定义最大优先排序的set容器需要显示定义：set<T,greater<T>> se。

我们来看一个例子：

set<string,greater<string>> se;//采用最大优先排序
for (int i = 0; i < 5; i++)//生成随机字符串元素
{
	int tmp = rand();
	string str = "";
	while (str.length()<=3)
	{
		if(tmp >= 97 && tmp <= 122)
			str += tmp;
		tmp = rand();
	}
	se.insert(str);
}
se.insert("strs");//插入相同的字符串元素
se.insert("strs");
se.insert("strs");
for (set<string, greater<string>>::iterator it = se.begin(); it != se.end(); it++)
	cout << *it << endl;

输出结果：

wqye
vfep
strs
omsk
kfnm
cdsb

可以看到，容器里的字符串确实按照字符串的比较规则按从大到小的顺序排列着，并且无论我们插入多少个相同的元素，在容器内只会存储一个相同的元素值。

值得注意的是：

set容器只提供了insert(T t)函数来插入元素。

自定义元素的排序

自定义类作元素可能会出现类中有多个字段，而我们需要其中的某一个字段来作为关键字在set容器中排序，要实现这样的行为，我们就需要用到仿函数了。

什么是仿函数？

仿函数实质上就是一个做了()重载的结构体，因为重载了()使用起来类似函数，所以称之为仿函数。

我们来看一个例子：

class Student
{
public:
	string name;
	int age;
	bool isStudent;
	Student(const string name, const int age, const bool isStudent)
	{
		this->age = age;
		this->name = name;
		this->isStudent = isStudent;
	}
};
struct AgeSort//仿函数
{
	bool operator()(const Student &lift, const Student &right)
	{
		return (lift.age < right.age);
	}
};
int main()
{
	set<Student, AgeSort> se;
	Student s1("Alian", 23, true);
	Student s2("Blank", 20, true);
	Student s3("Cary", 43, false);
	Student s4("Davel", 23, true);
	se.insert(s1); se.insert(s2);
	se.insert(s3); se.insert(s4);
	for (set<Student, AgeSort>::iterator it = se.begin(); it != se.end(); it++)
		cout << it->name << "\t" << it->age << "\t" << it->isStudent << endl;
	system("pause");
	return 0;
}

输出结果：

Blank   20      1
Alian   23      1
Cary    43      0

其中AgeSort就是仿函数，它的比较关键字是Student.age，所以set容器对象se会以age作为排序关键字，其实我们之前使用的less<>和greater<>也是反函数，只不过是C++预定义好的仿函数。

细心的朋友可能会发现，我们插入的s4对象居然不再容器里！！！这是因为set容器中的元素具有唯一性，而set容器是通过关键字来识别元素的，所当碰到关键字相同的元素时，set只会存储一个元素。

那么这种情况该怎么解决呢？答案是set容器没有办法解决这种情况，如果有出现这种情况，就不能使用set容器而改用multiset容器。

在后面的算法模块我们详细介绍仿函数。

set常用函数

函数	作用
find(T t)	查找元素t，返回指向t元素的迭代器，查找失败返回指向set.end()的迭代器
count(T t)	返回容器中元素t的个数，值要么是0，要么是1
lower_bound(T t)	返回一个指向>=t元素的迭代器，如果t存在则指向t，如果t不存在则指向t后面的一个元素
upper_bound(T t)	返回一个指向>t元素的迭代器，即t元素后面的一个元素
equal_range(T t)	返回一个包含两个set类型的迭代器的对组pair<set::iterator,set::iterator>第一个迭代器指向t元素，第二个迭代器指向t后面的一个元素，如果t不存在，则两个迭代器都指向t后面的一个元素

 小知识

事实上容器中的insert函数是有返回值的，insert的返回值是一个对组(pair)类型的泛型pair<set<T>::iterator, bool>的对象，pair是一个只有两个字段的模板，我们可以直接定义pair<set<T>::iterator, bool>类型对象来接收insert函数的返回值，如：

pair<set<Student,AgeSort>::iterator, bool> pait=se.insert(s1);

 我们可以通过pair.first和pair.second来访问对组中的两个元素，通过pair.first来访问对组中的第一个元素set<Student,AgeSort>::iterator类型的迭代器，通过pair.first->first，和pair.first->second可以访问迭代器所指向的容器元素，我们通过pair.second来访问对组中的第二个元素，bool型的元素记录的是insert函数插入是否成功，如果插入成功则记录true，否则记录false。

11.multiset容器

• multiset容器可以说是set容器的升级版，multiset容器支持多个相同键值的元素的存储，所以要使用multiset需要包含头文件#include<set>

multiset的用法和set一致。

12.map容器

• map是标准的关联式容器，一个map元素是一个键值对(key,value),map提供基于键值的快速检索能力
• map中 key值是唯一的
• map容器中的元素也是按一定顺序排列的，元素插入过程是按排序规则插入的，所以不能指定位置插入
• map容器的具体实现也是采用红黑二叉树变体的平衡二叉树的数据结构，在插入和删除的操作上比vector更快
• 与set不同的是map支持直接存取key值对应的value，也支持[]操作符
• 要使用map容器就需要包含头文件#include<map>

map的元素插入

int main()
{
	map<int, string> ma;
	//方法一
	ma.insert(pair<int, string>(1, "pair"));
	ma.insert(pair<int, string>(1, "pair_02"));
	//方法二
	ma.insert(make_pair(2, "make_pair"));
	ma.insert(make_pair(2, "make_pair_02"));
	//方法三
	ma.insert(map<int, string>::value_type(3, "value_type"));
	ma.insert(map<int, string>::value_type(3, "value_type_02"));
	//方法四
	ma[4] = "map";
	ma[4] = "map_02";
	for (map<int, string>::iterator it = ma.begin(); it != ma.end(); it++)
		cout << it->first << "\t" << it->second << endl;
	system("pause");
	return 0;
}

输出结果：

1       pair
2       make_pair
3       value_type
4       map_02

上面四种方法都可以向map容器里添加元素，但是四者中也有一些微小的区别，前面三种方法在插入相同键值时，只会保存第一存储的结果，之后插入相同键值的元素时都会插入失败，而第四种方法则是后面赋值的元素覆盖前面赋值的元素。

map似乎没办法来指定是从大到小排序或是从小到大排序

map除了元素的形式不同，在其他方面map的用法基本和set一致

13.multimap容器

multimap容器和multiset容器一样，是map容器的升级版，支持一个键对应多个值，所以multimap的一个重要应用场景就是数据分组。

14.容器在使用过程必须要注意的地方

 因为在将元素添加到容器里时，C++执行的是容器的默认的拷贝构造函数，将元素拷贝到容器里，这个过程是一个浅拷贝，既然是浅拷贝就会面临浅拷贝的两次内存释放的问题，尤其是类元素，所以在添加一些具有指针字段的元素到容器里时，一定在类里定义一个深拷贝的拷贝构造函数和=的重载函数。

15.各个容器的比较

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

三、算法

1.算法

​ 函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而C++通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL就利用了这一点提供了相当多的有用算法。它是在一个有效的框架中完成这些算法的–可以将所有的类型划分为少数的几类，然后就可以在模版的参数中使用一种类型替换掉同一种类中的其他类型。

STL提供了大约100个实现算法的模版函数，比如算法for_ each 将为指定序列中的每一个元素调用指定的函数，stable_ _sort 以你所指定的规则对序列进行稳定性排序等等，这样一-来,只要熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一-两个算法模板，就可以完成所需要的功能并大大地提升效率。

算法部分主要由头文件<algorithm>, <numeric>和<functional>组成。<algorithm>是所 有STL头文件中最大的一个(尽管它很好理解)，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functional>中则定义了一些模板类，用以声明函数对象。

2.算法的分类

非可变序列算法

计数算法：count,count_if等

搜索算法：search,find,find_if,find_list_of等

比较算法：equal,mismatch,lexicographical_compare等

可变排序算法

删除算法：remove,remove_if,remove_copy等

修改算法：for_each,transform等

排序算法：sort,stable_sort,partial_sort等

3.仿函数

4.一些常用的算法模板

find算法

原型:iterator find(iterator begin,iterator end,T t)

在容器的begin迭代器所指向的位置开始到end所指向的位置结束，查找元素t，如果找到了，则返回指向t的迭代器。

四、迭代器

1.迭代器

​ 迭代器从作用上来说是最基本的部分，可是理解起来比前两者都要费力一些。软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在 STL中就是用迭代器来完成的。概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。几乎STL提供的所有算法都是通过送代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的选代器，用以存取容器中的元素。

​ 迭代器部分主要由头文件<utility>,<iterator>和<memory>组成。<utility>是-一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明，<iterator>中提供 了迭代器使用的许多方法，而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类alocator,它负责产生所有容器中的默认分配器。

2.迭代器的基本原理

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

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

• 迭代器就如同一个指针

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

3.迭代器的分类

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

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

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

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

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