STL算法——常用算法

1、算法概述

算法部分主要由头文件<algorithm>和<functional>组成。<algorithm>是所有STL头文件中最大的一个，其中常见的功能涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等。<numeric>体积很小，只包括几个在序列上进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。<functioal>中则定义了一些模板类，用以声明函数对象。

2、常用遍历算法

for_each(iterator beg,iterator end, _callback);

功能：用指定函数依次对指定范围内所有元素进行迭代访问。 该函数不得修改序列中的元素。

参数1：开始迭代器

参数2：结束迭代器

参数3：函数回调或者函数对象，函数对象做函数参数， 函数对象做返回值

返回：函数对象

class CMyShow //一元函数对象 { public: CMyShow( ) { num = 0; } void operator( )(int &n) { num++; cout << n << " "; } void printNum( ) { cout << "num:" << num << endl; } protected: private: int num; }; void main( ) { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); CMyShow mya; //定义一个函数对象 CMyShow my1 = for_each(v1.begin(), v1.end(), mya); //注意 find 使用的只是 mya 的拷贝 mya.printNum(); //ma1 和 my1 是两个不同的对象 my1.printNum(); } 运行结果： 1 3 5 num: 0 //可以看出， 丝毫没有影响原来的 myanum:3

transform(iterator beg1, iterator end1, iterator beg2, _callbakc )

功能：将指定容器区间元素搬运到另一个容器中

参数1：原容器开始迭代器

参数2：原容器结束迭代器

参数3：目标容器开始迭代器

参数4：回调函数或者函数对象

返回：返回目标容器迭代器

template<class T> //函数模板， 既可以输出 vector 类中数据， 也可输出 list 类中数据 void printV( T &v) { for ( T::iterator it = v.begin(); it != v.end(); it++) { cout << *it << " "; } } void main() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); printV(v1); cout << endl; //transform 使用回调函数 transform(v1.begin(), v1.end(), v1.begin(), increase); printV(v1); cout << endl; //transform 使用 预定义的函数对象 transform(v1.begin( ), v1.end( ), v1.begin( ), negate<int>( )); printV(v1); cout << endl; //transform 使用 函数适配器辅助函数 和函数对象 list<int> mylist; mylist.resize(v1.size()); // 把 vector 中的数据运算后放到 list 容器中 transform(v1.begin(), v1.end(), mylist.begin(), bind2nd(multiplies<int>(), 10)); printList(mylist); cout << endl; //transform 也可以把运算结果 直接输出到屏幕 必须有头文件#include"iterator" 输出流迭代器的头文件 transform(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "), negate<int>()); cout << endl; }

3、常用查找算法

find(iterator beg, iterator end, value );

功能：查找元素

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：查找的元素

返回值：返回查找元素的位置

bool GreaterThree(int iNum) { if(iNum>=3) { return true; } else { return false; } } void main47_find_findif() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); v1.push_back(7); v1.push_back(7); v1.push_back(9); v1.push_back(7); vector<int>::iterator it = find(v1.begin(), v1.end(), 5); cout << "*it:" << *it << endl; //第一个大于 3 的位置 vector<int>::iterator it2 = find_if(v1.begin(), v1.end(), GreatThree); cout << "*it2:" << *it2 << endl; }

find_if(iterator beg, iterator end, _callback );

功能：条件查找

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：回调函数或者谓词（返回bool类型的函数对象）

返回值：查找返回true，否则false

adjacent_find(iterator beg, iterator end, _callback);

功能：查找相邻重复元素 参数1：容器开始迭代器 参数2：容器结束迭代器 参数3：回调函数或者谓词(返回 bool 类型的函数对象) 返回值：返回相邻元素的第一个位置的迭代器

bool binary_search(iterator beg, iterator end, value);

功能：二分查找法；注意: 在无序序列中不可用 参数1：容器开始迭代器 参数2：容器结束迭代器 参数3：查找的元素 返回值：查找返回 true 否则 false

count(iterator beg, iterator end, value);

功能：统计元素出现次数 参数1：容器开始迭代器 参数2：容器结束迭代器 参数3：回调函数或者谓词(返回 bool 类型的函数对象) 返回值：返回元素个数

count_if(iterator beg, iterator end, _callback)

功能：统计元素出现次数 参数1：容器开始迭代器 参数2：容器结束迭代器 参数3：回调函数或者谓词(返回 bool 类型的函数对象)

返回值：返回元素个数

4、常用排序算法

merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

功能：容器元素合并，并存储到另一容器中；注意:两个容器必须是有序的

参数1：容器1开始迭代器

参数2：容器1结束迭代器

参数3：容器2开始迭代器

参数4：容器2结束迭代器

参数5：目标容器开始迭代器

void main_merge() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); vector<int> v2; v2.push_back(2); v2.push_back(4); v2.push_back(6); vector<int> v3; //v3 要存放六个元素， 指定空间必须大于 6,否则编译错误 //v3.resize(v1.size() + v2.size()); v3.resize(7); merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); printV(v3); } 运行结果： 1 2 3 4 5 6 0

sort(iterator beg, iterator end, _callback)

功能：容器元素排序

参数1：beg容器1开始迭代器

参数2：容器1结束迭代器

