算法"/>
C++常用标准算法
算法主要由头文件<algorithm>、<functional>、<numeric>组成。
<algorithm>是所有STL头文件中最大的一个，范围涉及到比较、交换、查找、遍历、赋值、修改等等；<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数；<functional>定义了一些模板类。
一.遍历
1.std::for_each
std::for_each用于遍历容器
#include <iostream>
#include <vector>
#include <algorithm>void print1(const int &val)
{std::cout << val << " ";
}class print2
{
public:void operator()(const int &val){std::cout << val << " ";}
};void test1()
{std::vector<int> v;for (int i = 0; i < 10; i++){v.push_back(i);}for_each(v.begin(), v.end(), print1);std::cout << std::endl;for_each(v.begin(), v.end(), print2());
}int main()
{test1();return 0;
}
2.std::transform
std::transform用于搬运容器到另一个容器中
#include <iostream>
#include <vector>
#include <algorithm>void printVector(const int &val)
{std::cout << val << " ";
}class Transform
{
public:int operator()(int v){return v + 3;}
};void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int> v2;v2.resize(v1.size());transform(v1.begin(), v1.end(), v2.begin(), Transform());for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;for_each(v2.begin(), v2.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}二.查找
1.std::find
std::find用于查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()
#include <iostream>
#include <vector>
#include <algorithm>void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int>::iterator it = std::find(v1.begin(), v1.end(), 5);if (it == v1.end()){std::cout << "Find failed！" << std::endl;}else{std::cout << "Find succeed: " << *it << std::endl;}
}int main()
{test1();return 0;
}2.std::find_if
std::find_if用于按条件查找
#include <iostream>
#include <vector>
#include <algorithm>class GreaterFive
{
public:bool operator()(int val){return val > 5;}
};
void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int>::iterator it = find_if(v1.begin(), v1.end(), GreaterFive());if (it == v1.end()){std::cout << "Find failed" << std::endl;}else{std::cout << "Find numbers greater than 5: " << *it << std::endl;}
}int main()
{test1();return 0;
}
3.std::adjacent_find
std::adjacent_find用于查找相邻重复元素，返回相邻元素的第一个位置的迭代器
#include <iostream>
#include <vector>
#include <algorithm>void test1()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);std::vector<int>::iterator it = adjacent_find(v1.begin(), v1.end());if (it == v1.end()){std::cout << "Find failed" << std::endl;}else{std::cout << "Find adjacent numbers: " << *it << std::endl;}
}int main()
{test1();return 0;
}4.std::binary_search
std::binary_search(二分查找)用于查找指定元素是否存在。查到返回true，否则false。需要注意的是该算法在无序序列中不可用
#include <iostream>
#include <vector>
#include <algorithm>void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}bool ret = std::binary_search(v1.begin(), v1.end(), 9);if (ret){std::cout << "Find succeed" << std::endl;}else{std::cout << "Find failed" << std::endl;}
}int main()
{test1();return 0;
}三.统计元素个数
1.std::count
std::count用于统计元素出现的次数
#include <iostream>
#include <vector>
#include <algorithm>void test1()
{std::vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(2);int num = std::count(v1.begin(), v1.end(), 2);std::cout << "The count of 2: " << num<< std::endl;
}int main()
{test1();return 0;
}2.std::count_if
std::count_if用于按条件统计元素个数
#include <iostream>
#include <vector>
#include <algorithm>class CountIf
{
public:bool operator()(int val){return val > 5;}
};void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}int num = std::count_if(v1.begin(), v1.end(), CountIf());std::cout << "The count of numbers greater than 5: " << num << std::endl;
}int main()
{test1();return 0;
}四.排序
1.std::sort
std::sort用于进行升序或降序
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;v1.push_back(2);v1.push_back(1);v1.push_back(3);// 默认升序std::sort(v1.begin(), v1.end());std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;// 降序std::sort(v1.begin(), v1.end(), std::greater<int>());std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}2.std::random_shuffle
std::random_shuffle用于洗牌，指定范围内的元素随机调整次序
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::srand((unsigned int)time(nullptr));std::random_shuffle(v1.begin(), v1.end());std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
3.std::merge
std::merge用于将两个容器元素合并，并存储到另一个容器中。合并后，目标容器仍然是有序的
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;std::vector<int> v2;for (int i = 0; i < 10; i++){v1.push_back(i);v2.push_back(i + 1);}std::vector<int> v3;v3.resize(v1.size() + v2.size());std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());std::for_each(v3.begin(), v3.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
4.std::reverse
std::reverse用于将容器内元素进行反转
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::cout << "Before: ";std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;std::cout << "After: ";std::reverse(v1.begin(), v1.end());std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
五.拷贝和替换
1.std::copy
std::copy用于将容器内指定范围的元素拷贝到另一容器中。使用v2 = v1效果一样，记得提前给容器分配空间
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int> v2;v2.resize(v1.size());std::copy(v1.begin(), v1.end(), v2.begin());std::for_each(v2.begin(), v2.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
2.std::replace
std::replace用于将容器内指定范围的旧元素修改为新元素
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::cout << "Before: ";std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;std::cout << "After: ";std::replace(v1.begin(), v1.end(), 0, 1);std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
3.std::replace_if
std::replace_if用于将容器内指定范围满足条件的元素替换为新元素。可以利用仿函数灵活筛选满足的条件
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}class Rule
{
public:bool operator()(int val){return val > 5;}
};void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::cout << "Before: ";std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;std::cout << "After: ";// 把容器中所有大于5的元素，替换为6std::replace_if(v1.begin(), v1.end(), Rule(), 6);std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
4.std::swap
std::swap用于互换两个容器的元素。无需重新指定容器的大小
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int> v2;for (int i = 0; i < 5; i++){v2.push_back(i);}// 交换两个容器内的元素，无需重新指定容器大小std::swap(v1, v2);std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;std::for_each(v2.begin(), v2.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
六.算术生成
1.std::accumulate
std::accumulate用于计算容器内元素累计总和
#include <iostream>
#include <vector>
#include <numeric>void test1()
{std::vector<int> v1;for (int i = 0; i < 3; i++){v1.push_back(i);}// 最后一个参数是累加的初值，accumulate将它的一个内部变量设置为指定的初值，// 然后在此初值上累加输入范围内所有元素的值.1+0+1+2=4int total = std::accumulate(v1.begin(), v1.end(), 1);std::cout << total;
}int main()
{test1();return 0;
}
2.std::fill
std::fill用于向容器中添加元素
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;v1.resize(10);std::fill(v1.begin(), v1.end(), 1);std::for_each(v1.begin(), v1.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
七.集合
1.std::set_intersection
std::set_intersection用于求两个容器的交集。两个容器必须是有序序列，可以先用排序算法转化为有序序列，再求交集。目标容器开启空间需要从两个容器中取小值。返回值是交集中最后一个元素的位置
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int> v2;for (int i = 0; i < 5; i++){v2.push_back(i);}std::vector<int> v3;v3.resize(std::min(v1.size(), v2.size()));std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());std::for_each(v3.begin(), v3.end(), printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}2.std::set_union
std::set_union用于求两个容器的并集。两个容器必须是有序序列。目标容器开辟空间的大小为两个容器相加。返回值是并集中最后一个元素的位置
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int> v2;for (int i = 0; i < 5; i++){v2.push_back(i);}std::vector<int> v3;v3.resize(v1.size() + v2.size());std::vector<int>::iterator itEnd = std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());// 注意这里要判断itEnd，如果换成v3.end(),会输出v3后面的5个0std::for_each(v3.begin(), itEnd, printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
3.std::set_difference
std::set_difference用于求两个容器的差集。注意是v1-v2还是v2-v1。两个容器为有序序列。目标容器开辟空间为两个容器中的较大值。返回值是差集中最后一个元素的位置
#include <iostream>
#include <vector>
#include <algorithm>void printVector(int val)
{std::cout << val << " ";
}void test1()
{std::vector<int> v1;for (int i = 0; i < 10; i++){v1.push_back(i);}std::vector<int> v2;for (int i = 0; i < 5; i++){v2.push_back(i);}std::vector<int> v3; // 目标容器,需要提前开辟空间v3.resize(std::max(v1.size(), v2.size()));std::cout << "v1-v2: ";std::vector<int>::iterator itEnd1 = std::set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());std::for_each(v3.begin(), itEnd1, printVector);std::cout << std::endl;std::cout << "v2-v1: ";std::vector<int>::iterator itEnd2 = std::set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), v3.begin());// 输出为空，因为v2-v1，v2中没有v1的元素std::for_each(v3.begin(), itEnd2, printVector);std::cout << std::endl;
}int main()
{test1();return 0;
}
八.去重
std::unique，详见：C++之std::vector元素去重
原文链接：C++常用标准算法-CSDN博客
更多推荐
C++常用标准算法
发布评论