10. 泛型算法

youncyb 发布于 20 天前 55 次阅读 C++


泛型算法是一种通用的算法设计方法,通过模板和迭代器,能够适用于不同类型的数据结构。本篇内容涵盖了 C++ 标准库中的常用泛型算法,如排序、查找、变换等,旨在帮助开发者理解和高效地使用这些强大工具。

1. 只读算法

只读算法,用于读取容器的元素,不会修改容器的元素。

T accumulate(InputIt first, InputIt last, T init); // 累加函数,参数t作为初始值,可以是任意定义了`+`运算的类型且和迭代器的元素类型匹配(可转化或相同)。比如t=1,t=string("")。

bool equal(InputIt1 first1, InputIt1 last1, InputIt2 first2); // 对比v1和v2指定范围内,是否具有相同的元素序列。

InputIt find(InputIt first, InputIt last, const T& value); // 从序列中找到第一个匹配位置的迭代器,默认需要支持`==`操作。

typename iterator_traits<InputIt>::difference_type count(InputIt first, InputIt last, const T& value); // 计算序列中给定元素的个数,默认需要支持`==`操作。

作为 accumulate 的第三个参数,需要支持 + 运算符,例如字面值字符串 "",其类型是 const char *,则不支持 + 运算符。

equal 函数必须人为保证序列 2 长度至少与序列 1 长度相等或更长。并且需要支持 == 运算符。char *str 没有重载 == 运算符,意味着对两个 char * 进行比较,实际上是对两个指针的地址进行比较,地址相同则两个 char * 相等。

2. 读写算法

void fill(ForwardIt first, ForwardIt last, const T& value); // 用值填充序列,需要保证序列已经有元素

OutputIt fill_n(OutputIt first, Size count, const T& value); // 填充count个,需要保证序列已经有元素

OutputIt copy(InputIt first, InputIt last, OutputIt d_first); // 拷贝数据

void replace(ForwardIt first, ForwardIt last, const T& old_value, const T& new_value); // 替换

OutputIt replace_copy(InputIt first, InputIt last, OutputIt d_first, const T& old_value, const T& new_value); // 同上,复制到d_first的容器

void sort(RandomIt first, RandomIt last); // 用于对范围 [first, last) 中的元素进行排序,默认使用 < 运算符进行比较
void sort(RandomIt first, RandomIt last, Compare comp); // 同上,提供自定义比较的函数
void stable_sort(RandomIt first, RandomIt last); // stable 表示稳定版,不会更改相同元素的位置顺序
void stable_sort(RandomIt first, RandomIt last, Compare comp); 

ForwardIt unique(ForwardIt first, ForwardIt last); // 用于移除范围 [first, last) 中相邻的重复元素,只保留每个元素的第一个实例。返回移除重复元素后的新范围的终止迭代器。
OutputIt unique_copy(InputIt first, InputIt last, OutputIt d_first); 

ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPredicate p); // 将范围 [first, last) 中的元素分成两部分,使得满足谓词的元素排在前面,不满足谓词的元素排在后面。这个算法返回一个迭代器,指向不满足谓词的第一个元素。
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f); // 遍历范围 [first, last) 的每个元素,并对每个元素执行给定的函数。

OutputIt transform(InputIt first1, InputIt last1, OutputIt d_first, UnaryOperation unary_op); // 将一个范围内的元素应用一个函数,并将结果存储到另一个范围内。 
OutputIt transform(InputIt1 first1, InputIt1 last1, InputIt2 first2, OutputIt d_first, BinaryOperation binary_op); // 接受两个输入范围和一个输出迭代器,以及一个二元操作函数,并将该函数应用于两个输入范围的每对对应元素,然后将结果存储到输出范围。

ForwardIt remove(ForwardIt first, ForwardIt last, const T& value); // 将不等于value的元素移动到容器的前面位置,返回最后一个元素的下一个位置
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPred p); // 通过一元谓词函数批量移动容器的元素,将不满足p谓词的元素都移动到容器的前面,返回最后一个元素的下一个位置

写操作算法,不会改变容器的 size,只会对已经存在的元素进行修改。如果容器中不存在元素,即元素的个数为 0,无论是否对容器使用了 reserve,预留空间,都会导致 fillcopyreplace 等函数出错。

vector<int> int_vector;
list<int> int_list;
int i;
while(cin >> i)
{
    int_list.push_back(i);
}

copy(int_list.cbegin(), int_list.cend(), int_vector.begin()); // 错误,因为int_vector不包含任何元素
vector<int> int_vector;

int_vector.reserve(10); // 预留10个元素的内存占用

