當前位置：首頁 > 编程语言 > c/c++ >内容正文

c/c++

C++ STL 中提供的算法

發布時間：2024/7/23 c/c++ 23 豆豆

生活随笔收集整理的這篇文章主要介紹了 C++ STL 中提供的算法小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

1 算法

1.1 for_each()

參數有三個:

首迭代器
尾迭代器
執行的函數

例如如下代碼:

#include <algorithm> //必須包含 #include <vector> using namespace std;int main() {vector<int> tmp;tmp.push_back(10);tmp.push_back(20);tmp.push_back(30);tmp.push_back(40);for_each(tmp.begin(), tmp.end(), [](int vecVal){cout << vecVal << endl;});return 0; }

結果是:

1.2 accumulate與reduce 求和

1.2.1?accumulate

std::accumulate為一個求和函數, 在標準頭文件中定義<numeric>.

其有四中定義:

template<?class?InputIt,?class?T?>
T accumulate(?InputIt first, InputIt last, T init?);
template<?class?InputIt,?class?T?>
constexpr?T accumulate(?InputIt first, InputIt last, T init?);
template<?class?InputIt,?class?T,?class?BinaryOperation?>
T accumulate(?InputIt first, InputIt last, T init,
? ? ? ? ? ? ?BinaryOperation op?);
template<?class?InputIt,?class?T,?class?BinaryOperation?>
constexpr?T accumulate(?InputIt first, InputIt last, T init,
? ? ? ? ? ? ? ? ? ? ? ? BinaryOperation op?);

函數的作用是把一個序列的元素相加, 而前兩個參數InputIt first, InputIt last代表著序列的收尾迭代器,?T init代表著和的初始值.(注意, 這個參數是必須要傳的, 且必須與要相加的元素類型相同), 最后一個參數代表著自定義的相加法則(如果不傳就默認用"+"), 返回值代表著累加的結果.

在accumulate內部, 會讓迭代器iter從參數first開始, 循環到last, 然后調用accumulate第四個參數(函數) op(init, *iter) (如果沒傳入第四個參數, 就會調用默認 val + *iter)

1.2.2 reduce

reduce用途與accumulate基本一致, 至于具體區別是什么, 據說是reduce函數中可以并行化來增加效率.

1.3?unique

該函數為在起始迭代器到終止迭代器中找出所有與前一個元素符合某種條件的元素(默認是"==")并放置與尾部,返回放置于尾部所有元素的起始位置:

1.4 查找

1.4.1 find

也是三個參數, 與find_if不同的是, 第三個參數需要傳入的是找的值.

1.4.2 find_if

有三個參數: first, last, 條件; 如下測試代碼:

void find_if_test() {vector<char> tVec;char ch[] = "hello world";TestUtils::getInstance()->getSequentialContainerByArr<char>(tVec, PARAM_ARRAY(ch));TestUtils::getInstance()->showContainerElements(tVec);auto iter = find_if(tVec.begin(),tVec.end(),[](auto element){return element == 'o';});if (iter == tVec.end()) {cout << "find o failed" << endl;} else {cout << "successfully find " << *iter << endl;} }

結果:

1.4.3 adjacent_find

查找相鄰重復元素, 如果查到了返回第一個元素迭代器, 查不到的話返回end();

如下測試代碼:

void adjacent_find_test() {vector<int> tVec;int array[] = {2,3,5,8,7,1,5,6,2,5};TestUtils::getInstance()->getSequentialContainerByArr(tVec, PARAM_ARRAY(array));auto iter = adjacent_find(tVec.begin(), tVec.end());if (iter == tVec.end()) {cout << "find same element failed" << endl;} else {cout << "find same element " << *iter << endl;}sort(tVec.begin(), tVec.end(), less<int>());iter = adjacent_find(tVec.begin(), tVec.end());if (iter == tVec.end()) {cout << "find same element failed" << endl;} else {cout << "find same element " << *iter << endl;}auto riter = adjacent_find(tVec.rbegin(), tVec.rend());if (riter == tVec.rend()) {cout << "find same element failed" << endl;} else {cout << "find same element " << *riter << endl;} }

結果:

1.4.4 binary_search

參數列表跟find一樣, 但是返回值是true或者false. 這個查找法必須在有序的序列中才能使用, 效率比較高, 時間復雜度為o(log n).

如下測試函數:

