C++ STL中的变易算法(Modifying Algorithms)是指那些能够修改容器内容的算法,主要用于修改容器中的数据,例如插入、删除、替换等操作。这些算法同样定义在头文件 <algorithm>
中,它们允许在容器之间进行元素的复制、拷贝、移动等操作,从而可以方便地对容器进行修改和重组。
主要包括以下几类变易算法:
copy()
:将一个容器的元素复制到另一个容器中。copy_if()
:根据给定的条件(函数对象或谓词)复制满足条件的元素到另一个容器中。copy_n()
:从指定位置开始,复制指定个数的元素到另一个容器中。copy_backward()
:将一个容器的元素复制到另一个容器中,并保持原有的顺序。fill()
:用指定值替换容器中的所有元素。fill_n()
:用指定值替换容器中从指定位置开始的一定数量的元素。generate()
:根据给定的生成函数,替换容器中的所有元素。generate_n()
:根据给定的生成函数,替换容器中从指定位置开始的一定数量的元素。move()
:将一个容器中的元素移动到另一个容器中,通常用于移动语义的场景。这些变易算法允许我们在不创建新容器的情况下,对现有容器进行元素的复制、拷贝和重排。使用这些算法可以实现高效的数据操作,节省了内存开销和不必要的数据拷贝。同时,这些算法也是C++ STL中非常有用和常用的功能,为C++开发者提供了强大的工具来操作和修改容器中的元素。
Copy 算法函数,用于将一个源序列的内容复制到另一个目标序列中。copy函数的用法如下:
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);
其中,first、last
是迭代器,表示源序列的范围;result
是迭代器,表示目标序列的起始位置。调用copy
函数后,将会将[first, last]
区间内的元素复制到从result
开始的目标序列中,并返回指向目标序列最后一个复制元素之后的位置的迭代器。
需要注意的是,copy函数只能复制对象,不能使用于复制C字符串(包括char*和char[])
等字符数组。对于字符数组,可以使用strcpy
函数进行复制。另外,如果源序列区间和目标序列区间有重叠部分,需要使用copy_backward
函数。
如下案例中,实现容器之间元素的拷贝复制操作,将两个迭代器进行互相拷贝。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
vector<int> var1 = { 1,3,5,7,9 };
vector<int> var2 = { 2,4,6,8,10 };
// 复制var1到var2 此时var2中的内容将被覆盖
copy(var1.begin(), var1.end(), var2.begin());
// var1 -> 覆盖到 --> var2
for_each(var2.begin(), var2.end(), MyPrint);
cout << endl;
// 复制var1中的前3个元素,并输出
copy_backward(var1.begin(), var1.begin() + 2, var1.end());
for_each(var1.begin(), var1.end(), MyPrint);
system("pause");
return 0;
}
Swap 算法函数,用于交换两个对象或是两个结构的值。swap函数的用法如下:
template <class T>
void swap (T& a, T& b);
其中,a、b
是要交换值的两个对象。
swap函数使用时需要注意,swap并不像第一眼看到的那样简单粗暴地直接交换值,它实际上是通过移动指针进行的值交换,因此对于大规模的对象交换,使用swap
会比暴力直接交换值更加高效。同时,swap函数还保证了异常安全性,即在对象交换时如果发生了异常,swap函数会确保原始状态恢复,不会产生未定义行为。
在C++11中,类也可以自定义swap
成员函数,当使用了自定义的swap函数时,调用std::swap
函数将使用类内定义的swap函数进行值交换。一般而言,自定义swap函数应该优先使用std::swap
进行值交换,从而可以借助std::swap
的优势提高交换效率。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
vector<int> var1 = { 1,3,5,7,9 };
vector<int> var2 = { 2,4,6,8,10 };
// 两个容器之间数值互换
swap(var1, var2);
for_each(var1.begin(), var1.end(), MyPrint);
// 通过迭代的方式实现数值互换
iter_swap(&var1, &var2);
for_each(var2.begin(), var2.end(), MyPrint);
// 区间选择交换
swap_ranges(var1.begin(), var1.end(), var2.begin());
for_each(var2.begin(), var2.end(), MyPrint);
system("pause");
return 0;
}
Transform 算法函数,用于将给定源序列中的元素按照指定规则进行变换,并将结果存放到目标序列中。transform函数的用法如下:
template<class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);
其中,first1、last1
是迭代器,表示源序列的范围;result
是迭代器,表示目标序列的起始位置;op是一个一元函数对象,用于对源序列中的元素进行变换。调用transform
函数后,将会对[first1, last1]
区间内的每个元素执行一次op操作,并将结果存放到对应的result
位置。
但读者需要注意,transform函数会根据op的返回值类型确定目标序列的元素类型,并自动调用构造函数生成目标序列中的元素。因此,如果op返回的类型是一个自定义的类型,需要确保该类型具有默认构造函数和赋值运算符函数。另外,如果源序列与目标序列重叠,需要使用另一种重载的transform函数来保证正确性。
transform函数的使用场景十分广泛,可以用于对任意类型的序列进行任意类型的变换,例如将数组中的每个元素加1,将vector中的每个字符串转换为大写形式等等。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
class TransForm
{
// 在搬运的过程中每次+10写入到vTarget;
public: int operator()(int val)
{
return val + 10;
}
};
class New_TransForm
{
// 使用仿函数,将两个数组中的值相加
public: int operator()(int val1, int val2)
{
return val1 + val2;
}
};
int main(int argc, char* argv[])
{
vector<int> var = { 1,2,3,4,5 }; // 原容器
vector<int > vTarget; // 目标容器
// 第一种形式:将var中的数据每次+10后搬运到vTarget中
vTarget.resize(5); // transform 不会自动开辟内存,需要我们手动开辟
transform(var.begin(), var.end(), vTarget.begin(), TransForm());
// 循环输出 此处的 [](int val){cout << val << " "; 其实是 MyPrint 不过是匿名了
for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; });
cout << endl;
// 第二种形式:将var1,var2两个容器中的值相加,相加后搬运到new_vTarget容器中
vector<int> var1 = { 1, 2, 3, 4, 5 }; // 原容器
vector<int> var2 = { 6, 7, 8, 9, 10 }; // 原容器
vector<int> new_vTarget; // 目标容器
new_vTarget.resize(5);
transform(var1.begin(), var1.end(), var2.begin(), new_vTarget.begin(), New_TransForm());
for_each(new_vTarget.begin(), new_vTarget.end(), MyPrint);
system("pause");
return 0;
}
Replace 算法函数,用于将给定序列中的所有等于给定值的元素替换为指定的新值。replace函数的用法如下:
template <class ForwardIterator, class T>
void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);
其中,first、last
是迭代器,表示待替换的序列的范围;old_value
表示要被替换的值;new_value
表示替换后的新值。调用replace
函数后,会将[first, last]
区间内所有等于old_value
的元素全部替换为new_value
。
但读者需要注意,replace函数只能替换对象,不能复制对象。例如,replace函数无法用来替换字符串或其他类似C风格字符串或STL字符串的对象。如果需要替换字符串或其他复杂对象,可以考虑使用其他函数,例如字符串的replace成员函数。另外,replace函数只能对相等的元素进行替换,无法按照某种规律进行替换。如果需要按照某种规律替换序列,可以考虑使用replace_if函数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
class MyCompart
{
public: bool operator()(int val){
// 将大于5的数据替换
return val > 5;
}
};
int main(int argc, char* argv[])
{
vector<int> var = { 1,2,3,4,4,5,5,6,7,8,8,9,0,2,1,0 };
// 全部替换: 将var中的4全部替换为4000
replace(var.begin(), var.end(), 4, 4000);
for_each(var.begin(), var.end(), MyPrint);
// 条件替换:将所有的大于5的数替换为0
replace_if(var.begin(), var.end(), MyCompart(), 0);
for_each(var.begin(), var.end(), MyPrint);
system("pause");
return 0;
}
Fill 算法函数,用于将给定序列中的所有元素全部填充为指定的值。fill函数的用法如下:
template <class ForwardIterator, class T>
void fill (ForwardIterator first, ForwardIterator last, const T& val);
其中,first、last
是迭代器,表示待填充的序列的范围;val
表示要填充的值。调用fill
函数后,会将[first, last]
区间内的所有元素全部填充为val
。
需要注意的是,fill
函数只能填充对象,不能复制对象。例如,fill
函数无法用来填充字符串或其他类似C风格字符串或STL字符串的对象。如果需要填充字符串或其他复杂对象,可以考虑使用其他函数,例如memset
函数对于字符串数组的初始化。还需要注意的是,fill函数只能等量复制相同的值,无法按照某种规律变化,如果需要按照某种规律填充序列,可以使用generate
函数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
vector<int> var = { 1,2,3,4,4,5,5,6,7,8,8,9,0,2,1,0 };
// 将前3个元素填充为0
fill_n(var.begin(), 3, 0);
for_each(var.begin(), var.end(), MyPrint);
// 全部填充为0
fill_n(var.begin(), var.size(), 0);
for_each(var.begin(), var.end(), MyPrint);
// 全部填充为10
fill(var.begin(), var.end(), 10);
for_each(var.begin(), var.end(), MyPrint);
system("pause");
return 0;
}
Remove_if 算法函数,用于从给定序列中删除满足某个条件的元素。remove_if函数的用法如下:
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
其中,first、last
是迭代器,表示要进行操作的序列的范围;pred
是一个一元谓词函数,用于指定需要删除的元素。调用remove_if
函数后,将会删除[first, last]
区间内满足pred
条件的元素,并将其移到区间尾部,返回指向第一个被移动元素位置的迭代器。
remove_if函数并不会真正地删除被移动的元素,而是将它们移动到区间尾部,所以最终在[first, last]
区间剩下的元素是不确定的。如果想要真正地删除被移动的元素,可以再调用容器类的erase
函数删除尾部的元素。需要注意的是,erase
函数只能对带有erase成员函数(例如vector、list)的容器使用,对于没有erase
成员函数的容器(例如数组),需要手动调整数组的长度。
如下是一个使用案例,代码中实现了将容器中不等于某个值的元素移除出容器,代码如下所示;
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
bool even(int val) { return val % 2 ? 0 : 1; }
int main(int argc, char* argv[])
{
vector<int> var { 4,3,4,8,9,5,6,7,8,9,2,1,4 };
// 移除var里面的所有的4
vector<int>::iterator result;
result = remove(var.begin(), var.end(), 4);
for_each(var.begin(), var.end(), MyPrint);
cout << endl;
// 移除var里面所有的偶数
vector<int>::iterator result1;
result1 = remove_if(var.begin(), var.end(), even);
for_each(var.begin(), var.end(), MyPrint);
system("pause");
return 0;
}
Remove_copy 算法函数,用于将满足某个条件的元素从一个源序列复制到目标序列中,同时去除不满足条件的元素。remove_copy函数的用法如下:
template <class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& value);
其中,first、last
是迭代器,表示要进行操作的源序列的范围;result
是迭代器,表示复制后的目标序列起始位置;value
是需要去除的元素的值。调用remove_copy
函数后,将会将原序列[first, last]
中不等于value
的元素复制到目标序列[result, result + (last - first))
中,并返回目标序列最后一个复制元素的后继位置的迭代器。需要注意的是,remove_copy
函数并不会真正地将值为value
的元素从原序列中移除,而是将它们留在原序列中,因此返回的目标序列只包含不等于value
的元素。
remove_copy函数的使用场景通常是,需要在不破坏原序列的情况下,复制其中一些元素到目标序列中,并去除一些元素。如下案例中所示,算法实现了将原容器中不等于某个给定值的元素复制到新容器中。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
bool even(int val){ return val % 2 ? 0 : 1; }
int main(int argc, char* argv[])
{
vector<int> var { 4,3,4,8,9,5 };
int iarray[6] = { 0, 0, 0, 0, 0, 0, };
// 移除复制,将var中的数据的前4个数据复制到iarray中,var中数据保持不变
remove_copy(var.begin(), var.end(), iarray, 4);
for_each(iarray, iarray+6, MyPrint);
cout << endl;
// 移除var中的偶数,剩余元素复制到iarray中
remove_copy_if(var.begin(), var.end(), iarray, even);
for_each(iarray, iarray + 6, MyPrint);
system("pause");
return 0;
}
Unique 算法函数,用于删除给定序列中相邻的重复元素,只保留一个副本。unique函数的用法如下:
template <class ForwardIterator>
ForwardIterator unique (ForwardIterator first, ForwardIterator last);
其中,first、last
是迭代器,表示要进行去重的序列的范围。调用unique
函数后,将会去除[first, last]
区间内相邻的重复元素,仅保留第一个元素,其余相同的元素都将被删除,剩下的元素会被移动到前面,返回指向最后一个未被删除元素之后的迭代器,通常与erase
函数一起使用以删除多余的元素。
unique函数只删除相邻的重复元素,不删除中间隔着其他元素的重复元素,例如序列[a, b, b, c, b, d, d]
经过unique
去重后会变为[a, b, c, b, d]
,注意不会删除序列中间的b,因为它并不相邻。还需要注意的是,unique只对相邻元素进行去重,如果需要对无序序列进行去重,可以先对序列进行排序,然后再调用unique函数。
如下笔者提供两个案例,案例中函数unique_copy
实现邻近元素去重,函数unique
去除连续重复元素,如下所示;
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
vector<int> var { 2,5,5,5,5,5,6,7,5,9,5};
int iarray[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
// 实现邻近元素去重,只能去除相邻元素中重复的
unique_copy(var.begin(), var.end(), iarray);
for_each(iarray, iarray + 10, MyPrint);
cout << endl;
// 另一种邻近元素去重算法
vector<int>::iterator result;
result = unique(var.begin(), var.end());
for_each(var.begin(),result,MyPrint);
system("pause");
return 0;
}
Reverse 算法函数,用于将给定序列中的元素翻转,即将元素按逆序排列。reverse函数的用法如下:
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
其中,first、last
是迭代器,表示要进行翻转的序列的范围。调用reverse
函数后,将会把[first, last]
中的元素按相对位置逆序排列,即对于[first, last]
中的任意两个迭代器i、j
,若 i小于j,则翻转后的序列中,i对应的元素会出现在j之后。
读者需要注意,reverse函数不会改变序列中各个元素的值,只会改变它们的位置,因此是一个非变易算法。与rotate
函数类似,reverse
函数一般只用于BidirectionalIterator
迭代器类型的序列,即支持双向遍历的序列(例如双向链表),而不支持随机访问的序列(例如单向链表)。
简单总结来说,该算法实现了对容器中元素的反向排列,和反向复制容器中的数据,这个复制案例如下所示;
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
vector<int> var { 1,2,3,4,5,6,7,8,9,10 };
// 将元素反向排列后输出
reverse(var.begin(), var.end());
for_each(var.begin(), var.end(), MyPrint);
cout << endl;
// 将元素反向复制到iarray数组中存储
int iarray[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
reverse_copy(var.begin(), var.end(), iarray);
for_each(iarray,iarray+10, MyPrint);
system("pause");
return 0;
}
Rotate是的一个算法函数,用于将给定序列中的元素向左循环移动若干个位移,即将序列中前面的元素移动到末尾,其最终的位置与原来位置的距离是一个定值。rotate函数的用法如下:
template <class ForwardIterator>
void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last);
其中,first、middle、last
是迭代器,表示要进行循环移动的序列的范围。调用rotate函数后,将会将序列[first, last]
中的元素向左循环移动,使得中间区间[middle, last)
的元素移动到前面,前面的区间[first, middle)
的元素移动到后面,即做如下变换:
[ a b c d e f g ] -> [ d e f g a b c ]
↑ ↑
middle first
但读者需要注意,rotate
函数不会改变序列中各个元素的值,只会改变它们的位置。另外,若中间区间[middle, last)
为空,则整个序列不会发生变化;若其包含所有元素,则rotate
等效于reverse
函数。由于此函数的核心功能是反转数组,所以在使用时需要自行指定一个中心数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
vector<int> var { 1,2,3,4,5,6,7,8,9,10 };
for_each(var.begin(), var.end(), MyPrint);
// 以元素6为中心,将两边数据旋转后输出
cout << "middle => " << *(var.begin() + 5) << endl;
rotate(var.begin(), var.begin() + 5, var.end());
for_each(var.begin(), var.end(), MyPrint);
cout << endl;
// 旋转后复制到iarray数组中存储
int iarray[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
rotate_copy(var.begin(), var.begin() + 5, var.end(), iarray);
for_each(iarray,iarray+10, MyPrint);
system("pause");
return 0;
}
Random 是C++11
引入的标准库函数,用于生成随机数。该函数库提供了多个随机数引擎和分布函数,可以用于产生各种类型的随机数,例如在给定范围内生成整数或浮点数、生成布尔值等。以下是random
库中的一些常用函数:
使用random
库时,通常先创建一个随机数引擎实例,然后再创建一个特定的分布函数实例,最后利用分布函数实例的调用运算符()
来产生随机数。例如:
std::mt19937 gen{std::random_device{}()};
std::uniform_int_distribution<int> dist{1, 10};
int x = dist(gen); // 在1到10之间生成一个均匀分布的整数
如下案例中实现了简单的生成随机数,以及对随机数进行初始化,其代码中的算法generate_n
用于生成随机数,而random_shuffle
算法则用于打乱数组。
#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
int main(int argc, char* argv[])
{
// 增加此方法,每次都可以随机打乱
srand((unsigned int)time(NULL));
vector<int> var(10);
// 生成随机数:生成5个随机数,并存入var
generate_n(var.begin(), 5, rand);
for_each(var.begin(), var.end(), MyPrint);
cout << endl;
// 随机抖动: 随机的打乱一个数组
int iarray[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
random_shuffle(iarray, iarray + 10);
for_each(iarray, iarray + 10, MyPrint);
system("pause");
return 0;
}
Partition 算法函数,用于将给定序列中的元素根据某个条件分为两组,使得满足条件的元素全部在一组,不满足条件的元素在另一组,最终返回第一个不满足条件的元素的位置。具体流程是,首先在序列中选定一个元素作为分界点,然后将序列中的其他元素依次与分界点比较,如果满足条件则移动到左边,否则移动到右边,最终左边的所有元素都满足条件,右边的所有元素都不满足条件。partition函数的用法如下:
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
其中,first
和last
是一个前闭后开区间,表示待分割的序列的范围;pred
是一个一元谓词函数,用于指定元素满足的条件。函数执行完毕后,返回指向第一个不满足条件的元素的迭代器。
该算法用于重新分割排列容器的元素,第一种无序分割,第二种为有序分割,如下代码是该函数的具体使用案例。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void MyPrint(int x) { cout << x << " "; }
// 判断是否小于10
bool Less(int y){ return y < 10 ? 1 : 0; }
int main(int argc, char* argv[])
{
int iarray[10] = { 12,45,2,6,8,-5,-12,-78,-4,3 };
// 按照小于10对容器进行分割
int * result = partition(iarray, iarray + 10, Less);
// 输出小于10的元素
for_each(iarray, result , MyPrint);
cout << endl;
// 按照小于10对容器分割,但保持原来的次序
int * new_ret = stable_partition(iarray, iarray + 10, Less);
for_each(iarray, iarray + 10, MyPrint);
cout << " --> 分界元素 Mid:" << *new_ret << endl;
system("pause");
return 0;
}
本文作者: 王瑞 本文链接: https://www.lyshark.com/post/83787397.html 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!