fill_n(int_vector.begin(), 10, 1); // 错误,即使预留了10个元素的内存空间,但int_vector不包含任何元素

对于需要写入第三个容器的算法,例如 _copy 后缀的算法,需要使用 back_inserter(int_vector) 解决,它会将修改转换为 push_back 操作。

fill_n(std::back_inserter(vec1), 10, 1);
std::unique_copy(vec1.begin(), vec1.end(), std::back_inserter(vec2));

需要注意的是,uniq 操作不会删除元素,而是将重复元素移动到序列的末尾。为了得到非重复的序列,还需要使用 erase 函数进行删除操作。

auto new_end = std::unique(vec.begin(), vec.end());
vec.erase(new_end, vec.end()); // 删除多余元素

3. 条件算法

3.1 普通条件函数

泛型算法的额外参数,是支持条件比较的,例如 sort 的第三个参数支持一个二元谓词。谓词是一种表达式,其返回一个能作用条件的值。谓词分为:一元谓词(unary predicate)和二元谓词(binary predicate)。一元谓词只接收一个参数,二元谓词接收 2 个参数。

bool compareDesc(int a, int b) {
    return a > b;
}
// 使用降序排序的sort
std::sort(vec.begin(), vec.end(), compareDesc);

3.2 匿名条件函数

假设我们需要找到 vector<string> 的第一个长度大于 sz 的元素。可以使用 find_if,其支持一元谓词,接收的第一个参数是容器的元素,则我们不能传入需要比较的长度 sz。

为了解决这个问题,可以使用匿名函数(lambda)表达式:

[] (args...) return type {函数体; return xxx;}

lambda 函数,结构由以下部分组成:

  • [],捕获列表,用于获取当前函数作用域的局部变量(也可以获取全局变量和 static 变量),必备
  • (args…) 参数列表,
  • 返回类型,用 -> int 表示返回的是 int 类型,如果省略返回类型,则只有一条 return 语句时会自动推到,多余 1 条语句,则返回 void
  • 函数体,必备
void hello(){
    int sz = 5;
    auto fun1 = [sz] (int a) -> int {a += 1; return a > sz;};
    bool result = func1(3);   
}

auto it = std::partition(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });

假设不需要参数和多余的函数体,则 lambda 可以变为如下简洁形式:

auto func1 = [] {return true;};

捕获列表的参数传递

  • 值传递,在 lambda 表达式生成时,就已经确定了 sz 的值,即使后后续调用 lambda 时,改变了 sz 的值,也不会影响到 lambda,并且 lambda 内部无法修改捕获列表的值
  • 引用传递,[&sz],lambda 会随着 sz 改变而发生改变,但需要确保在调用 lambda 时,sz 依然有效,引用传递比较适用于不能拷贝的参数,例如 io 流
  • 隐式捕获,用于自动推断捕获的类型
    • [=],表明使用的列表是值传递
    • [&],表明使用的列表是引用传递
    • [&os, =] 表明 os 是引用传递,剩余的是值传递

可变 lambda

默认情况下,lambda 表达式中的捕获变量是只读的。如果你希望在 lambda 内部修改捕获的变量,需要使用 mutable 关键字。注意,mutable 只影响通过值捕获的变量(即 = 方式捕获)。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int x = 10;

    // 定义一个可变 lambda,尝试修改捕获的 x 的副本
    auto mutableLambda = [x]() mutable {
        std::cout << "Original x inside lambda: " << x << std::endl;
        x = 20; // 修改捕获的 x 的副本
        std::cout << "Modified x inside lambda: " << x << std::endl;
    };

    // 调用 lambda
    mutableLambda();

    // 输出 x 的值,以验证它是否在 lambda 外部发生了变化
    std::cout << "Original x outside lambda: " << x << std::endl;

    return 0;
}
Original x inside lambda: 10
Modified x inside lambda: 20
Original x outside lambda: 10

3.3 bind 条件函数

通过 lambda 函数,可以突破谓词数量限制。另一个实现方法则是使用 bind 函数,提前做参数绑定。bind 函数支持多个参数绑定,要使用 bind,需要包含头文件 <functional>

#include <functional>
int add(int a, int b) {
    return a + b;
}
auto add_five = std::bind(add, std::placeholders::_1, 5);
add_five(10)

通过 std::placeholder::_1 设置第一个占位符,同理其他占位符就是 _2_3… 这些占位符实际上是一个个命名空间(namespace),也可以先声明命名空间:

using namepsace std::placeholder;
auto add_five = std::bind(add, _1, 5);

引用传递

bind 参数都是通过拷贝的方式,例如上文的传入的第三个参数 5,则和 lambda 相同,在创建时就被确认了。

