标准模板库（STL）

STL

标准模板库（Standard Template Library，STL）是一个基于模板的容器类库。可用STL创建一个类，为任意数据类型定义矢量、链表、队列和栈等操作。STL中的泛型算法（generic algorithm）和函数对象（function object）使算法摆脱了对不同数据类型个性操作的依赖。

STL主要提供三类工具：容器、迭代器和算法。

---

目录

（一）容器类

（1）顺序容器

（2）关联容器

（3）容器适配器

（二）迭代器

（三）泛型算法

count()算法

count_if()算法

函数对象

---

---

（一）容器类

容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素、删除元素、查找元素等操作，这些成员函数通过返回迭代器来指定元素在序列中的位置。容器中提供了很多接口，许多基本操作是所有容器都适用的，而这些操作则适用于类似容器的子集，可以用有类似操作的新类来扩展STL。

STL容器分为三大类：顺序容器、关联容器及容器适配器。

STL容器类

标准库容器类	说明
顺序容器	voctor（矢量）	从后面快速插入与删除，直接访问任何元素
list（双向链表）	从任何地方快速插入与删除
deque（双端队列）	从前面或后面快速插入与删除，直接访问任何元素
关联容器	set（集合）	快速查找，不允许重复值
multiset（多重集合）	快速查找，允许重复值
map（映射）	一对一映射，基于关键字快速查找，不允许重复值
multimap（多重映射）	一对多映射，基于关键字快速查找，允许重复值
容器适配器	stack（栈）	后进先出（LIFO）
queue（队列）	先进先出（FIFO）
priority_queue（优先级队列）	最高优先级元素总是第一个出列

（1）顺序容器

vector类和deque类以数组为基础，list类以双向链表为基础。

vector类的特点：

• 提供具有连续内存地址的数据结构，可通过下标运算符[ ]直接有效的访问矢量的任何元素。
• 可以在能够使用数组的任意地方使用，但比数组操作更为简单便捷。
• 使用数组必须管理其大小，而使用vector容器时，管理容量和大小的工作自动完成。
• 当容器的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。
• 定义在头文件 vector.h 中。

容器声明形式如下：

vector<int> vi;            //定义存放整形序列的矢量容器，长度为0的空 vector
vector<float> vf(10);      //定义存放实形序列的矢量容器，10个初始化为0的元素 vector<double> vd(10,3.14);//定义存放实形序列的矢量容器，10个初始化3.14元素
vector<char*> vstr;        //定义存放字符串序列的矢量容器
vector<Box> vBox(20);      //定义存放20个盒子对象的矢量容器

//实例化特定矢量容器时自动调用如下构造函数：
vector(size_t n);          //构造一个有n个元素的矢量，每个元素都是由默认的构造函数所建立
vector(size_t n,T& V);     //T表示矢量的基本类型，为每个元素用同一个对象V来赋初值。类型T中至少要包括默认构造函数和复制构造函数才能被vector容器接收，有时需要重载复制运算符和比较运算符
vector(first,last);        //元素的初值由区间[first,last)指定的序列中的元素复制而来
vector(vector<T>& X);      //复制构造函数

测试STL中的vector的功能：

// STLVectorTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
typedef vector<int> INTVECTOR;					//typedef定义一种类型的别名

