优质校建设专题网站,公司优化网站的案例,福州网站设计软件公司,苏州市高新区建设局网站C STL中的变易算法#xff08;Modifying Algorithms#xff09;是指那些能够修改容器内容的算法#xff0c;主要用于修改容器中的数据#xff0c;例如插入、删除、替换等操作。这些算法同样定义在头文件 algorithm 中#xff0c;它们允许在容器之间进行元素的复制…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函数的用法如下
templateclass 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 algorithmusing namespace std;void MyPrint(int x) { cout x ; }int main(int argc, char* argv[])
{vectorint var1 { 1,3,5,7,9 };vectorint var2 { 2,4,6,8,10 };// 复制var1到var2 此时var2中的内容将被覆盖copy(var1.begin(), var1.end(), var2.begin());// var1 - 覆盖到 -- var2for_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;
}8.2 元素交换算法
Swap 算法函数用于交换两个对象或是两个结构的值。swap函数的用法如下
template class T
void swap (T a, T b);其中a、b是要交换值的两个对象。
swap函数使用时需要注意swap并不像第一眼看到的那样简单粗暴地直接交换值它实际上是通过移动指针进行的值交换因此对于大规模的对象交换使用swap会比暴力直接交换值更加高效。同时swap函数还保证了异常安全性即在对象交换时如果发生了异常swap函数会确保原始状态恢复不会产生未定义行为。
在C11中类也可以自定义swap成员函数当使用了自定义的swap函数时调用std::swap函数将使用类内定义的swap函数进行值交换。一般而言自定义swap函数应该优先使用std::swap进行值交换从而可以借助std::swap的优势提高交换效率。
#include iostream
#include vector
#include algorithmusing namespace std;void MyPrint(int x) { cout x ; }int main(int argc, char* argv[])
{vectorint var1 { 1,3,5,7,9 };vectorint 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函数的用法如下
templateclass 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[])
{vectorint var { 1,2,3,4,5 }; // 原容器vectorint 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容器中vectorint var1 { 1, 2, 3, 4, 5 }; // 原容器vectorint var2 { 6, 7, 8, 9, 10 }; // 原容器vectorint 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 algorithmusing 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[])
{vectorint var { 1,2,3,4,4,5,5,6,7,8,8,9,0,2,1,0 };// 全部替换: 将var中的4全部替换为4000replace(var.begin(), var.end(), 4, 4000); for_each(var.begin(), var.end(), MyPrint);// 条件替换:将所有的大于5的数替换为0replace_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 algorithmusing namespace std;void MyPrint(int x) { cout x ; }int main(int argc, char* argv[])
{vectorint var { 1,2,3,4,4,5,5,6,7,8,8,9,0,2,1,0 };// 将前3个元素填充为0fill_n(var.begin(), 3, 0);for_each(var.begin(), var.end(), MyPrint);// 全部填充为0fill_n(var.begin(), var.size(), 0);for_each(var.begin(), var.end(), MyPrint);// 全部填充为10fill(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 algorithmusing namespace std;void MyPrint(int x) { cout x ; }
bool even(int val) { return val % 2 ? 0 : 1; }int main(int argc, char* argv[])
{vectorint var { 4,3,4,8,9,5,6,7,8,9,2,1,4 };// 移除var里面的所有的4vectorint::iterator result;result remove(var.begin(), var.end(), 4);for_each(var.begin(), var.end(), MyPrint);cout endl;// 移除var里面所有的偶数vectorint::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 algorithmusing namespace std;void MyPrint(int x) { cout x ; }bool even(int val){ return val % 2 ? 0 : 1; }int main(int argc, char* argv[])
{vectorint 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, iarray6, MyPrint);cout endl;// 移除var中的偶数,剩余元素复制到iarray中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[])
{vectorint 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;// 另一种邻近元素去重算法vectorint::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 algorithmusing namespace std;void MyPrint(int x) { cout x ; }int main(int argc, char* argv[])
{vectorint 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,iarray10, 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 algorithmusing namespace std;void MyPrint(int x) { cout x ; }int main(int argc, char* argv[])
{vectorint 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,iarray10, MyPrint);system(pause);return 0;
}8.11 随机数相关算法
Random 是C11引入的标准库函数用于生成随机数。该函数库提供了多个随机数引擎和分布函数可以用于产生各种类型的随机数例如在给定范围内生成整数或浮点数、生成布尔值等。以下是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_distributionint 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));vectorint var(10);// 生成随机数生成5个随机数,并存入vargenerate_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 algorithmusing 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 许可协议。转载请注明出处