void binary_search_test() {vector<int> tVec;for (int i = 0; i < 100000; i ++) {tVec.push_back(i);}double findStartTime = TestUtils::getInstance()->getNowMillisecond();auto iter = find(tVec.begin(), tVec.end(),38472);if (iter != tVec.end()) {cout << "successfully find " << *iter << endl;} else {cout << "find failed" << endl;}double findEndTime = TestUtils::getInstance()->getNowMillisecond();cout << "find cost " << findEndTime - findStartTime << "ms" << endl;double binary_searchStartTime = TestUtils::getInstance()->getNowMillisecond();bool ret = binary_search(tVec.begin(), tVec.end(),38472);if (ret) {cout << "successfully binary_search " << endl;} else {cout << "find failed" << endl;}double binary_searchEndTime = TestUtils::getInstance()->getNowMillisecond();cout << "binary_search cost " << binary_searchEndTime - binary_searchStartTime << "ms" << endl; }

結果為:

參數中可以添加第四個參數, 就是序列排序的方法, 默認是從小到大排序的, 所以說當你傳入的數組是降序排列且沒有傳入降序排列的參數, 那么就會找不到, 如下測試代碼:

void binary_search_test_1() {vector<int> tVec;for (int i = 99999; i >= 0; i --) {tVec.push_back(i);}bool ret = binary_search(tVec.begin(), tVec.end(), 38472);if (ret) {cout << "successfully binary_search " << endl;} else {cout << "find failed" << endl;} }

結果為:

當傳入排序方式, 如下測試代碼:

void binary_search_test_1() {vector<int> tVec;for (int i = 99999; i >= 0; i --) {tVec.push_back(i);}bool ret = binary_search(tVec.begin(), tVec.end(), 38472, greater<int>());if (ret) {cout << "successfully binary_search " << endl;} else {cout << "find failed" << endl;} }

就會正常找到, 結果:

1.5 統計

1.5.1 count

同find類似, 三個參數是first, last, 統計值. 返回值是總數.

如下測試代碼:

void count_test() {vector<int> tVec;for (int i = 99999; i >= 0; i --) {tVec.push_back(i);}for (int i = 0; i < 10; i ++) {tVec.push_back(10);}cout << count(tVec.begin(), tVec.end(), 10) << endl; }

結果為:

1.5.2 count_if

同find_if類似, 也是三個參數,?first, last, 條件.

如下測試代碼:

void count_if_test() {vector<int> tVec;for (int i = 99999; i >= 0; i --) {tVec.push_back(i);}cout << count_if(tVec.begin(), tVec.end(), [](auto element){return element < 40000;}) << endl; }

結果為:

1.6 random_shuffle

隨機打亂序列算法, 只需傳入first, last就可以, 如下測試代碼:

void random_shuffle_test() {vector<int> tVec;TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);TestUtils::getInstance()->showContainerElements(tVec);random_shuffle(tVec.begin(),tVec.end());TestUtils::getInstance()->showContainerElements(tVec); }

結果如下:

1.7 merge

將兩個有序容器合并為一個有序容器, 如下測試代碼:

void mergeTest1() {vector<int> tVec1;vector<int> tVec2;int array1[] = {0,2,4,6,8};int array2[] = {1,3,5,7,9};TestUtils::getInstance()->getSequentialContainerByArr(tVec1, PARAM_ARRAY(array1));TestUtils::getInstance()->getSequentialContainerByArr(tVec2, PARAM_ARRAY(array2));vector<int> tVec3;tVec3.resize(tVec1.size() + tVec2.size());merge(tVec1.begin(), tVec1.end(), tVec2.begin(), tVec2.end(), tVec3.begin());TestUtils::getInstance()->showContainerElements(tVec3); }

?結果:

1.8 reverse

將序列反轉, 需要提供起始迭代器和終止迭代器.測試代碼如下:

void reverseTest() {vector<int> tVec;TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);TestUtils::getInstance()->showContainerElements(tVec);reverse(tVec.begin(), tVec.end());TestUtils::getInstance()->showContainerElements(tVec); }

結果如下:

1.9 替換

1.9.1 replace

把一個容器中數據替換為另一個數據, 參數有四個, 起始迭代器, 終止迭代器, 需要被替換的值, 替換后的值.

如下測試代碼:

void replaceTest() {vector<int> tVec;TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);TestUtils::getInstance()->showContainerElements(tVec);tVec.push_back(6);tVec.push_back(6);tVec.push_back(6);tVec.push_back(6);replace(tVec.begin(), tVec.end(), 6, 10);TestUtils::getInstance()->showContainerElements(tVec); }

結果為:

1.9.2 replace_if

