跳至內容

C++/STL/Algorithm

新增連結
維基教科書，自由的教學讀本
< C++

algorithm 是b:C++標準程式庫中的一個b:頭文件，定義了C++ STL標準中的基礎性的算法（均為函數模板）。[1] 在C++98中，共計有70個算法模板函數；在C++11中，增加了20個算法模板函數。其中有5個算法模板函數定義在頭文件numeric中。

下文所稱的「序列」（sequence），是指可以用迭代器順序訪問的容器。

對序列的每個元素執行函數調用

[編輯]
  • for_each(inIterBegin, inIterEnd,ufunc)：用函數對象ufunc調用序列中每一項元素
  • for_each_n(inIterBegin, numElements,ufunc)：用函數對象ufunc調用序列的前numElements項元素。C++17引入
  • transform (InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op)：對序列中每一個元素，執行一元操作op，結果寫入另一序列中
  • transform (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, OutputIterator result,BinaryOperation binary_op)：對兩個序列中對應的每一對元素，執行二元操作binary_op，結果寫入另一序列中

測試序列的性質

[編輯]
  • all_of (InputIterator first, InputIterator last, UnaryPredicate pred)：C11算法。如果序列所有元素均滿足謂詞pred，則返回true
  • any_of (InputIterator first, InputIterator last, UnaryPredicate pred)：C11算法。如果序列存在元素滿足謂詞pred，則返回true
  • none_of (InputIterator first, InputIterator last, UnaryPredicate pred)：C11版。如果序列中所有元素不滿足為此pred，則返回true

有序序列中的邊界查找

[編輯]
  • equal_range(forIterBegin, forIterEnd, targetVal)：在已排序的序列中查找目標值的位置範圍；返回範圍的下界與上界。對於隨機迭代器，用二分查找；否則線性查找。返回pair<ForwardIterator,ForwardIterator>
  • equal_range(forIterBegin, forIterEnd, targetVal, binPred)：重載版本，其中binPred是給定的序關係函數。
  • lower_bound(forIterBegin, forIterEnd, targetVal)：在升序的序列中查找第一個不小於targetVal的元素。實際上是二分查找。
  • lower_bound(forIterBegin, forIterEnd, targetVal, binPred)：重載版本，其中binPred是給定的序關係函數。
  • upper_bound(forIterBegin, forIterEnd, val)：在已排序的序列中查找目標值val出現的上界（即第一個大於目標值val的元素的位置）。
  • upper_bound(forIterBegin, forIterEnd, val, binPred)：重載版本，其中binPred是給定的序關係函數。

比較

[編輯]
  • equal(inIter1Begin, inIter1End, inIter2Begin)：比較兩個序列的對應元素是否相等
  • equal(inIter1Begin, inIter1End, inIter2Begin, binPred)：重載版本，其中binPred是給定的相等比較函數。
  • lexicographical_compare(inIter1Begin, inIter1End, inIter2Begin, inIter2End)：對兩個序列做詞典比較。兩個序列的對應元素用 < 運算符比較。如果第一個序列在詞典序下小於第二個序列，返回true
  • lexicographical_compare(inIter1Begin, inIter1End, inIter2Begin, inIter2End, binPred)：重載版本，其中binPred是給定的「小於」比較函數。
  • mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2)：比較兩個序列的對應元素，返回用std::pair表示的第一處不匹配在兩個序列的位置。比較時使用==運算符。
  • mismatch (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, BinaryPredicate pred)：重載版本，其中binPred是給定的「相等」比較函數。

複製

[編輯]
  • copy (InputIterator first, InputIterator last, OutputIterator result)：複製一個序列到另一個序列
  • copy_backward (BidirectionalIterator1 first,BidirectionalIterator1 last,BidirectionalIterator2 result)：把一個序列複製到另一個序列，按照由尾到頭順序依次複製元素。
  • copy_if (InputIterator first, InputIterator last,OutputIterator result, UnaryPredicate pred)：C11算法。複製序列中所有滿足謂詞pred的元素
  • copy_n (InputIterator first, Size n, OutputIterator result)：C11算法。複製序列中前n個元素

計數

[編輯]
  • count (InputIterator first, InputIterator last, const T& val)：序列中等於給定值的元素的計數
  • count_if (InputIterator first, InputIterator last, UnaryPredicate pred)：序列中滿足給定謂詞的元素的計數

填充

