当前位置:   article > 正文

C++ STL 中提供的算法_c++ reduce accumulate

c++ reduce accumulate

1 算法

1.1 for_each()

参数有三个:

  • 首迭代器
  • 尾迭代器
  • 执行的函数

例如如下代码:

  1. #include <algorithm> //必须包含
  2. #include <vector>
  3. using namespace std;
  4. int main() {
  5. vector<int> tmp;
  6. tmp.push_back(10);
  7. tmp.push_back(20);
  8. tmp.push_back(30);
  9. tmp.push_back(40);
  10. for_each(tmp.begin(), tmp.end(), [](int vecVal){cout << vecVal << endl;});
  11. return 0;
  12. }

结果是:

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, 条件; 如下测试代码:

  1. void find_if_test() {
  2. vector<char> tVec;
  3. char ch[] = "hello world";
  4. TestUtils::getInstance()->getSequentialContainerByArr<char>(tVec, PARAM_ARRAY(ch));
  5. TestUtils::getInstance()->showContainerElements(tVec);
  6. auto iter = find_if(tVec.begin(),tVec.end(),[](auto element){return element == 'o';});
  7. if (iter == tVec.end()) {
  8. cout << "find o failed" << endl;
  9. } else {
  10. cout << "successfully find " << *iter << endl;
  11. }
  12. }

结果:

1.4.3 adjacent_find

查找相邻重复元素, 如果查到了返回第一个元素迭代器, 查不到的话返回end();

如下测试代码:

  1. void adjacent_find_test() {
  2. vector<int> tVec;
  3. int array[] = {2,3,5,8,7,1,5,6,2,5};
  4. TestUtils::getInstance()->getSequentialContainerByArr(tVec, PARAM_ARRAY(array));
  5. auto iter = adjacent_find(tVec.begin(), tVec.end());
  6. if (iter == tVec.end()) {
  7. cout << "find same element failed" << endl;
  8. } else {
  9. cout << "find same element " << *iter << endl;
  10. }
  11. sort(tVec.begin(), tVec.end(), less<int>());
  12. iter = adjacent_find(tVec.begin(), tVec.end());
  13. if (iter == tVec.end()) {
  14. cout << "find same element failed" << endl;
  15. } else {
  16. cout << "find same element " << *iter << endl;
  17. }
  18. auto riter = adjacent_find(tVec.rbegin(), tVec.rend());
  19. if (riter == tVec.rend()) {
  20. cout << "find same element failed" << endl;
  21. } else {
  22. cout << "find same element " << *riter << endl;
  23. }
  24. }

结果:

1.4.4 binary_search

参数列表跟find一样, 但是返回值是true或者false. 这个查找法必须在有序的序列中才能使用, 效率比较高, 时间复杂度为o(log n).

如下测试函数:

  1. void binary_search_test() {
  2. vector<int> tVec;
  3. for (int i = 0; i < 100000; i ++) {
  4. tVec.push_back(i);
  5. }
  6. double findStartTime = TestUtils::getInstance()->getNowMillisecond();
  7. auto iter = find(tVec.begin(), tVec.end(),38472);
  8. if (iter != tVec.end()) {
  9. cout << "successfully find " << *iter << endl;
  10. } else {
  11. cout << "find failed" << endl;
  12. }
  13. double findEndTime = TestUtils::getInstance()->getNowMillisecond();
  14. cout << "find cost " << findEndTime - findStartTime << "ms" << endl;
  15. double binary_searchStartTime = TestUtils::getInstance()->getNowMillisecond();
  16. bool ret = binary_search(tVec.begin(), tVec.end(),38472);
  17. if (ret) {
  18. cout << "successfully binary_search " << endl;
  19. } else {
  20. cout << "find failed" << endl;
  21. }
  22. double binary_searchEndTime = TestUtils::getInstance()->getNowMillisecond();
  23. cout << "binary_search cost " << binary_searchEndTime - binary_searchStartTime << "ms" << endl;
  24. }

结果为:

