C++之 泛型算法

概述

在《数据结构与算法》这门课中，我们学习了不少有关算法的底层知识，例如各种的排序算法，如何合并一个有序链表，元素计数等简单的算法。在STL库中，这些算法全都被封装起来，平常我们使用只需要调用即可。

泛型算法的泛型，就代表着这类算法任何容器都能使用，甚至包括内置的数组类型。大多数算法都定义在头文件algorithm中。还有一些数值算法定义在numeric中。

为什么泛型算法能够匹配不同的容器？这主要是迭代器的功劳。迭代器另算法不依赖于容器，通过迭代器的自加减功能就可以完成遍历的操作，在遍历中就能实现各种算法。但是算法依赖于元素类型的操作，例如某算法中需要判断相等，那么元素类型就必须能判断相等。此外我们还能通过lambda表达式等用自定义的操作代替默认的运算符。

只读算法

只读算法只会读取其范围内的元素，不会改变元素。

find

find寻找第一个匹配的值，返回一个迭代器。找到了则返回指向元素的迭代器，没找到则返回给定迭代器范围的尾部迭代器。

  vector<int> vNums{3, 5, 8, 1, 2, 5, 6};
  auto iter = find(vNums.cbegin(), vNums.cend(), 5);
  if (iter != vNums.cend())
  {
      cout << "Successfully find element: " << *iter << endl;
  }
  else
  {
      cout << "Find element failed." << endl;
  }

begin end

在头文件iterator中，内置数组专用，返回指向数组头部和尾部的迭代器。

  int nums[7] = {3, 5, 8, 1, 2, 5, 6};
  auto iter = find(begin(nums), end(nums), 4);
  if (iter != end(nums))
  {
      cout << "Successfully find element: " << *iter << endl;
  }
  else
  {
      cout << "Find element failed." << endl;
  }

accumulate

该函数会对迭代器范围内的元素进行求和。第三个参数为和的初值，注意：第三个参数的类型决定了使用哪个加法运算符和返回值的类型。

vector<float> FloatNums{1.1f, 4.5f, 7.0f, 5.6f, 1.0f, 23.2f};
cout << "int accumulate: " << accumulate(FloatNums.cbegin(), FloatNums.cend(), 0) << endl; // int 类型的加法运算符
cout << "float accumulate: " << accumulate(FloatNums.cbegin(), FloatNums.cend(), 0.0f) << endl;

vector<string> words{"hello ", "from ", "stl ","! "};
cout << "string accumulate: " << accumulate(words.cbegin(), words.cend(), string("")) << endl; // 不能用"", const char* 不支持加法运算符

equal

比较两个序列是否保存了相同的值。输入三个参数，前两个是一个序列的迭代器范围，第三个参数是第二个序列的的起始迭代器。

equal基于一个重要的假设，第二个序列与第一个序列一样长。

vector<int> nums1{1, 2, 3, 4, 5, 6};
vector<int> nums2{1, 2, 3, 4, 5};

cout << "nums1 " << (equal(nums1.cbegin(), nums1.cbegin() + 5, nums2.cbegin()) 
? "equals to " : "doesn't equal to ") << "nums2" << endl;

cout << "nums1 " << (equal(nums1.cbegin(), nums1.cend(), nums2.cbegin())
? "equals to " : "doesn't equal to ") << "nums2" << endl;;

写容器算法

在使用写容器算法是，确保序列原大小至少不小于我们要求算法写入的元素数目。这是因为算法不会执行容器操作，不能改变容器的大小。

fill

fill的参数接受一对迭代器范围，还有需要填充的值。

  vector<int> nums(6, 0);
  fill(nums.begin(), nums.end(), 1);  // 全部改为1
  for (auto& i : nums)
  {
      cout << i << " ";   // 1 1 1 1 1 1
  }
  cout << endl;

fill_n

fill_n接受的参数为起始迭代器，填充元素个数，填充元素值。请注意：填充元素个数一定要大于容器涵盖的范围。

vector<int> nums(6, 0);
fill_n(nums.begin(), nums.size(), 1);
for (auto& i : nums)
{
    cout << i << " ";   // 1 1 1 1 1 1
}
cout << endl;

一种安全的做法是使用插入迭代器，有关插入迭代器以及其他迭代器，将会在后面详细解释。使用back_inserter定义一个插入迭代器，接收参数为一个容器，返回一个插入迭代器。它是定义在头文件iterator中。当我们使用这个迭代器进行赋值，将会自动调用容器的push_back，并把元素插入到容器的后面。

