8.1 C++ STL 变易拷贝算法

C++ STL中的变易算法（Modifying Algorithms）是指那些能够修改容器内容的算法，主要用于修改容器中的数据，例如插入、删除、替换等操作。这些算法同样定义在头文件 <algorithm> 中，它们允许在容器之间进行元素的复制、拷贝、移动等操作，从而可以方便地对容器进行修改和重组。

主要包括以下几类变易算法：

1. 复制算法：
   • copy()：将一个容器的元素复制到另一个容器中。
   • copy_if()：根据给定的条件（函数对象或谓词）复制满足条件的元素到另一个容器中。
   • copy_n()：从指定位置开始，复制指定个数的元素到另一个容器中。
   • copy_backward()：将一个容器的元素复制到另一个容器中，并保持原有的顺序。
2. 拷贝算法：
   • fill()：用指定值替换容器中的所有元素。
   • fill_n()：用指定值替换容器中从指定位置开始的一定数量的元素。
   • generate()：根据给定的生成函数，替换容器中的所有元素。
   • generate_n()：根据给定的生成函数，替换容器中从指定位置开始的一定数量的元素。
3. 移动算法：
   • 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 };

  // 复制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;
}

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
{
  // 在搬运的过程中每次+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;
}

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){
  // 将大于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;
}

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 };

  // 将前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;
}

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 };

  // 移除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;
}

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, };

  // 移除复制,将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;
}

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;

  // 将元素反向复制到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;
}

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);

  // 以元素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;
}

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);  // 在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;
}

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 << " "; }

// 判断是否小于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 许可协议。转载请注明出处！