参数中可以添加第四个参数, 就是序列排序的方法, 默认是从小到大排序的, 所以说当你传入的数组是降序排列且没有传入降序排列的参数, 那么就会找不到, 如下测试代码:

  1. void binary_search_test_1() {
  2. vector<int> tVec;
  3. for (int i = 99999; i >= 0; i --) {
  4. tVec.push_back(i);
  5. }
  6. bool ret = binary_search(tVec.begin(), tVec.end(), 38472);
  7. if (ret) {
  8. cout << "successfully binary_search " << endl;
  9. } else {
  10. cout << "find failed" << endl;
  11. }
  12. }

结果为:

当传入排序方式, 如下测试代码:

  1. void binary_search_test_1() {
  2. vector<int> tVec;
  3. for (int i = 99999; i >= 0; i --) {
  4. tVec.push_back(i);
  5. }
  6. bool ret = binary_search(tVec.begin(), tVec.end(), 38472, greater<int>());
  7. if (ret) {
  8. cout << "successfully binary_search " << endl;
  9. } else {
  10. cout << "find failed" << endl;
  11. }
  12. }

就会正常找到, 结果:

1.5 统计

1.5.1 count

同find类似, 三个参数是first, last, 统计值. 返回值是总数.

如下测试代码:

  1. void count_test() {
  2. vector<int> tVec;
  3. for (int i = 99999; i >= 0; i --) {
  4. tVec.push_back(i);
  5. }
  6. for (int i = 0; i < 10; i ++) {
  7. tVec.push_back(10);
  8. }
  9. cout << count(tVec.begin(), tVec.end(), 10) << endl;
  10. }

结果为:

 

1.5.2 count_if

同find_if类似, 也是三个参数, first, last, 条件.

如下测试代码:

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

结果为:

1.6 random_shuffle

随机打乱序列算法, 只需传入first, last就可以, 如下测试代码:

  1. void random_shuffle_test() {
  2. vector<int> tVec;
  3. TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);
  4. TestUtils::getInstance()->showContainerElements(tVec);
  5. random_shuffle(tVec.begin(),tVec.end());
  6. TestUtils::getInstance()->showContainerElements(tVec);
  7. }

结果如下:

 

1.7 merge

将两个有序容器合并为一个有序容器, 如下测试代码:

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

 结果:

1.8 reverse

将序列反转, 需要提供起始迭代器和终止迭代器.测试代码如下:

  1. void reverseTest() {
  2. vector<int> tVec;
  3. TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);
  4. TestUtils::getInstance()->showContainerElements(tVec);
  5. reverse(tVec.begin(), tVec.end());
  6. TestUtils::getInstance()->showContainerElements(tVec);
  7. }

结果如下:

 

1.9 替换

1.9.1 replace

把一个容器中数据替换为另一个数据, 参数有四个, 起始迭代器, 终止迭代器, 需要被替换的值, 替换后的值.

如下测试代码:

  1. void replaceTest() {
  2. vector<int> tVec;
  3. TestUtils::getInstance()->getSequentialContainerByArr<int>(tVec);
  4. TestUtils::getInstance()->showContainerElements(tVec);
  5. tVec.push_back(6);
  6. tVec.push_back(6);
  7. tVec.push_back(6);
  8. tVec.push_back(6);
  9. replace(tVec.begin(), tVec.end(), 6, 10);
  10. TestUtils::getInstance()->showContainerElements(tVec);
  11. }

结果为:

1.9.2 replace_if

同find_if类似, 四个参数, 起始迭代器, 终止迭代器, 条件, 替换成的值, 如下测试代码:

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

结果为:

1.10 fill

如下测试代码:

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

结果:

1.11 集合算法

1.11.1 求容器交集 set_intersection

测试代码如下:

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

结果为:

 

说明返回的是交集结束的迭代器, 剩下的都是0(因为调用的是resize). 接下来吧返回值迭代器到end() erase掉就可以了.

1.11.2 求容器并集 set_union

如下测试代码:

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

 结果为:

与交集同理.

1.11.3 求容器差集 set_difference

如下测试代码:

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

结果为:

 

结果与刚开始想象的不一样, 之前以为是v1和v2的差集是两个集合中不相交的部分的集合, 但是输出的结果显示为set_difference的参数分别是:

  • 第一个集合的首
  • 第一个集合尾
  • 第二个集合的首
  • 第二个集合尾
  • 输出集合首

结果显示为输出的集合为第一个集合去掉了两个集合相交的部分即为第一个集合的差集.

2 STL提供的函数对象

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号