C++中算法與泛型算法的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)C++中算法與泛型算法的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

本文包括的算法有：

• 只讀算法：find()、count()、accumulate()、equal()

• 寫算法：fill()、fill_n()、back_inserter()、copy()、copy_backward()、replace()、replace_copy()、next_permutation()、prev_permutation()

• 重排元素算法：sort()、stable_sort()、unique()

一、算法簡介

大多數(shù)算法在頭文件algorithm中。標(biāo)準(zhǔn)庫還在頭文件numeric中定義了一組數(shù)值泛型算法
算法是如何工作的：

• 迭代器令算法不依賴于容器類型：算法不依賴于容器所保存的元素類型。只要有一個(gè)迭代器可以來訪問元素，就可以進(jìn)行運(yùn)算

• 但算法依賴于元素類型的操作：雖然迭代器令算法不依賴于容器類型，但大多數(shù)算法都是用了一個(gè)（多個(gè)）元素類型上的操作。例如find用元素類型的==運(yùn)算符完成每個(gè)元素與給定值的比較。其他算法可能要求元素類型支持“<”運(yùn)算符。不過，我們將看到，大多數(shù)算法提供了一種方法，允許我們使用自定義的操作來替代默認(rèn)的運(yùn)算符

二、泛型算法

• 標(biāo)準(zhǔn)庫提供了超過100個(gè)算法，這些算法都對(duì)一個(gè)范圍內(nèi)的元素來進(jìn)行操作

• 算法基本上分為3類：是否讀取元素、改變?cè)?、重排元素順?/p>

三、只讀算法

• 只可以操作容器元素，不可以改變?nèi)萜鲀?nèi)的值

• 因?yàn)槭侵蛔x，所以建議使用只讀迭代器（cbegin()、cend()）

find()

• 功能：遍歷一個(gè)范圍中是否包含某元素

• 參數(shù)：前2個(gè)參數(shù)是一個(gè)迭代器范圍或者指針范圍。第3個(gè)參數(shù)是要查找的元素

• 返回值：成功返回要查找的元素所在的迭代器。失敗返回參數(shù)2
  

//判斷value在vec中是否存在，因?yàn)閒ind如果失敗返回的是參數(shù)2.所以可以用來判斷是否查找成功
 
vector<int> vec{ 1,2,3};
int value = 2;
auto result=find(vec.cbegin(),vec.cend(), value);
cout << "The value " << value << (result == vec.cend()
 ? "is not present" : "is present") << endl;

vector<string> vec{ "A","B","C" };
auto result=find(vec.cbegin(),vec.cend(), "B");
cout << "The B "<< (result == vec.cend()
 ? "is not present" : "is present") << endl;

對(duì)數(shù)組的操作：可以用內(nèi)置函數(shù)begin()、end()作為數(shù)組的迭代器，也可以用指針作為迭代器

int arr[] = { 1,2,3,4,5 };
int val = 4;
int* result = find(begin(arr), end(arr), val);
if (result != end(arr)) {
 cout << "find succcess,value is："<< *result<< endl;
}

int arr[] = { 1,2,3,4,5 };
int value = 3;
auto result = find(arr + 1, arr + 3, value);
cout << "The value "<<value<<((result == arr + 3)
	?" is not present":"is present")<< endl;

count()

• 功能：返回元素在指定迭代器范圍內(nèi)出現(xiàn)的次數(shù)

• 返回值：成功返回出現(xiàn)的次數(shù)，沒有返回0

list<int> li{ 1,2,3,66,66,66,100 };
cout <<"The 66 count is：" 
	<<count(li.cbegin(),li.cend(),66)<< endl;

accumulate()

• 頭文件：numeric

• 功能：將指定范圍內(nèi)的元素進(jìn)行和運(yùn)算，參數(shù)3為和運(yùn)算的初始值

• 返回值：返回和運(yùn)算的結(jié)果

• 注意：此函數(shù)操作的元素必須能夠與+運(yùn)算符進(jìn)行操作

