C++:STL常用算法随笔

主要的头文件#include <algorithm>  < functional>  <numeric>

遍历算法：

for_each、transform(搬运容器到另一个容器中 )

void print1(int val)
{cout << val <<" ";
}
for_each (v.begin(),v.end() , print1)

或者用仿函数的形式遍历：

class print2{
public:void operator()(int val){cou <<val <<" ";}
}

for_each(v.begin(),v.end(),print2()) ;  不同于上述，此处需要传入匿名函数对象

---

对于transform搬运算法:

vector <int> vtarget;   //创建目标容器

vtarget.resize(v.size()) ; //目标容器必须提前开辟空间，与原vector一致，否则无法搬运

class trans1{
public :int operator () (int val ){return val;    }
}

transform (v.begin();v.end();vtarget.begin(),trans1());  //最后需要加个仿函数 ,注意中间的vtarget.begin()迭代器

查找算法：

find         //查找元素  ，找到返回指定元素的迭代器，找不到返回结束迭代器end()；

                利用find可以在容器中找指定的元素，返回值是迭代器，使用迭代器接收
find_if        //按条件查找元素 ，三个参数：开始迭代器、结束迭代器、谓词（返回bool的仿函数）

vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
if (it ==v.end()) {...}  //没找到
else{} ;  //找到了

对于查找自定义数据类型：

class Person{public:person(string name ,int age){this->m_Name = name;this->m_Age = age;
}
public:string m_Name;int m_Age ;
};class Greater{bool operator()(Person &p){return p.m_Age >20;    
}
}vector <Person>::iterator it  = find_if (v.begin() , v.end() , Greater());
if(it == v.end()){};
else {};

---

adjacent_find        //查找相邻重复元素,返回相邻重复元素的第一个元素迭代器

vector<int>::iterator pos = adjacent_find(v.begin(), v.end());

---

binary_search        //二查找法,查找指定元素是否存在，但是只能在有序数组中使用，返回一个bool类型，速度快，logN时间复杂度
bool ret =binary_search(v.begin(),v.end()，9 ) //查找容器中是否有9元素,但是只能是升序，降序需要提供重载版本

  //升序vector<int> v;for (int i = 0; i < 10; i++) {v.push_back(i);}bool ret = binary_search(v.begin(), v.end(), 8);if (ret == true) {cout << "true" << endl;}else {cout << "false" << endl;}//测试降序是否适用vector<int> v1;for (int i = 10; i > 0; i--) {v1.push_back(i);}bool ret2 = binary_search(v1.begin(), v1.end(), 8);if (ret2 == true) {cout << "true" << endl;}else {cout << "false" << endl;}//结果输出：
true
false

---

count        //统计元素个数,返回一个int整形。

int num=count(v.begin(),v.end()，40);
count_if        //按条件统计元素个数

int num = count_if (v.begin(),v.end(),Greater())  ; 最后一个参数为谓词

或者自定义数据类型：

 排序算法：

sort(v.begin(),v.end()); //升序排列，降序需要添加<functional>中的模板

void myPrint(int val)

{cout << val <<" ";}

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

for_each (v.begin(),v.end(),myPrint);

打乱算法：random_shuffle

srand((unsigned int) time (NULL));   // 使用时间作为随机数种子来确保真正的随机

random_shuffle(v.begin(),v.end());

合并算法：merge(前提两个容器必须有序，合并之后的也是有序的)

//目标容器
vector<int>vTarget;

vTarget.resize(v1.size()+v2.size()); // 前提必须要给目标容器分配内存！！！
merge(v1.begin(),v1.end(),v2.begin(),v2.end(),vTarget.begin());

数据反转：reverse

reverse(v.begin,v.end());

拷贝和替换算法：

vector <int> v2;

v2.resize(v1.size());  //注意记得先开辟空间！

copy（v1.begin(),v1.end(),v2.begin()）;

替换算法：replace 

replace(v1.begin(),v1.end() ,20  , 2000) ; // 把所有的20替换为2000

按照条件替换：replace_if

一般构建仿谓词来作为参数

构建谓词(把大于等于30 的数替换)

class Greater30

{

public :
        bool operator() (int val )

        {

                return val>=30;

        }

}

replace_if (v1.begin() , v1. end() , Greater30() ,30000) ; 把大于等于30的数替换为30000;

常用算数生成算法：#include <numeric>

accumulate   // 计算容器元素累计总和，可以设置起始值
fill // 向容器中添加元素,填充所有空间为指定的值

int sum = accumulate(v.begin() , v.end() , value)；  //value 表示起始的累加值

常用的集合算法： (此处的集合并不指set容器，而是数学概念)

求交集： set_ intersection    （原容器必须是有序序列）

vector <int> vtarget;

vtarget.resize(min(v1.size(),v2.size())) ;  //这样做是考虑到最大的目标容器内存情况：原容器1包含原容器2

vector<int>::interator itEnd=set_ intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget.begin());  //返回迭代器，指向新的vtarget的最后
打印输出：
for_each (vTarget.begin(),itEnd , myprint());

求并集 ： set_union（原容器必须是有序序列）

vtarget.resize(v1.size()+v2.size()) ;  //这样做是考虑到最大的目标容器内存情况：原容器1与原容器2无交集

vector<int>::interator itEnd=set_ union(v1.begin(),v1.end(),v2.begin(),v2.end(),vtarget.begin());  //返回迭代器，指向新的vtarget的最后

打印输出：
for_each (vTarget.begin(),itEnd , myprint());

求差集 ： set _difference