C++：STL迭代


Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

Warning: WP_Syntax::substituteToken(): Argument #1 ($match) must be passed by reference, value given in /www/wwwroot/fawdlstty.com/wp-content/plugins/wp-syntax/wp-syntax.php on line 383

STL中的迭代是个重点，里面提供了大量的方法来方便我们程序猿开发，不过由于提供的太多导致学习比较吃力。这儿记录部分学习过程。
首先是C++11的for循环，比如对于一个vector v，可以通过for(int i : v)来实现迭代。如果对于自定义结构呢？也可以实现，如下代码示例调用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
class Int_col {
public:
    Int_col () { for (int i = 0; i < 10; i++) data [i] = i; }
    int data [10];
    int* begin () { return &data [0]; }
    int* end () { return &data [10]; }
};
 
int main(int argc, char* argv[]) {
    Int_col v;
    for (int i : v) {
        cout << i << " ";
    }
 
    return 0;
}

这儿的结构中只有10个数据，在结构中提供begin与end方法的迭代器，即可实现C++11的for循环调用。结果如下所示：
20160502225605

除此之外，STL提供迭代器语法，比如对一个数组中每个元素加10：

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int main(int argc, char* argv[]) {
    vector<int> v = { 0, 1, 2, 3, 4, 5 };
    for_each (v.begin (), v.end (), [] (int& i) { i += 10; });
    for (int i : v) cout << i << " ";
    return 0;
}

这儿用到了一个Lambda表达式，如果不太了解那么在这儿看看 C++11：lambda表达式
for_each通过两个迭代器指针依次遍历每个元素，然而分别调用后面的函数。for_each里面放lambda表达式的方法非常方便实际控制，但也有不用lambda，通过适配器来适配函数的实现，下面的代码仅为C++03及之前标准常用手法，这儿只是列出调用方法，并不代表推荐使用，切记！
对于不用lambda表达式的情况，一般用仿函数实现迭代器的迭代调用，实现每个元素值+10的效果的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
class Iter_Func {
public:
    Iter_Func () {}
    void operator()(int &i) {
        i += 10;
    }
};
 
int main(int argc, char* argv[]) {
    vector<int> v = { 0, 1, 2, 3, 4, 5 };
    for_each (v.begin (), v.end (), Iter_Func ());
    for (int i : v) cout << i << " ";
    return 0;
}

实现效果同上不再重复粘贴。可以看到在调用时构造了一个对象然后通过对象的仿函数进行调用实现。但值得注意的是，任何类，就算空类，也至少有1字节的内存开销。站在处女座角度来说，博主并不推荐仿函数的使用。开销还好说，主要是仿函数实现比较麻烦，远不如lambda表达式清晰直观，另外还得声明一个在项目其他地方基本用不到的类，违背了软件开发基本法则，公开了一个其他地方基本不使用的接口。
不再bb了，对于仿函数来说，可能其他地方会用到，并且不如lambda表达式灵活，可能有个仿函数在其他地方用的多，不能直接更改适配器实现，但在这儿并不能直接调用。这时候除了lambda表达式之外，还有种方法，叫适配器。这个在C++03上非常常用。适配器的原理是，提供一个接口，在需要的地方调用适配器的接口，适配器进行相应的参数的改动或者对返回值的改动，然后返回给调用者，相当于一个介质。比如如下代码，适配器绑定第一个参数以及绑定第二个参数的实现（注：bind1st、bind2nd这俩货在C++11里面也基本不用，建议通过bind函数实现绑定，具体请参考 C++11：std::bind实现参数动态绑定 ）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
 
class Iter_Func : public binary_function<int, int, void> {
public:
    void operator()(int i, int j) const {
        cout << "i = " << i << "  j = " << j << endl;
    }
};
 
int main(int argc, char* argv[]) {
    vector<int> v = { 0, 1, 2, 3, 4, 5 };
    for_each (v.begin (), v.end (), bind1st (Iter_Func (), 5));
    cout << endl;
    for_each (v.begin (), v.end (), bind2nd (Iter_Func (), 8));
    return 0;
}

由于bind1st与bind2nd只能适配调用，不能修改参数，所以仿函数后面得加上const关键字。bind1st时，将第一个参数全部绑定为5，bind2nd时，将第二个参数全部绑定为8。代码运行结果如下：
20160502235119
下面是函数指针适配器，lambda表达式出现之后彻底绝迹。C++03及之前主要用于将函数指针转为迭代器可调用函数，在C++11出来之后，不写函数指针转换器也不会报错。示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
 
void func (int &a) {
    a += 10;
}
 
int main(int argc, char* argv[]) {
    vector<int> v = { 0, 1, 2, 3, 4, 5 };
    for_each (v.begin (), v.end (), ptr_fun(func));//这儿直接写func也不会有任何问题
    for (int i : v) cout << i << " ";
    return 0;
}

结果大家都能猜出来，猜不出来运行就知道了，这儿不贴结果咯。
迭代除了调用之外，还能查找，比如如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
 
int main(int argc, char* argv[]) {
    vector<int> v = { 0, 1, 2, 3, 4, 5 };
    vector<int>::iterator i = find (v.begin (), v.end (), 3);
    if (i != v.end ()) {
        cout << "找到3" << endl;
    } else {
        cout << "没找到3" << endl;
    }
    return 0;
}

结果为找到3。这是对于基本类型的查找，如果对于类，那就需要重载==运算符实现查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
 
class Int {
public:
    Int (int i = 0) : val(i) {}
    bool operator==(const Int& o) const {
        return val == o.val;
    }
    int val;
};
 
int main(int argc, char* argv[]) {
    vector<Int> v = { 0, 1, 2, 3, 4, 5 };
    vector<Int>::iterator i = find (v.begin (), v.end (), Int (3));
    if (i != v.end ()) {
        cout << "找到3" << endl;
    } else {
        cout << "没找到3" << endl;
    }
    return 0;
}

结果同样为找到3。这里如果需要条件反转，那么需要用到not适配器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
 
class Int {
public:
    Int (int i = 0) : val(i) {}
    bool is3() const {
        return val == 3;
    }
    int val;
};
 
int main(int argc, char* argv[]) {
    vector<Int> v = { 0, 1, 2, 3, 4, 5 };
    vector<Int>::iterator i = find_if (v.begin (), v.end (), not1 (mem_fun_ref (&Int::is3)));
    if (i != v.end ()) {
        cout << "找到非3" << endl;
    } else {
        cout << "没找到非3" << endl;
    }
    vector<Int*> v1 = { new Int (0), new Int (1), new Int (2), new Int (3), new Int (4) };
    vector<Int*>::iterator i1 = find_if (v1.begin (), v1.end (), not1 (mem_fun (&Int::is3)));
    if (i1 != v1.end ()) {
        cout << "找到非3" << endl;
    } else {
        cout << "没找到非3" << endl;
    }
    for (Int *p : v1) delete p;
    return 0;
}

结果为两个找到非3。对于一个参数的取反适配器为not1，对于两个参数的为not2。这儿同时用到了mem_fun适配器与mem_fun_ref，分别代表类指针容器的对象方法调用与类对象容器的对象方法调用。
查找除了find与find_if外，还有binary_search二分法查找（对于有序向量）以及adjacent_find相邻重复元素查找（没发现有什么卵用），这儿不再举例。

发布者

fawdlstty

又一只萌萌哒程序猿~~

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注