C++ STL中常見的算法使用方式
什么是STL？
STL（Standard Template Library），即標(biāo)準(zhǔn)模板庫(kù)，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。
STL的一個(gè)重要特點(diǎn)是數(shù)據(jù)結(jié)構(gòu)和算法的分離。盡管這是個(gè)簡(jiǎn)單的概念，但這種分離確實(shí)使得STL變得非常通用。例如，由于STL的sort()函數(shù)是完全通用的，你可以用它來操作幾乎任何數(shù)據(jù)集合，包括鏈表，容器和數(shù)組；
STL另一個(gè)重要特性是它不是面向?qū)ο蟮?。為了具有足夠通用性，STL主要依賴于模板而不是封裝，繼承和虛函數(shù)（多態(tài)性）——OOP的三個(gè)要素。你在STL中找不到任何明顯的類繼承關(guān)系。這好像是一種倒退，但這正好是使得STL的組件具有廣泛通用性的底層特征。另外，由于STL是基于模板，內(nèi)聯(lián)函數(shù)的使用使得生成的代碼短小高效；
從邏輯層次來看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想，引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)；
從實(shí)現(xiàn)層次看，整個(gè)STL是以一種類型參數(shù)化的方式實(shí)現(xiàn)的，這種方式基于一個(gè)在早先C++標(biāo)準(zhǔn)中沒有出現(xiàn)的語言特性--模板（template）。
0. < algorithm> 是什么：
< algorithm> 頭文件定義了一組專門用于操作元素范圍的函數(shù)（designed to be used on ranges of elements）。
所謂“元素范圍”指的是可以通過 迭代器 或 指針 進(jìn)行訪問的對(duì)象序列，例如數(shù)組或某些SLT容器。注意，< algorithm>中的算法通過迭代器直接對(duì)值進(jìn)行操作，不會(huì)以任何形式影響任何容器的結(jié)構(gòu)（它永遠(yuǎn)不會(huì)影響容器的大小或存儲(chǔ)分配）。
一句話概括：
< algorithm> 中定義的STL算法通過 “迭代器” 來操作STL容器中的元素，且不會(huì)影響容器的結(jié)構(gòu)。
需要注意的事：
< algorithm> 中的算法的參數(shù)迭代器范圍一般都是 [first, last)，即“前閉后開”區(qū)間，last類似于end尾迭代器，指向容器最后一個(gè)元素后面的位置。
1. Non-modifying sequence operations：
不會(huì)修改容器中元素的順序的操作：
1.1 find：（Find value in range）
函數(shù)原型：
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()函數(shù)在給定的迭代器區(qū)間[first, last) 中查找值 val。
如果val存在，則返回區(qū)間內(nèi)的指向第一個(gè)元素的迭代器；
如果val不存在，則返回 last迭代器。
使用舉例：
#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()函數(shù)不會(huì)修改容器中元素的值，所以可以使用 const_iterator 迭代器，但需要注意返回值、入?yún)⒌念愋捅仨毝际莄onst類型的，否則編譯時(shí)會(huì)因類型匹配報(bào)錯(cuò)（報(bào)錯(cuò)原因：it = find() 中的 “=” 沒有重載）。
時(shí)間復(fù)雜度：
因?yàn)橐獜膄irst到last的區(qū)間遍歷，所以時(shí)間復(fù)雜度是 O(n)。
1.2 count：（Count appearances of value in range）
函數(shù)原型：
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(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() 函數(shù)在給定的迭代器區(qū)間 [first, last) 中統(tǒng)計(jì)參數(shù) val出現(xiàn)的次數(shù)，返回統(tǒng)計(jì)到的個(gè)數(shù)。
使用舉例：
#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
時(shí)間復(fù)雜度：
count()函數(shù)同樣需要遍歷整個(gè)容器，所以時(shí)間復(fù)雜度是 O(n)。
1.3 equal：（Test whether the elements in two ranges are equal）
函數(shù)原型：
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;
}
//使用自定義的比較函數(shù)的equal()版本：
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2, bool func) {}
比較兩個(gè)容器中指定范圍的值是否相等，返回bool值。
equal()函數(shù)有兩種重載形式，接收三個(gè)參數(shù)的版本使用 operator= 對(duì)兩個(gè)容器中的元素進(jìn)行比較；接受四個(gè)參數(shù)的版本可使用自定義的比較函數(shù)。
使用舉例：
#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));
//接受三個(gè)參數(shù)的equal版本，使用 operator= 進(jìn)行比較：
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";
}
//接受四個(gè)參數(shù)的equal版本，使用自定義的比較函數(shù)：
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.
時(shí)間復(fù)雜度：
同樣需要遍歷迭代器范圍的容器內(nèi)容，所以時(shí)間復(fù)雜度是 O(n)。
1.4 search：（Search range for subsequence）
函數(shù)原型：
//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()函數(shù)是用于在一個(gè)范圍內(nèi)查找某一個(gè)元素是否存在，search()函數(shù)是用于一個(gè)范圍內(nèi)查找一個(gè)一連串的元素是否存在。
find()函數(shù)同樣存在兩個(gè)版本：使用 operator=進(jìn)行比較的版本 及 使用自定義方法進(jìn)行比較的版本。
返回值：如果找到，則返回指向找到的范圍內(nèi)的第一元素的迭代器；如果未找到，則返回last1。
使用舉例：
#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";
}
//方式二，使用自定義的比較函數(shù)：
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: 3
needle found at position: 3
時(shí)間復(fù)雜度：
O(n2).
2. Modifying sequence operations：
會(huì)修改容器中元素順序的操作：
2.1 copy：（Copy range of elements）
函數(shù)原型：
template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);
作用相當(dāng)于：
template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last) {
*result = *first;
++result; ++first;
}
return result;
}
將 [first, last) 范圍到的源數(shù)據(jù) 拷貝到 result 指定的目標(biāo)位置，返回值是目標(biāo)位置的末尾迭代器（An iterator to the end of the destination range where elements have been copied）。
使用舉例：
#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
時(shí)間復(fù)雜度：
O(n).
2.2 move：（move range of elements）
函數(shù)原型：
template <class InputIterator, class OutputIterator> OutputIterator move (InputIterator first, InputIterator last, OutputIterator result);
作用相當(dāng)于：
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()函數(shù)的作用是將 [first, last) 區(qū)間內(nèi)的元素 “移動(dòng)” 到 result 指定的目標(biāo)位置。
移動(dòng)后，源位置 [first, last) 的狀態(tài)是“未指定但有效的狀態(tài)”（in an unspecified but valid state），這個(gè)作用類似于 移動(dòng)構(gòu)造函數(shù)中使用的 std::move 函數(shù)的效果，事實(shí)上 STL中的move函數(shù)中也確實(shí)調(diào)用了 單個(gè)參數(shù)的 std::move 函數(shù)版本。
“未指定但有效的狀態(tài)” 可以理解為空間上的元素因?yàn)楸灰谱咭呀?jīng)為空，但對(duì)其求 sizeof 大小仍在。
使用舉例：
#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
時(shí)間復(fù)雜度：
O(n).
2.3 fill：（Fill range with value）
函數(shù)原型：
template <class ForwardIterator, class T> void fill (ForwardIterator first, ForwardIterator last, const T& val);
fill()函數(shù)的作用是將 [first, last) 范圍內(nèi)容器的值全部填寫為 val。
fill()函數(shù)的返回值是none（void函數(shù)）。
使用舉例：
#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```
**時(shí)間復(fù)雜度：**
O(n).
## 2.6 remove：（Remove value from range）
## 2.7 reverse：（Reverse range）
**函數(shù)原型：**
```cpp
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
reverse()函數(shù)的作用是將區(qū)間 [first, last) 內(nèi)的元素在容器內(nèi)的順序進(jìn)行反轉(zhuǎn)。
reverse()函數(shù)的返回值是 none（void函數(shù)）。
使用舉例：
#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：
分區(qū)：
3.1 partition：（Partition range in two）
函數(shù)原型：
template <class ForwardIterator, class UnaryPredicate> ForwardIterator partition (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
partition() 函數(shù)的作用是將 [first, last) 范圍內(nèi)的容器元素 按照自定義的方法 pred 進(jìn)行分區(qū)（分成 兩個(gè)部分），返回值是指向第二部分分區(qū)的首元素的迭代器。
使用舉例：
#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）
函數(shù)原型：
//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() 函數(shù)的作用是將 [first, last) 范圍內(nèi)的元素進(jìn)行排序，默認(rèn)的排序方式為 operator<（即“從小到大”排序），也可以接受自定義的排序方式 comp。
使用舉例：
#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：
函數(shù)原型：
//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：
函數(shù)原型：
//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() 函數(shù)的作用是將 [first1, last1)區(qū)間 及 [first2, last2) 區(qū)間的容器元素合并到一起，合并后的結(jié)果存儲(chǔ)到 result指定的位置上。 merge() 默認(rèn)的合并順序?yàn)?operator< （從小到大），也可接受用戶自定義的排序方式 comp。
merge() 函數(shù)必須在 sort() 的基礎(chǔ)上進(jìn)行合并，否則合并的結(jié)果會(huì)出現(xiàn)亂序。且sort()與merge() 的排序算法必須保持一致，即都使用 operator< 或相同的 comp函數(shù)。
merge()函數(shù)返回值是合并后的容器的尾迭代器（容器最后一個(gè)元素的后面的位置）。
使用舉例：
#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：
求最大/最小值，可接受用戶指定的比較方法
到此這篇關(guān)于C++ STL中常見的算法使用方式的文章就介紹到這了,更多相關(guān)C++ STL算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
一篇文章帶你了解C語言內(nèi)存對(duì)齊解決的問題
內(nèi)存對(duì)齊的目的是為了提高CPU讀寫內(nèi)存里數(shù)據(jù)的速度?，F(xiàn)代的CPU讀取內(nèi)存并不是一個(gè)一個(gè)字節(jié)挨著讀取，這樣做的效率非常低?，F(xiàn)代的CPU一般以4個(gè)字節(jié)(32bit數(shù)據(jù)總線）或者8個(gè)字節(jié)（64bit數(shù)據(jù)總線）為一組，一組一組地讀寫內(nèi)存里的數(shù)據(jù)2021-08-08
如何用C寫一個(gè)web服務(wù)器之I/O多路復(fù)用
本文主要介紹了如何用C寫一個(gè)web服務(wù)器之I/O多路復(fù)用，本次選擇了 I/O 模型的優(yōu)化，因?yàn)樗欠?wù)器的基礎(chǔ)，這個(gè)先完成的話，后面的優(yōu)化就可以選擇各個(gè)模塊來進(jìn)行，不必進(jìn)行全局化的改動(dòng)了。2021-05-05
利用Qt實(shí)現(xiàn)獲取計(jì)算機(jī)的硬件信息
在開發(fā)時(shí)，常常會(huì)需要用到計(jì)算機(jī)的相關(guān)信息。利用這些信息，我們可以開發(fā)一些輔助模塊。本文將利用Qt實(shí)現(xiàn)獲取計(jì)算機(jī)的硬件信息，感興趣的可以嘗試一下2022-12-12
C++ VTK實(shí)例之高斯隨機(jī)數(shù)的生成
這篇文章主要介紹了VTK的一個(gè)實(shí)例之高斯隨機(jī)數(shù)的生成，本文演示了從一個(gè)平均數(shù)是0.0和標(biāo)準(zhǔn)偏差是2.2的高斯分布中隨機(jī)生成3個(gè)隨機(jī)數(shù)。感興趣的同學(xué)可以學(xué)習(xí)一下2021-11-11
全排列算法的非遞歸實(shí)現(xiàn)與遞歸實(shí)現(xiàn)的方法(C++)
本篇文章是對(duì)全排列算法的非遞歸實(shí)現(xiàn)與遞歸實(shí)現(xiàn)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
回溯在迷宮搜索中使用很常見，就是這條路走不通，然后返回前一個(gè)路口，繼續(xù)下一條路?；厮菟惴ㄕf白了就是窮舉法，下面讓我們一起來看看回溯算法中深度優(yōu)先搜索吧2023-01-01
C++?是手工管理內(nèi)存的分配和釋放，這給了程序員極大的自由度也給了我們極高的門檻，弄不好就得內(nèi)存泄露。使用智能指針能更好的管理堆內(nèi)存,本文主要給大家介紹一下c++的智能指針,需要的朋友可以參考下2022-07-07
linux安裝mysql和使用c語言操作數(shù)據(jù)庫(kù)的方法 c語言連接mysql
Linux下使用C語言操作數(shù)據(jù)庫(kù)的方法，我將從MySQL環(huán)境的搭建，MySQL命令的使用到使用C接口來操作MySQL等過程詳細(xì)的介紹在Linux下管理MySQL數(shù)據(jù)庫(kù)的方法2014-01-01
C++字符數(shù)組、字符數(shù)組指針和string類
這篇文章主要介紹了C++字符數(shù)組、字符數(shù)組指針和string類，string是一個(gè)類而不是基本數(shù)據(jù)類型，數(shù)組不含有處理函數(shù)，下面更多詳細(xì)內(nèi)容，需要的小伙伴可以參考下面文章2022-03-03![C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義](http://img.jbzj.com/images/xgimg/bcimg9.png)
C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義
這篇文章主要介紹了C++程序中main（int argc, char *argv[]）函數(shù)的參數(shù)意義,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2018-09-09