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底層是快排
)
)
