STL
标准模板库(Standard Template Library,STL)是一个基于模板的容器类库。可用STL创建一个类,为任意数据类型定义矢量、链表、队列和栈等操作。STL中的泛型算法(generic algorithm)和函数对象(function object)使算法摆脱了对不同数据类型个性操作的依赖。
STL主要提供三类工具:容器、迭代器和算法。
目录
(一)容器类
(1)顺序容器
(2)关联容器
(3)容器适配器
(二)迭代器
(三)泛型算法
count()算法
count_if()算法
函数对象
(一)容器类
容器类是管理序列的类,是容纳一组对象或对象集的类。通过由容器类提供的成员函数,可以实现诸如向序列中插入元素、删除元素、查找元素等操作,这些成员函数通过返回迭代器来指定元素在序列中的位置。容器中提供了很多接口,许多基本操作是所有容器都适用的,而这些操作则适用于类似容器的子集,可以用有类似操作的新类来扩展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。