C++常用算法函数
1. 前置知识
1.1 迭代器的类别
C++中，迭代器是 STL 容器库的核心组件之一，具有举足轻重的作用，它提供了一种 统一的方式来访问和遍历容器，而无需关心底层数据结构的具体实现。迭代器类似指针，但比指针更通用，可以用于各种容器类型。
迭代器可以分为两类：
-
方向性质：
-
单向迭代器（Forward Iterator）
-
双向迭代器（Bidirectional Iterator）
-
随机访问迭代器（Random Access Iterator）
-
输入迭代器（Input Iterator）
-
输出迭代器（Output Iterator）
-
-
遍历方向：
-
正向迭代器（iterator）
-
反向迭代器（reverse_iterator）
-
| 特性 | 输入迭代器 | 输出迭代器 | 单向迭代器 | 双向迭代器 | 随机迭代器 |
|---|---|---|---|---|---|
读（*iter） | ✅ | ✅ | ✅ | ✅ | |
写（*iter =） | ✅ | ✅ | ✅ | ✅ | |
| ++ | ✅ | ✅ | ✅ | ✅ | ✅ |
| – | ✅ | ✅ | |||
| + | ✅ | ||||
| - | ✅ |
-
常见的单向迭代器：
forward_list、unordered_map、unordered_set -
常见的双向迭代器：
list、map、set -
常见的随机迭代器：
vector、string、deque
1.2. 仿函数
仿函数是C++中一种行为类似函数的对象，通过重载函数调用运算符operator()实现。它们比普通函数更灵活，比函数指针更具有可读性，并且可以作为模板参数传递。
1.2.1 less仿函数
#include <functional>template <typename T>
struct less {bool operator() (const T& x , const T& y) const { return x < y; }
};
1.2.2 greater仿函数
#include <functional>template <typename T>
struct greater {bool operator() (const T& x , const T& y) const { return x > y; }
};
2. find
std::find 在 [first, last) 范围内线性搜索第一个等于 val 的元素。它使用 operator== 来比较元素。
函数原型
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
参数说明
-
first、last：一段左闭右开的迭代器区间。 -
val：查找的值。
返回值：
-
如果找到指定值，返回指向该元素的迭代器。
-
如果未找到，返回
last迭代器（end()）。
3. swap
std::swap 是 C++ 标准库中用于交换两个对象的函数模板。
函数原型：
template <class T>
void swap (T& a, T& b);
参数说明
-
a：第一个要交换的值。 -
b：第二个要交换的值。
4. reverse
std::reverse 是 C++ 标准库中用于反转指定范围内元素顺序的函数模板。
函数原型
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
参数说明
first、last：一段左闭右开的迭代器区间。
5. sort
std::sort 是 C++ 标准库中用于排序的核心算法（默认升序）。
函数原型
// 1.默认
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
// 2.重载
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
参数说明
-
first、last：一段左闭右开的迭代器区间。 -
comp：比较函数对象，决定升序还是降序。-
升序：less 仿函数。
-
降序：greater 仿函数。
-
sort底层是快排
)
)