如果需要引用的方式进行参数绑定,则需要使用 ref(os)cref(aa)cref 代表使用 const 的方式进行传递。

4. 算法迭代器

泛型算法自身无法修改容器的 size,例如无法为容器增加元素。所以,出现了为泛型算法设计的迭代器。

4.1 插入迭代器

迭代器的 *itit++it-- 等操作被重载为返回 it 本身,而不会修改 it 的值。通过 *it = xxx 的赋值方式,底层调用容器的 push_back 操作,当前的 it 会自动+1,所以 forward_list 类型的容器时无法 back_inserter。

auto it = std::back_inserter(vec);
*it = 123;
  • back_inserter:使用 push_back 的方式插入数据
  • front_inserter:使用 push_front 的方式插入数据
  • inserter:使用 c.insert(p, t) 的方式插入数据。该函数与前两个在构造函数方面不同之处在于需要指定第二个参数,第二个参数是一个迭代器。

例如:

auto it = std::inserter(vec, iter);
*it = 1234;

// 等价于
it = vec.insert(it, 1234);
++it;

4.2 iostream 迭代器

流迭代器分为:istream_iteratorostream_iterator。前者用于读取输入流的数据,后者用户向输出流写数据。istream_iterator 支持以下操作:

istream_iterator<T> in(is); // is是输入流,in会从输入流中读取T类型的数据
istream_iterator<T> end; // 定义一个尾后迭代器,意味着输入流的结束

// 支持的运算操作
in1 == in2;
in1 != in2;
in1++; // 后置递增运算
++in1; // 前置递增运算

// 支持的读取操作
T var1 = *in; // 返回从in中读取的值
in->mem; // 同(*in).mem
#include <iterator>
#include <iostream>

std::istream_iterator<int> input_it(std::cin);
std::istream_iterator<int> end;
std::vector<int> vec(input_it, end); // 用输入流填充vector

ostream_iterator 支持以下操作:

ostream_itrator<T> out(os); // 将类型为T的值,写入到os输出流
ostream_itrator<T> out(os, d); // 每个传入的T后面都追加一个d,d是以\0结尾的字符串数组

out = val; // 用`<<`符号将val写入out的输出流,val的类型必须与T相同

*out、out++、out--; // 这些运算符不会对ostream_iterator产生影响,每个运算符都返回out
*out_iter++ = e;

// 等价于
out_iter = e;

实际应用中,推荐使用 *out_iter++ = e;,与其他迭代器更相似,也不容易造成语义分歧。

4.3 反向迭代器

反向迭代器是由 rbegin()/rend()crbegin()/crend() 产生,对于反向迭代器,it++ 操作会使 it 朝着下图中箭头方向移动。

image-20240723222413038

sort 函数传递一对反向迭代器,则会使默认的升序变为降序。反向迭代器需要使用递减运算符,所以 forward_list 无法使用反向迭代器。反向迭代器可以通过 it.base() 函数转变为普通迭代器,但需要注意的是,base() 返回的正向迭代器,受到 “左闭右开” 的设计影响,会返回相邻的一个迭代器,如果是由 find() 函数返回的反向迭代器,则需要使用一次 r_it++;,才能得到真正的位置。

例如 find(str.crbegin(), str.crend, ',') 返回的位置是下图中的 L

image-20240723223143711

5. 链表容器的特定算法

通用版的算法:sort 排序,需要支持随机访问。所以对于 list 和 forward_list,应该优先使用成员版本的算法,而不是通用版本。而链表容器的 “特有版本” 则会改变迪底层容器。

removeuniq 都会删除多余的元素,修改底层容器。使用 lst.uniq 同样需要先保证元素的有序。

lst.merge (lst2); //将 来 自 1st2 的 元 素合 并 入 1st。lst 和 1st2 都 必须 是有 序的 。合并完成后,lst2变为空的。
lst.merge (lst2, comp); // 默认使用<符号进行合并,也可以使用comp作为条件

lst.remove(val); // 调用erase删除与val相等的元素
lst.remove_if(pred); // 调用erase删除令一元谓词为真的元素

lst.reverse(); // 反转lst的元素

lst.sort(); 
lst.sort(comp); // 排序

lst.uniq(); // 默认使用`==`进行比较,调用erase删除重复元素
lst.uniq(pred); // 使用自定义谓词

链表容器的拼接操作:

splicesplice_after 用于对 list 和 forward_list 实现拼接操作。

lst.splice(p, lst2); // 将lst2拼接到lst的p位置之前,元素会从lst2中删除,还支持以下重载。
(p, lst2, p2)
(p, lst2, b, e)