//計(jì)算li元素的和，和的初始值為0
list<int> li{ 1,2,3 };
cout <<"The sum is：" <<accumulate(li.cbegin(),li.cend(),0)<< endl; //6

使用string時(shí)，必須顯示地調(diào)用，不能夠直接使用字符串，因?yàn)檫@樣會(huì)被accumulate函數(shù)認(rèn)為是一個(gè)const char*對(duì)象而出錯(cuò)

//正確
ist<string> li{"A","B","C"};
cout <<accumulate(li.cbegin(),li.cend(),string("String："))<< endl; //String：ABC

//錯(cuò)誤
list<string> li{"A","B","C"};
cout <<accumulate(li.cbegin(),li.cend(),"String：")<< endl;

//正確
list<string> li{"A","B","C"};
string s = "String：";
cout <<accumulate(li.cbegin(),li.cend(), s)<< endl;

附加：如果想要進(jìn)行別的運(yùn)行，例如乘、除等，可以使用參數(shù)4.例如下面是對(duì)一個(gè)數(shù)組內(nèi)的元素進(jìn)行乘操作（備注：初始化不要填0，否則結(jié)果就為0）

int *p = new int[4] {1, 2, 3, 4};
cout << accumulate(p, p + 4, 1,multiplies<int>()) << endl; //24

equal()

• 功能：用來比較兩個(gè)指定范圍內(nèi)的元素是否都是相同的值（常來比較兩個(gè)元素是否相同）

• 參數(shù)：參數(shù)1和參數(shù)2指定一個(gè)容器的范圍。參數(shù)3指定另一個(gè)容器的開始范圍

• 比較規(guī)則：將參數(shù)1和2指定的范圍內(nèi)的所有元素，查看這些元素是否與參數(shù)3所指定的另一個(gè)容器的開始處是否都存在（不一定要個(gè)數(shù)都相同，只要容器1的元素在容器2中都要一一對(duì)應(yīng)）

• 返回值：都相同返回1。不相同返回0

• 因?yàn)閑qual調(diào)用迭代器完成操作，所以equal可以用來比較兩個(gè)不同類型的容器。例如vector<string>和list<const char*>可以進(jìn)行比較
  

vector<int> vec1{ 1,2};
vector<int> vec2{ 1,2,3};
vector<int> vec3{ 1,2,3,4};
vector<int> vec4{ 1,2,3,4 };
 
cout << equal(vec1.cbegin(),vec1.cend(), vec4.cbegin())<< endl; //1
cout << equal(vec2.cbegin(), vec2.cend(), vec4.cbegin()) << endl; //1
cout << equal(vec3.cbegin(), vec3.cend(), vec4.cbegin()) << endl; //1

vector<int> vec1{ 2,3};
vector<int> vec2{ 1,2,3,4 };
 
cout << equal(vec1.cbegin(),vec1.cend(), vec2.cbegin())<< endl; //0

vector<string> vec1{ "A","B"};
vector<string> vec2{ "B" };
vector<const char*> vec3{ "A","B","C" };
 
cout << equal(vec1.cbegin(), vec1.cend(), vec3.cbegin()) << endl; //1
cout << equal(vec2.cbegin(), vec2.cend(), vec3.cbegin())<< endl; //0

四、寫算法

可以讀寫容器內(nèi)的元素，但不可以改變?nèi)萜鞯拇笮?。因此操作時(shí)要注意容器的大?。ɡ绮荒軐?duì)空容器操作）

因?yàn)闀?huì)改變值，所以不能使用只讀迭代器（cbegin()、cend()）

fill()

• 用來改變指定位置處的元素

• 參數(shù)：參數(shù)1、2指定容器的范圍，參數(shù)3位要設(shè)置的值

vector<int> vec{ 1,2,3,4,5 };
fill(vec.begin(), vec.end(), 0);//將vec全部置為0
for (auto v = vec.cbegin(); v != vec.cend(); v++)
	cout << *v << endl;

vector<int> vec{ 1,2,3,4,5,6 };
fill(vec.begin(), vec.begin()+vec.size()/2, 66); //將vec的前半部分元素變?yōu)?6
 