参数3：回调函数或者谓词(返回bool类型的函数对象)

class Student { public: Student(string name, int id) //构造函数 { m_name = name; m_id = id; } void printT() { cout << "name: " << m_name << " id " << m_id << endl; } public: string m_name; int m_id; }; bool CompareS(Student &s1, Student &s2) //自定义的排序函数， 必须是布尔型 { return (s1.m_id < s2.m_id); } void main_sort() { Student s1("老大", 1); Student s2("老二", 2); Student s3("老三", 3); Student s4("老四", 4); vector<Student> v1; v1.push_back(s4); v1.push_back(s1); v1.push_back(s3); v1.push_back(s2); for (vector<Student>::iterator it = v1.begin(); it != v1.end(); it++) { it->printT(); } //sort 根据自定义函数对象 进行自定义数据类型的排序 //替换 算法的统一性 (实现的算法和数据类型的分离) ===>技术手段函数对象 sort(v1.begin(), v1.end(), CompareS); for (vector<Student>::iterator it = v1.begin(); it != v1.end(); it++) { it->printT(); } }

random_shuffle(iterator beg, iterator end)

功能：对指定范围内的元素随机调整次序

参数1：容器开始迭代器

参数2：容器结束迭代器

reverse(iterator beg, iterator end)

功能：反转指定范围的元素

参数1：容器开始迭代器

参数2：容器结束迭代器

5、常用拷贝和替换算法

copy(iterator beg, iterator end, iterator dest)

功能：将容器内指定范围的元素拷贝到另一容器中

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：目标起始迭代器

void main52_copy() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); v1.push_back(7); vector<int> v2; v2.resize(v1.size()); //该语句必须要有， 并且大小要比原来的空间要大，否则出错 copy(v1.begin(), v1.end(), v2.begin()); printV(v2); }

replace(iterator beg, iterator end, oldvalue, newvalue)

功能：将容器内指定范围的旧元素修改为新元素

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：旧元素

参数4：新元素

void main53_replace_replace_if() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); v1.push_back(7); v1.push_back(3); replace(v1.begin(), v1.end(), 3, 8); printV(v1); cout << endl; // >=5 replace_if(v1.begin(), v1.end(), great_equal_5, 1); printV(v1); cout << endl; } 运行结果： 1 8 5 7 8 1 1 1 1 1

replace_if(iterator beg, iterator end, _callback, newvalue)

功能：将容器内指定范围满足条件的元素替换为新元素

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：函数回调或者谓词(返回Bool类型的函数对象)

参数4：新元素*/

swap(container c1, container c2)

功能：互换两个容器的元素

参数1：容器1

参数2：容器2

void main54_swap() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); vector<int> v2; v2.push_back(2); v2.push_back(4); //v2.push_back(6); swap(v1, v2); //两个容器中的元素个数不同时仍然可以赋值成功。 printV(v1); cout << endl; printV(v2); } 运行结果： 2 4 //并没有出现 0 元素 1 3 5

6、常用算数生成算法

accumulate(iterator beg, iterator end, value)

功能：计算容器元素累计总和

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：累加值

#include<numeric> void main55_accumulate() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); int tmp = accumulate(v1.begin(), v1.end(), 100); //指定的初始值必须要有， 自己指定 cout << tmp << endl; }

fill(iterator beg, iterator end, value)

功能：向容器中添加元素

参数1：容器开始迭代器

参数2：容器结束迭代器

参数3：填充元素

void main56_fill() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); fill(v1.begin(), v1.end(), 8); printV(v1); } 运行结果： 8 8 8

7、常用集合算法

set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

功能：求两个set集合的交集；注意:两个集合必须是有序序列

参会1：容器1开始迭代器

参数2：容器1结束迭代器

参数3：容器2开始迭代器

参数4：容器2结束迭代器

参数5：目标容器开始迭代器

返回值：目标容器的最后一个元素的迭代器地址

set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

功能：求两个set集合的并集注意:两个集合必须是有序序列

参数1：容器1开始迭代器

参数2：容器1结束迭代器

参数3：容器2开始迭代器

参数4：容器2结束迭代器

参数5：目标容器开始迭代器

返回值：目标容器的最后一个元素的迭代器地址

set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

功能：求两个set集合的差集；注意:两个集合必须是有序序列

参数1：容器1开始迭代器

参数2：容器1结束迭代器

参数3：容器2开始迭代器

参数4：容器2结束迭代器

参数5：目标容器开始迭代器

返回值：目标容器的最后一个元素的迭代器地址

void main57_union() { vector<int> v1; v1.push_back(1); v1.push_back(3); v1.push_back(5); vector<int> v2; v2.push_back(2); v2.push_back(4); v2.push_back(6); vector<int> v3; v3.resize(v1.size() + v2.size()); set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin()); cout <<"并集为： " <<" "; printV(v3); cout << endl; vector<int> v4; v4.resize(v1.size() + v2.size()); set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v4.begin()); cout << "交集为： " << " "; printV(v4); cout << endl; vector<int> v5; v5.resize(v1.size() + v2.size()); set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v5.begin()); cout << "第一个序列中存在而第二个序列不存在的： " << " "; printV(v5); cout << endl; } 运行结果： 并集为： 1 2 3 4 5 6