[編輯]
  • fill (ForwardIterator first, ForwardIterator last, const T& val)：用給定值填充序列中每個元素
  • fill_n (OutputIterator first, Size n, const T& val)：用給定值填充序列的n個元素

單值過濾

[編輯]
  • unique (ForwardIterator first, ForwardIterator last)：對序列中一群連續的相等的元素，僅保留第一個元素，該群其他元素被這群元素之後的其他值的元素替換。該函數不改變這些值的相互順序，不改變容器的size。函數返回值為最後一個保留元素的下一個位置（past-the-end element）。建議函數返回後resize容器對象。
  • unique (ForwardIterator first, ForwardIterator last,BinaryPredicate pred)：重載版本，用二元謂詞pred替換operator==算符。
  • unique_copy (InputIterator first, InputIterator last,OutputIterator result)：把一個序列中的元素拷貝到另一個序列；對於一群連續的相等的元素，僅拷貝第一個元素。
  • unique_copy (InputIterator first, InputIterator last,OutputIterator result, BinaryPredicate pred)：重載版本，用二元謂詞pred替換operator==算符。

生成

[編輯]
  • generate (ForwardIterator first, ForwardIterator last, Generator gen)：對序列中每個元素，依次調用函數gen的返回值賦值。
  • generate_n (OutputIterator first, Size n, Generator gen)：對序列中的n個元素，依次調用指定函數的返回值賦值。

堆操作

[編輯]

這裡的堆是指b:二叉堆，默認為b:最大堆。用數組或std::vector等順序結構按照廣度優先順序存儲堆的元素。數組的第一個元素是堆的根節點元素。元素的比較使用operator< 或者comp函數（對於重載版本）。

  • is_heap (RandomAccessIterator first, RandomAccessIterator last)：C11版，判斷序列是否為二叉堆
  • is_heap_until (RandomAccessIterator first, RandomAccessIterator last,Compare comp)：C11版，重載版本
  • is_heap_until (RandomAccessIterator first, RandomAccessIterator last)：C11版，返回有效二叉堆的最末範圍
  • is_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp)：C11版，重載版本
  • make_heap (RandomAccessIterator first, RandomAccessIterator last)：對於一個序列，其元素任意放置，原地(in-place)構造一顆最大樹。
  • make_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp )：重載版本
  • pop_heap (RandomAccessIterator first, RandomAccessIterator last)：堆的根節點被移除到last-1位置，堆的元質數目減1並保持堆性質。
  • pop_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp)：重載版本
  • push_heap (RandomAccessIterator first, RandomAccessIterator last)：對一個範圍為[first,last-1)的堆，增加一個新元素。新元素最初保存在last-1位置。
  • push_heap(r,r,bpred)：重載版本
  • sort_heap (RandomAccessIterator first, RandomAccessIterator last)：對一個堆，執行原地堆排序，得到一個升序結果。
  • sort_heap (RandomAccessIterator first, RandomAccessIterator last,Compare comp)：重載版本

合併

[編輯]
  • inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last)：對兩個升序的序列[first,middle) 與[middle,last)，執行原地合併，合併後的序列仍保持升序。空間複雜度O(1)，時間複雜度O(N)
  • inplace_merge (BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last, Compare comp)重載版本。operator< 被函數對象comp代替。
  • merge (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result)：兩個升序的序列合併，結果序列保持升序。
  • merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)：重載版本。operator< 被函數對象comp代替。

最小最大

[編輯]
  • min (const T& a, const T& b)：兩個值中的最小值。
  • min (const T& a, const T& b, Compare comp)：重載版本
  • max (const T& a, const T& b)：兩個值中的最大值。
  • max (const T& a, const T& b, Compare comp)：重載版本
  • min_element (ForwardIterator first, ForwardIterator last)：返回序列中最小值的迭代器
  • min_element (ForwardIterator first, ForwardIterator last,Compare comp) ：重載版本
  • max_element (ForwardIterator first, ForwardIterator last)：返回序列中最大值的迭代器
  • max_element (ForwardIterator first, ForwardIterator last,Compare comp) ：重載版本
  • max (initializer_list<T> il, Compare comp)：C11版本
  • minmax (const T& a, const T& b)：C11版，返回由最小值與最大值構成的std:pair
  • minmax (const T& a, const T& b, Compare comp)：重載版本
  • minmax (initializer_list<T> il)：C11版，返回由初始化列表中最小元素與最大元素構成的std:pair
  • minmax (initializer_list<T> il, Compare comp)：重載版本
  • minmax_element (ForwardIterator first, ForwardIterator last)：C11版，返回由序列中最小元素與最大元素構成的std:pair
  • minmax_element (ForwardIterator first, ForwardIterator last, Compare comp)：重載版本

