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