for (auto v = vec.cbegin(); v != vec.cend(); v++)
	cout << *v << endl;

fill_n()

• 用來將指定數(shù)量的元素變?yōu)槟硞€(gè)值

• 參數(shù)：參數(shù)1為迭代器起始位置。參數(shù)2為要改變的元素個(gè)數(shù)。參數(shù)3為要設(shè)定的值

• 注意：要注意參數(shù)2的設(shè)定，不能超出容器的大小，也不能對(duì)空容器操作

vector<int> vec{ 1,2,3,4,5,6 };
 
fill_n(vec.begin(), 3, 66); //將vec的前3個(gè)元素變?yōu)?6
for (auto v = vec.cbegin(); v != vec.cend(); v++)
	cout << *v << endl;
 
fill_n(vec.begin(), vec.size(), 66); //將vec全部變?yōu)?6
for (auto v = vec.cbegin(); v != vec.cend(); v++)
	cout << *v << endl;

//下面代碼不會(huì)出錯(cuò)，但是也不會(huì)有效果，因?yàn)関ec是空向量
 
vector<int> vec;
fill_n(vec.begin(), vec.size(), 66);
for (auto v = vec.cbegin(); v != vec.cend(); v++) //不打印任何信息
	cout << *v << endl;

back_inserter()

• 又名插入迭代器

• 參數(shù)：為一個(gè)容器的引用

• 返回值：返回與該容器綁定的插入迭代器

• 功能：常用來返回一個(gè)容器的迭代器，然后對(duì)此迭代器進(jìn)行操作

• 當(dāng)我們通過返回的插入迭代器賦值時(shí)，會(huì)自動(dòng)調(diào)用push_back將一個(gè)具有給定值的元素添加到容器中

• 頭文件iterator
  

vector<int> vec; //空容器
 
auto it = back_inserter(vec); //返回vec的第一個(gè)迭代器
*it = 42; //此時(shí)vec有了一個(gè)元素，值為42

現(xiàn)在我們可以使用fill_n來給一個(gè)空容器賦值：在每次迭代中，back_inserter返回迭代器，因此每次賦值都會(huì)在vec上調(diào)用push_back，因此fill_n就能夠操作了。下面是在vec的末尾添加10個(gè)新的元素

vector<int> vec;
fill_n(back_inserter(vec), 10, 0);//通過back_inserter創(chuàng)建一個(gè)插入迭代器，然后可以向vec添加元素了
for (auto v = vec.cbegin(); v != vec.cend(); v++) //打印10個(gè)0
	cout << *v << endl;

copy()

• 將參數(shù)1、2指定范圍的元素拷貝給參數(shù)3指定的容器

• 參數(shù)：參數(shù)1、2為一個(gè)容器的范圍。參數(shù)3要接受拷貝的容器起始位置

• 注意：參數(shù)3要有足夠的空間保存拷貝的數(shù)據(jù)

• 返回值：返回拷貝目的位置的迭代器值

int arr1[] = { 1,2,3 };
int arr2[sizeof(arr1)/sizeof(*arr1)];
 
auto ret = copy(begin(arr1), end(arr1), arr2); //將數(shù)組1拷貝給數(shù)組2。ret為arr2數(shù)組最后元素的下一個(gè)位置
 
for (auto i = 0; i < sizeof(arr2) / sizeof(*arr2); i++) {
 cout << arr2[i]<< endl;
}

copy_backward

• 該函數(shù)與copy的不同之處在于：

• copy是從第一個(gè)元素開始拷貝，而copy_backward是從最后一個(gè)元素開始拷貝

• copy的第3個(gè)參數(shù)是接受拷貝的容器起始位置，而copy_backward是目的序列的結(jié)束迭代器

• 會(huì)復(fù)制前兩個(gè)迭代器參數(shù)指定的序列。第三個(gè)參數(shù)是目的序列的結(jié)束迭代器
  

replace()

• 將指定范圍內(nèi)指定的元素替換為另一個(gè)值

