泛型算法是一种通用的算法设计方法,通过模板和迭代器,能够适用于不同类型的数据结构。本篇内容涵盖了 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,预留空间,都会导致 fill
、copy
、replace
等函数出错。
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 插入迭代器
迭代器的 *it
、it++
、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_iterator
和 ostream_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 朝着下图中箭头方向移动。
对 sort
函数传递一对反向迭代器,则会使默认的升序变为降序。反向迭代器需要使用递减运算符,所以 forward_list 无法使用反向迭代器。反向迭代器可以通过 it.base()
函数转变为普通迭代器,但需要注意的是,base()
返回的正向迭代器,受到 “左闭右开” 的设计影响,会返回相邻的一个迭代器,如果是由 find()
函数返回的反向迭代器,则需要使用一次 r_it++;
,才能得到真正的位置。
例如 find(str.crbegin(), str.crend, ',')
返回的位置是下图中的 L
。
5. 链表容器的特定算法
通用版的算法:sort
排序,需要支持随机访问。所以对于 list 和 forward_list,应该优先使用成员版本的算法,而不是通用版本。而链表容器的 “特有版本” 则会改变迪底层容器。
remove
和 uniq
都会删除多余的元素,修改底层容器。使用 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); // 使用自定义谓词
链表容器的拼接操作:
splice
和 splice_after
用于对 list 和 forward_list 实现拼接操作。
lst.splice(p, lst2); // 将lst2拼接到lst的p位置之前,元素会从lst2中删除,还支持以下重载。
(p, lst2, p2)
(p, lst2, b, e)
Comments NOTHING