1.常用算法
文章目录
1.常用遍历算法
1.for_each
C++的std::for_each算法是标准库中的一个迭代器算法，它对容器或范围内的每个元素执行指定的操作。这个算法特别适用于你想要对容器内的每个元素应用同一个操作，但操作本身不需要积累结果（例如累加或查找最大值）的情形。std::for_each返回作用于每个元素的函数对象的副本。
基本语法如下：
template< class InputIt, class UnaryFunction>
UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );
InputIt first, InputIt last: 这是一个半开区间[first, last)，定义了要遍历的元素范围。UnaryFunction f: 一个可调用的对象（如函数、lambda表达式或者函数对象），它接受一个参数（即容器中的元素类型）并对其进行操作。该对象会在区间内的每个元素上被调用。
示例：
#include <algorithm>
#include <iostream>
#include <vector>
void print(int i) {
std::cout << i << ' ';
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用std::for_each打印vector中的每个元素
std::for_each(numbers.begin(), numbers.end(), print);
return 0;
}
在这个例子中，print函数被传递给std::for_each，它会对numbers向量中的每个元素调用print函数，从而打印出向量中的所有数字。
自C++11起，还可以直接使用lambda表达式作为第三个参数，使得操作更加灵活：
std::for_each(numbers.begin(), numbers.end(), [](int i){ std::cout << i * 2 << ' '; });
这段代码会打印出向量中每个数字的两倍。
2.transform
C++的std::transform算法是标准库中的一个迭代器算法，用于将一个范围内或两个范围内的元素通过某个操作转换后存放到另一个范围。这个算法常用于对容器内容进行批量修改或计算转换后的结果。与std::for_each不同的是，std::transform通常涉及输入范围和输出范围，并且转换操作可能产生新的值。
基本语法如下：
// 单输入范围到单输出范围
template< class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op);
// 双输入范围到单输出范围
template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op);
-
对于单输入范围版本：
InputIt first1, InputIt last1: 定义了输入范围。OutputIt d_first: 指向输出范围的开始位置。UnaryOperation unary_op: 一个可调用对象，接受一个输入范围的元素作为参数，并返回转换后的结果。
-
对于双输入范围版本：
InputIt1 first1, InputIt1 last1,InputIt2 first2: 分别定义了两个输入范围。- 其余参数同上，但
BinaryOperation binary_op接受两个输入范围对应位置的元素作为参数，并返回一个转换后的结果。
示例：
单输入范围示例，将一个vector中的每个元素平方后存入另一个vector：
#include <algorithm>
#include <iostream>
#include <vector>
int square(int x) {
return x * x;
}
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
std::vector<int> squared;
// 保留足够空间以避免插入时重新分配
squared.resize(numbers.size());
// 使用std::transform进行转换
std::transform(numbers.begin(), numbers.end(), squared.begin(), square);
for(int num : squared) {
std::cout << num << ' ';
}
return 0;
}
双输入范围示例，将两个vector对应元素相加后存入第三个vector：
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec1 = {1, 2, 3};
std::vector<int> vec2 = {4, 5, 6};
std::vector<int> result(vec1.size());
// 使用std::transform进行转换，这里使用lambda表达式代替函数对象
std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), [](int a, int b){ return a + b; });
for(int res : result) {
std::cout << res << ' ';
}
return 0;
}
这些示例展示了如何使用std::transform进行简单的数值转换和组合操作。
2.常用查找算法
在C++标准库中，提供了多种查找算法来帮助处理容器或范围内的数据。以下是您提到的一些常用查找算法的简要说明：
1. find
std::find用于在一个范围内查找指定的值。如果找到该值，则返回指向该值的第一个匹配项的迭代器；如果没有找到，则返回表示范围末尾的迭代器。
基本用法:
template< class InputIt, class T>
InputIt find(InputIt first, InputIt last, const T& value);
示例：
// 包含标准输入输出库、算法库和向量库
#include <iostream>
#include <algorithm>
#include <vector>
// 使用标准命名空间，简化代码中标准库函数的调用
using namespace std;
// 程序的主入口函数
int main(){
// 初始化一个字符串变量name
string name = "Felipe";
// 查找字符串name中字符'F'的位置
auto in = find(name.begin(), name.end(),'F');
// 输出找到的字符
cout << *in << endl;
// 初始化一个整数向量V，并赋初值
vector<int>V = {1,2,3,5,6,7};
// 在向量V中查找数值1的位置
auto it = find(V.begin(), V.end(),1);
// 判断是否找到数值1，如果找到则输出相应信息
if(it != V.end()){
cout << "find 1" << endl;
}
// 程序正常结束
return 0;
}
2. find_if
std::find_if类似于find，但它不是直接查找特定值，而是使用提供的谓词（如函数、lambda表达式）来测试每个元素，直到找到第一个使谓词返回true的元素。如果找到这样的元素，则返回指向它的迭代器；否则，返回last。
基本用法:
template< class InputIt, class UnaryPredicate>
InputIt find_if(InputIt first, InputIt last, UnaryPredicate pred);
示例：
// Filename: find_example.cpp
// Created by 86189 on 2024/7/7.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 主函数，演示如何使用标准库函数find_if查找向量中第一个大于5的元素
int main() {
// 初始化一个整数向量，包含1到6的几个数字，其中有重复
vector<int> V = {1, 2, 3, 3, 4, 5, 6};
// 使用find_if算法查找向量中第一个大于5的元素
// find_if函数接受一个范围（向量的开始和结束迭代器）和一个谓词（用于判断条件的lambda表达式）
// 这里lambda表达式返回值为true时意味着找到了满足条件的元素
auto it = find_if(V.begin(), V.end(), [](const int &val) { return val > 5; });
// 检查是否找到了满足条件的元素
if (it != V.end()) {
// 如果找到了，输出该元素的值
cout << *it << endl;
} else {
// 如果没有找到，输出提示信息
cout << "No element greater than 5 found." << endl;
}
return 0;
}
3. adjacent_find
std::adjacent_find用于查找序列中相邻重复的元素对。它返回一个指向序列中第一个重复元素的迭代器，如果序列中没有相邻的重复元素，则返回最后一个元素的下一个位置。
基本用法:
template< class InputIt >
InputIt adjacent_find( InputIt first, InputIt last );
template< class InputIt, class BinaryPredicate >
InputIt adjacent_find( InputIt first, InputIt last, BinaryPredicate pred );
第二个版本接受一个比较谓词。
示例：
// 包含标准输入输出库和向量库
#include <iostream>
#include <vector>
#include <algorithm>
// 使用标准命名空间，简化代码中标准库函数的调用
using namespace std;
// 程序入口函数
int main(){
// 初始化一个整数向量v，包含一组数字
vector<int>v = {0,1,3,4,5,5,7,7};
// 使用adjacent_find函数查找向量v中相邻重复的元素
// adjacent_find返回的是一个迭代器，指向第一个相邻重复元素的位置
auto it = adjacent_find(v.begin(), v.end());
// 如果找到相邻重复元素，输出该元素的值
cout << *it << endl;
// 使用lambda表达式作为谓词，查找向量v中相邻元素差值绝对值大于1的元素
// 这里的lambda表达式接收两个int类型的引用，返回一个bool值
// 它比较两个引用所指的元素的差值的绝对值是否大于1
auto in = adjacent_find(v.begin(), v.end(),[](const int &val,const int &b){return (abs(b-val)>1);});
// 如果找到满足条件的元素，输出该元素的值
cout << *in << endl;
// 程序正常结束
return 0;
}
4. binary_search
std::binary_search在一个已排序的范围内查找特定值。如果找到了该值，则返回true；否则，返回false。这个算法假设范围是按升序排序的。
基本用法:
template< class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value);
template< class ForwardIt, class T, class Compare>
bool binary_search(ForwardIt first, ForwardIt last, const T& value, Compare comp);
第二个版本接受一个比较函数。
示例：
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
// 使用set的查找，无需自定义比较函数，因为set本身就是有序的且默认升序
set<int> s = {1, 2, 3, 4, 5, 6};
if (binary_search(s.begin(), s.end(), 5)) {
cout << "Found: " << 5 << endl; // 更正输出格式
}
// 对于vector，如果要使用非默认比较（例如降序），需要正确传递比较函数
// 但是，注意binary_search要求容器是已排序的。先对vector排序
vector<int> v = {1, 3, 6, 5, 8, 4, 6};
sort(v.begin(), v.end(), [](const int &a, const int &b) { return a > b; }); // 先排序
// 确保v是按所需顺序排序后，再使用binary_search
if (binary_search(v.begin(), v.end(), 5, [](const int &a, const int &b) { return a > b; })) {
cout << "Found: " << 5 << endl; // 更正输出格式
} else {
cout << "Not found: " << 5 << endl; // 添加未找到时的输出
}
return 0;
}
注意：
binary_search算法要求其操作的范围必须是已排序的，不论是否提供了第四个比较函数参数。这是因为binary_search的工作原理基于二分查找算法，该算法的前提是输入数据是有序的。提供自定义的比较函数（即第四个参数）是为了适应不同的排序逻辑（如降序、自定义排序依据等），而不是为了处理无序数据。
如果输入范围是无序的，即使你提供了比较函数，binary_search的结果也是未定义的，可能会导致错误的查找结果。因此，在调用binary_search之前，你应该确保范围内的元素是按照你所指定的比较规则排序的。在上面的例子中，对vector<int> v应用了sort函数配合同样的比较函数进行了排序，之后才进行binary_search，这是正确的做法。
5. count
std::count计算范围内与给定值匹配的元素数量。
基本用法:
template< class InputIt, class T>
typename std::iterator_traits<InputIt>::difference_type count(InputIt first, InputIt last, const T& value);
示例：
//
// Created by 86189 on 2024/7/7.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main(){
// 初始化一个整数向量v，包含一组数字，用于后续的计数操作
vector<int>v = {1,2,2,2,2,2,5,6,9,8};
// 使用标准库函数count计算向量v中值为2的元素的数量，并输出结果
cout << count(v.begin(), v.end(),2) << endl;
return 0;
}
6. count_if
std::count_if类似于count，但它不是直接计数特定值，而是使用谓词来决定哪些元素应该被计数。
基本用法:
template< class InputIt, class UnaryPredicate>
typename std::iterator_traits<InputIt>::difference_type count_if(InputIt first, InputIt last, UnaryPredicate pred);
示例：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main(){
// 初始化一个整数向量，包含一组数字用于后续操作
vector<int>v = {1,2,2,3,2,2,5,6,9,8};
// 使用标准库函数count计算向量v中值为2的元素个数
// 并将结果输出到标准输出流
cout << count(v.begin(), v.end(),2) << endl;
// 使用标准库函数count_if计算向量v中大于2的元素个数
// 使用lambda表达式作为谓词，对每个元素进行判断
cout << count_if(v.begin(), v.end(),[](const int &a){return a>2;});
return 0;
}
这些算法是C++标准库 <algorithm> 头文件的一部分，为处理容器和数组提供了强大的工具。
3.常用排序算法
在C++中，排序和相关操作是非常实用的功能。
1. sort
sort函数是C++标准库提供的一个强大的排序算法，它能够对容器（如std::vector、std::list、std::deque等）或数组中的元素进行排序。默认情况下，它执行升序排序，但也可以通过提供自定义比较函数来进行降序或其他定制排序。sort位于<algorithm>头文件中。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main(){
// 初始化一个整数向量，包含一组待排序的数字
vector<int>v = {1,3,2,6,5,7,4};
// 对向量进行升序排序
sort(v.begin(), v.end());
// 遍历并打印排序后的向量
for(int n : v){
cout << n << " ";
}
cout << endl;
// 对向量进行降序排序
sort(v.begin(), v.end(),[](int &a,int &b){return a > b;});
// 再次遍历并打印排序后的向量
for(int n : v){
cout << n << " ";
}
return 0;
}
2. random_shuffle
random_shuffle函数用于将容器中的元素随机重新排列。不过需要注意的是，在C++14之后，random_shuffle已经被标记为已弃用，推荐使用shuffle函数，它提供了更好的随机性控制。random_shuffle同样位于<algorithm>头文件中。
基本用法示例 :
//
// Created by 86189 on 2024/7/10.
//
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;
/* 主函数 */
int main(){
/* 初始化一个整数向量，包含一组数字 */
vector<int>v = {1,9,6,4,5,3,5};
/* 初始化一个随机设备，用于生成随机数种子 */
random_device rd;
/* 使用Mersenne Twister算法初始化随机数生成器 */
mt19937 g(rd());
/* 使用随机数生成器对向量进行洗牌操作，以打乱其元素顺序 */
shuffle(v.begin(), v.end(), g);
/* 遍历并输出洗牌后的向量元素 */
for(int n : v) cout << n << " ";
return 0;
}
3. merge
merge函数用于合并两个已排序的序列，将它们合并成一个新的有序序列。这通常与sort配合使用于更复杂的排序算法中，如归并排序。它同样位于<algorithm>头文件中。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 主函数，演示如何使用标准库函数merge合并两个有序向量
int main(){
// 初始化两个有序向量v1和v2
vector<int>v1 = {1,3,5};
vector<int>v2 = {2,4,6};
// 初始化一个足够大的向量v3用于存放合并后的结果
// 其大小为v1和v2的大小之和
vector<int>v3(v1.size()+v2.size());
// 调用标准库函数merge将v1和v2合并到v3中
// 这里的merge函数假设输入的两个向量v1和v2是有序的
// 合并后的向量v3仍然保持有序
merge(v1.begin(), v1.end(),v2.begin(), v2.end(),v3.begin());
// 遍历并打印合并后的向量v3
for(int n : v3) cout << n << " ";
return 0;
}
4. reverse
reverse函数用于反转容器或数组中元素的顺序。它同样简单易用，只需提供起始和结束迭代器即可。此函数也在<algorithm>头文件中定义。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main() {
// 初始化一个整数向量v1，包含元素1, 3, 5
vector<int> v1 = {1, 3, 5};
// 翻转向量v1中的元素顺序
reverse(v1.begin(), v1.end());
// 遍历并打印翻转后的向量v1中的每个元素
for(int n : v1) cout << n << " ";
return 0;
}
4.常用拷贝和替换算法
在C++中，常用的拷贝和替换算法是处理容器或数组元素时非常基础且重要的操作。
1. copy
copy函数用于将一个范围内的元素复制到另一个范围内。这个函数位于<algorithm>头文件中。
基本用法示例:
// 包含标准库的头文件，用于输入输出和算法操作
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 程序的入口点
int main() {
// 初始化源向量，包含一组整数
vector<int> src = {1, 2, 3, 4};
// 初始化目标向量，大小与源向量相同
vector<int> dest(4);
// 将源向量的内容复制到目标向量
// 使用标准库算法copy进行复制操作
copy(src.begin(), src.end(), dest.begin());
// 遍历目标向量并打印每个元素
// 用于展示复制操作的结果
for(int n : dest) cout << n << " ";
// 程序正常结束
return 0;
}
2. replace
replace函数用于在给定范围内查找指定的旧值，并将其替换为新值。它也位于<algorithm>头文件中。
基本用法示例:
#include <algorithm> // 包含算法库，用于使用replace函数
#include <iostream> // 包含输入输出流，用于标准输出
#include <vector> // 包含向量容器，用于存储和操作整数序列
using namespace std;
int main() {
vector<int> src = {1, 2, 3, 4}; // 初始化一个整数向量，包含1, 2, 3, 4
// 使用replace函数将向量src中所有的2替换为99
// replace函数的作用是：在给定的范围内，找到所有与目标值相同的元素，并将其替换为新值
replace(src.begin(), src.end(), 2, 99);
// 遍历向量src，并打印每个元素
// 这里使用范围for循环来遍历向量，展示replace操作后的结果
for(int n : src) cout << n << " ";
return 0; // 程序正常退出
}
3. replace_if
replace_if函数类似于replace，但它不是直接匹配值，而是基于谓词（一个返回bool值的函数或函数对象）来决定是否进行替换。当谓词对元素返回true时，该元素会被替换。
基本用法示例:
#include <algorithm> // 使用标准库的算法
#include <iostream> // 使用标准库的输入输出流
#include <vector> // 使用标准库的向量容器
using namespace std;
// 主函数，程序的入口点
int main() {
// 初始化一个整数向量，包含1到4
vector<int> src = {1, 2, 3, 4};
// 使用replace_if算法替换向量中所有满足条件的元素
// 条件是元素值为偶数，将其替换为99
replace_if(src.begin(), src.end(), [](int n){return n%2==0;}, 99);
// 遍历向量并打印每个元素
for(int n : src) cout << n << " ";
return 0; // 程序正常结束
}
4. swap
swap函数用于交换两个对象的值。它可以用于内置类型，也可以用于自定义类型（只要这些类型重载了swap函数或遵循移动语义）。对于标准库容器，可以直接调用它们的swap成员函数，或者使用std::swap函数，它位于<utility>头文件中。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main() {
// 初始化源向量
vector<int> src = {1, 2, 3, 4};
// 初始化目标向量
vector<int> dest = {7,6,8,5,3,4};
// 交换源向量和目标向量的内容
// 说明：这里使用swap函数来交换两个向量的内容，目的是为了展示向量内容的交换过程
swap(src, dest);
// 遍历并打印源向量的内容
for (int n : src) cout << n << " ";
cout << endl;
// 遍历并打印目标向量的内容
for (int n : dest) cout << n << " ";
return 0;
}
这些算法极大地简化了在C++中处理数据集合的任务，提高了代码的可读性和效率。
5.常用算术生成算法
在C++中，除了拷贝和替换算法外，算术生成算法也是处理数据集合时经常使用的工具。
1. accumulate
accumulate函数用于计算一系列数值的总和（累积和）。此函数位于<numeric>头文件中，可以接受一个初始值作为累积和的起始点。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main(){
// 初始化一个整数向量v，包含一组预设的整数
vector<int>v = {1,10,2,3,5};
// 使用accumulate函数对向量v中的所有元素进行累加，初始值为0
// accumulate函数是标准库中用于累加的算法，这里展示了其在向量操作中的应用
int sum = accumulate(v.begin(), v.end(),0);
// 输出累加结果
cout << sum << endl;
// 程序正常结束
return 0;
}
2. fill
fill算法用于将一个范围内所有元素赋值为某个特定的值。它同样位于<algorithm>头文件中。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 主函数，程序的入口点
int main() {
// 初始化一个长度为10的整数向量，所有元素初始值为0
vector<int> vec(10, 0);
// 使用标准库函数fill将向量的所有元素赋值为7
fill(vec.begin(), vec.end(), 7);
// 遍历向量并打印每个元素
for(int num : vec)
cout << num << " ";
return 0;
}
这两个算法在处理数值集合时非常有用，accumulate用于求和运算，而fill则用于快速设置一系列值，比如初始化数组或向量等。
6.常用集合算法
集合算法在C++标准库中的<algorithm>头文件里定义，它们主要用于处理集合（如数组、向量等容器）之间的数学集合操作。
1. set_intersection
set_intersection算法用于找出两个已排序的集合的交集，并将结果存放到另一个集合中。集合需要是有序的，且不能有重复元素。
基本用法示例:
// 包含必要的头文件
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
// 主函数
int main(){
// 初始化两个集合，分别包含一组整数
set<int>s = {1,2,3,4,5,6};
set<int>s1 = {2,4,6,8,10};
// 初始化一个向量，用于存储两个集合的交集元素
// 其大小预先估计为两个集合元素总数之和
vector<int>v(s.size()+s1.size());
// 使用set_intersection算法计算两个集合的交集
// 并将结果存储在向量v中
auto it = set_intersection(s.begin(), s.end()
,s1.begin(), s1.end(),
v.begin());
// 调整向量的大小，以去除多余的未使用的空间
// 它的大小现在等于交集中实际元素的数量
v.resize(it - v.begin());
// 遍历并打印向量中的元素，即两个集合的交集
for(int n : v) cout << n << " ";
// 程序正常退出
return 0;
}
2. set_union
set_union算法用于合并两个已排序的集合，去除重复元素，得到并集，并将结果存放到另一个集合中。
基本用法示例:
// 包含必要的头文件
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
// 主函数
int main(){
// 初始化两个集合，分别包含一组不重复的整数
set<int>s = {1,2,3,4,5,6};
set<int>s1 = {2,4,6,8,10};
// 初始化一个向量，大小为两个集合元素总数，用于存储合并后的结果
vector<int>v(s.size()+s1.size());
// 使用set_union算法将两个集合的元素合并到向量v中，重复的元素只出现一次
// set_union算法返回一个迭代器，指向向量v中第一个未被写入的元素
auto it = set_union(s.begin(), s.end()
,s1.begin(), s1.end(),
v.begin());
// 根据返回的迭代器调整向量v的大小，使其正好包含所有合并后的元素
v.resize(it - v.begin());
// 遍历向量v，输出合并后的所有元素
for(int n : v) cout << n << " ";
return 0;
}
3. set_difference
set_difference算法用于找出两个已排序的集合的差集，即第一个集合中存在但第二个集合中不存在的元素，并将结果存放到另一个集合中。
基本用法示例:
//
// Created by 86189 on 2024/7/10.
//
//
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
// 主函数
int main(){
// 初始化两个集合，分别包含一组整数
set<int>s = {1,2,3,4,5,6};
set<int>s1 = {2,4,6,8,10};
// 初始化一个向量，用于存储两个集合的差集结果
vector<int>v(s.size()+s1.size());
// 使用std::set_difference算法计算两个集合的差集
// 并将结果写入向量v中
auto it = set_difference(s.begin(), s.end()
,s1.begin(), s1.end(),
v.begin());
// 调整向量的大小，使其正好包含所有差集元素
v.resize(it - v.begin());
// 遍历并输出向量中的差集元素
for(int n : v) cout << n << " ";
return 0;
}
这些算法都要求输入序列是预先排序的，并且对于set_intersection和set_difference来说，如果输入序列中有重复元素，结果只包含每个不同元素的一个实例。