STL之算法(一)

本质

它就是一个模板函数.
拿for_each来说, 不一定要传递一个迭代器, 我们传递一个指针也可以
只要传入的类型支持 !=, *, ++ 操作即可.

lambda表达式

它其实就是个匿名函数.
以[] 开始, 后跟参数列表, 使用()括起来, 然后是函数体, 使用{}包括.
[]可以捕获变量, 并且可以指定以引用(&)方式, 值(=)方式进行捕获.
再此不在详述.

非变动型算法介绍

all_of

是否全部符合 of 的条件.
相对来说效率较高.

#include <algorithm>
#include <array>

int main()
{

    // all_of
    // 判断是否都是 奇数
    std::array<int, 8> foo = { 3,5,7,11,13,17,19,23 };
    if (std::all_of(foo.begin(), foo.end(), [](int i) {return i % 2; }))
        std::cout << "All the elements are odd numbers.\n";

    return 0;
}

any_of

有一个符合 of 的条件就可以.
相对效率较高.

#include <iostream>     // std::cout
#include <algorithm>    // std::any_of
#include <array>        // std::array

int main () {
  std::array<int,7> foo = {0,1,-1,3,-3,5,-5};
  // 判断是否有负数
  if ( std::any_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
    std::cout << "There are negative elements in the range.\n";

  return 0;
}

none_of

全部不符合 of 的条件
相对效率较高

#include <iostream>     // std::cout
#include <algorithm>    // std::none_of
#include <array>        // std::array

int main () {
  std::array<int,8> foo = {1,2,4,8,16,32,64,128};

  // 判断是否都是正数
  if ( std::none_of(foo.begin(), foo.end(), [](int i){return i<0;}) )
    std::cout << "There are no negative elements in the range.\n";

  return 0;
}

for_each

遍历容器, 并进行指定的动作

find

与给定的值做比较, 相等则查找到.
给定的值的类型, 不必与所查找的区间元素类型相同
只要支持 operator== 就可以
没找到, 返回 last (查找范围的底部)

#include <iostream>

#include <algorithm>

class Demo
{
    int num_;
public:
    Demo(int num = 0) : num_(num) {}

    bool operator==(int num)
    {
        return num_ == num;
    }
};

int main()
{

    Demo demoArr[10];

    std::find(demoArr, demoArr + sizeof(demoArr) / sizeof(Demo), 20);
    std::find(&demoArr[0], &demoArr[9], 20);

    return 0;
}

例子的情况, 可能无法正确判断.
因为如果查找的元素正好是 demoArr[9], 那么就不知道是否查找到了!
我们换成 &demoArr[10], 或者 demoArr + sizeof(demoArr) / sizeof(Demo) + 1 就可以了.

find_if

符合 if 的条件的查找结果
效率相对较高
返回last(查找的范围尾)
传入的区间必须是 前闭后开 区间

find_if_not

不符合 if 的条件的查找结果
效率相对较高
返回last(查找的范围尾)
传入的区间必须是 前闭后开 区间

find_end

范围查找, 查找第二个区间最后一次在第一个区间内出现的位置
没找到则返回区间一的 last(范围尾)
传递进入的对象必须支持 operator==
传入的区间必须都是 前闭后开 区间

#include <iostream>     // std::cout
#include <algorithm>    // std::find_end
#include <vector>       // std::vector

int main()
{
    int myints[] = { 1,2,3,4,5,1,2,3,4,5 };
    std::vector<int> haystack(myints, myints + 10);

    int needle1[] = { 1,2,3 };

    std::vector<int>::iterator it;
    it = std::find_end(haystack.begin(), haystack.end(), needle1, needle1 + 3);

    if (it != haystack.end())
        std::cout << "needle1 last found at position " << (it - haystack.begin()) << '\n';

    int needle2[] = { 4,5,1 };

    // using predicate comparison:
    it = std::find_end(haystack.begin(), haystack.end(), needle2, needle2 + 3, [](int i, int j) {return (i == j); });

    if (it != haystack.end())
        std::cout << "needle2 last found at position " << (it - haystack.begin()) << '\n';

    return 0;
}

find_first_of

范围查找, 查找第一个区间中第一个在第二个区间中存在的元素位置
查找第一个符合 of 条件的
没找到则返回区间一的 last(范围尾)
传递进入的对象必须支持 operator==
传入的区间必须都是 前闭后开 区间

adjacent_find

找到第一个相邻元素相等的位置
没找到返回 last(范围尾)
传入的区间需要是 前闭后开 的区间

#include <iostream>     // std::cout
#include <algorithm>    // std::find_end
#include <vector>       // std::vector

int main()
{
    int myints[] = { 5,20,5,30,30,20,10,10,20 };
    std::vector<int> myvector(myints, myints + 8);
    std::vector<int>::iterator it;

    // using default comparison:
    it = std::adjacent_find(myvector.begin(), myvector.end());

    if (it != myvector.end())
        std::cout << "the first pair of repeated elements are: " << *it << '\n';

    //using predicate comparison:
    it = std::adjacent_find(++it, myvector.end(), [](int i, int j) {return i == j; });

    if (it != myvector.end())
        std::cout << "the second pair of repeated elements are: " << *it << '\n';

    return 0;
}

count

计数
全部遍历

count_if

符合 if 的计数
全部遍历

mismatch

返回两个区间第一个不相同的对

#include <iostream>     // std::cout
#include <algorithm>    // std::find_end
#include <vector>       // std::vector

int main()
{
    std::vector<int> myvector;
    for (int i = 1; i<6; i++) myvector.push_back(i * 10); // myvector: 10 20 30 40 50

    int myints[] = { 10,20,80,320,1024 };                //   myints: 10 20 80 320 1024

    std::pair<std::vector<int>::iterator, int*> mypair;

    // using default comparison:
    mypair = std::mismatch(myvector.begin(), myvector.end(), myints);
    std::cout << "First mismatching elements: " << *mypair.first;
    std::cout << " and " << *mypair.second << '\n';

    ++mypair.first; ++mypair.second;

    // using predicate comparison:
    mypair = std::mismatch(mypair.first, myvector.end(), mypair.second, [](int i, int j) {return i == j; });
    std::cout << "Second mismatching elements: " << *mypair.first;
    std::cout << " and " << *mypair.second << '\n';


    return 0;
}

equal

判断是否完全相等

#include <iostream>     // std::cout
#include <algorithm>    // std::equal
#include <vector>       // std::vector

int main()
{
    int myints[] = { 20,40,60,80,100 };               //   myints: 20 40 60 80 100
    std::vector<int>myvector(myints, myints + 5);     // myvector: 20 40 60 80 100

    // using default comparison:
    if (std::equal(myvector.begin(), myvector.end(), myints))
        std::cout << "The contents of both sequences are equal.\n";
    else
        std::cout << "The contents of both sequences differ.\n";

    myvector[3] = 81;                                 // myvector: 20 40 60 81 100

    // using predicate comparison:
    if (std::equal(myvector.begin(), myvector.end(), myints, [](int i, int j) {return (i == j); }))
        std::cout << "The contents of both sequences are equal.\n";
    else
        std::cout << "The contents of both sequences differ.\n";

    return 0;
}

search

范围查找, 类似strstr
查找第二个区间第一次在第一个区间内出现的位置

search_n

搜索序列中是否有一系列元素值均为某个给定值的子序列

#include <iostream>     // std::cout
#include <algorithm>    // std::search_n
#include <vector>       // std::vector

int main()
{
    int myints[] = { 10,20,30,30,20,10,10,20 };
    std::vector<int> myvector(myints, myints + 8);

    std::vector<int>::iterator it;

    // using default comparison:
    // 搜索出现2次30的地方
    it = std::search_n(myvector.begin(), myvector.end(), 2, 30);

    if (it != myvector.end())
        std::cout << "two 30s found at position " << (it - myvector.begin()) << '\n';
    else
        std::cout << "match not found\n";

    // using predicate comparison:
    // 搜索连续出现2次等于10的地方
    it = std::search_n(myvector.begin(), myvector.end(), 2, 10, [](int i, int j) {return (i == j); });

    if (it != myvector.end())
        std::cout << "two 10s found at position " << int(it - myvector.begin()) << '\n';
    else
        std::cout << "match not found\n";

    return 0;
}

状态判断技法

我们写模板函数的时候, 可以对模板函数进行特化
例如在SGI的代码中, 我们在destroy函数的调用过程中
针对有无析构函数进行了判定
而判定不是用if来完成的, 而是用模板函数特化了true_value和false_value完成的
这样效率高, 可读性好

未完待续...

如有错误,请提出指正!谢谢.

本文由花心胡萝卜创作，采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: 2017-04-14 at 04:12 pm

PoEdu培训 STL班第十一课 STL源码解析之算法(一)

STL之算法(一)

分类

本质

lambda表达式

非变动型算法介绍

all_of

any_of

none_of

for_each

find

find_if

find_if_not

find_end

find_first_of

adjacent_find

count

count_if

mismatch

equal

search

search_n

状态判断技法

未完待续...

如有错误,请提出指正!谢谢.

PoEdu培训 STL班 第十一课 STL源码解析之算法(一)

STL之算法(一)

分类

本质

lambda表达式

非变动型算法介绍

all_of

any_of

none_of

for_each

find

find_if

find_if_not

find_end

find_first_of

adjacent_find

count

count_if

mismatch

equal

search

search_n

状态判断技法

未完待续...

如有错误,请提出指正!谢谢.

PoEdu培训 STL班第十一课 STL源码解析之算法(一)