同find_if類似, 四個參數, 起始迭代器, 終止迭代器, 條件, 替換成的值, 如下測試代碼:

void replace_ifTest() {vector<int> tVec;TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);TestUtils::getInstance()->showContainerElements(tVec);replace_if(tVec.begin(), tVec.end(), [](auto element){return element < 5;}, 10);TestUtils::getInstance()->showContainerElements(tVec); }

結果為:

1.10 fill

如下測試代碼:

void fillTest() {vector<int> tVec;tVec.resize(10);fill(tVec.begin(), tVec.end(), 10);TestUtils::getInstance()->showContainerElements(tVec); }

結果:

1.11 集合算法

1.11.1 求容器交集 set_intersection

測試代碼如下:

void set_intersectionTest() {int array1[] = {0,1,2,3,4,5,6,7,8,9};int array2[] = {8,9,10,11,12,13,14,15,16,17};vector<int> tVec1;TestUtils::getInstance()->getSequentialContainerByArr(tVec1, PARAM_ARRAY(array1));vector<int> tVec2;TestUtils::getInstance()->getSequentialContainerByArr(tVec2, PARAM_ARRAY(array2));vector<int> tVec3;tVec3.resize(min(tVec1.size(), tVec2.size()));auto iterEnd = set_intersection(tVec1.begin(), tVec1.end(), tVec2.begin(), tVec2.end(),tVec3.begin());TestUtils::getInstance()->showContainerElements(tVec3);tVec3.erase(iterEnd, tVec3.end());TestUtils::getInstance()->showContainerElements(tVec3); }

結果為:

說明返回的是交集結束的迭代器, 剩下的都是0(因為調用的是resize). 接下來吧返回值迭代器到end() erase掉就可以了.

1.11.2?求容器并集 set_union

如下測試代碼:

void set_unionTest() {int array1[] = {0,1,2,3,4,5,6,7,8,9};int array2[] = {8,9,10,11,12,13,14,15,16,17};vector<int> tVec1;TestUtils::getInstance()->getSequentialContainerByArr(tVec1, PARAM_ARRAY(array1));vector<int> tVec2;TestUtils::getInstance()->getSequentialContainerByArr(tVec2, PARAM_ARRAY(array2));vector<int> tVec3;tVec3.resize(tVec1.size() + tVec2.size());auto iterEnd = set_union(tVec1.begin(), tVec1.end(), tVec2.begin(), tVec2.end(),tVec3.begin());TestUtils::getInstance()->showContainerElements(tVec3);tVec3.erase(iterEnd, tVec3.end());TestUtils::getInstance()->showContainerElements(tVec3); }

?結果為:

與交集同理.

1.11.3?求容器差集 set_difference

如下測試代碼:

void set_differenceTest() {int array1[] = {0,1,2,3,4,5,6,7,8,9};int array2[] = {8,9,10,11,12,13,14,15,16,17};vector<int> tVec1;TestUtils::getInstance()->getSequentialContainerByArr(tVec1, PARAM_ARRAY(array1));vector<int> tVec2;TestUtils::getInstance()->getSequentialContainerByArr(tVec2, PARAM_ARRAY(array2));vector<int> tVec3;tVec3.resize(tVec1.size() + tVec2.size());auto iterEnd = set_difference(tVec1.begin(), tVec1.end(), tVec2.begin(), tVec2.end(),tVec3.begin());TestUtils::getInstance()->showContainerElements(tVec3);tVec3.erase(iterEnd, tVec3.end());TestUtils::getInstance()->showContainerElements(tVec3);vector<int> tVec4;tVec4.resize(tVec1.size() + tVec2.size());iterEnd = set_difference(tVec2.begin(), tVec2.end(), tVec1.begin(), tVec1.end(),tVec4.begin());TestUtils::getInstance()->showContainerElements(tVec4);tVec4.erase(iterEnd, tVec4.end());TestUtils::getInstance()->showContainerElements(tVec4); }

結果為:

結果與剛開始想象的不一樣, 之前以為是v1和v2的差集是兩個集合中不相交的部分的集合, 但是輸出的結果顯示為set_difference的參數分別是:

第一個集合的首
第一個集合尾
第二個集合的首
第二個集合尾
輸出集合首

結果顯示為輸出的集合為第一個集合去掉了兩個集合相交的部分即為第一個集合的差集.

2 STL提供的函數對象

總結

以上是生活随笔為你收集整理的C++ STL 中提供的算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

算法
STL

上一篇： java保存文件到linux指定目录_怎
下一篇： ubuntu tomcat上传目录权限_