C++ STL中的变易算法(Modifying Algorithms)是指那些能够修改容器内容的算法,主要用于修改容器中的数据,例如插入、删除、替换等操作。这些算法同样定义在头文件 <algorithm>
中,它们允许在容器之间进行元素的复制、拷贝、移动等操作,从而可以方便地对容器进行修改和重组。
主要包括以下几类变易算法:
- 复制算法:
copy()
:将一个容器的元素复制到另一个容器中。
copy_if()
:根据给定的条件(函数对象或谓词)复制满足条件的元素到另一个容器中。
copy_n()
:从指定位置开始,复制指定个数的元素到另一个容器中。
copy_backward()
:将一个容器的元素复制到另一个容器中,并保持原有的顺序。
- 拷贝算法:
fill()
:用指定值替换容器中的所有元素。
fill_n()
:用指定值替换容器中从指定位置开始的一定数量的元素。
generate()
:根据给定的生成函数,替换容器中的所有元素。
generate_n()
:根据给定的生成函数,替换容器中从指定位置开始的一定数量的元素。
- 移动算法:
move()
:将一个容器中的元素移动到另一个容器中,通常用于移动语义的场景。
这些变易算法允许我们在不创建新容器的情况下,对现有容器进行元素的复制、拷贝和重排。使用这些算法可以实现高效的数据操作,节省了内存开销和不必要的数据拷贝。同时,这些算法也是C++ STL中非常有用和常用的功能,为C++开发者提供了强大的工具来操作和修改容器中的元素。
8.1 元素复制算法
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 };
copy(var1.begin(), var1.end(), var2.begin());
for_each(var2.begin(), var2.end(), MyPrint); cout << endl;
copy_backward(var1.begin(), var1.begin() + 2, var1.end()); for_each(var1.begin(), var1.end(), MyPrint);
system("pause"); return 0; }
|
8.2 元素交换算法
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; }
|
8.3 元素搬运算法
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 { 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;
vTarget.resize(5); transform(var.begin(), var.end(), vTarget.begin(), TransForm()); for_each(vTarget.begin(), vTarget.end(), [](int val){cout << val << " "; }); cout << endl; 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; }
|
8.4 元素替换算法
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){ 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 };
replace(var.begin(), var.end(), 4, 4000); for_each(var.begin(), var.end(), MyPrint);
replace_if(var.begin(), var.end(), MyCompart(), 0); for_each(var.begin(), var.end(), MyPrint);
system("pause"); return 0; }
|
8.5 容器初始化算法
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 };
fill_n(var.begin(), 3, 0); for_each(var.begin(), var.end(), MyPrint);
fill_n(var.begin(), var.size(), 0); for_each(var.begin(), var.end(), MyPrint);
fill(var.begin(), var.end(), 10); for_each(var.begin(), var.end(), MyPrint);
system("pause"); return 0; }
|
8.6 普通条件移除
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 };
vector<int>::iterator result; result = remove(var.begin(), var.end(), 4); for_each(var.begin(), var.end(), MyPrint); cout << endl; vector<int>::iterator result1; result1 = remove_if(var.begin(), var.end(), even); for_each(var.begin(), var.end(), MyPrint);
system("pause"); return 0; }
|
8.7 条件移除复制
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, };
remove_copy(var.begin(), var.end(), iarray, 4); for_each(iarray, iarray+6, MyPrint); cout << endl;
remove_copy_if(var.begin(), var.end(), iarray, even); for_each(iarray, iarray + 6, MyPrint); system("pause"); return 0; }
|
8.8 容器元素去重算法
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; }
|
8.9 元素反向拷贝算法
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;
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; }
|
8.10 容器旋转复制算法
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);
cout << "middle => " << *(var.begin() + 5) << endl; rotate(var.begin(), var.begin() + 5, var.end()); for_each(var.begin(), var.end(), MyPrint); cout << endl;
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; }
|
8.11 随机数相关算法
Random 是C++11
引入的标准库函数,用于生成随机数。该函数库提供了多个随机数引擎和分布函数,可以用于产生各种类型的随机数,例如在给定范围内生成整数或浮点数、生成布尔值等。以下是random
库中的一些常用函数:
- std::mt19937:是一种随机数引擎,使用梅森旋转算法产生高质量的伪随机数。
- std::uniform_int_distribution:用于生成随机的整数分布,可以指定整数范围。
- std::uniform_real_distribution:用于生成随机的浮点数分布,可以指定实数范围。
- std::normal_distribution:用于生成随机的标准正态分布或自定义正态分布。
- std::bernoulli_distribution:用于模拟一个伯努利分布,即二项分布的情况,可以生成布尔值。
使用random
库时,通常先创建一个随机数引擎实例,然后再创建一个特定的分布函数实例,最后利用分布函数实例的调用运算符()
来产生随机数。例如:
std::mt19937 gen{std::random_device{}()}; std::uniform_int_distribution<int> dist{1, 10}; int x = dist(gen);
|
如下案例中实现了简单的生成随机数,以及对随机数进行初始化,其代码中的算法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);
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; }
|
8.12 容器元素分割算法
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 << " "; }
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 };
int * result = partition(iarray, iarray + 10, Less);
for_each(iarray, result , MyPrint); cout << endl;
int * new_ret = stable_partition(iarray, iarray + 10, Less); for_each(iarray, iarray + 10, MyPrint); cout << " --> 分界元素 Mid:" << *new_ret << endl;
system("pause"); return 0; }
|