移動語義

[編輯]
  • move (InputIterator first, InputIterator last, OutputIterator result)：C11版，把輸入序列中的逐個元素移動到結果序列。需要注意的是，把一個對象移動給另一個對象的std::move定義在頭文件<utility>中。
  • move_backward (BidirectionalIterator1 first,BidirectionalIterator1 last,BidirectionalIterator2 result)：C11版，把輸入序列中的逐個元素自尾到頭移動到結果序列

劃分

[編輯]
  • nth_element (RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last)：對序列重排，使得指定的位置出現的元素就是有序情況下應該在該位置出現的那個元素，且在指定位置之前的元素都小於指定位置元素，在指定位置之後的元素都大於指定位置元素。
  • nth_element (RandomAccessIterator first, RandomAccessIterator nth,RandomAccessIterator last, Compare comp)：重載版本
  • is_partitioned (InputIterator first, InputIterator last, UnaryPredicate pred)：C11版，判斷序列中滿足為此pred的元素是否都在頭部
  • partition (ForwardIterator first,ForwardIterator last, UnaryPredicate pred)：對序列重排，使得滿足謂詞pred的元素位於最前，返回值為指向不滿足謂詞pred的第一個元素的迭代器。
  • stable_partition (BidirectionalIterator first,BidirectionalIterator last,UnaryPredicate pred)：對序列重排，使得滿足謂詞pred的元素在前，不滿足謂詞pred的元素在後，且兩組元素內部的相對順序不變。一般是用臨時緩衝區實現本函數。
  • partition_copy (InputIterator first, InputIterator last, OutputIterator1 result_true, OutputIterator2 result_false, UnaryPredicate pred)：C11版，輸入序列中滿足謂詞pred的元素複製到result_true，其他元素複製到result_false
  • partition_point (ForwardIterator first, ForwardIterator last, UnaryPredicate pred)：C11版，輸入隊列已經是partition，折半查找到分界點。

排列

[編輯]
  • is_permutation (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2)：C11版本，判斷兩個序列是否為同一元素集的兩個排列
  • is_permutation (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred)：C11版本，重載版本
  • next_permutation (BidirectionalIterator first, BidirectionalIterator last)：n個元素有n!種排列。這些排列中，規定升序序列為最小排列，降序序列為最大的排列，任意兩個排列按照字典序分出大小。該函數返回當前序列作為一個排列按字典序的下一個排列。
  • next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp)：重載版本
  • prev_permutation (BidirectionalIterator first, BidirectionalIterator last )：返回當前序列作為一個排列按字典序的上一個排列
  • prev_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp)：重載版本

隨機洗牌

[編輯]
  • random_shuffle (RandomAccessIterator first, RandomAccessIterator last)：n個元素有n!個排列。該函數給出隨機選擇的一個排列。
  • random_shuffle (RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& gen)：使用給定的隨機數發生器來產生隨機選擇的一個排列。
  • shuffle (RandomAccessIterator first, RandomAccessIterator last, URNG&& g)：C11版，其中參數g為隨機數發生器（uniform random number generator），如在<random>中定義的標準隨機數發生器。

刪除

[編輯]
  • remove (ForwardIterator first, ForwardIterator last, const T& val)：刪除序列中等於給定值的所有元素，保留的元素存放在容器的前部且相對次序不變。容器的size不變。
  • remove_if (ForwardIterator first, ForwardIterator last,UnaryPredicate pred)：刪除序列中滿足給定謂詞pred的元素，保留的元素存放在容器的前部且相對次序不變。容器的size不變。
  • remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& val)：把一個序列中不等於給定值的元素複製到另一個序列中。
  • remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred)：把一個序列中不滿足給定謂詞pred的元素複製到另一個序列中。

替換

[編輯]
  • replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)：把序列中為給定值的元素替換為新值
  • replace_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred, const T& new_value )：把序列中滿足給定謂詞pred的元素替換為新值
  • replace_copy (InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value)：複製序列，對於等於老值的元素複製時使用新值
  • replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred, const T& new_value)：複製序列，對於滿足給定謂詞pred的元素複製新值。

逆序

[編輯]
  • reverse (BidirectionalIterator first, BidirectionalIterator last)：把序列中的元素逆序
  • reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)：複製序列的逆序