• 參數(shù)：1、2指定替換的范圍。3：目標(biāo)值，4：替換后的值
  

vector<int> vec{ 1,0,0,0,5 };
replace(vec.begin(), vec.end(), 0,66); //將vec中為0的全部替換為66
 
for (auto v = vec.cbegin(); v != vec.cend(); v++) {
	cout << *v << endl;
}

replace_copy()

• 此函數(shù)會(huì)保留原容器不變，然后將替換后的結(jié)果保存在另一個(gè)容器中

• 參數(shù)：參數(shù)12位要替換的范圍。參數(shù)3位另一個(gè)容器的起始位置。參數(shù)4目標(biāo)值。參數(shù)5替換后的值
  

vector<int> vec{ 1,0,0,0,5 };
vector<int> vec2;
 
replace_copy(vec.begin(), vec.end(),back_inserter(vec2), 0,66); //vec的元素保持不變，vec2為替換后的值
	
for (auto v = vec2.cbegin(); v != vec2.cend(); v++) {
 cout << *v << endl;
}

next_permutation()

• 功能：對(duì)一個(gè)迭代區(qū)間的數(shù)值進(jìn)行全排列

• 返回值：會(huì)根據(jù)前面next_permutation函數(shù)的調(diào)用，當(dāng)操作的區(qū)間不存在下一個(gè)排列時(shí)，函數(shù)返回false；否則如果可以繼續(xù)進(jìn)行全排列，那么就返回true

//函數(shù)原型
#include <algorithm>
bool next_permutation(iterator start,iterator end)

演示案例：下面的程序每調(diào)用一次next_permutation就會(huì)對(duì)我們制定的迭代區(qū)間進(jìn)行一次排列，直到得出全部排列之后，返回false

int *p = new int[3] {1, 2, 3};
do {
 for (int i = 0; i < 3; ++i){
  cout << p[i];
 }
 cout << endl;
} while (next_permutation(p, p + 3));

prev_permutation()

• 與next_permutation的功能顯示，區(qū)別就是prev_permutation是求當(dāng)前排列的前一個(gè)排列，而next_permutation是求當(dāng)前排列的下一個(gè)排列

五、重排元素算法

sort()、unqie()、stable_sort()

因?yàn)闀?huì)改變值，所以不能使用只讀迭代器（cbegin()、cend()）

sort()

• 將容器內(nèi)的元素按照運(yùn)算符“<”的規(guī)則排序，從小到大

• 參數(shù)：一個(gè)容器的迭代器范圍
  

vector<int> vec{ 1,4,2,8,4,1 };
sort(vec.begin(), vec.end()); //將vec的值從小到大排序
 
for (auto v = vec.cbegin(); v != vec.cend(); v++) {
 cout << *v << endl;
}

unique()

• 相鄰之間如果有重復(fù)相同的元素，則刪除重復(fù)的元素只保留一個(gè)

• 參數(shù)：一個(gè)容器的迭代器范圍

• 返回值：返回刪除重復(fù)元素之后的最后一個(gè)元素的后一個(gè)位置

• 注意（重點(diǎn)）：雖然刪除了元素，但是容器的大小依然沒有變，迭代器也沒有變。所有變?yōu)榈鲿r(shí)一定要注意

vector<int> vec{ 1,1,2,3,4,4,4,5,1 };
auto end_unique=unique(vec.begin(), vec.end());
 
//for循環(huán)時(shí)使用unique的返回值，如果使用vec.cend()，那么會(huì)打印后面沒有元素位置的亂值
for (auto v = vec.cbegin(); v != end_unique; v++) { 
	cout << *v << endl;
}

stable_sort()

• 也是排序

• 如果非字符串，就先按照數(shù)值的個(gè)數(shù)排序，個(gè)數(shù)相同時(shí)再按照大小排序

• 如果是字符串：按照長度排序，長度相同的按照字典排序

vector<int> vec{ 1,10,2,100,4,1 };
stable_sort(vec.begin(), vec.end());
 
//1,1,2,4,10,100
for (auto v = vec.cbegin(); v != vec.cend(); v++) {
 cout << *v << endl;
}

