什么是STL？
STL（Standard Template Library），即標準模板庫，是一個具有工業強度的，高效的C++程序庫。它被容納于C++標準程序庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域里所常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架，高度體現了軟件的可復用性。
STL的一個重要特點是數據結構和算法的分離。盡管這是個簡單的概念，但這種分離確實使得STL變得非常通用。例如，由于STL的sort()函數是完全通用的，你可以用它來操作幾乎任何數據集合，包括鏈表，容器和數組；
STL另一個重要特性是它不是面向對象的。為了具有足夠通用性，STL主要依賴于模板而不是封裝，繼承和虛函數（多態性）——OOP的三個要素。你在STL中找不到任何明顯的類繼承關系。這好像是一種倒退，但這正好是使得STL的組件具有廣泛通用性的底層特征。另外，由于STL是基于模板，內聯函數的使用使得生成的代碼短小高效；
從邏輯層次來看，在STL中體現了泛型化程序設計的思想，引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態（polymorphism）一樣，泛型也是一種軟件的復用技術；
從實現層次看，整個STL是以一種類型參數化的方式實現的，這種方式基于一個在早先C++標準中沒有出現的語言特性--模板（template）。
0. < algorithm> 是什么：
< algorithm> 頭文件定義了一組專門用于操作元素范圍的函數（designed to be used on ranges of elements）。
所謂“元素范圍”指的是可以通過 迭代器 或 指針 進行訪問的對象序列，例如數組或某些SLT容器。注意，< algorithm>中的算法通過迭代器直接對值進行操作，不會以任何形式影響任何容器的結構（它永遠不會影響容器的大小或存儲分配）。
一句話概括：
< algorithm> 中定義的STL算法通過 “迭代器” 來操作STL容器中的元素，且不會影響容器的結構。
需要注意的事：
< algorithm> 中的算法的參數迭代器范圍一般都是 [first, last)，即“前閉后開”區間，last類似于end尾迭代器，指向容器最后一個元素后面的位置。
1. Non-modifying sequence operations：
不會修改容器中元素的順序的操作：
1.1 find：（Find value in range）
函數原型：
|
1
2
3
4
5
6
7
8
9
|
template<class InputIterator, class T>InputIterator find(InputIterator first, InputIterator last, const T& val){ while(first != last) { if(*first == val) return first; ++first; } return last;} |
find()函數在給定的迭代器區間[first, last) 中查找值 val。
如果val存在，則返回區間內的指向第一個元素的迭代器；
如果val不存在，則返回 last迭代器。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { int myints[] = { 10, 20, 30, 40 }; vector<int> myvector(myints, myints + 4); vector<int>::const_iterator it; it = find(myvector.cbegin(), myvector.cend(), 30); if(it != myvector.cend()) { cout << "Element found in myvector: " << *it << '\n'; } else { cout << "Element not found in myvector\n"; } return 0;}------Element found in myvector: 30 |
注意：find()函數不會修改容器中元素的值，所以可以使用 const_iterator 迭代器，但需要注意返回值、入參的類型必須都是const類型的，否則編譯時會因類型匹配報錯（報錯原因：it = find() 中的 “=” 沒有重載）。
時間復雜度：
因為要從first到last的區間遍歷，所以時間復雜度是 O(n)。
1.2 count：（Count appearances of value in range）
函數原型：
|
1
2
3
4
5
6
7
8
9
10
11
|
template <class InputIterator, class T>typename iterator_traits<InputIterator>::difference_typecount(InputIterator first, InputIterator last, const T& val){ typename iterator_traits<InputIterator>::differenct_type ret = 0; while(first != last) { if(*first == val) ++ret; ++first; } return ret;} |
count() 函數在給定的迭代器區間 [first, last) 中統計參數 val出現的次數，返回統計到的個數。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { int myints[] = { 10,20,30,30,20,10,10,20 }; vector<int> myvector(myints, myints + sizeof(myints)/sizeof(int)); int mycount = count(myvector.cbegin(), myvector.cend(), 10); cout << "10 appears times: " << mycount << '\n'; return 0;}------10 appears times: 3 |
時間復雜度：
count()函數同樣需要遍歷整個容器，所以時間復雜度是 O(n)。
1.3 equal：（Test whether the elements in two ranges are equal）
函數原型：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
template <class InputIterator1, class InputIterator2>bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2){ while(first1 != last1) { if(*first1 != *first2) return false; ++first1; ++first2; } return true;}//使用自定義的比較函數的equal()版本：bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2, bool func) {} |
比較兩個容器中指定范圍的值是否相等，返回bool值。
equal()函數有兩種重載形式，接收三個參數的版本使用 operator= 對兩個容器中的元素進行比較；接受四個參數的版本可使用自定義的比較函數。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;bool mypredicate(int i, int j) { return (i == j);}int main() { int myints[] = { 20,40,60,80,100 }; vector<int> myvector(myints, myints + sizeof(myints)/sizeof(int)); //接受三個參數的equal版本，使用 operator= 進行比較： if( equal(myvector.cbegin(), myvector.cend(), myints) ) { cout << "The contents of both sequences are equal.\n"; } else { cout << "The contents of both sequences differ.\n"; } //接受四個參數的equal版本，使用自定義的比較函數： if( equal(myvector.cbegin(), myvector.cend(), myints, mypredicate) ) { cout << "The contents of both sequences are equal.\n"; } else { cout << "The contents of both sequences differ.\n"; } return 0;}------The contents of both sequences are equal.The contents of both sequences are equal. |
時間復雜度：
同樣需要遍歷迭代器范圍的容器內容，所以時間復雜度是 O(n)。
1.4 search：（Search range for subsequence）
函數原型：
|
1
2
3
4
5
6
7
8
9
|
//equality (1) template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);//predicate (2) template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); |
find()函數是用于在一個范圍內查找某一個元素是否存在，search()函數是用于一個范圍內查找一個一連串的元素是否存在。
find()函數同樣存在兩個版本：使用 operator=進行比較的版本 及 使用自定義方法進行比較的版本。
返回值：如果找到，則返回指向找到的范圍內的第一元素的迭代器；如果未找到，則返回last1。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;bool mypredicate(int i, int j) { return (i == j);}int main() { vector<int> haystack; for(int i = 1; i < 10; i++) { haystack.push_back(i * 10); //haystack: 10,20,30,40,50,60,70,80,90 } int needle[] = { 40,50,60,70 }; vector<int>::const_iterator it; it = search(haystack.cbegin(), haystack.cend(), needle, needle + sizeof(needle)/sizeof(int)); if(it != haystack.cend()) { cout << "needle found at position: " << (it - haystack.cbegin()) << '\n'; } else { cout << "needle not found\n"; } //方式二，使用自定義的比較函數： it = search(haystack.cbegin(), haystack.cend(), needle, needle + sizeof(needle)/sizeof(int), mypredicate); if(it != haystack.cend()) { cout << "needle found at position: " << (it - haystack.cbegin()) << '\n'; } else { cout << "needle not found\n"; } return 0; }------needle found at position: 3needle found at position: 3 |
時間復雜度：
O(n2).
2. Modifying sequence operations：
會修改容器中元素順序的操作：
2.1 copy：（Copy range of elements）
函數原型：
|
1
2
|
template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result); |
作用相當于：
|
1
2
3
4
5
6
7
8
9
|
template<class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result){ while (first != last) { *result = *first; ++result; ++first; } return result;} |
將 [first, last) 范圍到的源數據 拷貝到 result 指定的目標位置，返回值是目標位置的末尾迭代器（An iterator to the end of the destination range where elements have been copied）。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { int myints[] = { 10, 20, 30, 40, 50, 60, 70 }; vector<int> myvector(7); copy(myints, myints + 7, myvector.begin()); cout << "myvector contains: "; for(vector<int>::const_iterator it = myvector.cbegin(); it != myvector.cend(); ++it) { cout << *it << ' '; } cout << '\n'; return 0;}------myvector contains: 10 20 30 40 50 60 70 |
時間復雜度：
O(n).
2.2 move：（move range of elements）
函數原型：
|
1
2
|
template <class InputIterator, class OutputIterator> OutputIterator move (InputIterator first, InputIterator last, OutputIterator result); |
作用相當于：
|
1
2
3
4
5
6
7
8
9
|
template<class InputIterator, class OutputIterator> OutputIterator move (InputIterator first, InputIterator last, OutputIterator result){ while (first != last) { *result = std::move(*first); ++result; ++first; } return result;} |
move()函數的作用是將 [first, last) 區間內的元素 “移動” 到 result 指定的目標位置。
移動后，源位置 [first, last) 的狀態是“未指定但有效的狀態”（in an unspecified but valid state），這個作用類似于 移動構造函數中使用的 std::move 函數的效果，事實上 STL中的move函數中也確實調用了 單個參數的 std::move 函數版本。
“未指定但有效的狀態” 可以理解為空間上的元素因為被移走已經為空，但對其求 sizeof 大小仍在。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { string array[] = { "air", "water", "fire", "earth" }; vector<string> foo(array, array + 4); vector<string> bar(4); move(foo.begin(), foo.end(), bar.begin()); cout << "foo.size(): " << foo.size() << "; " << "bar.size(): " << bar.size() << ".\n"; cout << "foo content: "; for(auto &r : foo) cout << r << ' '; cout << '\n'; cout << "bar content: "; for(auto &r : bar) cout << r << ' '; cout << '\n'; return 0;}------foo.size(): 4; bar.size(): 4.foo content: bar content: air water fire earth |
時間復雜度：
O(n).
2.3 fill：（Fill range with value）
函數原型：
|
1
2
|
template <class ForwardIterator, class T> void fill (ForwardIterator first, ForwardIterator last, const T& val); |
fill()函數的作用是將 [first, last) 范圍內容器的值全部填寫為 val。
fill()函數的返回值是none（void函數）。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { vector<int> myvector(8); fill(myvector.begin(), myvector.end(), 5); cout << "after fill myvector content: "; for(vector<int>::const_iterator it = myvector.begin(); it != myvector.end(); ++it) { cout << *it << ' '; } cout << '\n'; return 0;}------after fill myvector content: 5 5 5 5 5 5 5 5```**時間復雜度：**O(n).## 2.6 remove：（Remove value from range）## 2.7 reverse：（Reverse range）**函數原型：**```cpptemplate <class BidirectionalIterator> void reverse (BidirectionalIterator first, BidirectionalIterator last); |
reverse()函數的作用是將區間 [first, last) 內的元素在容器內的順序進行反轉。
reverse()函數的返回值是 none（void函數）。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; vector<int> myvector(array, array + sizeof(array)/sizeof(int)); reverse(myvector.begin(), myvector.end()); cout << "after reverse myvector content: "; for(vector<int>::const_iterator it = myvector.cbegin(); it != myvector.cend(); ++it) { cout << *it << ' '; } cout << '\n'; return 0;} |
3. Partitions：
分區：
3.1 partition：（Partition range in two）
函數原型：
|
1
2
3
|
template <class ForwardIterator, class UnaryPredicate> ForwardIterator partition (ForwardIterator first, ForwardIterator last, UnaryPredicate pred); |
partition() 函數的作用是將 [first, last) 范圍內的容器元素 按照自定義的方法 pred 進行分區（分成 兩個部分），返回值是指向第二部分分區的首元素的迭代器。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;bool IsOdd(int i) { return ( (i%2) ==1 );}int main() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; vector<int> myvector(array, array + sizeof(array)/sizeof(int)); vector<int>::iterator bound; bound = partition(myvector.begin(), myvector.end(), IsOdd); cout << "after partition myvector content: "; for(vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) { cout << *it << ' '; } cout << '\n'; cout << "the second partition content: "; for(vector<int>::iterator it = bound; it != myvector.end(); ++it) { cout << *it << ' '; } cout << '\n'; return 0;}------1 9 3 7 5 6 4 8 2 6 4 8 2 |
4. Sorting：
排序：
4.1 sort：（Sort elements in range）
函數原型：
|
1
2
3
4
5
6
7
|
//default (1) template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);//custom (2) template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); |
sort() 函數的作用是將 [first, last) 范圍內的元素進行排序，默認的排序方式為 operator<（即“從小到大”排序），也可以接受自定義的排序方式 comp。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;bool myfunction(int i, int j) { return ( i > j );}int main() { int array[] = { 32, 71, 12, 45, 26, 80, 53, 33 }; vector<int> myvector(array, array + sizeof(array)/sizeof(int)); sort(myvector.begin(), myvector.end()); cout << "after sort myvector content: "; for(auto &r : myvector) cout << r << ' '; cout << '\n'; sort(myvector.begin(), myvector.end(), myfunction); cout << "after another sort myvector content: "; for(auto &r : myvector) cout << r << ' '; cout << '\n'; return 0;}------after sort myvector content: 12 26 32 33 45 53 71 80 after another sort myvector content: 80 71 53 45 33 32 26 12 |
5. Binary Search（operating on partitioned/sorted ranges）：
二分查找：
5.1 binary_search：
函數原型：
|
1
2
3
4
5
6
7
8
|
//default (1) template <class ForwardIterator, class T> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val);//custom (2) template <class ForwardIterator, class T, class Compare> bool binary_search (ForwardIterator first, ForwardIterator last, const T& val, Compare comp); |
6. Merge（operating on sorted ranges）：
合并：
6.1 merge：
函數原型：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
//default (1) template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);//custom (2) template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); |
merge() 函數的作用是將 [first1, last1)區間 及 [first2, last2) 區間的容器元素合并到一起，合并后的結果存儲到 result指定的位置上。 merge() 默認的合并順序為 operator< （從小到大），也可接受用戶自定義的排序方式 comp。
merge() 函數必須在 sort() 的基礎上進行合并，否則合并的結果會出現亂序。且sort()與merge() 的排序算法必須保持一致，即都使用 operator< 或相同的 comp函數。
merge()函數返回值是合并后的容器的尾迭代器（容器最后一個元素的后面的位置）。
使用舉例：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() { int first[] = { 5, 10, 15, 20, 25 }; int second[] = { 50, 1, 2, 3, 4 }; vector<int> result(10); sort(first, first + 5); sort(second, second + 5); vector<int>::iterator it = merge(first, first + 5, second, second + 5, result.begin()); for(vector<int>::iterator iter = result.begin(); iter != it; iter++) { cout << *iter << ' '; } cout << '\n'; return 0;}------1 2 3 4 5 10 15 20 25 50 |
7. Heap：
堆操作：
8. Min/max：
求最大/最小值，可接受用戶指定的比較方法
到此這篇關于C++ STL中常見的算法使用方式的文章就介紹到這了,更多相關C++ STL算法內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/ArtAndLife/article/details/120103004