vector<int> nums(6, 1);
back_insert_iterator<decltype(nums)> it = back_inserter(nums);
fill_n(it, 3, 3);
for (auto& i : nums)
{
    cout << i << " ";   // 1 1 1 1 1 1 3 3 3
}
cout << endl;

copy

copy接受一个迭代器范围和被拷贝的容器迭代器起始范围，其返回值为目的位置迭代器的值。

vector<int> nums(6, 3);
vector<int> newNums(2, 2);
copy(nums.begin(), nums.end(), back_inserter(newNums));
for (auto& i : newNums)
{
    cout << i << " ";   // 2 2 3 3 3 3 3 3
}
cout << endl;

replace

replace接受一对迭代器范围，查询值和替换值，容器内所有符合查询值替换成替换值。

vector<int> nums{1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
replace(nums.begin(), nums.end(), 3, 5);
for (auto& i : nums)
{
    cout << i << " ";   // 1 2 2 5 5 5 4 4 4 4
}
cout << endl;

replace_copy

将替换和拷贝综合，一个数组先复制一份到副本，再将副本的值进行替换。接受参数为，原数组迭代器范围，替换数组起始迭代器，查询值，和替换值。

重排元素的算法

sort

sort接受一对迭代器范围，然后以递增顺序进行排序。sort的底层排序算法是快速排序、插入排序和堆排序的综合。

数据量大时，采用快排。当分段后的元素数小于一个固定值（16），则会改用插入排序。如果递归层次太深，还会使用堆排序。

vector<int> nums{4, 2, 6, 2, 1, 3, 8};
sort(nums.begin(), nums.end());
for (auto& i : nums)
{
    cout << i << " ";   // 1 2 2 3 4 6 8
}
cout << endl;

unique

用于移除容器中相邻的重复元素。它返回一个迭代器，指向去重后的范围的末尾。常用用法是，先将无序数组进行排序，然后再使用这个算法，最后删除多余的部分。

vector<int> nums{4, 2, 6, 2, 1, 3, 8};
sort(nums.begin(), nums.end());
auto end = unique(nums.begin(), nums.end());
nums.erase(end);
for (auto& i : nums)
{
    cout << i << " ";   // 1 2 3 4 6 8
}
cout << endl;

定制操作

定制的sort

我们可以自定义一些函数，来完成元素排序的一些操作。通过向sort传入第三个参数，第三个参数一般是一个可以调用的表达式。

使用函数

例如我们可以按字符串字符个数从大到小进行排列：

bool isLonger(const string& ls, const string& rs)
{
    return ls.size() > rs.size();
}

int main()
{
    vector<string> words{"this", "is", "a", "example", "sentence"};
    sort(words.begin(), words.end(), isLonger);
    for (auto& i : words)
    {
        cout << i << " ";   // sentence example this is a
    }
    cout << endl;
}

使用lambda表达式

有关lambda表达式的知识，可以移步至：

https://bg.littleao.top/archives/cpp_lambda

vector<string> words{"this", "is", "a", "example", "sentence"};
sort(words.begin(), words.end(), [](const string& ls, const string& rs){
    return ls.size() > rs.size();
});
for (auto& i : words)
{
    cout << i << " ";   // sentence example this is a
}
cout << endl;

find_if

返回第一个满足条件表达式的迭代器。参数为迭代器范围，一个可调用的表达式。

vector<string> words{"this", "is", "a", "example", "sentence"};
size_t sz = 7;
auto iter = find_if(words.begin(), words.end(), [sz](const string& s){
    return s.size() == sz;
});
cout << *iter << endl; // example

for_each

接受一对迭代器范围和一个可调用的表达式，对每个元素都调用一遍这个表达式。

vector<string> words{"this", "is", "a", "example", "sentence"};
for_each(words.begin(), words.end(), [](const string& s){
    cout << s << " "; // this is a example sentence
});
cout << endl;

其他迭代器

插入迭代器

在之前我们介绍了后向插入迭代器back_inserter，类似于容器执行了一次push_back。此外还有front_inserter和inserter两种插入迭代器。

• front_inserter：相当于在容器中执行了push_front。

• inserter : 接受第二个参数，为给定容器的迭代器。元素赋值操作将会在这个迭代器之前插入元素。

  deque<int> nums{4, 5, 6};
  auto back_iter = back_inserter(nums);
  back_iter = 7;
  auto front_iter = front_inserter(nums);
  front_iter = 3;
  auto iter = inserter(nums, nums.begin() + nums.size()/2);
  iter = 4;

  for (auto& i : nums)
  {
      cout << i << " ";   // 3, 4, 4, 5, 6, 7
  }
  cout << endl;

容器支持push_back才能用back_inserter，容器支持push_front才能用front_inserter。

iostream迭代器

iostream不是容器，但是标准库定义了这些IO类型对象的迭代器。

• istream_iterator：读取输入流；

• ostream_iterator：向一个输出流写数据。

通过使用流迭代器，可以用结合泛型算法从流对象读取数据以及向其写数据。

istream_iterator<int> in_iter(cin), eof;
vector<int> nums(in_iter, eof);

for (auto& i : nums)
{
    cout << i << " "; 
}
cout << endl;

ostream_iterator<int> out_iter(cout, " ");
vector<int> nums(10, 8);
copy(nums.begin(), nums.end(), out_iter); // 8 8 8 8 8 8 8 8 8 8
cout << endl;

反向迭代器

反向迭代器就是尾元素向首元素反向移动的迭代器。其用法和普通迭代器十分相似。

string s("Hello, world!");
ostream_iterator<const char> out_iter(cout);
copy(s.rbegin(), s.rend(), out_iter); // !dlrow ,olleH
cout << endl;

forward_list不支持反向迭代器

总结

五种迭代器

不同迭代器能够执行的操作不同，不同的算法要求的迭代器的权限也不同。总的来说，迭代器可以分成以下5种迭代器：

• 输入迭代器

  • 可以进行两个迭代器的相等和不相等的比较；

  • 可以推进迭代器的前置和后置运算；

  • 读取元素的解引用运算符；

  • 箭头运算符，提取对象的成员

例如，find和accumulate要求的输入迭代器。istream_iterator是一种输入迭代器。

• 输出迭代器

  • 输入迭代器的补集，只写不读元素。

  • 推进迭代器的前置和后置运算。

  • 解引用运算符。

例如，copy的第三个参数就是输出迭代器，ostream_iterator就是输出迭代器。

• 前向迭代器

  • 可以读写元素，只能沿一个方向移动

  • 可以多次读写同一个元素

例如，replace要求前向迭代器，forward_list的迭代器就是前向迭代器。

• 双向迭代器

  • 可以正向和反向读取元素，需要支持递减运算符。

例如，reverse要求双向迭代器。

• 随机访问迭代器

  • 在常量时间内访问序列任意元素；

  • 支持关系运算符；

  • 支持整数值的加减运算；

  • 两个迭代器相减，可以计算距离；

  • 下标运算符(iter[n])和*(iter[n])等价。

算法形参模式

在任何其他算法分类之上，还有一组参数的规范。大多数算法有如下4种形式之一：

• alg(beg, end, other args);

• alg(beg, end, dest, other args);

• alg(beg, end, beg2, other args);

• alg(beg, end, beg2, end2, other args);

其中，alg是算法的名字，beg, end是算法所操作的输入范围。dest是算法可以写入的目的位置的迭代器。beg2是第二个输入范围的开始迭代器，有些算法可以补上end2。

算法命名规范

• 一些算法支持传入一个谓词来代替运算比较符。例如unique。

• _if版本的算法接受一个谓词来代替元素值。

• 区分拷贝元素的版本和不拷贝的版本，写到额外空间的算法名字一般会附加一个_copy。

特定容器算法

有些算法只支持特定的算法，作为特定容器的成员函数。

// 使用 std::list
std::list<int> lst1 = {1, 3, 5, 7};
std::list<int> lst2 = {2, 4, 6, 8};

// 1. merge
lst1.merge(lst2); // lst1 现在包含 1, 2, 3, 4, 5, 6, 7, 8
std::cout << "After merge: ";
for (int n : lst1) std::cout << n << " ";
std::cout << std::endl;

// 2. remove
lst1.remove(4); // 删除值为 4 的元素
std::cout << "After remove(4): ";
for (int n : lst1) std::cout << n << " ";
std::cout << std::endl;

// 3. remove_if
lst1.remove_if([](int n) { return n % 2 == 0; }); // 删除所有偶数
std::cout << "After remove_if (remove even numbers): ";
for (int n : lst1) std::cout << n << " ";
std::cout << std::endl;

// 4. reverse
lst1.reverse(); // 反转列表
std::cout << "After reverse: ";
for (int n : lst1) std::cout << n << " ";
std::cout << std::endl;

// 5. sort
lst1.sort(); // 排序列表
std::cout << "After sort: ";
for (int n : lst1) std::cout << n << " ";
std::cout << std::endl;

// 6. unique
lst1.push_back(1);
lst1.push_back(3); // 添加重复元素
lst1.unique(); // 删除重复元素
std::cout << "After unique: ";
for (int n : lst1) std::cout << n << " ";
std::cout << std::endl;

• lst.splice(args)或flst.splice_after(args)