int main()
{
	INTVECTOR vec1;					//vec1对象初始为空
	INTVECTOR vec2(10,6);			//vec2对象最初有10个值为6的元素
	INTVECTOR vec3(vec2.begin(),vec2.begin() + 3);//vec3对象最初有3个值为6的元素
	INTVECTOR::iterator i;			//声明一个名为 i 的双向迭代器

	//从前向后显示vec1中的数据
	cout<<"vec1.begin()--vec1.end():"<<endl;
	for(i = vec1.begin(); i != vec1.end(); ++ i)//begin()返回指向容器最开始位置数据的指针
		cout<< *i <<" ";						//end()返回指向容器的结尾，且值为空
	cout<<endl;

	//从前向后显示vec2中的数据
	cout<<"vec2.begin()--vec2.end():"<<endl;
	for(i = vec2.begin(); i != vec2.end(); ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//从前向后显示vec3中的数据
	cout<<"vec3.begin()--vec3.end():"<<endl;
	for(i = vec3.begin(); i != vec3.end(); ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//测试添加和插入成员函数
	vec1.push_back(2);		//push_back()在vector尾部加入一个数据
	vec1.push_back(4);

	vec1.insert(vec1.begin() + 1, 5);//insert()将5插入到列表中的vec1.begin() + 1位置
	vec1.insert(vec1.begin() + 1, vec3.begin(), vec3.end());//insert()将vec3的所有值插入到列表中的vec1.begin() + 1位置
	cout<<"push() and insert():"<<endl;
	for(i = vec1.begin(); i != vec1.end(); ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//测试赋值成员函数
	vec2.assign(8, 1);//给vector重新分配新的内容，新的容器一共有8个元素，每一个元素都初始化为1的拷贝
	cout<<"vec2.assign(8, 1):"<<endl;
	for(i = vec2.begin(); i != vec2.end(); ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//测试引用类函数
	cout<<"vec1.front()="<<vec1.front()<<endl;	//返回当前vector容器中起始元素的引用
	cout<<"vec1.back()="<<vec1.back()<<endl;	//返回当前vector容器中末尾元素的引用。
	cout<<"vec1.at(5)="<<vec1.at(5)<<endl;		//返回5首次出现的位置
	cout<<"vec1[4]="<<vec1[4]<<endl;			//返回4位置处的值

	//测试移出和删除函数
	vec1.pop_back();							//pop_back()在vector尾部移出一个数据
	vec1.erase(vec1.begin() + 1, vec1.end() - 2);//删除 [vec1.begin() + 1,vec1.end() - 2) 范围内位置处的值
	cout<<"vec1.pop_back() and vec1.erase():"<<endl;
	for(i = vec1.begin(); i != vec1.end(); ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//显示序列的状态信息
	cout<<"vec1.capacity()="<<vec1.capacity()<<endl;//指在发生realloc前能允许的最大元素数，即预分配的内存空间或存放过最多数据元素数
	cout<<"vec1.max_size()="<<vec1.max_size()<<endl;//STL容器允许的最大元素数
	cout<<"vec1.size()="<<vec1.size()<<endl;		//当前vector容器真实占用的大小，也就是容器当前拥有多少个元素
	cout<<"vec1.empty()="<<vec1.empty()<<endl;		//检查当前容器是否为空，空返回1，否则返回0

	//vector序列容器的运算
	cout<<"vec1==vec3:"<<(vec1==vec3)<<endl;
	cout<<"vec1<=vec3:"<<(vec1<=vec3)<<endl;
	cout<<"vec2<=vec3:"<<(vec2<=vec3)<<endl;
	cout<<"vec1<=vec2:"<<(vec1<=vec2)<<endl;	//从 [0] 开始比较，如果相同继续比较；如果不同直接按照大小给出最后结果大小
	return 0;
}

结果
vec1.begin()--vec1.end():

vec2.begin()--vec2.end():
6 6 6 6 6 6 6 6 6 6
vec3.begin()--vec3.end():
6 6 6
push() and insert():
2 6 6 6 5 4
vec2.assign(8, 1):
1 1 1 1 1 1 1 1
vec1.front()=2
vec1.back()=4
vec1.at(5)=4
vec1[4]=5
vec1.pop_back() and vec1.erase():
2 6 5
vec1.capacity()=6
vec1.max_size()=1073741823
vec1.size()=3
vec1.empty()=0
vec1==vec3:0
vec1<=vec3:1
vec2<=vec3:1
vec1<=vec2:0
请按任意键继续. . .

list类的特点：

• 双向链表组成。
• 有两个指针域，可以向前和向后进行访问，不能随机访问。即支持的迭代器为双向迭代器。
• 不能使用下标运算符 [ ]。
• 定义在头文件<list>中。
• 有多种构造函数，与vector类形式相同。

deque类的特点：

• 是序列容器，与vector容器十分相似，其中保存的元素必须类型相同。
• 允许在序列两头添加数据。
• 提供了在序列中插入和删除元素的函数。
• 支持随机访问元素。
• 元素数目可动态变化，即它可以自动进行内存管理。

deque与vector的区别：

• deque以指针数组的方法访问元素，而vector以数组的方式存放元素。
• 对于插入删除操作，deque容器执行的效率更高。
• 在deque序列的头部或尾部插入或移走元素的时间为常数。
• deque没有类似vector中的capacity()和reserve()这类函数。

（2）关联容器

关联容器中每个元素在容器的位置与其他元素相关，容器总是按元素的键（key)的大小自动排序。

set容器的特点：

• 是唯一性关联容器，即容器中任何两元素都不相同。
• 输入set容器的元素会自动按大小排序，适合使用STL的set类的算法包括：set_union(),set_intersection(),set_difference()等
• 使用set容器提供的插入和删除元素的功能时，能保持指向元素的迭代器继续有效。
• 容器及相关成员函数定义在<set>中。
• set是类模板。
• 容器中没有两个相同元素，如果插入的新元素与原元素相同，则将被忽略。

// STLSetTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <set>
using namespace std;

//创建set模板的实例
typedef set<int> SET_INT;

//put_HTest函数，从头向尾显示set容器的所有元素
void put_HTset(SET_INT set1, char *name)
{
	SET_INT::iterator it;

	cout<<name<<":";
	cout<<"Head to Tail=";
	for(it = set1.begin(); it != set1.end(); ++ it)
		cout<<(*it)<<" ";
	cout<<endl;
}

//put_THest函数，从尾向头显示set容器的所有元素
void put_THset(SET_INT s1, char *name)
{
	SET_INT::reverse_iterator i;

	cout<<name<<":";
	cout<<"Tail to Head=";
	for(i = s1.rbegin(); i != s1.rend(); i ++)	//rbegin和rend反向迭代器
		cout<<(*i)<<" ";
	cout<<endl;
}

int main()
{
	int i;
	//声明set的对象和迭代器
	SET_INT s1;				//容器初始为空
	SET_INT::iterator it;

	//向s1对象中插入值
	for(i = 1; i < 20; i = i + 2)
	{
		s1.insert(i);
	}

	//正向显示s1中的数值
	put_HTset(s1,"s1");

	//反向显示s1中的数值
	put_THset(s1,"s1");

	//构造含有元素的序列并显示
	SET_INT s2(s1);
	put_HTset(s2,"s2");

	//删除s2的第2个元素并显示
	s2.erase(++ s2.begin());
	put_HTset(s2,"s2");

	//向s2插入8和9并显示
	s2.insert(8);
	s2.insert(9);
	put_HTset(s2,"s2");

	//清空s3的序列
	s2.clear();
	put_HTset(s2,"s2");

	//按关键给定的区间显示序列中的元素
	cout<<"[s1.lower_bound(5),s1.upper_bound(15)]:";
	for(it = s1.lower_bound(4); it != s1.upper_bound(16); it ++)
		cout<<(*it)<<" ";
	cout<<endl;

	//显示s1的状态信息
	cout<<"s1.size():"<<s1.size()<<endl;			
	cout<<"s1.max_size():"<<s1.max_size()<<endl;
	cout<<"s1.count(15):"<<s1.count(15)<<endl;		//元素为15的个数

	//交换两个set容器的元素并显示
	s1.swap(s2);
	put_HTset(s1,"s1");
	put_HTset(s2,"s2");

	//关系运算
	s1.insert(5);
	cout<<"s1>s2="<<(s1>s2)<<endl;

	return 0;
}

结果
s1:Head to Tail=1 3 5 7 9 11 13 15 17 19
s1:Tail to Head=19 17 15 13 11 9 7 5 3 1
s2:Head to Tail=1 3 5 7 9 11 13 15 17 19
s2:Head to Tail=1 5 7 9 11 13 15 17 19
s2:Head to Tail=1 5 7 8 9 11 13 15 17 19
s2:Head to Tail=
[s1.lower_bound(5),s1.upper_bound(15)]:5 7 9 11 13 15
s1.size():10
s1.max_size():1073741823
s1.count(15):1
s1:Head to Tail=
s2:Head to Tail=1 3 5 7 9 11 13 15 17 19
s1>s2=1
请按任意键继续. . .

multiset容器的特点：

• multiset 与 set使用方式基本相同，最大的不同就是  multiset 允许元素有重复。
• 元素在序列中是有序的。每插入一个元素，容器都会按照其键值的大小顺序插入序列的适当位置。
• 允许插入和删除元素，并保持指向已有元素的迭代器继续有效。

map容器的特点：

每个元素都使由类型为Key的键和类型为Data的数据相关联构成的数据对。

map 保存元素的键是唯一的。

元素按键的大小关系自动排序，与插入先后顺序无关。

插入新元素不会使已有的迭代器失效，删除元素也不会使迭代器无效，除非该迭代器指向了被删除的对象。

// STLMapTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>

using namespace std;

//创建map的实例，整数（int）映射字符串（string）
typedef map<int, string> INT2STRING;

int _tmain(int argc, _TCHAR* argv[])
{
	//创建map对象theMap
	INT2STRING theMap;
	INT2STRING::iterator theIterator,it;

	//向theMap容器中添加数据，数字和字符串配对
	//每个元素是一个映射对
	theMap.insert(INT2STRING::value_type(0,"Zero"));
	theMap.insert(INT2STRING::value_type(2,"Two"));
	theMap.insert(INT2STRING::value_type(4,"Four"));

	//显示map容器的所有对象
	cout<<"theMap.begin()--theMap.end():"<<endl;
	for(theIterator = theMap.begin();theIterator!=theMap.end();++ theIterator)
	{
		cout<<(*theIterator).first;
		cout<<","<<(*theIterator).second<<" ";
	}
	cout<<endl;

	//测试map容器的唯一性	
	theMap.insert(INT2STRING::value_type(1,"One"));

	//下列语句不能插入到map容器中
	theMap.insert(INT2STRING::value_type(0,"Zero1"));
	theMap.insert(INT2STRING::value_type(4,"AAA"));

	//显示map容器的所有对象
	cout<<"theMap.begin()--theMap.end():"<<endl;
	for(theIterator = theMap.begin();theIterator!=theMap.end();++ theIterator)
	{
		cout<<(*theIterator).first;
		cout<<","<<(*theIterator).second<<" ";
	}
	cout<<endl;

	//显示theMap的状态信息
	cout<<"theMap.size():"<<theMap.size()<<endl;			
	cout<<"theMap.max_size():"<<theMap.max_size()<<endl;
	cout<<"theMap.count(15):"<<theMap.count(15)<<endl;		//元素为15的个数

	//从键盘上输入数字，显示对应的字符串
	string theString = "";
	int index;
	for(;;)
	{
		cout<<"Enter \"q\" to quit, or enter a Number:";
		cin>>theString;
		if(theString == "q")
			break;

		for(index = 0; index < theString.length(); index ++)
		{
			theIterator = theMap.find(theString[index] - '0');
			if(theIterator != theMap.end())
				cout<<(*theIterator).second<<" ";
			else
				cout<<"[err] ";
		}
		cout<<endl;
	}

	return 0;
}

结果
theMap.begin()--theMap.end():
0,Zero 2,Two 4,Four
theMap.begin()--theMap.end():
0,Zero 1,One 2,Two 4,Four
theMap.size():4
theMap.max_size():119304647
theMap.count(15):0
Enter "q" to quit, or enter a Number:3
[err]
Enter "q" to quit, or enter a Number:12
One Two
Enter "q" to quit, or enter a Number:444
Four Four Four
Enter "q" to quit, or enter a Number:q
请按任意键继续. . .

（3）容器适配器

容器适配器包括栈、队列和优先级队。栈（stack）是为堆栈而设计的专用容器，具有后进先出的特性，主要包括压栈和弹出。

适配器的特点：

适配器不独立，它依附在一个顺序容器上。例如声明一个用矢量容器实现的字符型堆栈： stack<vector<char>> sk;

适配器没有自己的构造和析构函数。其中，队列（queue）默认用deque问基础，栈（stack）可用vector或deque为基础。

stack类模板声明在<stack>中。

// STLStackTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <stack>

using namespace std;

typedef stack<int> STACK_INT;

int _tmain(int argc, _TCHAR* argv[])
{
	STACK_INT stack1;
	int i;

	//判断栈是否为空
	cout<<"stack1.empty() returned "<<(stack1.empty()?"true":"false")<<endl;

	//入栈
	for(i = 0; i < 10; i = i + 2)
		stack1.push(i);

	//top()函数
	if(!stack1.empty())
		cout<<"stack1.top() returned "<<stack1.top()<<endl;
	
	//计算栈的长度
	cout<<"stack1.size():"<<stack1.size()<<endl;

	//改变栈顶的值为20
	if(!stack1.empty())
	{
		cout<<"stack1.top()=20; "<<endl;
		stack1.top()=20;
	}

	//弹出栈中所有的数据并显示
	cout<<"stack1:";
	while(!stack1.empty())
	{
		cout<<stack1.top()<<" ";
		stack1.pop();
	}
	cout<<endl;

	return 0;
}

结果
stack1.empty() returned true
stack1.top() returned 8
stack1.size():5
stack1.top()=20;
stack1:20 6 4 2 0
请按任意键继续. . .

（二）迭代器

迭代器是指针概念的泛型化，它指向容器中的元素。迭代器可以包括指针，但它又不仅仅是一个指针。迭代器把算法与容器连接起来，算法本身与容器无关，只是间接通过迭代化器操作容器元素。迭代器主要有四种类型：输入输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。

STL中普通类型迭代器按照基本访问功能主要分为五种，根据功能灵活性分为四级（输入输出为一级），功能最强且最灵活的是随机访问迭代器。

迭代器属性

标准库迭代子类型	说明
输入 InputIterator	从容器中读取元素，输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开始
输出 OutputIterator	向容器写入元素，输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始
正向 ForwardIterator	组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始
双向 BidirectionalIterator	组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）
随机访问 RandomAccessIterator	组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后调任意个元素

迭代子可执行的操作

迭代操作	说明
所有迭代子 ++p p++	前置自增迭代子，先++后使用 后置自增迭代子，先使用后++
输入迭代子 *p p = p1 p == p1 p != p1	间接引用迭代子，作为右值 将一个迭代子赋给另一个迭代子 比较迭代子的相等性 比较迭代子的不等性
输出迭代子 *p p = p1	间接引用迭代子，作为左值 将一个迭代子赋给另一个迭代子
正向迭代子	提供输入和输出迭代子的所有功能
双向迭代子 --p p--	包含正向迭代子所有功能，再增加 先--再使用，前置自减迭代子 先使用后--，后置自减迭代子
随机访问迭代子 p += i p -= i p + i p - i p[i] p < p1 p <= p1 p >= p1 p > p1	包含双向迭代子所有功能，再增加 迭代子p递增i位（后移i位）（p本身变） 迭代子p递减i位（前移i位）（p本身变） 在p所在位置后移i位后的迭代子（迭代子p本身不变） 在p所在位置前移i位后的迭代子（迭代子p本身不变） 返回与p所在位置后移i位的元素引用 如迭代子p小于p1，返回true，所谓小，即p在p1之前 如迭代子p小于等于p1，返回true，否则返回false 如迭代子p大于等于p1，返回true，所谓大，即p在p1之后 如迭代子p大于p1，返回true，否则返回false

STL中迭代器的使用：

// STLIteratorTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <list>
#include <numeric>

using namespace std;

//创建一个list容器的实例LISTINT，其存放Int型数据
typedef list<int> LISTINT;

int _tmain(int argc, _TCHAR* argv[])
{
	//用LISTINT创建一个名为listOne的list对象
	LISTINT listOne;
	//指定 i 为迭代器变量
	LISTINT::iterator i;			//迭代器
	LISTINT::reverse_iterator ir;	//反向迭代器

	//从前面向listOne容器中添加数据
	listOne.push_front(2);
	listOne.push_front(1);

	//从后面向listOne容器中添加数据
	listOne.push_back(3);
	listOne.push_back(4);

	//从前向后显示listOne中的数据
	for(i = listOne.begin();i != listOne.end();  ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//从后向前显示listOne中的数据
	for(ir = listOne.rbegin();ir != listOne.rend();  ++ ir)
		cout<< *ir <<" ";
	cout<<endl;

	//从键盘上输入数据
	for(i = listOne.begin();i != listOne.end();  ++ i)
	{
		cout<< "listOne:";
		cin>>(*i);
	}

	//从前向后显示listOne中的数据
	for(i = listOne.begin();i != listOne.end();  ++ i)
		cout<< *i <<" ";
	cout<<endl;

	//bidirectional迭代器不允许加减运算
	//i = listOne.begin() + 1;
	return 0;
}

结果
1 2 3 4
4 3 2 1
listOne:5
listOne:10
listOne:15
listOne:20
5 10 15 20
请按任意键继续. . .

（三）泛型算法

算法为迭代器访问的对象组提供了计算和分析的函数。在模板中算法不依赖于具体的数据类型，而泛型算法更进一步不依赖于具体的容器，它们应用于可以通过迭代器访问的任何序列。泛型算法中采用函数对象引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，是STL 效率更高。

算法是STL中最大的工具集合。主要分三类：

算法操作分类

不修改序列的操作	find()、find_end()、find_first()、adjacent_find()、cout()、equal()、mismatch()、search()等
修改序列的操作	swap()、copy()、transform()、replace()、remove()、reverse()、rotate()、fill()等
排序、合并和相关操作	sort()、stable_sort()、binary_search()、merge()、min()、max()等

典型算法：

• 查找算法：有13种，各种策略判断容器中是否存在指定值。equal_range()、lower_bound()、upper_bound()提供折半查找形式。
• 排序和通用整序算法：有14种。整序是按一定规律分类，如分割算法把容器分两组，一组满足条件的元素组成，其余为另一组。
• 删除和代替算法：有15种。
• 排列组合算法：有2种。排列组合是指全排列。如{a,b,c}有6种按顺序的全排列为 abc.acb.bac.bca.cab.cba。abc最小，cba最大。
• 生成和改变算法：有6种。包含生成（generate）和填充（fill）等。
• 关系算法：有7种。为比较两个容器提供了各种策略，包括相等（equal()），最大（max()），最小（min()）等等。
• 集合算法：有4种。并(union)、交(intersection)、差(difference)、对称差(symmetric difference)。
• 堆算法：有4种。堆是以数组来表示二叉树的一种形式。标准库提供大顶堆（max_heap)，每个结点关键字都大于其子节点。
• 算术算法：有4种。要求包含头文件<numeric>

所有泛型算法的前两个实参是一对 iterator ，通常称为 first 和 last，它们标出要操作的容器或内置数组中的元素范围。元素的范围，包括 first，但不包含last的左闭合区间，即 [first, last）。当 first == last 成立，则范围为空。对iterator的属性，则要求在每个算法声明中指出，所声明的是最低要求。如 find() 算法的最低要求为：InputIterator；还可以传递更高级别的迭代子。如：ForwardIterator、BidirectionalIterator、RandomAccessIterator，但不能用 OutputIterator。

count()算法

count()算法是独立于容器类模板的非成员函数，对于对STL的各种容器包括数组进行元素个数统计。定义在<algorithm>文件中，原型如下：

template<class Init,class T>
size_t count(Init first, Init last, const T&val);

算法的使用：

// countSTLTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <set>

using namespace std;

#define size 10

//产生指定范围的整数随机数
int getrand(int min,int max)
{
	int m;
	m = max - min;
	m = min + double(rand()) / RAND_MAX * m;
	return m;
}

//利用类模板生成实例
typedef vector<int> IntArray;
typedef list<int> LISTINT;
typedef set<int> SET_INT;

int main()
{
	//------------------------------
	//count算法对于普通数组的计算
	//------------------------------
	int x[size];
	cout<<"x[]:";
	for(int i = 0; i < size; i ++)
	{
		x[i] = getrand(1,3);
		cout<<x[i]<<" ";
	}
	cout<<endl;
	cout<<"count(x,x + size,2)=";
	cout<<count(x,x + size,2)<<endl;		//统计2在x~x+size之间出现的次数
	cout<<"count(x + 2,x + 8,2)=";
	cout<<count(x + 2,x + 8,2)<<endl;

	//------------------------------
	//count算法对于vector容器的计算
	//------------------------------
	//声明intvector容器和迭代器 ii 
	IntArray intvector;
	IntArray::iterator ii;

	//向intvector容器中插入元素
	for(int i = 1; i < size; i ++)
	{
		intvector.push_back(getrand(2,6));
	}

	//显示intvector容器的元素值和统计结果
	cout<<"intvector:";
	for(ii = intvector.begin();ii != intvector.end();++ ii)
		cout<<(*ii)<<" ";
	cout<<endl;
	cout<<"count(intvector.begin(),intvector.end(),4)=";
	cout<<count(intvector.begin(),intvector.end(),4)<<endl;

	//------------------------------
	//count算法对于list容器的计算
	//------------------------------
	//声明list容器和迭代器 iL 
	LISTINT list1;
	LISTINT::iterator iL;

	//向list1容器中插入元素
	for(int i = 1; i < size; i ++)
	{
		list1.push_front(getrand(3,5));
	}

	//显示list1容器的元素值和统计结果
	cout<<"list1:";
	for(iL = list1.begin();iL != list1.end();++ iL)
		cout<<(*iL)<<" ";
	cout<<endl;
	cout<<"count(list1.begin(),list1.end(),3)=";
	cout<<count(list1.begin(),list1.end(),3)<<endl;

	//------------------------------
	//count算法对于set容器的计算
	//------------------------------
	//声明set容器和迭代器 si 
	SET_INT set1;
	SET_INT::iterator si;

	//向list1容器中插入元素
	for(int i = 1; i < size; i ++)
	{
		set1.insert(getrand(1,10));
	}

	//显示set1容器的元素值和统计结果
	cout<<"set1:";
	for(si = set1.begin();si != set1.end();++ si)
		cout<<(*si)<<" ";
	cout<<endl;
	cout<<"count(set1.begin(),set1.end(),5)=";
	cout<<count(set1.begin(),set1.end(),5)<<endl;

	return 0;
}

结果
x[]:1 2 1 2 2 1 1 2 2 2
count(x,x + size,2)=6
count(x + 2,x + 8,2)=3
intvector:2 5 4 4 3 2 2 3 2
count(intvector.begin(),intvector.end(),4)=2
list1:4 4 3 3 3 3 3 4 3
count(list1.begin(),list1.end(),3)=6
set1:1 2 4 5 6 8
count(set1.begin(),set1.end(),5)=1
请按任意键继续. . .

count_if()算法

count_if()算法是独立于容器类模板的非成员函数，对于对STL的各种容器包括数组进行元素个数统计。定义在<algorithm>文件中，原型如下：

template<class Init,class T>
size_t count_if(Init first, Init last, Pred pr);  
//对容器中的 [first,last) 区间的每个元素执行一次 Pred pr函数，返回符合条件的元素个数
//pr为要执行的函数，此函数由用户根据需要自己定义

算法的使用：

// count_ifSTLTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

//如果字符串以'S'开头，则返回true
int MatchFirstChar(const string& str)
{
	string s("S");
	return s == str.substr(0,1);
}

int main()
{
	const int VECTOR_SIZE = 8;

	//生成成员类型为string的vector容器类
	typedef vector<string> StringVector;

	//定义迭代器类型
	typedef StringVector::iterator StringVectorIt;

	//声明vector容器的对象
	StringVector NamesVect(VECTOR_SIZE);

	//声明迭代器
	StringVectorIt start,end,it;

	int result = 0;		//存放统计数据

	//初始化vector容器NamesVect
	NamesVect[0] = "She";
	NamesVect[1] = "Sells";
	NamesVect[2] = "Sea";
	NamesVect[3] = "Shells";
	NamesVect[4] = "by";
	NamesVect[5] = "the";
	NamesVect[6] = "Sea";
	NamesVect[7] = "Shore";

	//设置容器的起始位置和终止位置
	start = NamesVect.begin();
	end = NamesVect.end();

	//显示NamesVect容器的元素
	cout<<"NamesVect:";
	for(it = start;it != end;it ++)
		cout<<*it<<" ";
	cout<<endl;

	//统计并显示NamesVect容器的所有元素中以'S'字符开头的字符串
	result = count_if(start,end,MatchFirstChar);
	cout<<"Number of elements that start with letter \"S\"="
		<<result<<endl;

	return 0;
}

结果
NamesVect:She Sells Sea Shells by the Sea Shore
Number of elements that start with letter "S"=6
请按任意键继续. . .

函数对象

每个泛型算法的实现都独立于容器类型，它消除了算法对类型的依赖性。当一个算法应用于一个具体的容器时，STL的泛型算法采用“函数对象”（Function Object）来解决该问题。

函数对象是一个类对象，通常它仅有一个成员函数，该函数重载了函数调用操作符（operator()）。函数对象亦称为拟函数对象（Function_Like Object）和函子（Functor）。该操作符封装了应该被实现为一个函数的操作。具体情况下，函数对象被作为实参传递给泛型算法。和引用一样，函数对象很少独立使用。

使用函数对象实现泛型算法，可将其作为泛型算法的实参使用，通常用来改变默认的操作，如：

sort(vec.begin(), vec.end(), greater<int>());

这里把整数的大于关系函数对象作为实参，得降序排列。如果是字符串，则只需要改一下参数就可以用于字符串的排序：

sort(svec.begin(), svec.end(), greater<string>());

例如：以函数对象作为“求序列中最小值的函数模板”中的“数值比较算法”中的参数：

//Comp为比较函数对象类模板，对不同的数据类型，可以产生不同的比较函数，以实现泛型类
template<typename Type,typename Comp>
const Type& min(const Type* p,int size,Comp comp)
{
    int minIndex = 0;
    //最小元素下标初值为0，即设0号元素最小
    for(int i = 1; i < size; i ++)
        if(comp(p[i],p[minIndex]))
            minIndex = i;
    return p[minIndex];
}

函数对象一般有以下几种：

• 标准库预定义的一组算术、关系和逻辑函数对象；
• 预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展。
• 自定义函数对象。

函数对象和指针的功能相似，使用函数对象的优点：

• 函数指针是间接引用，不是作为内联函数，而函数对象可以，这样速度更快；
• 函数对象可以拥有任意数量的额外数据，这些数据可以用来缓冲当前数据和结果，提高运行质量；
• 编译时对函数对象作类型检查。

函数对象定义和测试如下：

// sumFunctionObjectTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using namespace std;

template<typename T>
class Sum
{
	T res;
public:
	Sum(T i = 0):res(i){}	//构造函数，即Sum(T i = 0){res = i;}
	T operator()(T x)		//累加，重载的调用操作符
	{
		res += x;
		return res;
	}
};

template<typename FuncObject,typename T>
T Func1(FuncObject fob,const T &val)	//函数对象作为参数
{
	return fob(val);		//调用重载的()，实现加法
}

template<typename FuncObject,typename T>
T Func2(FuncObject &fob,const T &val)	//参数为引用，建议用此方式
{
	return fob(val);		//调用重载的()，实现加法
}

int main()
{
	Sum<int> sum(10);		//调用构造函数建立sum，res值为10
	int i = 5, j = 10;

	//cout<<sum(j)<<'\t'<<sum(i)<<endl;//实现累加，先+10=20，后+5=25为啥输出的是：25 15，莫非是先计算后面的，再计算前面的？？？

	cout<<sum(j)<<'\t';
	cout<<sum(i)<<endl;	//调用重载的sum(),实现累加，输出：20 25
	cout<<Func1(sum, i)<<'\t';
	//Func1传参传值，sum::res保持25，在一份拷贝上完成sum+i，输出：30
	cout<<Func1(sum, j)<<endl;	//在一份拷贝上完成sum+j，未实现累加，输出：35
	cout<<Func2(sum, i)<<'\t';
	//Func1传参为引用，在原sum上完成sum=sum+i，实现累加，输出：30
	cout<<Func2(sum, j)<<endl;	//完成sum=sum+j，实现累加，输出：40
	//以下函数对象标准用法，每次新建函数对象，Func1和Func2结果无差别
	cout<<Func1(Sum<int>(5),i)<<'\t';	//5+i，输出10
	cout<<Func2(Sum<int>(),j)<<endl;	//0+j，输出10

	return 0;
}

结果
20      25
30      35
30      40
10      10
请按任意键继续. . .

问题：

cout<<sum(j)<<'\t'<<sum(i)<<endl;//实现累加，先+10=20，后+5=25为啥输出的是：25 15。

查阅相关博客，部分作者给出的解释是：

对于  cout<<函数1<<函数2;  ，通常  先算函数2，再函数1。