算法部分主要由头文件
,
和
组成。
是所有STL头文件中最大的一个,其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
体积很小,只包括几个在序列上面进行简单数学运算的模板函数,包括加法和乘法在序列上的一些操作。
中则定义了一些模板类,用以声明函数对象。
STL提供了大量实现算法的模版函数,只要我们熟悉了STL之后,许多代码可以被大大的化简,只需要通过调用一两个算法模板,就可以完成所需要的功能,从而大大地提升效率。
需要添加头文件:
#include
#include
#include
重载函数调用操作符的类,其对象常称为函数对象(function object),即它们是行为类似函数的对象。一个类对象,表现出一个函数的特征,就是通过“对象名+(参数列表)”的方式使用一个类对象,如果没有上下文,完全可以把它看作一个函数对待。
这是通过重载类的operator()来实现的。
标准库中的很多算法都可以使用函数对象或者函数来作为自定的回调行为
一元函数对象:函数参数1个;二元函数对象:函数参数2个。
一元谓词函数参数1个,函数返回值是bool类型,可以作为一个判断式
谓词可以是一个仿函数,也可以是一个回调函数。
二元谓词 函数参数2个,函数返回值是bool类型
一元谓词函数举例如下
判断给出的string对象的长度是否小于6
bool GT6(const string &s)
{return s.size() >= 6;
}
bool isShorter(const string &s1, const string &s2)
{return s1.size() < s2.size();
}
标准模板库STL提前定义了很多预定义函数对象,头文件
必须包含。
plus
minus
multiplies
divides
modulus
negate
equal_to
equal_to stringEqual;
sres = stringEqual(sval1,sval2);
not_equal_to
greater
greater_equal
less
less_equal
logical_and
logical_or
logical_not
标准库提供一组函数适配器,用来特殊化或者扩展一元和二元函数对象。常用适配器是:
1、绑定器(binder): binder通过把二元函数对象的一个实参绑定到一个特殊的值上,将其转换成一元函数对象。C++标准库提供两种预定义的binder适配器:bind1st和bind2nd,前者把值绑定到二元函数对象的第一个实参上,后者绑定在第二个实参上。
2、取反器(negator) : negator是一个将函数对象的值翻转的函数适配器。标准库提供两个预定义的ngeator适配器:not1翻转一元预定义函数对象的真值,而not2翻转二元谓词函数的真值。
常用函数适配器列表如下:
bind1st(op, value)
bind2nd(op, value)
not1(op)
not2(op)
mem_fun_ref(op)
mem_fun(op)
ptr_fun(op)
示例代碼:
#include
#include
#include using namespace std;bool Equal(string str)
{return str == "bb";
}int main()
{vector v;v.push_back("aa");v.push_back("bb");v.push_back("cc");v.push_back("dd");//vector::iterator it = find_if(v.begin(), v.end(), Equal);vector::iterator it = find_if(v.begin(), v.end(), bind1st(equal_to(), "bb"));if (it == v.end()){cout << "不存在" << endl;}else{cout << *it << endl;}return 0;
}
運行結果:
for_each: 用指定函数依次对指定范围内所有元素进行迭代访问。该函数不得修改序列中的元素。
transform: 与for_each类似,遍历所有元素,但可对容器的元素进行修改。
完整示例代码:
#include
#include
#include using namespace std;void show(int x)
{cout << x << endl;
}class print
{
public:void operator()(int x){cout << x << endl;}
};int main()
{int array[5] = {1, 2, 3, 4, 5};vector v(array, array + 5);//for_each遍历过程中 不能修改数据for_each(v.begin(), v.end(), show); //回调函数形式遍历for_each(v.begin(), v.end(), print()); //函数对象形式遍历 //transform遍历过程中 可以修改数据string s("helloworld");// 从s.begin()开始,到s.eng()结束。把修改的元素从s.begin()开始放,这里是把元素变成大写transform(s.begin(), s.end(), s.begin(), ::toupper);cout << s << endl;return 0;
}
运行结果:
在iterator对标识元素范围内,查找一对相邻重复元素,找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end。
在有序序列中查找value,找到则返回true。注意:在无序序列中,不可使用。
count:利用等于操作符,把标志范围内的元素与输入值比较,返回相等的个数。
count_if:利用自定义操作符,把标志范围内的元素与输入值比较,返回满足条件的元素个数
例:
序列1 3 5 7 9 11 13
统计等于3的元素的个数,使用count
统计大于3的元素的个数,使用count_if
find: 利用底层元素的等于操作符,对指定范围内的元素与输入值进行比较。当匹配时,结束搜索,返回该元素的迭代器。
find_if:利用自定义条件,对指定范围内的元素与输入值进行比较,当匹配时,结束搜索,返回该元素的迭代器。
例:
序列:1 3 5 7 9 11 13
查找元素3,找到返回该元素的迭代器,用find
查找大于3的元素,找到返回该元素的迭代器,用find_if
完整示例代码:
#include
#include
#include using namespace std;bool GreaterTwo(int x)
{return x > 2;
}class GreaterThree
{
public:bool operator()(int x){return x > 3;}
};int main()
{int array[6] = {1, 2, 2, 3, 4, 4};vector v(array, array + 6);vector::iterator it = adjacent_find(v.begin(), v.end());if (it == v.end()){cout << "不存在重复且相邻的" << endl;}else{cout << *it << endl;}bool ret = binary_search(v.begin(), v.end(), 4); //在有序的序列里面查找if (ret){cout << "元素存在" << endl;}else{cout << "元素不存在" << endl;}int num = count(v.begin(), v.end(), 2);cout << num << endl;num = count_if(v.begin(), v.end(), GreaterTwo); //一元谓词 回调函数cout << num << endl;it = find(v.begin(), v.end(), 3);if (it == v.end()){cout << "元素不存在" << endl;}else{cout << *it << endl;}it = find_if(v.begin(), v.end(), GreaterThree()); //函数对象if (it == v.end()){cout << "元素不存在" << endl;}else{cout << *it << endl;}return 0;
}
运行结果:
merge: 合并两个有序序列,存放到另一个序列。
sort: 以默认升序的方式重新排列指定范围内的元素。若要改排序规则,可以输入比较函数。
random_shuffle: 对指定范围内的元素随机调整次序。
完整示例代码:
#include
#include
#include
#include
#include using namespace std;void show(int x)
{cout << x << " ";
}int main()
{vector v1;vector v2;srand(time(NULL));for (int i = 0; i < 5; i++){v1.push_back(rand() % 10);v2.push_back(rand() % 10);}sort(v1.begin(), v1.end(), less());sort(v2.begin(), v2.end(), less());cout << "v1:" << endl;for_each(v1.begin(), v1.end(), show);cout << endl;cout << "v2:" << endl;for_each(v2.begin(), v2.end(), show);cout << endl;vector v3;v3.resize(10); // 对v3进行扩容merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());for_each(v3.begin(), v3.end(), show);cout << endl;random_shuffle(v1.begin(), v1.end());cout << "v1:" << endl;for_each(v1.begin(), v1.end(), show);cout << endl;reverse(v3.begin(), v3.end());for_each(v3.begin(), v3.end(), show);cout << endl;return 0;
}
运行结果:
例子:
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);vector vecIntB;
vecIntB.resize(5); //扩大空间
//vecIntB: {1,3,5,7,9}
copy(vecIntA.begin(), vecIntA.end(), vecIntB.begin());
replace(beg,end,oldValue,newValue):
将指定范围内的所有等于oldValue的元素替换成newValue。例子:
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);replace(vecIntA.begin(), vecIntA.end(), 3, 8); //{1,8,5,8,9}
replace_if(vecIntA.begin(),vecIntA.end(),GreaterThree,newVal)
//把大于等于3的元素替换成8
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);replace_if(vecIntA.begin(), vecIntA.end(), GreaterThree, 8);
swap: 交换两个容器的元素
完整示例代码:
#include
#include
#include using namespace std;void show(int x)
{cout << x << " ";
}int main()
{vector v1(5, 1);vector v2(5, 2);v2.resize(6);copy(v1.begin(), v1.end(), ++(v2.begin()));for_each(v2.begin(), v2.end(), show);cout << endl;swap(v1, v2);for_each(v2.begin(), v2.end(), show);cout << endl;return 0;
}
运行结果:
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
int iSum = accumulate(vecIntA.begin(), vecIntA.end(), 100); //iSum==125
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);fill(vecIntA.begin(), vecIntA.end(), 8); //8, 8, 8, 8, 8
vector vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);vector vecIntB;
vecIntB.push_back(1);
vecIntB.push_back(3);
vecIntB.push_back(5);
vecIntB.push_back(6);
vecIntB.push_back(8);vector vecIntC;
vecIntC.resize(10);// 并集
// vecIntC : {1,3,5,6,7,8,9,0,0,0}
set_union(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin()); // 交集
// vecIntC: {1,3,5,0,0,0,0,0,0,0}
fill(vecIntC.begin(), vecIntC.end(), 0);
set_intersection(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin()); // 差集
// vecIntC: {7,9,0,0,0,0,0,0,0,0}
fill(vecIntC.begin(), vecIntC.end(), 0);
set_difference(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());