旋轉

[編輯]
  • rotate (ForwardIterator first, ForwardIterator middle,ForwardIterator last)：等效於循環左移序列，使得迭代器middle所指的元素成為首元素。
  • rotate_copy (ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result)：等效於循環左移序列並複製到新的存儲空間，使得迭代器middle所指的元素成為首元素。

搜索

[編輯]
  • ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)：在序列中發現第一對相鄰且值相等的元素
  • ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate pred)：重載版本。用給定謂詞pred代替了operator ==
  • binary_search (ForwardIterator first, ForwardIterator last,const T& val)：對一個升序序列做b:二分搜索，判定序列中是否有給定值val。
  • binary_search (ForwardIterator first, ForwardIterator last,const T& val, Compare comp)：重載版本。用給定謂詞pred代替了operator ==
  • find (InputIterator first, InputIterator last, const T& val)：對一個輸入序列，找到第一個等於給定值的元素
  • ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)：在序列[first1,last1)中，找到序列[first2,last2)最後出現的位置
  • ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)：重載版本，用給定謂詞pred代替operator==
  • find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2)：在序列[first1, last1)中，找到集合[first2,last2)中任何一個元素的第一次出現
  • find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred)：重載版本，用給定謂詞pred代替operator==
  • find_if (InputIterator first, InputIterator last, UnaryPredicate pred)：在序列中返回滿足謂詞pred的第一個元素
  • find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred)：C11算法，在序列中返回不滿足謂詞pred的第一個元素
  • search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)：在序列[first1,last1)中，找到序列[first2,last2)首次出現的位置
  • search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred)：重載版本，用給定謂詞pred代替operator==
  • search_n (ForwardIterator first, ForwardIterator last, Size count, const T& val)：給定序列中，搜索給定值val連續出現n次的位置
  • search_n ( ForwardIterator first, ForwardIterator last, Size count, const T& val, BinaryPredicate pred )：重載版本，用給定謂詞pred代替operator==

集合操作

[編輯]

下述算法的操作數，均為已排序的升序序列。

  • includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 )：判斷第2個已為升序的序列的元素是否都出現在第1個升序序列中
  • includes ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp )：重載版本，用給定謂詞pred代替operator<
  • set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)：兩個升序序列之差
  • set_difference (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result, Compare comp)：重載版本
  • set_intersection (InputIterator1 first1, InputIterator1 last1,InputIterator2 first2, InputIterator2 last2,OutputIterator result)：兩個升序序列（集合）的交
  • set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)：重載版本
  • set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)：兩個升序序列的b:對稱差
  • set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)：重載版本
  • set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)：兩個升序序列的並
  • set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp)：重載版本

排序

[編輯]
  • partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last)：使得[first, middle)為整個序列中最小的那些元素並為升序。[middle,last)的元素任意安排。
  • partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last, Compare comp)：重載版本
  • partial_sort_copy (InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last)：從輸入序列複製最小的一批元素到結果序列中，並按升序排列
  • partial_sort_copy (InputIterator first,InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp)：重載版本
  • is_sorted (ForwardIterator first, ForwardIterator last)：C11版本，判斷序列是否為升序
  • is_sorted (ForwardIterator first, ForwardIterator last, Compare comp)：C11版本，重載版本
  • is_sorted_until (ForwardIterator first, ForwardIterator last)：C11版本，返回序列從頭部開始為升序的子序列的結束處
  • is_sorted_until (ForwardIterator first, ForwardIterator last, Compare comp)：C11版本，重載版本
  • sort (RandomAccessIterator first, RandomAccessIterator last)：排序
  • sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)：重載版本
  • stable_sort ( RandomAccessIterator first, RandomAccessIterator last )：穩定排序
  • stable_sort ( RandomAccessIterator first, RandomAccessIterator last,Compare comp )：重載版本

交換

[編輯]
  • iter_swap (ForwardIterator1 a, ForwardIterator2 b)：交換兩個迭代器所指的元素對象
  • swap (T& a, T& b)：交換兩個對象。優先使用移動語義
  • swap(T (&a)[N], T (&b)[N])：交換兩個對象數組
  • swap_ranges (ForwardIterator1 first1, ForwardIterator1 last1,ForwardIterator2 first2)：交換兩個序列中對應元素

參考文獻

[編輯]
  1. ↑ numeric頭文件說明
取自「https://zh.wikibooks.org/w/index.php?title=C%2B%2B/STL/Algorithm&oldid=176641」