六、向算法傳遞函數(shù)和lambda表達(dá)式

注意事項(xiàng)：

向算法傳遞函數(shù)或者lambda表達(dá)式時(shí)要注意。該算法支持調(diào)用一元謂詞（參數(shù)）還是多元謂詞（參數(shù)）

例如：find_if的第3個(gè)參數(shù)傳遞的函數(shù)/lambda只接受一個(gè)參數(shù)，如果是兩個(gè)參數(shù)的函數(shù)或lambda，那么就不能調(diào)用（后面會(huì)介紹bind函數(shù)解決這個(gè)問題）

sort()

bool isMin(const int &s1, const int & s2) {
 return s1 < s2;
}
 
bool isMax(const int &s1, const int & s2) {
 return s1 > s2;
}
 
vector<int> vec{1,2,3,4,5};
sort(vec.begin(), vec.end(), isMin); //從小到大排序
sort(vec.begin(), vec.end(), isMax); //從大到小排序
 
//使用lambda表達(dá)式
sort(vec.begin(), vec.end(),
 [](const int &a, const int &b) {return a < b; });//從小到大排序
sort(vec.begin(), vec.end(), 
 [](const int &a, const int &b) {return a > b; });//從大到小排序

stable_sort()

//按照長度排序，長度相同的按照字典排序
bool isShorter(const string &s1, const string & s2) {
	return s1.size() < s2.size();
}
 
vector<string> vec{"fox","jumps","over","quick","res","slow","the","turtle"};
stable_sort(vec.begin(), vec.end(), isShorter);
 
for (auto v = vec.cbegin(); v != vec.cend(); v++) {
	cout << *v << endl;
}

find_if()

• 用來在指定范圍內(nèi)查找比指定值大/下的元素

• 如果是大于（那么就是最大的那個(gè)）。如果是小于（那么就是比他小一個(gè)的那個(gè)）

• 參數(shù)3：為一個(gè)函數(shù)指針或者lambda表達(dá)式

• 返回值：存在就返回這個(gè)值，不存在返回尾迭代器

vector<int> vec{ 1,2,3,4,5 };
int sz = 4;
 
//在vec中尋找比sz大的數(shù)
auto wc=find_if(vec.begin(), vec.end(), 
 [sz](const int &a) {return a > sz; }); //查找比sz大的
auto wc2=find_if(vec.begin(), vec.end(), 
		[sz](const int &a) {return a < sz; }); //查找比sz小的
 
cout << *wc << endl; //5
cout << *wc2 << endl; //3

for_each()

• 用來遍歷一個(gè)集合

• 參數(shù)：參數(shù)12是一個(gè)容器的迭代器范圍。參數(shù)3lambda表達(dá)式
  

vector<int> vec{ 1,2,3,4,5 };
 
for_each(vec.begin(), vec.end(), 
 [](const int&s) {cout << s << " "; });
cout << endl;

vector<string> vec{ "ABC","AB","A","sd" };
 
for_each(vec.begin(), vec.end(), 
 [](const string&s) {cout << s << " "; });
cout << endl;

transform()

• 參數(shù)：參數(shù)12為輸入序列。參數(shù)3為目的位置

• 該算法對(duì)輸入序列中每個(gè)元素調(diào)用課調(diào)用對(duì)象，并將結(jié)果寫到目的位置

• 下面使用transform算法和一個(gè)lambda表達(dá)式來將vector中的每個(gè)負(fù)數(shù)替換為絕對(duì)值。因?yàn)閰?shù)3位vec.begin()，所以就是將vec的全部元素取絕對(duì)值然后再寫入vec的開頭
  

vector<int> vec{ -1,-2,-3,4 };
//將vec的數(shù)全部取絕對(duì)值
transform(vec.begin(), vec.end(), vec.begin(),
		[](int i) {return i < 0 ? -i : i; });
 
for (auto v = vec.begin() ; v != vec.end(); ++v)
	cout <<*v << endl;

關(guān)于“C++中算法與泛型算法的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。