前情提要： CppNote3

容器的选择

序列式容器：vector、deque、list、array、forward_list
关联式容器：set、multiset、map、multimap
无序关联式容器：unordered_set、unordered_multiset、unordered_map、unordered_multimap
容器适配器：stack、queue、priority_queue

容器中元素是否有顺序？

  • 如果有顺序，首选关联式容器或者优先级队列，备选序列式容器（sort），肯定不会用到无序关联式容
    器。
  • 如果没有顺序，首选就是无序关联式容器，备选序列式容器，不会选择关联式容器或者优先级队列。

容器是否具有下标？
vector、deque、map、unordered_map

迭代器的类型？

  • 随机访问迭代器（LegacyRandomAccessIterator）：vector、deque
  • 双向迭代器（LegacyBidirectionalIterator）：list、关联式容器
  • 前向迭代器（LegacyForwardIterator）：无序关联式容器

容器是否具有迭代器？
除了容器适配器之外，其他的容器都具备迭代器。

迭代器概述

从前面的用法看，迭代器类似于指针。

模板的引入使函数和类的定义脱离了存储类型的限制，在需要时指定即可，是一种泛化的思维观念。
迭代器是更高层次的抽象，它使算法独立于容器，算法独立于类型。

不同的算法对迭代器的要求不同，为此，STL定义了5种迭代器，分别是

  • 随机访问迭代器（RandomAccessIterator）
  • 双向迭代器（BidirectionalIterator）
  • 前向迭代器（ForwardIterator）
  • 输出迭代器（OutputIterator）
  • 输入迭代器（InputIterator）

其层次结构如图所示：

74-1.png

为什么要定义这么多迭代器？

  • 不同的算法要求的迭代器类型不同，定义 5 种迭代器，是为了使用 “最合适” 的工具，编写算法时在满足要求的基础上尽可能地使用功能少的迭代器，减少副作用。假设要编写一个查找函数find()，只要能读取容器中的元素即可，最理想的方案是使用输入迭代器，这样，有效防止了在find()函数内对元素的修改，真正“物尽其用”。打个比方，一把刀既能削铁如泥，又能砍瓜切菜，还能理发，真正用其理发是很危险的，不如剃头刀来的安全方便。
  • 对 5 种迭代器初步了解后，重看上图，实际上，依照箭头的方向，迭代器实现的功能越来越少，除了输出迭代器和输入迭代器是功能相反的并列关系外，箭头左侧的迭代器不仅都实现了右侧迭代器所有的功能，而且在其基础上增加了一些功能。所以说，箭头左侧的迭代器“适应”于箭头右侧的迭代器。因此，如果某个算法的形参为前向迭代器，则实参可以是双向迭代器和随机访问迭代器，但不能是输出迭代器或输入迭代器。

迭代器操作和类别：

74-2.png

流迭代器

流迭代器是特殊的迭代器，包括两种：

  • 输出流迭代器(ostream_iterator)
  • 输入流迭代器(istream_iterator)

理解的要点是将 输入/输出流 作为容器看待。因此，任何接受迭代器参数的算法都可以和流一起工作。使用流迭代器必须要包含头文件<iterator>。

输出流迭代器

ostream_iterator 的构造函数：

1
2
ostream_iterator( ostream_type& stream, const CharT* delim );
ostream_iterator( ostream_type& stream );

std::copy，在头文件<algorithm>中：

1
2
3
template< class InputIt, class OutputIt >
OutputIt copy( InputIt first, InputIt last,
               OutputIt d_first );

看一个演示例子：

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
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::vector;
using std::copy;
using std::ostream_iterator;

void test() {
    vector<int> vec = {1, 3, 5, 2, 4};
    // 流对象可以看作容器
    ostream_iterator<int> osi(cout, "\n");
    copy(vec.begin(), vec.end(), osi);
}

int main() {
    test();
    return 0;
}
/*
1
3
5
2
4
*/

下面我们试着从源码上看看究竟发生了什么。（为简单起见，源码作了一定修改，重要的是理解其逻辑）

ostream_iterator 的源码：

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
35
36
37
38
39
40
41
42
class ostream_iterator
{
public:
    //ostream_iterator<int> osi(cout, "\n");
    //__s = cout;
    //const _CharT* __c = "\n"
    //_M_stream = &cout;
    //_M_string = __c;
    ostream_iterator(ostream_type& __s, const _CharT* __c)
    : _M_stream(&__s)
    , _M_string(__c)
    {
    }

    //__value = 1
    ostream_iterator<_Tp>& operator=(const int& __value)
    {
        *_M_stream << __value;//cout << 1
        if (_M_string)
        *_M_stream << _M_string;//cout << "\n"
        return *this;
    }

    ostream_iterator<_Tp>& operator*()
    {
        return *this;
    }

    ostream_iterator<_Tp>& operator++()
    {
        return *this;
    }

    ostream_iterator<_Tp>& operator++(int)
    {
        return *this;
    }

private:
    ostream_type* _M_stream;
    const _CharT* _M_string;
};

copy 的源码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//copy--->__copy_aux--->__copy_aux2--->__copy
template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last,
                        _OutputIter __result)
{
    __STL_REQUIRES(_InputIter, _InputIterator);
    __STL_REQUIRES(_OutputIter, _OutputIterator);
    return __copy_aux(__first, __last, __result, __VALUE_TYPE(__first));
}

template <class _InputIter, class _OutputIter, class _Tp>
inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
                              _OutputIter __result, _Tp*) {
    typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
            _Trivial;
    return __copy_aux2(__first, __last, __result, _Trivial());
}

template <class _InputIter, class _OutputIter>
inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
                               _OutputIter __result, __false_type) {
    return __copy(__first, __last, __result,
                  __ITERATOR_CATEGORY(__first),
                  __DISTANCE_TYPE(__first));
}

template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result,
                          input_iterator_tag, _Distance*)
{
    for ( ; __first != __last; ++__result, ++__first)
        *__result = *__first;
    return __result;
}

//vector<int> vec = {1, 3, 7, 9, 6};
//copy(vec.begin(), vec.end(), osi);
//__first = vec.begin()
//__last = vec.end()
//__result = osi
                    last
1   3   5   2   4
    f

osi = 1
_OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result )
{
    for ( ; __first != __last; ++__result, ++__first)
        *__result = *__first;
    return __result;
}

输入流迭代器、gdb 调试

接下来，看看 istream_iterator 的例子：

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 <iterator>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::cin;
using std::copy;
using std::vector;
using std::istream_iterator;
using std::ostream_iterator;

void test() {
    vector<int> vec;
    istream_iterator<int> isi(cin);
    copy(isi, istream_iterator<int>(), vec.begin());
    copy(vec.begin(), vec.end(), 
         ostream_iterator<int>(cout, " ")); // 右值
    cout << endl;
}

int main() {
    test();
    return 0;
}

上面这份代码出错了，我们尝试使用 gdb 调试。

使用编译选项-g，例如：

1
g++ .\tmptest.cpp -o main -g

生成了 main.exe ，继续键入命令：

1
gdb .\main.exe

进入了 gdb 调试。

常用命令list，显示代码：

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
35
36
37
38
(gdb) list
10      using std::vector;
11      using std::istream_iterator;
12      using std::ostream_iterator;
13
14      void test() {
15          vector<int> vec;
16          istream_iterator<int> isi(cin);
17          copy(isi, istream_iterator<int>(), vec.begin());
18          copy(vec.begin(), vec.end(),
(gdb) list 1     ostream_iterator<int>(cout, " ")); // 鍙冲€?
1       #include <iostream>
2       #include <iterator>
3       #include <vector>
4       #include <algorithm>
5
6       using std::cout;
7       using std::endl;
8       using std::cin;
9       using std::copy;
10      using std::vector;
(gdb) list
11      using std::istream_iterator;
12      using std::ostream_iterator;
13
14      void test() {
15          vector<int> vec;
16          istream_iterator<int> isi(cin);
17          copy(isi, istream_iterator<int>(), vec.begin());
18          copy(vec.begin(), vec.end(),
20          cout << endl;iterator<int>(cout, " ")); // 鍙冲€?
(gdb) list
21      }
22
23      int main() {
24          test();
25          return 0;
26      }

运行程序（100是输入）：

1
2
3
4
5
6
7
8
9
10
11
(gdb) run
Starting program: D:\c++code\main.exe
[New Thread 16524.0x3c68]
[New Thread 16524.0x265c]
[New Thread 16524.0x31a8]
100

Thread 1 received signal SIGSEGV, Segmentation fault.
0x00007ff7eeab3498 in std::__copy_move<false, false, std::input_iterator_tag>::__copy_m<std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:356
356                 *__result = *__first;

bt命令，打印堆栈信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(gdb) bt
#0  0x00007ff7eeab3498 in std::__copy_move<false, false, std::input_iterator_tag>::__copy_m<std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:356
#1  0x00007ff7eeab3e3b in std::__copy_move_a2<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=...,
    __result=0x0) at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:506
#2  0x00007ff7eeab3d8b in std::__copy_move_a1<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=...,
    __result=0x0) at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:533
#3  0x00007ff7eeab3cd9 in std::__copy_move_a<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > > (__first=..., __last=...,
    __result=non-dereferenceable iterator for std::vector)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:540
#4  0x00007ff7eeab3f2b in std::copy<std::istream_iterator<int, char, std::char_traits<char>, long long>, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > > (__first=..., __last=...,
    __result=non-dereferenceable iterator for std::vector)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:633
#5  0x00007ff7eeab173e in test () at .\tmptest.cpp:17
#6  0x00007ff7eeab17ea in main () at .\tmptest.cpp:24

由上面的信息，我们可以定位到出错代码的行号。

我们继续看看 gdb 调试的其他命令。

打断点：

1
2
3
4
5
6
7
8
(gdb) b 15
Breakpoint 1 at 0x1400016e1: file .\tmptest.cpp, line 15.
(gdb) b 24
Breakpoint 2 at 0x1400017e5: file .\tmptest.cpp, line 24.
(gdb) info b
Num     Type           Disp Enb Address            What
1       breakpoint     keep y   0x00000001400016e1 in test() at .\tmptest.cpp:15
2       breakpoint     keep y   0x00000001400017e5 in main() at .\tmptest.cpp:24

开始运行：

1
2
3
4
5
6
7
8
9
(gdb) r
Starting program: D:\c++code\main.exe
[New Thread 7156.0x3b14]
[New Thread 7156.0x4534]
[New Thread 7156.0x179c]

Thread 1 hit Breakpoint 2, main () at .\tmptest.cpp:24
24          test();
(gdb)

单步调试s：

1
2
3
4
(gdb) s

Thread 1 hit Breakpoint 1, test () at .\tmptest.cpp:15
15          vector<int> vec;

一行一行地执行：

1
2
(gdb) n
16          istream_iterator<int> isi(cin);

继续（10 是输入）：

1
2
3
(gdb) n
10
17          copy(isi, istream_iterator<int>(), vec.begin());

继续：

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

Thread 1 received signal SIGSEGV, Segmentation fault.
0x00007ff6ef5c3498 in std::__copy_move<false, false, std::input_iterator_tag>::__copy_m<std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:356
356                 *__result = *__first;
(gdb) bt
#0  0x00007ff6ef5c3498 in std::__copy_move<false, false, std::input_iterator_tag>::__copy_m<std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:356
#1  0x00007ff6ef5c3e3b in std::__copy_move_a2<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=...,
    __result=0x0) at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:506
#2  0x00007ff6ef5c3d8b in std::__copy_move_a1<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=...,
    __result=0x0) at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:533
#3  0x00007ff6ef5c3cd9 in std::__copy_move_a<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > > (__first=..., __last=...,
    __result=non-dereferenceable iterator for std::vector)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:540
#4  0x00007ff6ef5c3f2b in std::copy<std::istream_iterator<int, char, std::char_traits<char>, long long>, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > > (__first=..., __last=...,
    __result=non-dereferenceable iterator for std::vector)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:633
#5  0x00007ff6ef5c173e in test () at .\tmptest.cpp:17
#6  0x00007ff6ef5c17ea in main () at .\tmptest.cpp:24

使某个断点失效，disable 1，其中 1 是断点的编号。

c(continue)，运行到下一个断点。

栈帧的切换：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
PS D:\c++code> gdb .\main.exe
GNU gdb (GDB for MinGW-W64 x86_64, built by Brecht Sanders) 13.2
Copyright (C) 2023 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.
Type "show copying" and "show warranty" for details.
This GDB was configured as "x86_64-w64-mingw32".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<https://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
    <http://www.gnu.org/software/gdb/documentation/>.

For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from .\main.exe...
(gdb) r
Starting program: D:\c++code\main.exe
[New Thread 13656.0x3134]
[New Thread 13656.0x2c08]
[New Thread 13656.0x13cc]
10

Thread 1 received signal SIGSEGV, Segmentation fault.
0x00007ff6ef5c3498 in std::__copy_move<false, false, std::input_iterator_tag>::__copy_m<std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:356
356                 *__result = *__first;
(gdb) bt
#0  0x00007ff6ef5c3498 in std::__copy_move<false, false, std::input_iterator_tag>::__copy_m<std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=..., __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:356
#1  0x00007ff6ef5c3e3b in std::__copy_move_a2<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=...,
    __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:506
#2  0x00007ff6ef5c3d8b in std::__copy_move_a1<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=...,
    __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:533
#3  0x00007ff6ef5c3cd9 in std::__copy_move_a<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > > (__first=...,
    __last=..., __result=non-dereferenceable iterator for std::vector)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:540
#4  0x00007ff6ef5c3f2b in std::copy<std::istream_iterator<int, char, std::char_traits<char>, long long>, __gnu_cxx::__normal_iterator<int*, std::vector<int, std::allocator<int> > > > (__first=..., __last=...,
    __result=non-dereferenceable iterator for std::vector)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:633
#5  0x00007ff6ef5c173e in test () at .\tmptest.cpp:17
#6  0x00007ff6ef5c17ea in main () at .\tmptest.cpp:24
(gdb) f 2
#2  0x00007ff6ef5c3d8b in std::__copy_move_a1<false, std::istream_iterator<int, char, std::char_traits<char>, long long>, int*> (__first=...,
    __last=..., __result=0x0)
    at D:/mingw64/include/c++/13.2.0/bits/stl_algobase.h:533
533         { return std::__copy_move_a2<_IsMove>(__first, __last, __result); }

现在回到本级标题下最开始遇到的问题。

解决方案：

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
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

using std::cout;
using std::endl;
using std::cin;
using std::copy;
using std::vector;
using std::istream_iterator;
using std::ostream_iterator;

void test() {
    vector<int> vec;
    istream_iterator<int> isi(cin);

    copy(isi, istream_iterator<int>(), std::back_inserter(vec));
    copy(vec.begin(), vec.end(), 
         ostream_iterator<int>(cout, " ")); // 右值
    cout << endl;
}

int main() {
    test();
    return 0;
}
/*
1
2
3
4
6
7

334
3456
3456

3434
^Z
1 2 3 4 6 7 334 3456 3456 3434
*/

// 此为 windows 环境

解释，需要看源码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class istream_iterator
{
public:
    istream_iterator()
    : _M_stream(0)
    , _M_ok(false)
    {}
    //istream_iterator<int> isi(cin);
    //__s = cin;
    //_M_stream = &cin;
    istream_iterator(istream_type& __s)
    : _M_stream(&__s)
    {
        _M_read();
    }

    void _M_read()
    {
        _M_ok = (_M_stream && *_M_stream) ? true : false; //true
        if (_M_ok)
        {
            *_M_stream >> _M_value; // cin >> _M_value
            _M_ok = *_M_stream ? true : false;
        }
    }

    reference operator*() const
    {
        return _M_value;
    }

    istream_iterator& operator++()
    {
        _M_read();
        return *this;
    }

    bool _M_equal(const istream_iterator& __x) const
    {
        return (_M_ok == __x._M_ok) && (!_M_ok || _M_stream == __x._M_stream);
    }

private:
    istream_type* _M_stream;
    _Tp _M_value;
    bool _M_ok;
};

//__x = isi;
//__y = istream_iterator<int>()
bool operator==(const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __x,
                const istream_iterator<_Tp, _CharT, _Traits, _Dist>& __y)
{
    return __x._M_equal(__y);
}

class back_insert_iterator
{
public:
    back_insert_iterator<_Container>&
    operator=(const typename _Container::value_type& __value)
    {
        container->push_back(__value);
        return *this;
    }

    back_insert_iterator<_Container>& operator*()
    {
        return *this;
    }

    back_insert_iterator<_Container>& operator++()
    {
        return *this;
    }

    back_insert_iterator<_Container>& operator++(int) { return *this; }
};
1
2
3
4
5
6
7
8
9
10
11
//copy(isi, istream_iterator<int>(), std::back_inserter(vec));
//__first = isi;
//__last = istream_iterator<int>()
//__result = std::back_inserter(vec)
_OutputIter copy(_InputIter __first, _InputIter __last, _OutputIter __result )
{
    for ( ; __first != __last; ++__result, ++__first)
        *__result = *__first;
    return __result;
}
// __result = 2

插入迭代器

在尾部进行插入：back_inserter、back_insert_iterator
在头部进行插入：front_inserter、front_insert_iterator
在任意位置进行插入：inserter、insert_iterator

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <iterator>
#include <vector>
#include <set>
#include <list>
#include <algorithm>

using std::cout;
using std::endl;
using std::back_inserter;
using std::back_insert_iterator;
using std::front_inserter;
using std::front_insert_iterator;
using std::inserter;
using std::insert_iterator;
using std::vector;
using std::list;
using std::set;
using std::ostream_iterator;
using std::copy;

void test() {
    vector<int> vecNum = {1, 3, 5, 9, 7};
    list<int> listNum = {11, 22, 44, 66, 99, 33};
    copy(vecNum.begin(), vecNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;

    // 在 vector 尾部插入
    copy(listNum.begin(), listNum.end(), back_inserter(vecNum));

    copy(vecNum.begin(), vecNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
/*
1 3 5 9 7 
1 3 5 9 7 11 22 44 66 99 33 
*/
}

void test2() {
    vector<int> vecNum = {1, 3, 5, 9, 7};
    list<int> listNum = {11, 22, 44, 66, 99, 33};
    copy(vecNum.begin(), vecNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;

    // 在 vector 尾部插入
    copy(listNum.begin(), listNum.end(),
         back_insert_iterator<vector<int>>(vecNum));
    // 可以参考 cppreference

    copy(vecNum.begin(), vecNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
/*
1 3 5 9 7 
1 3 5 9 7 11 22 44 66 99 33 
*/
}

void test3() {
    // 在 list 前面插入数据
    vector<int> vecNum = {1, 3, 5, 9, 7};
    list<int> listNum = {11, 22, 44, 66, 99, 33};
    copy(listNum.begin(), listNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;

    // 在 vector 尾部插入
    copy(vecNum.begin(), vecNum.end(),
         front_inserter(listNum));

    copy(listNum.begin(), listNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
/*
11 22 44 66 99 33 
7 9 5 3 1 11 22 44 66 99 33 
*/
}

void test4() {
    vector<int> vecNum = {1, 3, 5, 9, 7};
    set<int> setNum = {1, 3, 7, 99, 66, 55, 22, 22, 7, 33};

    copy(setNum.begin(), setNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;

    auto sit = setNum.begin();

    copy(vecNum.begin(), vecNum.end(),
         inserter(setNum, sit));
    // 可以参考 cppreference

    copy(setNum.begin(), setNum.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
/*
1 3 7 22 33 55 66 99 
1 3 5 7 9 22 33 55 66 99 
*/
}

int main(int argc, char** argv) {
    test4();
    return 0;
}

反向迭代器

看例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <vector>

using std::cout;
using std::vector;

int main() {
    vector<int> num = {1, 3, 5, 7};
    vector<int>::reverse_iterator rit = num.rbegin();
    for(; rit != num.rend(); ++rit) {
        cout << *rit << " ";
    }
    return 0;
}
/*
7 5 3 1 
*/

算法

算法库中的函数，都是非成员函数。不是针对与某一种具体的类型或容器编程，而是针对所有的类型或者容器进行编程，可以体现通用编程或者泛型编程的思想。

分类：

  • 非修改式的算法：for_each、count、find、search
  • 修改式的算法：copy、remove_if、move、replace
  • 排序算法：sort
  • 二分搜索：lower_bound、upper_bound、equal_range
  • 集合操作：set_difference、set_intersection、set_union
  • 未初始化的内存操作：uninitialized_copy

不是所有的算法都要一一去进行使用，需要懂得方法，然后在使用的时候，可以进行查找即可。（学方法）

for_each

1
2
template< class InputIt, class UnaryFunc >
UnaryFunc for_each( InputIt first, InputIt last, UnaryFunc f );

学点单词：

1
unary   adj. [数] 一元的

例子：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using std::cout;
using std::endl;
using std::vector;
using std::for_each;
using std::ostream_iterator;
using std::copy;

void func(int value) {
    ++ value;
    cout << value << " " ;
}

void func2(int& value) {
    ++ value;
    cout << value << " " ;
}

void test() {
    vector<int> num = {1, 4, 7, 9, 5, 8, 2};
    cout << "original data:" << endl;
    copy(num.begin(), num.end(), 
         ostream_iterator<int>(cout, " "));
    cout << endl;

    cout << "entering func..." << endl;
    for_each(num.begin(), num.end(), func);

    cout << endl;
    cout << "data in vector:" << endl;
    copy(num.begin(), num.end(), 
         ostream_iterator<int>(cout, " "));
    cout << endl;

    cout << "entering func2..." << endl;
    for_each(num.begin(), num.end(), func2);
    cout << endl;
    cout << "data in vector:" << endl;
    copy(num.begin(), num.end(), 
         ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main() {
    test();
    return 0;
}
/*
original data:
1 4 7 9 5 8 2 
entering func...
2 5 8 10 6 9 3 
data in vector:
1 4 7 9 5 8 2 
entering func2...
2 5 8 10 6 9 3 
data in vector:
2 5 8 10 6 9 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
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using std::cout;
using std::endl;
using std::vector;
using std::for_each;
using std::ostream_iterator;
using std::copy;

void test() {
    vector<int> num = {1, 4, 7, 9, 5, 8, 2};
    cout << "original data:" << endl;
    copy(num.begin(), num.end(), 
         ostream_iterator<int>(cout, " "));
    cout << endl << endl;

    // 匿名函数，lambda 表达式
    // [] 捕获列表
    for_each(num.begin(), num.end(), [](int& value){
        ++ value;
        cout << value << " ";
    });
}

int main() {
    test();
    return 0;
}
/*
original data:
1 4 7 9 5 8 2 

2 5 8 10 6 9 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 在匿名函数中，需要捕获
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using std::cout;
using std::endl;
using std::vector;
using std::for_each;
using std::ostream_iterator;
using std::copy;

void test() {
    int a = 10;
    vector<int> num = {1, 4, 7, 9, 5, 8, 2};
    cout << "original data:" << endl;
    copy(num.begin(), num.end(), 
         ostream_iterator<int>(cout, " "));
    cout << endl << endl;

    // 匿名函数，lambda 表达式
    // [] 捕获列表
    // () 参数列表
    // {} 函数体
    for_each(num.begin(), num.end(), [&a](int& value)->void {
        cout << "a = " << a << endl;
        ++ value;
        cout << value << " ";
    });
}

int main() {
    test();
    return 0;
}
/*
original data:
1 4 7 9 5 8 2 

a = 10
2 a = 10
5 a = 10
8 a = 10
10 a = 10
6 a = 10
9 a = 10
3
*/

remove_if

来看一个例子：

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
35
36
37
38
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using std::cout;
using std::endl;
using std::vector;
using std::for_each;
using std::ostream_iterator;
using std::copy;

bool func(int value) {
    return value > 9;
}

void test() {
    vector<int> num = {1, 9, 8, 22, 55, 123, 8, 3, 2};
    for_each(num.begin(), num.end(), [](int& value){
        cout << value << " ";
    });
    cout << endl;

    remove_if(num.begin(), num.end(), func);

    copy(num.begin(), num.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main() {
    test();
    return 0;
}
/*
1 9 8 22 55 123 8 3 2 
1 9 8 8 3 2 8 3 2 
*/

上面的代码输出结果似乎和我们预期不符。来看一下源码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
bool func(int value)
{
    return value > 9;
}

//remove_if(number.begin(), number.end(), func);
//vector<int> number = {1, 9, 8, 22, 55, 123, 8, 3, 2};
//first = number.begin()
//last = number.end()
//p = func
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if(first, last, p);
    if (first != last)
    {
        for(ForwardIt i = first; ++i != last; )
        {
            if (!p(*i))
            {
                *first = std::move(*i);
                first++;
            }
        }
    }
    return first;
}

                  f        last
1, 9, 8, 8, 3, 2, 8, 3, 2
                           i

bool func(int value)
{
    return value > 9;
}
                                last
1, 9, 8, 22, 55, 123, 8, 3, 2
         f

constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
{
    for (; first != last; ++first)
    {
        if (p(*first)) {
            return first;
        }
    }
    return last;
}

人话总结：将不要的元素删除，位置由后面的合法元素填充。同时并不会删除后面的合法元素。

remove_if 是有返回值的，由此给出改进方案：

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
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using std::cout;
using std::endl;
using std::vector;
using std::for_each;
using std::ostream_iterator;
using std::copy;

bool func(int value) {
    return value > 9;
}

void test() {
    vector<int> num = {1, 9, 8, 22, 55, 123, 8, 3, 2};
    for_each(num.begin(), num.end(), [](int& value){
        cout << value << " ";
    });
    cout << endl;

    // remove_if 返回待删除元素的首迭代器
    auto it = remove_if(num.begin(), num.end(), func);
    num.erase(it, num.end());

    copy(num.begin(), num.end(),
         ostream_iterator<int>(cout, " "));
    cout << endl;
}

int main() {
    test();
    return 0;
}
/*
1 9 8 22 55 123 8 3 2 
1 9 8 8 3 2 
*/

remove_if 之所以要这样设计，是为了满足泛型编程的思想（通用编程的思想），要针对于所有的容器进行编程。

1
2
3
4
5
6
7
vector                      i
1, 9, 8, 8,3, 2, 8, 3, 2
                 f

list
1, 9, 8, 22 , 55, 123, 8, 3, 2
         f

bind

bind1st 可以绑定二元函数对象 f 的第一个参数，第一个参数使用 x 进行替代，bind2nd 可以绑定二元函数对象 f 的第二个参数，第二个参数使用 x 进行替代。

以下代码若有不懂的可以结合 cppreference 理解：

74-3.png

bind1st 和 bind2nd 已经过时。

大伙流行用这个：

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
35
#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::bind;

int add(int x, int y) {
    cout << "int add(int, int)" << endl;
    return x+y;
}

int func(int x, int y, int z) {
    cout << "int func(int, int, int)" << endl;
    return x+y+z;
}

void test() {
    auto f1 = bind(&add, 10, 20);
    cout << "f1()" << f1() <<endl;

    auto f2 = bind(&func, 1, 2, 3);
    cout << "f2()" << f2() <<endl;
}

int main() {
    test();
    return 0;
}
/*
f1()int add(int, int)
30
f2()int func(int, int, int)
6
*/

以下写法效果相同：

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
35
#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::bind;

int add(int x, int y) {
    cout << "int add(int, int)" << endl;
    return x+y;
}

int func(int x, int y, int z) {
    cout << "int func(int, int, int)" << endl;
    return x+y+z;
}

void test() {
    auto f1 = bind(add, 10, 20); // 函数名是函数的入口地址
    cout << "f1()" << f1() <<endl;

    auto f2 = bind(func, 1, 2, 3);
    cout << "f2()" << f2() <<endl;
}

int main() {
    test();
    return 0;
}
/*
f1()int add(int, int)
30
f2()int func(int, int, int)
6
*/

看点骚操作：

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
#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::bind;

class Example {
public:
    int add(int x, int y) {
        cout << "嘿嘿，成员函数" << endl;
        return x+y;
    }
};

void test() {
    Example ex;
    auto f1 = bind(&Example::add, &ex, 1, 3);
    cout << "f1() = " << f1() << endl;
}

int main() {
    test();
    return 0;
}
/*
f1() = 嘿嘿，成员函数
4
*/

【杂项】关于函数指针的杂项知识点：
回调函数可以分为注册和执行（思想：延迟）。

继续看看 bind 的其他细节。

占位符本身代表的是函数的形参，占位符中的数字代表的是函数的实参：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::bind;

int add(int x, int y) {
    return x+y;
}

void func(int x1, int x2, int x3, const int& x4, int x5)
{
    cout << "x1 = " << x1 << endl
         << "x2 = " << x2 << endl
         << "x3 = " << x3 << endl
         << "x4 = " << x4 << endl
         << "x5 = " << x5 << endl;
    return ;
}

void test() {
    auto f1 = bind(add, 10, std::placeholders::_1);
    cout << "f1() = " << f1(5) << endl;

    auto f2 = bind(add, std::placeholders::_1, std::placeholders::_2);
    cout << "f2() = " << f2(1, 1) << endl;
/*
f1() = 15
f2() = 2
*/
}

void test2() {
    using namespace std::placeholders;
    int num = 50;
    auto f = bind(func, 1, _3, _1, num, num);
    f(11, 33, 22, 66, 55, 77, 88);
/*
x1 = 1
x2 = 22
x3 = 11
x4 = 50
x5 = 50
*/
}

int main() {
    test2();
    return 0;
}

bind 默认情况下采用值传递：

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
35
36
#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::bind;

void func(int x1, int x2, int x3, const int& x4, int x5)
{
    cout << "x1 = " << x1 << endl
         << "x2 = " << x2 << endl
         << "x3 = " << x3 << endl
         << "x4 = " << x4 << endl
         << "x5 = " << x5 << endl;
    return ;
}

void test() {
    using namespace std::placeholders;
    int num = 50;
    auto f = bind(func, 1, _3, _1, std::cref(num), num);
    num = 100;
    f(11, 33, 22, 66, 55, 77, 88);
}

int main() {
    test();
    return 0;
}
/*
x1 = 1
x2 = 22
x3 = 11
x4 = 100
x5 = 50
*/

关于 auto 到底推导了什么类型：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <functional>

using std::cout;
using std::endl;
using std::bind;
using std::function;

class Example {
public:
    int add(int x, int y) {
        cout << "嘿嘿，成员函数" << endl;
        return x+y;
    }
};

int add(int x, int y) {
    return x+y;
}

int func(int x, int y, int z) {
    // cout << "int func(int, int, int)" << endl;
    return x+y+z;
}

void test() {
    function<int()> f1 = bind(add, 10, 20);
    cout << "f1() = " << f1() << endl;

    function<int()> f2 = bind(func, 1, 2, 3);
    cout << "f2() = " << f2() << endl;

    Example ex;
    function<int()> f3 = bind(&Example::add, &ex, 1, 3);
    cout << "f3() = " << f3() << endl;

    function<int(int)> f4 = bind(add, 10, std::placeholders::_1);
    cout <<"f4(30) = " << f4(30) <<endl;
}

int main() {
    test();
    return 0;
}
/*
f1() = 30
f2() = 6
f3() = 嘿嘿，成员函数
4
f4(30) = 40
*/

在上面的代码中，function 被称为函数的容器。

面向过程地实现多态（std::bind + std::function）：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <functional>
#include <math.h>

using std::cout;
using std::endl;
using std::bind;
using std::function;

class Figure {
    // 回调函数的设计思想
public:
    using DisplayCallBack = function<void()>;
    using AreaCallBack = function<double()>;

    DisplayCallBack _displayCallBack;
    AreaCallBack _areaCallBack;

    // 回调函数的注册
    void setDisplayCallBack(DisplayCallBack&& cb)
    {
        _displayCallBack = std::move(cb);
    }
    
    void setAreaCallBack(AreaCallBack&& cb)
    {
        _areaCallBack = std::move(cb);
    }

    // 回调函数的执行
    void handleDisplayCallBack() const 
    {
        if(_displayCallBack)
        {
            _displayCallBack();
        }
    }

    double handleAreaCallBack() const
    {
        if(_areaCallBack) {
            return _areaCallBack();
        }
        else {
            return 0.0;
        }
    }
};

class Rectangle {
public:
    Rectangle(double length = 0, double width = 0)
    :_length(length), _width(width) {
        cout << "Rectangle(double, double)" << endl;
    }

    void display() const {
        cout << "Rectangle";
    }

    double area() const {
        return _length*_width;
    }

    ~Rectangle() {
        cout <<"~Rectangle()" <<endl;
    }

private:
    double _length;
    double _width;
};

class Circle {
public:
    Circle(double radius = 0):_radius(radius) {
        cout << "Circle(double = 0)" <<endl;
    }

    void display() const {
        cout << "Circle";
    }

    double area() const {
        return 3.14 * _radius * _radius;
    }

    ~Circle() {
        cout <<"~Circle()" <<endl;
    }
private:
    double _radius;
};

class Triangle {
public:
    Triangle(double a = 0, double b= 0, double c = 0)
    : _a(a), _b(b), _c(c) {
        cout << "Triangle(double = 0, double = 0, double = 0)" <<endl;
    }

    void display() const {
        cout << "Triangle";
    }

    double area() const {
        double tmp = (_a + _b + _c)/2;
        return sqrt(tmp*(tmp-_a)*(tmp-_b)*(tmp-_c));
    }

    ~Triangle() {
        cout << "~Triangle()" << endl;
    }

private:
    double _a;
    double _b;
    double _c;
};

void func(const Figure& fig) {
    fig.handleDisplayCallBack();
    cout << "的面积：" << fig.handleAreaCallBack() <<endl;
}

int main() {
    Rectangle rectangle(10, 20);
    Circle circle(10);
    Triangle triangle(3, 4, 5);

    // Figure 是具体的类
    Figure fig;
    fig.setDisplayCallBack(bind(&Rectangle::display, &rectangle));
    fig.setAreaCallBack(bind(&Rectangle::area, &rectangle));
    func(fig);

    fig.setDisplayCallBack(bind(&Circle::display, &circle));
    fig.setAreaCallBack(bind(&Circle::area, &circle));
    func(fig);
    
    fig.setDisplayCallBack(bind(&Triangle::display, &triangle));
    fig.setAreaCallBack(bind(&Triangle::area, &triangle));
    func(fig);

    return 0;
}
/*
Rectangle(double, double)
Circle(double = 0)
Triangle(double = 0, double = 0, double = 0)
Rectangle的面积：200
Circle的面积：314
Triangle的面积：6
~Triangle()
~Circle()
~Rectangle()
*/

上面的代码结合函数指针的思路去理解，就会方便很多。

成员函数适配器

成员函数适配器 mem_fun_ref 的用法示例：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//成员函数适配器mem_fun_ref的用法示例
#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>

using namespace std;

class NumVals
{
private:
    int val;
public:
    NumVals()
    {
        val = 0;
    }
    NumVals(int j)
    {
        val = j;
    }
    
    bool display()
    {
        cout << val << " ";
        return true;
    }
    bool isEven()
    {
        return (bool) !(val % 2);
    }
    bool isPrime()
    {
        for (int i = 2; i <= (val / 2); i++)
        {
            if (!(val % i)) return false;
        }
        return true;
    }
};

int main()
{
    //1. 
    vector<NumVals> v1(13);
    vector<NumVals>::iterator it1;
    for (int i = 0; i < 13; i++)
    {
        v1[i] = NumVals(i + 1);
    }

    cout << "v1中的原始值为: " << endl;
    for_each(v1.begin(), v1.end(), mem_fun_ref(&NumVals::display));
    cout << endl;
    
    // Use of mem_fun_ref calling member function through a reference
    // remove the primes in the vector using isPrime ( )
    it1 = remove_if(v1.begin(), v1.end(), mem_fun_ref(&NumVals::isPrime));
    cout << "v1中删除质数后剩下的值为: " << endl;
    for_each(v1.begin(), it1, mem_fun_ref(&NumVals::display));
    cout << endl;
    cout << endl;
    
    //2.
    vector<NumVals>v2(13);
    vector<NumVals>::iterator it2;
    for (int k = 0; k < 13; k++)
    {
        v2 [k] = NumVals (k + 1);
    }

    cout << "v2中的原始值为: " << endl;
    for_each(v2.begin(), v2.end(), mem_fun_ref(&NumVals::display));
    cout << endl;
    
    // Use of mem_fun_ref calling member function through a reference
    // remove the even numbers in the vector v2 using isEven ( )
    it2 = remove_if(v2.begin(), v2.end(), mem_fun_ref(&NumVals::isEven));
    cout << "v2中删除偶数后剩下的值为: " << endl;
    for_each(v2.begin(), it2, mem_fun_ref(&NumVals::display));
    cout << endl;
    
    getchar();
    return 0;
}
/*
v1中的原始值为: 
1 2 3 4 5 6 7 8 9 10 11 12 13 
v1中删除质数后剩下的值为: 
4 6 8 9 10 12 

v2中的原始值为: 
1 2 3 4 5 6 7 8 9 10 11 12 13 
v2中删除偶数后剩下的值为: 
1 3 5 7 9 11 13 

*/

上面代码使用 mem_fn 可以达到同样效果：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>

using namespace std;

class NumVals
{
private:
    int val;
public:
    NumVals()
    {
        val = 0;
    }
    NumVals(int j)
    {
        val = j;
    }
    
    bool display()
    {
        cout << val << " ";
        return true;
    }
    bool isEven()
    {
        return (bool) !(val % 2);
    }
    bool isPrime()
    {
        for (int i = 2; i <= (val / 2); i++)
        {
            if (!(val % i)) return false;
        }
        return true;
    }
};

int main()
{
    //1. 
    vector<NumVals> v1(13);
    vector<NumVals>::iterator it1;
    for (int i = 0; i < 13; i++)
    {
        v1[i] = NumVals(i + 1);
    }

    cout << "v1中的原始值为: " << endl;
    for_each(v1.begin(), v1.end(), mem_fn(&NumVals::display));
    cout << endl;
    
    it1 = remove_if(v1.begin(), v1.end(), mem_fn(&NumVals::isPrime));
    cout << "v1中删除质数后剩下的值为: " << endl;
    for_each(v1.begin(), it1, mem_fn(&NumVals::display));
    cout << endl;
    cout << endl;
    
    //2.
    vector<NumVals>v2(13);
    vector<NumVals>::iterator it2;
    for (int k = 0; k < 13; k++)
    {
        v2 [k] = NumVals (k + 1);
    }

    cout << "v2中的原始值为: " << endl;
    for_each(v2.begin(), v2.end(), mem_fn(&NumVals::display));
    cout << endl;
    
    it2 = remove_if(v2.begin(), v2.end(), mem_fn(&NumVals::isEven));
    cout << "v2中删除偶数后剩下的值为: " << endl;
    for_each(v2.begin(), it2, mem_fn(&NumVals::display));
    cout << endl;
    
    getchar();
    return 0;
}
/*
v1中的原始值为: 
1 2 3 4 5 6 7 8 9 10 11 12 13 
v1中删除质数后剩下的值为: 
4 6 8 9 10 12 

v2中的原始值为: 
1 2 3 4 5 6 7 8 9 10 11 12 13 
v2中删除偶数后剩下的值为: 
1 3 5 7 9 11 13 

*/

mem_fn 的另一个示例：

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
//mem_fn

#include <functional>
#include <iostream>
 
struct Foo {
    void display_greeting() {
        std::cout << "Hello, world.\n";
    }
    void display_number(int i) {
        std::cout << "number: " << i << '\n';
    }
    int data = 7;
};
 
int main() {
    Foo f;
 
    auto greet = std::mem_fn(&Foo::display_greeting);
    greet(f);
 
    auto print_num = std::mem_fn(&Foo::display_number);
    print_num(f, 42);
 
    auto access_data = std::mem_fn(&Foo::data);
    std::cout << "data: " << access_data(f) << '\n';
}
/*
Hello, world.
number: 42
data: 7
*/

再来看一种刁钻的写法，这样同样是合法的：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <vector>
#include <functional>
#include <algorithm>
#include <iostream>

using namespace std;

class NumVals
{
private:
    int val;
public:
    NumVals()
    {
        val = 0;
    }
    NumVals(int j)
    {
        val = j;
    }
    
    bool display()
    {
        cout << val << " ";
        return true;
    }
    bool isEven()
    {
        return (bool) !(val % 2);
    }
    bool isPrime()
    {
        for (int i = 2; i <= (val / 2); i++)
        {
            if (!(val % i)) return false;
        }
        return true;
    }
};

int main()
{
    //1. 
    vector<NumVals> v1(13);
    vector<NumVals>::iterator it1;
    for (int i = 0; i < 13; i++)
    {
        v1[i] = NumVals(i + 1);
    }

    cout << "v1中的原始值为: " << endl;
    for_each(v1.begin(), v1.end(),
             std::bind(&NumVals::display, std::placeholders::_1));
    cout << endl;
    
    return 0;
}
/*
v1中的原始值为: 
1 2 3 4 5 6 7 8 9 10 11 12 13
*/

上面的代码需要解释：
NumVals::display 是个无参函数，但隐式地有一个 this 参数，因此用 std::placeholders::_1 占位。这个参数在运行时接受 v1.begin() 至 v1.end() 传过来的迭代器（指针）。
std::bind(&NumVals::display, std::placeholders::_1) 则返回一个类似于函数指针的东西，符合 for_each 的要求。

函数对象

函数对象（仿函数）：所有可与小括号结合，并且体现函数的形式。（将函数对象的概念进行扩充）

  • 重载了函数调用运算符的类创建的对象
  • 普通函数或者成员函数
  • 函数指针

空间配置器

空间配置器负责空间的申请与回收。

空间配置器将空间的申请与对象的构建分开，将空间的释放与对象的销毁也分开。

STL中，元素都是批量的，所以出于效率考虑，需要将空间的申请与对象的构建分开。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <memory>//头文件

//类模板
template< class T >
struct allocator;

//空间的申请
pointer allocate( size_type n, const void * hint = 0 );
T* allocate( std::size_t n, const void * hint);

//空间的释放
void deallocate( T* p, std::size_t n );

//对象的构建
void construct( pointer p, const_reference val );

//对象的销毁
void destroy( pointer p );

实现自己的 vector

整体逻辑不算难，但是很多细节弄不出来，很麻烦。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <iostream>
#include <memory>
#include <algorithm>

using std::cout;
using std::endl;

template<typename T>
class Vector
{
public:
    using iterator = T*;
    Vector()
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr) {}

    iterator begin() const {
        return _start;
    }

    iterator begin() {
        return _start;
    }

    iterator end() const {
        return _finish;
    }

    iterator end() {
        return _finish;
    }

    ~Vector();
    void push_back(const T& value); 
    void pop_back();    
    int size() const;
    int capacity() const;

private:
    void reallocate(); //重新分配内存,动态扩容要用的

    static std::allocator<T> _alloc;
     
    T *_start;                 //指向数组中的第一个元素
    T *_finish;                //指向最后一个实际元素之后的那个元素
    T *_end_of_storage;        //指向数组本身之后的位置
};

template <typename T>
std::allocator<T> Vector<T>::_alloc; // 静态数据成员进行初始化

template <typename T>
Vector<T>::~Vector()
{
    if(_start) {
        while(_finish != _start) {
            // 销毁空间上的元素
            _alloc.destroy(--_finish);
        }
        // 回收空间
        _alloc.deallocate(_start, capacity());
    }
}

template <typename T>
void Vector<T>::push_back(const T& value)
{
    if(size() == capacity())
    {
        reallocate();
    }
    _alloc.construct(_finish++, value);
}

template <typename T>
void Vector<T>::pop_back()
{
    if(size() <= 0) return;
    _alloc.destroy(--_finish);
}

template <typename T>
int Vector<T>::size() const
{
    return _finish - _start;
}

template <typename T>
int Vector<T>::capacity() const
{
    return _end_of_storage - _start;
}

template <typename T>
void Vector<T>::reallocate()
{
    int oldCapacity = capacity();
    int newCapacity = 2*oldCapacity > 0 ? 2*oldCapacity : 1;
    T* tmp = _alloc.allocate(newCapacity);

    if(_start) {
        // 拷贝老空间上的元素到新空间
        std::uninitialized_copy(_start, _finish, tmp);
        while(_finish != _start) {
            // 销毁老空间上的元素
            _alloc.destroy(--_finish);
        }
        // 回收老的空间
        _alloc.deallocate(_start, capacity());
    }
    _start = tmp;
    _finish = _start + oldCapacity;
    _end_of_storage = _start + newCapacity;
}

template <typename Container>
void printinfo(const Container& con)
{
    cout << "con.size() = " << con.size() << endl
         << "con.capacity() = " << con.capacity() << endl;
}

void test() {
    Vector<int> num;
    num.push_back(1);
    printinfo(num);

    num.push_back(2);
    printinfo(num);

    num.push_back(3);
    printinfo(num);

    num.push_back(4);
    printinfo(num);

    num.push_back(5);
    printinfo(num);

    num.push_back(6);
    printinfo(num);

    num.push_back(7);
    printinfo(num);

    num.push_back(8);
    printinfo(num);

    num.push_back(9);
    printinfo(num);

    for(auto& elem : num) {
        cout << elem << " ";
    }
    cout << endl;
}

int main() {
    test();
    return 0;
}
/*
con.size() = 1
con.capacity() = 1
con.size() = 2
con.capacity() = 2
con.size() = 3
con.capacity() = 4
con.size() = 4
con.capacity() = 4
con.size() = 5
con.capacity() = 8
con.size() = 6
con.capacity() = 8
con.size() = 7
con.capacity() = 8
con.size() = 8
con.capacity() = 8
con.size() = 9
con.capacity() = 16
1 2 3 4 5 6 7 8 9 
*/

源码阅读

74-4.png

以下代码块展开约 500+ 行。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
typedef alloc _Alloc;

//第一个分支（一级空间配置器）
typedef malloc_alloc alloc;
typedef __malloc_alloc_template<0> malloc_alloc;

template <int __inst>
class __malloc_alloc_template
{
public:
    static void* allocate(size_t __n)
    {
        void* __result = malloc(__n);
        if (nullptr == __result)
            __result = _S_oom_malloc(__n);//S = static, oom = out of memory

        return __result;
    }

    static void deallocate(void* __p, size_t /* __n */)
    {
        free(__p);
    }
};

//第二个分支（默认分支，二级空间配置器）
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
class __default_alloc_template
{
public:
    static void* allocate(size_t __n)
    {
        if(__n > 128)
        {
            ret = malloc(__n);//对空间，new
        }
        else
        {
            //16个自由链表_S_free_list + 内存池
            _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);

            _Obj* __RESTRICT __result = *__my_free_list;
            if (__result == 0)
                __ret = _S_refill(_S_round_up(__n));
            else
            {
                *__my_free_list = __result -> _M_free_list_link;
                __ret = __result;
            }
        }
    }

    static void deallocate(void* __p, size_t __n)
    {
        if (__n > (size_t) 128)
            malloc_alloc::deallocate(__p, __n);
        else
        {
            // 此处代码有较大改动，目的是方便理解其主要逻辑
            _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[3]
            _Obj* __q = (_Obj*)__p;

            __q -> _M_free_list_link = *__my_free_list;
            *__my_free_list = __q;
        }
    }
};


class allocator
{
    typedef alloc _Alloc;
public:
    //空间的申请
    _Tp* allocate(size_type __n, const void *ptr = nullptr)
    {
        return __n != 0 ? static_cast<_Tp*>(_Alloc::allocate(__n * sizeof(_Tp))) : nullptr;
    }
    
    //空间的回收
    void deallocate(pointer __p, size_type __n)
    {
        _Alloc::deallocate(__p, __n * sizeof(_Tp));
    }
    
    //对象的构建
    void construct(pointer __p, const _Tp& __val)
    {
        //int *pInt = new int(10);
        new(__p) _Tp(__val); //定位new表达式 allocate
    }
    
    //对象的销毁
    void destroy(pointer __p)
    {
        __p->~_Tp(); //显示调用析构函数
    }
};


//联合体
union _Obj
{
    union _Obj* _M_free_list_link;
    char _M_client_data[1]; /* The client sees this.*/
};

enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16};

typename __default_alloc_template::_Obj* __default_alloc_template::_S_free_list[
# if defined(__SUNPRO_CC) || defined(__GNUC__) || defined(__HP_aCC)
    _NFREELISTS
# else
    __default_alloc_template::_NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };


char* __default_alloc_template::_S_start_free = nullptr;//指向内存池的头
char* __default_alloc_template::_S_end_free = nullptr;//指向内存池的尾
size_t __default_alloc_template::_S_heap_size = 0;


//取自由链表的下标的函数
static size_t _S_freelist_index(size_t __bytes) //__bytes = 32
{
    return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
    //return (32 + 8 - 1)/8 - 1 = 39/8 - 1 = 4.x - 1 = 3
}

__bytes = 33
[25, 32]  32    3.x  4
[33,   ]  40
[  , 24]  24
//向上取整，得到8的整数倍
static size_t _S_round_up(size_t __bytes)
{
    return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1));
                (32 + 8 - 1) & ~ (8 - 1) = 39 & ~7
                39 = 32 + 4 + 2 + 1    0010 0111
                7 = 4 + 2 + 1          0000 0111   1111 1000
            
                0010 0111
            &   1111 1000
                0010 0000   = 2^5 = 32

                (31 + 8 - 1) & ~ (8 - 1) = 38 & ~7
                0010 0110
                1111 1000
                0010 0000 = 2^5 = 32

                (33 + 8 - 1) & ~ (8 - 1) = 40 & ~7
                40 = 32 + 8
                0010 1000
                1111 1000
                0010 1000   40

                (25 + 8 - 1) & ~ (8 - 1) = 32 & ~7
                0010 0000
            &   1111 1000
                0010 0000 = 2^5 = 32

                (24 + 8 - 1) & ~ (8 - 1) = 31 & ~7
                31 = 16 + 8 + 4 + 2 + 1
                0001 1111
            &   1111 1000
                0001 1000 = 16 + 8 = 24
}


//1、申请32字节时候,内存（堆空间）是足够的
//__size = 32
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs = 32 * 20 = 640;
    size_t __bytes_left = _S_end_free - _S_start_free = 0;

    else
    {
        size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4)
                              = 2 * 640 + _S_round_up(0 >> 4) = 1280;

        _S_start_free = (char*)malloc(__bytes_to_get) = malloc(1280);
    
        _S_heap_size += __bytes_to_get = 1280;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
    //递归调用
    char* __result;
    size_t __total_bytes = __size * __nobjs = 32 * 20 = 640;
    size_t __bytes_left = _S_end_free - _S_start_free = 1280;
    if (__bytes_left >= __total_bytes)
    {
        __result = _S_start_free;
        _S_start_free += __total_bytes;

        return(__result);//分割出来了640字节，然后将剩余的640自己交给_S_end_free与_S_start_free
    }
}

//该函数就是在按照__n为一个等分，进行将大段空间进行切割，分成多个等分
void* __default_alloc_template::_S_refill(size_t __n)//__n = 32
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    __my_free_list = _S_free_list +
                     _S_freelist_index(__n);//_S_free_list[3]

    __result = (_Obj*)__chunk;
    *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
    for (__i = 1; ; __i++)
    {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i)
        {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
    }
    return(__result);
}

void* allocate(size_t __n)//__n = 32
{
    else
    {
        _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);//_S_free_list[3]

        _Obj*  __result = *__my_free_list;
        
        if (__result == nullptr)
            __ret = _S_refill(_S_round_up(__n));//32 * 20 * 2 = 1280  640/32 = 20
        else {
            *__my_free_list = __result -> _M_free_list_link;
            __ret = __result;
        }
    }
}


//2、申请64字节时候,内存（堆空间）是足够的
//__size = 64
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs = 64 * 20 = 1280;
    size_t __bytes_left = _S_end_free - _S_start_free = 640;

    else if (__bytes_left >= __size)
    {
        __nobjs = (int)(__bytes_left/__size) = 640/64 = 10;
        __total_bytes = __size * __nobjs = 64 * 10 = 640;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }
}

void* __default_alloc_template::_S_refill(size_t __n)//__n = 64
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    __my_free_list = _S_free_list +
                     _S_freelist_index(__n);//_S_free_list[7]

    /* Build free list in chunk */
    __result = (_Obj*)__chunk;
    *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
    for (__i = 1; ; __i++) {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
    }
}

static void* allocate(size_t __n)//__n = 64
{
    void* __ret = 0;
    else
    {
        _Obj** __my_free_list = _S_free_list +
                                _S_freelist_index(__n);//_S_free_list[7]

        _Obj* __result = *__my_free_list;
        if (__result == nullptr)
            __ret = _S_refill(_S_round_up(__n));
        else
        {
            *__my_free_list = __result -> _M_free_list_link;
            __ret = __result;
        }
    }
}

//3、申请96字节时候,内存（堆空间）是足够的
//__size = 96
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs = 96 * 20 = 1920;
    size_t __bytes_left = _S_end_free - _S_start_free = 0;

    else
    {
        size_t __bytes_to_get = 2 * __total_bytes + 
                                _S_round_up(_S_heap_size >> 4)
                              = 2 * 1920 + _S_round_up( 1280 >> 4)
                              = 3840 + 80 = 3920;
                              
        _S_start_free = (char*)malloc(__bytes_to_get) = malloc(3920);

        _S_heap_size += __bytes_to_get = 1280 + 3920 = 5200;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));
    }
    //递归调用
    char* __result;
    size_t __total_bytes = __size * __nobjs = 96 * 20 = 1920;
    size_t __bytes_left = _S_end_free - _S_start_free = 3920;

    if (__bytes_left >= __total_bytes)
    {
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);//3920 = 1920 + 2000
    }
}


void* __default_alloc_template::_S_refill(size_t __n)//__n = 96
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;


    __my_free_list = _S_free_list +
                     _S_freelist_index(__n);//_S_free_list[11]

    /* Build free list in chunk */
    __result = (_Obj*)__chunk;
    *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
    for (__i = 1; ; __i++)
    {
        __current_obj = __next_obj;
        __next_obj = (_Obj*)((char*)__next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj -> _M_free_list_link = 0;
            break;
        } else {
            __current_obj -> _M_free_list_link = __next_obj;
        }
    }
}

static void* allocate(size_t __n)//__n = 96
{
    void* __ret = 0;
    else
    {
        _Obj** __my_free_list = _S_free_list +
                                _S_freelist_index(__n);//_S_free_list[11]

        _Obj* __result = *__my_free_list;
        if (__result == nullptr)
            __ret = _S_refill(_S_round_up(__n));
        else
        {
            *__my_free_list = __result -> _M_free_list_link;
            __ret = __result;
        }
    }
}


//4、申请72字节时候，内存池与堆空间没有连续的72字节(堆空间与内存池容量不足)
//表名内存池中没有连续的72字节，表明上一次96字节分割完毕之后，内存池中2000字节被使用完毕了
//__size = 72
//__nobjs = 20
char* __default_alloc_template::_S_chunk_alloc(size_t __size, int& __nobjs)
{
    char* __result;
    size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;
    size_t __bytes_left = _S_end_free - _S_start_free = 0;

    else
    {
        size_t __bytes_to_get = 2 * __total_bytes +
                                _S_round_up(_S_heap_size >> 4)
                              = 2 * 1440 + _S_round_up(5200 >> 4)
                              = 2880 + 325 = 3205;
        _S_start_free = (char*)malloc(__bytes_to_get) = malloc(3205);
        if(nullptr == _S_start_free)
        {
            size_t __i;
            _Obj** __my_free_list;
            _Obj* __p;

            //__size = 72
            //__i = 72  80  88  96,想找连续72字节的时候，没有满足条件的，那么就只能向上“借”
            for (__i = __size; __i <= (size_t) 128; __i += (size_t)8)
            {
                //_S_free_list[8] _S_free_list[9] _S_free_list[10] _S_free_list[11]
                __my_free_list = _S_free_list + _S_freelist_index(__i);
                __p = *__my_free_list;

            if (nullptr != __p)
            {
                *__my_free_list = __p -> _M_free_list_link;
                _S_start_free = (char*)__p;
                _S_end_free = _S_start_free + __i;
                return(_S_chunk_alloc(__size, __nobjs));
            }
        }
    }
    //递归调用
    char* __result;
    size_t __total_bytes = __size * __nobjs = 72 * 20 = 1440;
    size_t __bytes_left = _S_end_free - _S_start_free = 96;

    else if (__bytes_left >= __size)
    {
        __nobjs = (int)(__bytes_left/__size) = 96/72 = 1;
        __total_bytes = __size * __nobjs = 72 * 1 = 72;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    }
}


//__n = 72
void* __default_alloc_template::_S_refill(size_t __n)
{
    int __nobjs = 20;
    char* __chunk = _S_chunk_alloc(__n, __nobjs);
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __result;
    _Obj* __current_obj;
    _Obj* __next_obj;
    int __i;

    if (1 == __nobjs) return(__chunk);
}

//__n = 72
static void* allocate(size_t __n)
{
    void* __ret = 0;

    else
    {
        _Obj** __my_free_list = _S_free_list +
                                _S_freelist_index(__n);//_S_free_list[8]

        _Obj* __RESTRICT __result = *__my_free_list;
        if (__result == 0)
            __ret = _S_refill(_S_round_up(__n));

        else
        {
            *__my_free_list = __result -> _M_free_list_link;
            __ret = __result;
        }
    }
}


总结：
1、STL中，所有容器申请的空间在内存的那个位置？
A:都在堆上

2、空间配置器中，代码流程是怎么样的？
第一分支：一级空间配置器，底层调用的是malloc申请空间
第二分支：二级空间配置器，当申请的长度大于128字节时候，底层走的还是malloc申请堆空间；但
是当申请的长度小于128字节时候，会使用自由链表（数组的长度为16，_S_free_list） + 内存
池（使用_S_start_free与_S_end_free指向内存池的首尾）的思想。

3、函数调用过程是怎么样的？
allocate：进行申请空间，该函数会调用_S_refill
_S_refill：会将申请的空间进行切割，分成多个等分，然后进行挂接，该函数会调用_S_chunk_alloc
_S_chunk_alloc：是真正的申请空间的函数，该函数底层调用的是malloc，申请大片空间。该函数还有可能会进行递归调用。
_S_round_up：向上取整，得到8的整数倍
_S_freelist_index：获取自由链表的下标

可以多多回顾 D27-4、D27-5、D28-1

作业 - LRU 算法

题目链接： leetcode 146. LRU Cache

我的做法：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    typedef std::list<std::pair<int,int>>::iterator  listptr;
    typedef std::unordered_map<int,std::pair<int,listptr>>::iterator  mapptr;
    LRUCache(int capacity) {
        Capacity = capacity;
    }
    
    int get(int key) {
        mapptr it = mmap.find(key);
        if(it == mmap.end()) {
            return -1;
        }
        else {
            /*get 到的值需要更新优先级为最新*/
            put(key, mmap[key].first);
            return it->second.first;
        }
    }
    
    void put(int key, int value) {
        mlist.insert(mlist.end(), {key, value});

        mapptr it = mmap.find(key);
        if(it != mmap.end()) // 新元素之前就有
        {
            /*在 list 中移除旧元素*/
            mlist.erase(it->second.second);
        }

        if(mlist.size() > Capacity)
        {
            mmap.erase(mlist.begin()->first);
            // 在 list 中移除队头
            mlist.erase(mlist.begin());
        }

        mmap[key] = std::make_pair(value, std::prev(mlist.end()));
    }

private:
    std::unordered_map<int,std::pair<int,listptr>> mmap;
    std::list<std::pair<int,int>> mlist;
    int Capacity;
};

/*
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
*/

int main() {
    LRUCache* obj = new LRUCache(2);
    obj->put(1, 1);
    obj->put(2, 2);
    std::cout << obj->get(1) << std::endl; // 返回 1
    obj->put(3, 3); // 该操作会使得键 2 作废
    std::cout << obj->get(2) << std::endl; // 返回 -1（未找到）
    obj->put(4, 4); // 该操作会使得键 1 作废
    std::cout << obj->get(1) << std::endl; // 返回 -1（未找到）
    std::cout << obj->get(3) << std::endl; // 返回 3
    std::cout << obj->get(4) << std::endl; // 返回 4
    delete obj;
    return 0;
}
/*
1
-1
-1
3
4
*/

大体思路还算 ok ，但是不少语法上的细节是在 GPT 帮助下完成的，例如：

  • it->second.second
  • std::prev()

面向对象设计

手打目录：

0 ⾯向对象设计 1
1 为什么要⾯向对象设计 3
2 UML语言 6
3 类与类之间的关系 9
3.1 继承(泛化) 10
3.2 关联 12
3.3 聚合 14
3.4 组合 16
3.5 依赖 18
3.6 比较和总结 19
4 面向对象设计原则 20
4.1 单一职责原则 22
4.2 开放闭合原则 25
4.3 里氏替换原则 27
4.4 接口分离原则 30
4.5 依赖倒置原则 33
4.6 迪米特法则 35
4.7 组合复⽤原则 39

文本查询代码再再探

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//wordQueryTest.cpp
get_file函数会传两个参数，作用是打开文件，返回一个TextQuery的对象
get_file返回的TextQuery类型的对象，所以会调用TextQuery的构造，该函数执行了相应的读操
作，将文件里面每一行放在file对应的shared_ptr<vector<string>>存起来；然后将每个单词与
行号存在wm对应的map<string, shared_ptr<set<size_t>>>存起来。

//sought是待查询的单词，可以使用"hello"进行替代，然后构建Query对象，调用Query的构造函数，将基类指针q指向派生类对象WordQuery，
Query name(sought);
Query::Query(const std::string &s)
: q(new WordQuery(s))
{
}

//使用Query的eval方法，在该方法中能体现多态，调用的就是派生类WordQuery的eval方法
const QueryResult results = name.eval(file);
QueryResult Query::eval(const TextQuery &t) const
{
    return q->eval(t);//体现多态
//动态多态被激活的五个条件就全部都满足
//eval在基类Query_base中是虚函数
//在派生类WordQuery也是虚函数并且实现
//基类的指针q指向了派生类对象new WordQuery
//q调用了eval
}

//调用WordQuery的eval方法，在该方法中执行TextQuery的query函数
QueryResult WordQuery::eval(const TextQuery &t) const
{
    return t.query(query_word);
}
//该函数讲带查询的单词sought，也就是"hello",单词的行号nodata/loc->second,单词对应的
// 一行内容file传递给QueryResult的构造函数
QueryResult TextQuery::query(const string &sought) const
{
    static lineType nodata(new set<line_no>);
    wmIter loc = wm.find(cleanup_str(sought));

    if (loc == wm.end())
        return QueryResult(sought, nodata, file); //待查询单词不存在
    else
        return QueryResult(sought, loc->second, file);//待查询单词存在
}

//这三个值就会分别交给sought，lines，file
QueryResult(std::string s,
            std::shared_ptr<std::set<line_no> > p,
            std::shared_ptr<std::vector<std::string> > f)
: sought(s)
, lines(p)
, file(f)
{
}

//最后执行print函数进行打印（实质上就是输出流运算符的重载）
print(cout, results) << endl;

//该函数就将待查询单词，单词的次数，单词行号，单词对应的一行内容打出来
ostream &print(ostream & os, const QueryResult &qr)
//std::ostream &operator<<(std::ostream & os, const QueryResult &qr)
{
    os << qr.sought << " occurs " << qr.lines->size() << " "
       << make_plural(qr.lines->size(), "time", "s") << endl;
    for (lineIter num = qr.lines->begin();num != qr.lines->end(); ++num)
    {
        os << "\t(line " << *num + 1 << ") " << *(qr.file->begin() + *num)
           << endl;
    }
    return os;
}

//注意：一定要熟悉多态，掌握多态的五个条件
//抽象类，纯虚函数
//私有的数据成员或者成员函数不能在类外面进行访问，如果必须在类外进行使用，需要友元的支撑。
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
ifstream ifs(argv[1]);
if(!ifs)
{
    cerr << "jksdjs" << endl;
    return;
}

ifstream infile;
if (argc == 2)
    infile.open(argv[1]);
    
shared_ptr<Query_base> q(new WordQuery(s));
Query_base *q = new WordQuery(s);
Computer *pc = new Computer("xiaomi", 8888);
Base *pbase = new Derived(12,34);

///////////////////////////////////////////

shared_ptr<Query_base> q;

Query::Query(const std::string &s)
: q(new WordQuery(s))
{
}

QueryResult eval(const TextQuery &t) const
{
    return q->eval(t); //eval在基类Query_base中是纯虚函数
}
//动态多态被激活的五个条件就全部都满足
//eval在基类Query_base中是虚函数
//在派生类WordQuery也是虚函数并且实现
//基类的指针q指向了派生类对象new WordQuery
//q调用了eval
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//andQueryTest.cpp
sought1 = "hello",sought2 = "world"

inline Query operator&(const Query &lhs, const Query &rhs)
{
    //Query(shared_ptr<Query_base> )
    return std::shared_ptr<Query_base>(new AndQuery(lhs, rhs));
    //shared_ptr<Query_base> t(new AndQuery(lhs, rhs));
    // return t; Query(t)
}

Query func()
{
    Query t;
    return t;
    shared_ptr<Query_base>---->Query(xxx)
}

Query(shared_ptr<Query_base> )
1
2
3
4
5
// NotQuery 的逻辑
hello
1 2 3 4 5 6 7 8 9 10
单词有的时候：1 3 6 9 10 "hello"
没有出现单词：2 4 5 7 8 ~"hello"

上面的代码，包括之前的一些代码阅读，都是草稿性质的，并不能实际执行。

使用 StarUML 画出的类图（这个软件出的图有点不尽人意）：

74-5.png

设计模式

简单工厂

我们先来看一下之前写的代码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <string>
#include <math.h>
#define PI acos(-1)

using std::cout;
using std::endl;
using std::string;

class Figure {
public:
    Figure() = default;
    virtual ~Figure() {}

    virtual double getArea() = 0;
    virtual string getName() = 0;
    virtual void show()=0;

protected:
    string _name;
};

class Circle: public Figure {
public:
    Circle(): _radius(0) {
        _name = "Circle";
    }
    Circle(double r): _radius(r) {
        _name = "Circle";
    }

    double getArea() override {
        return PI*_radius*_radius;
    }

    string getName() override {
        return _name;
    }

    double getPerimeter() const {
        return 2*PI*_radius;
    }

    void show() override {
        cout << "name = " << _name << endl
             << "radius = " << _radius << endl
             << "perimeter = " << getPerimeter() << endl
             << "area = " << getArea() << endl << endl;
    }

protected:
    double _radius;
};

class Cylinder: public Circle {
public:
    Cylinder(double r, double h)
            :Circle(r), _height(h) {_name = "Cylinder";}

    double getArea() override {
        double sum1 = Circle::getArea();
        double sum2 = Circle::getPerimeter() * _height;
        return sum1*2 + sum2;
    }

    string getName() const {
        return _name;
    }

    double getHeight() const {
        return _height;
    }

    double getVolume(){
        return Circle::getArea() * _height;
    }

    void show() override {
        cout << "name = " << _name << endl
             << "height = " << _height << endl
             << "area = " << getArea() << endl
             << "volume = " << getVolume() << endl << endl;
    }

protected:
    double _height;
};

void func(Figure* pfig)
{
    cout << pfig->getName() << "'s area is "
         << pfig->getArea() << endl;
}

int main() {
    Circle o1(1.0);
    o1.show();
    func(&o1);
    cout << endl;

    Circle o2(2.0);
    o2.show();
    func(&o2);
    cout << endl;
    
    Cylinder cy1(1.0, 1.0);
    cy1.show();
    func(&cy1);
    cout << endl;

    Cylinder cy2(2.0, 2.0);
    cy2.show();
    func(&cy2);
    cout << endl;

    return 0;
}
/*
name = Circle
radius = 1
perimeter = 6.28319
area = 3.14159

Circle's area is 3.14159

name = Circle
radius = 2
perimeter = 12.5664
area = 12.5664

Circle's area is 12.5664

name = Cylinder
height = 1
area = 12.5664
volume = 3.14159

Cylinder's area is 12.5664

name = Cylinder
height = 2
area = 50.2655
volume = 25.1327

Cylinder's area is 50.2655

*/

现在，我们尝试更优雅地创建对象：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <string>
#include <math.h>
#include <memory>
#define PI acos(-1)

using std::cout;
using std::endl;
using std::string;
using std::unique_ptr;

class Figure {
public:
    Figure() = default;
    virtual ~Figure() = default;

    virtual double getArea() = 0;
    virtual string getName() = 0;
    virtual void show()=0;

protected:
    string _name;
};

class Circle: public Figure {
public:
    Circle(): _radius(0) { _name = "Circle"; }
    Circle(double r): _radius(r) { _name = "Circle"; }

    double getArea() override 
    {
        return PI*_radius*_radius;
    }

    string getName() override 
    {
        return _name;
    }

    double getPerimeter() const 
    {
        return 2*PI*_radius;
    }

    void show() override 
    {
        cout << "name = " << _name << endl
             << "radius = " << _radius << endl
             << "perimeter = " << getPerimeter() << endl
             << "area = " << getArea() << endl << endl;
    }

protected:
    double _radius;
};

class Cylinder: public Circle 
{
public:
    Cylinder(double r, double h)
            :Circle(r), _height(h) { _name = "Cylinder"; }

    double getArea() override 
    {
        double sum1 = Circle::getArea();
        double sum2 = Circle::getPerimeter() * _height;
        return sum1*2 + sum2;
    }

    string getName() const 
    {
        return _name;
    }

    double getHeight() const 
    {
        return _height;
    }

    double getVolume()
    {
        return Circle::getArea() * _height;
    }

    void show() override 
    {
        cout << "name = " << _name << endl
             << "height = " << _height << endl
             << "area = " << getArea() << endl
             << "volume = " << getVolume() << endl << endl;
    }

protected:
    double _height;
};

void func(Figure* pfig)
{
    cout << pfig->getName() << "'s area is "
         << pfig->getArea() << endl;
}

class Factory {
public:
    static Figure* create(const string& name)
    {
        if(name == "Circle")
        {
            // 读配置文件
            // 解析配置文件
            // 获取数据
            return new Circle(1.0);
        }
        else if(name == "Cylinder")
        {
            // 读配置文件
            // 解析配置文件
            // 获取数据
            return new Cylinder(1.0, 1.0);
        }
        else return nullptr;
    }
};

int main() 
{
    unique_ptr<Figure> pCir(Factory::create("Circle"));
    unique_ptr<Figure> pCyl(Factory::create("Cylinder"));

    func(pCir.get());  // get() 方法得到裸指针
    func(pCyl.get());

    return 0;
}
/*
Circle's area is 3.14159
Cylinder's area is 12.5664
*/

上面的代码采用了简单工厂的思想。

简单工厂模式又叫静态工厂方法模式。提供一个工厂类，在工厂类中做判断，根据传入的类型创造相应的产品。当增加新的产品时，就需要修改工厂类。简单工厂模式提供了专门的工厂类用于创建对象，将对象的创建和对象的使用分离开。

74-6.png

应用场景：一个公司、一个工厂可以生产很多的产品（类似于富士康）。

缺点:

  1. 违背了开闭原则（扩展性比较差）
  2. 违背了单一职责原则（该类可以做很多事情）
  3. 违背了依赖倒置原则，不能更好的应对变化

优点:

  1. 直接通过配置文件就可以获取产品信息
  2. 无需知道产品的生产过程，就可以获取产品

工厂方法

在简单工厂上进行改进。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <iostream>
#include <string>
#include <math.h>
#include <memory>
#define PI acos(-1)

using std::cout;
using std::endl;
using std::string;
using std::unique_ptr;

class Figure {
public:
    Figure() = default;
    virtual ~Figure() = default;

    virtual double getArea() = 0;
    virtual string getName() = 0;
    virtual void show()=0;

protected:
    string _name;
};

class Circle: public Figure {
public:
    Circle(): _radius(0) { _name = "Circle"; }
    Circle(double r): _radius(r) { _name = "Circle"; }

    double getArea() override 
    {
        return PI*_radius*_radius;
    }

    string getName() override 
    {
        return _name;
    }

    double getPerimeter() const 
    {
        return 2*PI*_radius;
    }

    void show() override 
    {
        cout << "name = " << _name << endl
             << "radius = " << _radius << endl
             << "perimeter = " << getPerimeter() << endl
             << "area = " << getArea() << endl << endl;
    }

protected:
    double _radius;
};

class Cylinder: public Circle 
{
public:
    Cylinder(double r, double h)
            :Circle(r), _height(h) { _name = "Cylinder"; }

    double getArea() override 
    {
        double sum1 = Circle::getArea();
        double sum2 = Circle::getPerimeter() * _height;
        return sum1*2 + sum2;
    }

    string getName() const 
    {
        return _name;
    }

    double getHeight() const 
    {
        return _height;
    }

    double getVolume()
    {
        return Circle::getArea() * _height;
    }

    void show() override 
    {
        cout << "name = " << _name << endl
             << "height = " << _height << endl
             << "area = " << getArea() << endl
             << "volume = " << getVolume() << endl << endl;
    }

protected:
    double _height;
};

void func(Figure* pfig)
{
    cout << pfig->getName() << "'s area is "
         << pfig->getArea() << endl;
}

class Factory {
public:
    virtual Figure* create() = 0;
    virtual ~Factory() = default;
};

class CircleFactory: public Factory {
public:
    Figure* create() override {
        // 读配置文件
        // 解析配置文件
        // 获取数据
        return new Circle(1.0);
    }
};

class CylinderFactory: public Factory {
public:
    Figure* create() override {
        // 读配置文件
        // 解析配置文件
        // 获取数据
        return new Cylinder(1.0, 1.0);
    }
};

int main() 
{
    unique_ptr<Factory> factoryCir(new CircleFactory());
    unique_ptr<Figure> myCir(factoryCir->create());

    unique_ptr<Factory> factoryCyl(new CylinderFactory());
    unique_ptr<Figure> myCyl(factoryCyl->create());

    func(myCir.get());  // get() 方法得到裸指针
    func(myCyl.get());

    return 0;
}
/*
Circle's area is 3.14159
Cylinder's area is 12.5664
*/

74-7.png

抽象工厂

在软件开发及运行过程中，经常面临着“一系列相互依赖的对象”的创建工作；而由于需求的变化，常常存在更多系列对象的创建问题。

做法是：提供一个接口，该接口负责创建一系列“相关或者相互依赖的对象”，无需指定它们具体的类。

74-8.png

参考代码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//A类型的抽象产品
class AbstractProductA
{
public:
    virtual void show() = 0;
    ~AbstractProductA(){}
};

//B类型的抽象产品
class AbstractProductB
{
public:
    virtual void show() = 0;
    ~AbstractProductB(){}
};

class ProductA1
: public AbstractProductA
{
public:
    virtual void show() override
    {
        cout << "void ProductA1::show()" << endl;
    }
};

class ProductA2
: public AbstractProductA
{
public:
    virtual void show() override
    {
        cout << "void ProductA2::show()" << endl;
    }
};

class ProductB1
: public AbstractProductB
{
public:
    virtual void show() override
    {
        cout << "void ProductB1::show()" << endl;
    }
};

class ProductB2
: public AbstractProductB
{
public:
    virtual void show() override
    {
        cout << "void ProductB2::show()" << endl;
    }
};

class AbstractFactory
{
public:
    virtual AbstractProductA *createProductA() = 0;
    virtual AbstractProductB *createProductB() = 0;
    ~AbstractFactory() {}
};

class ConcreteFactory1
: public AbstractFactory
{
public:
    AbstractProductA *createProductA() override
    {
        return new ProductA1();
    }

    AbstractProductB *createProductB() override
    {
        return new ProductB1();
    }
};

class ConcreteFactory2
: public AbstractFactory
{
public:
    AbstractProductA *createProductA() override
    {
        return new ProductA2();
    }

    AbstractProductB *createProductB() override
    {
        return new ProductB2();
    }
};

void test()
{
    AbstractFactory *factory1 = new ConcreteFactory1();
    AbstractProductA *productA = factory1->createProductA();
    AbstractProductB *productB = factory1->createProductB();
    productA->show();
    productB->show();

    cout << endl;
    AbstractFactory *factory2 = new ConcreteFactory2();
    productA = factory2->createProductA();
    productB = factory2->createProductB();
    productA->show();
    productB->show();
}

观察者模式

《设计模式：可复用面向对象软件的基础》对观察者模式定义如下：

定义对象的一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。 当一个对象发生了变化，关注它的对象就会得到通知。这种交互也称为发布-订阅（publish - subscribe）。

74--9.png

代码示例：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <memory>

using std::cout;
using std::endl;
using std::list;
using std::find;
using std::string;
using std::unique_ptr;

class Observer;
class Subject
{
public:
    virtual void attach(Observer *pObserver) = 0;
    virtual void detach(Observer *pObserver) = 0;
    virtual void notify() = 0;
    virtual ~Subject() = default;
};

class ConcreteSubject
: public Subject
{
public:
    void attach(Observer *pObserver) override;
    void detach(Observer *pObserver) override;
    void notify() override;

    void setStatus(int status)
    {
        _status = status;
    }

    int getStatus() const
    {
        return _status;
    }

private:
    list<Observer *> _obList;
    int _status;
};

class Observer
{
public:
    virtual void update(int) = 0;
    virtual ~Observer() = default;
};

class ConcreteObserver
: public Observer
{
public:
    ConcreteObserver(const string &name)
                    : _name(name) {}
    
    void update(int value)
    {
        cout << "ConcreteObserver " << _name << ", value = " << value << endl;
    }
    
private:
    string _name;
};

class ConcreteObserver2
: public Observer
{
public:
    ConcreteObserver2(const string &name)
    : _name(name)
    {
    }

    void update(int value)
    {
        cout << "ConcreteObserver2 " << _name << ", value = " << value << endl;
    }

private:
    string _name;
};

void ConcreteSubject::attach(Observer *pObserver)
{
    _obList.push_back(pObserver);
}

void ConcreteSubject::detach(Observer *pObserver)
{
    for(auto it = _obList.begin(); it != _obList.end(); ++it)
    {
        if(*it == pObserver)
        {
            _obList.remove(pObserver);
            break;
        }
    }
}

void ConcreteSubject::notify()
{
    for(auto &ob : _obList)
    {
        ob->update(_status);
    }
}

void test()
{
    unique_ptr<ConcreteSubject> pSubject(new ConcreteSubject());
    unique_ptr<Observer> pObserver(new ConcreteObserver("lili"));
    unique_ptr<Observer> pObserver2(new ConcreteObserver2("lucy"));

    // 成为 ikun
    pSubject->attach(pObserver.get());
    pSubject->attach(pObserver2.get());

    // gege 更新状态
    pSubject->setStatus(2);

    // gege 发布动态
    pSubject->notify();

    // 虚伪的拥护
    pSubject->detach(pObserver2.get());

    pSubject->setStatus(3);
    pSubject->notify();
    
    // Observer2 遗憾离场
}

int main() {
    test();
    return 0;
}
/*
ConcreteObserver lili, value = 2
ConcreteObserver2 lucy, value = 2
ConcreteObserver lili, value = 3
*/

多线程概述

线程与进程的区别

进程是系统中程序执行和资源分配的基本单位。 每个进程有自己的数据段、代码段和堆栈段。这就造成进程在进行切换等操作时都需要有比较多的上下文切换等动作。为了进一步减少处理器的空转时间支持多处理器和减少上下文切换开销，也就出现了线程。

线程是操作系统能够进行运算调度的最小单位。 它被包含在进程之中，是进程中的实际运作单位。是进程的基本调度单元，每个进程至少都有一个 main 线程，它与同进程中的其他线程共享进程空间（堆代码、数据、文件描述符、信号等），只拥有少量的栈空间，大大减少了上下文切换的开销。

线程和进程在使用上各有优缺点：线程执行开销小，占用的 CPU 少，线程之间的切换快，但不利于资源的管理和保护；而进程正相反。

同进程一样，线程也将相关的变量值放在 线程控制表（TCB） 内。一个进程可以有多个线程，也就是有多个线程控制表及堆栈寄存器，共享一个用户地址空间。要注意的是，由于线程共享了进程的资源和地址空间，因此，任何线程对系统资源的操作都会给其他线程带来影响。

线程的分类

用户态空间（0-3G）：运行在用户态的线程称为用户级线程（用户态线程），可以使用系统调用。

内核态空间（3G-4G）：运行在内核态的线程称为内核级线程（内核态线程）。

线程的 Linux 实现

Linux 的线程是通过用户级的函数库实现的，一般采用 pthread 线程库实现线程的访问和控制。它用第三方 posix 标准的 pthread，具有良好的可移植性。编译时要在后面加上 –lpthread。

创建 退出 等待
进程 fork() exit() wait()
线程 pthread_create() pthread_exit() pthread_join()

线程的创建

1
2
3
4
5
6
7
8
9
10
11
12
13
// Compile and link with -pthread.
#include <pthread.h>

int pthread_create(pthread_t *thread,
                   const pthread_attr_t *attr,
                   void *(*start_routine) (void *),
                   void *arg);
// thread:线程id，为了与其他线程做区分。
// attr:线程的属性，线程的特性，可以使用默认属性，将其设置空即可。
// start_routine:线程入口函数，线程需要去做的任务，都写在该函数中。start_routine是一个函数指针。
// arg:代表的是线程的参数。

//函数的返回类型是一个int，如果线程创建成功，就会返回0，如果线程创建失败，会返回错误码。

传多个参数的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
// just an example...
int number;
float fx;
const char *pstr = "hello";

typedef struct
{
    int number;
    float fx;
    char *pstr;
}Data_t;

Data_t *p;

来看一个简单的例子，它展示了线程的不确定性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <pthread.h>
#include <iostream>
#include <string.h>

void* threadFunc(void* arg) {
    printf("I'm a child thread.\n");
    return nullptr;
}

int main() {
    pthread_t thid;
    int ret = pthread_create(&thid, nullptr, threadFunc, nullptr);
    if(ret) {
        printf("pthread_create: %s\n", strerror(ret));
    }
    printf("I'm a main thread.\n");
    return 0;
}
/*
输出结果是不确定的
*/

可以考虑使用 sleep 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

void* threadFunc(void* arg) {
    printf("I'm a child thread.\n");
    return nullptr;
}

int main() {
    pthread_t thid;
    int ret = pthread_create(&thid, nullptr, threadFunc, nullptr);
    if(ret) {
        printf("pthread_create: %s\n", strerror(ret));
    }
    printf("I'm a main thread.\n");
    sleep(1);
    return 0;
}
/*
I'm a main thread.
I'm a child thread.
*/

更改 sleep 函数的位置，可以得到不一样的效果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

void* threadFunc(void* arg) {
    printf("I'm a child thread.\n");
    return nullptr;
}

int main() {
    pthread_t thid;
    int ret = pthread_create(&thid, nullptr, threadFunc, nullptr);
    if(ret) {
        printf("pthread_create: %s\n", strerror(ret));
    }
    sleep(1);
    printf("I'm a main thread.\n");
    return 0;
}
/*
I'm a child thread.
I'm a main thread.
*/

用宏包装一下：

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
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void* threadFunc(void* arg) {
    printf("I'm a child thread.\n");
    return nullptr;
}

int main() {
    pthread_t thid;
    int ret = pthread_create(&thid, nullptr, threadFunc, nullptr);
    ERROR_CHECK("pthread_create", ret);

    usleep(100);
    printf("I'm a main thread.\n");
    return 0;
}
/*
pthread_create: Success
I'm a child thread.
I'm a main thread.
*/

向线程入口函数中传参数：

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
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void* threadFunc(void* arg) {
    int* pInt = (int*)arg;
    printf("I'm a child thread. %d\n", *pInt);
    return nullptr;
}

int main() {
    pthread_t thid;
    int aaa = 10;
    int ret = pthread_create(&thid, nullptr, threadFunc, (void*)&aaa);
    ERROR_CHECK("pthread_create", ret);

    usleep(100);
    printf("I'm a main thread.\n");
    return 0;
}
/*
thread_create: Success
I'm a child thread. 10
I'm a main thread.
*/

线程的退出

1
2
3
#include <pthread.h>
void pthread_exit(void *retval);
//retVal:线程退出时候的值（状态）

示例：

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
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void* threadFunc(void* arg) {
    int* pInt = (int*)arg;
    printf("I'm a child thread. %d\n", *pInt);

    pthread_exit(nullptr);
}

int main() {
    pthread_t thid;
    int aaa = 10;
    int ret = pthread_create(&thid, nullptr, threadFunc, (void*)&aaa);
    ERROR_CHECK("pthread_create", ret);

    usleep(100);
    printf("I'm a main thread.\n");
    return 0;
}
/*
pthread_create: Success
I'm a child thread. 10
I'm a main thread.
*/

main 线程是主线程，主线程执行完毕之后，不管子线程，子线程有可能还没有来得及执行。所以一般都需要让主线程等待子线程执行完毕，再退出。

线程的等待

1
2
3
int pthread_join(pthread_t thread, void **retval);
//thread：传递进来的是被等待线程的id
//retVal：将等待线程的状态值取出来

示例：

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
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void* threadFunc(void* arg) {
    printf("I'm a child thread.\n");
    pthread_exit(nullptr);
}

int main() {
    pthread_t thid;
    int ret = pthread_create(&thid, nullptr, threadFunc, nullptr);
    ERROR_CHECK("pthread_create", ret);

    ret = pthread_join(thid, nullptr);
    ERROR_CHECK("pthread_join", ret);

    printf("I'm a main thread.\n");
    return 0;
}
/*
pthread_create: Success
I'm a child thread.
pthread_join: Success
I'm a main thread.
*/

获取线程 id：

1
pthread_t pthread_self(void);

线程的执行具有随机性。因为时序不同，所以每次运行的结果都可能不同。

线程的取消

1
2
int pthread_cancel(pthread_t thread);
//thread:被取消的线程id

线程也可以被其它线程杀掉，在 Linux 中的说法是一个线程被另一个线程取消（cancel）。

线程取消的方法是一个线程向目标线程发 cancel 信号， 但是如何处理 cancel 信号则由目标线程自己决定，目标线程或者忽略、或者立即终止、或者继续运行至 cancelation-point（取消点）后终止。默认的行为是运行到取消点。

根据 POSIX 标准：一些会引起阻塞的系统调用都是取消点。不过经过测试一些非阻塞性函数也可以是取消点。可以通过 man 7 pthreads 查看，不过由于 Linux 线程库和 C 库结合的不是很好，有很多函数没有明确是否为取消点。

总之，线程的取消一方面是一个线程强行杀另外一个线程，从程序设计角度看并不是一种好的风格，另一方面目前 Linux 本身对这方面的支持并不完善，所以在实践中应该谨慎使用。

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
35
36
37
#include <pthread.h>
#include <unistd.h>
#include <iostream>
#include <string.h>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void* threadFunc(void* arg) {
    usleep(100);
    printf("I'm a child thread.\n");
    pthread_exit(nullptr);
}

int main() {
    pthread_t thid;
    int ret = pthread_create(&thid, nullptr, threadFunc, nullptr);
    ERROR_CHECK("pthread_create", ret);

    // 主线程尝试杀死子线程
    ret = pthread_cancel(thid);
    ERROR_CHECK("pthread_cancel", ret);

    ret = pthread_join(thid, nullptr);
    ERROR_CHECK("pthread_join", ret);

    printf("I'm a main thread.\n");
    return 0;
}
/*
pthread_create: Success
pthread_cancel: Success
pthread_join: Success
I'm a main thread.
*/

线程的分离

如果想让主线程不去等待或者回收子线程，那么可以将子线程设置为分离状态：

1
int pthread_detach(pthread_t thread);

面向对象的线程封装

整体思路：

74-10.png

Thread.h：

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

#include <pthread.h>

class Thread {
public:
    Thread();
    virtual ~Thread();
    void start();
    void join();

private:
    static void* threadFunc(void* arg); // 线程的入口函数
    virtual void run() = 0;      // 线程的执行任务

    pthread_t _thid;  // 线程 id
    bool _isRunning; // 线程运行的标志位
};

#endif

Thread.cc：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "Thread.h"
#include <stdio.h>

Thread::Thread()
: _thid(0)
, _isRunning(false)
{
}

Thread::~Thread()
{
    if(_isRunning)
    {
        // 让子线程与主线程分离，主线程不管子线程的回收
        pthread_detach(_thid);
        _isRunning = false;
    }
}

// 线程，启动！
void Thread::start()
{
    int ret = pthread_create(&_thid, nullptr, threadFunc, this);
    if(ret)
    {
        perror("pthread_create\n");
        return;
    }
    _isRunning = true;
}

void Thread::join()
{
    if(_isRunning)
    {
        int ret = pthread_join(_thid, nullptr);
        if(ret)
        {
            perror("pthread_join\n");
            return;
        }
        _isRunning = false;
    }
}

void* Thread::threadFunc(void* arg)
{
    Thread* pth = static_cast<Thread*>(arg);
    if(pth)
    {
        // threadFunc 是 static 的，没有 this 指针
        // 故在 pthread_create 中将 this 传进来
        pth->run(); // 体现多态
    }
    // 让子线程主动退出
    pthread_exit(nullptr);
}

testThread.cc：

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 "Thread.h"
#include <iostream>
#include <memory>
#include <unistd.h>

using std::unique_ptr;

class MyThread: public Thread
{
private:
    void run() override
    {
        // 具体逻辑根据需要书写
        while(1){
        std::cout << "My Thread is Running !" << std::endl;
        sleep(1);
        }
    }
};

int main() {
    unique_ptr<Thread> p(new MyThread());
    p->start();
    p->join();
    return 0;
}

基于对象的线程封装

思路：

74-11.jpg

Thread.h :

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
#ifndef __THREAD_H__
#define __THREAD_H__

#include <pthread.h>
#include <functional>

using std::function;

class Thread {
    using ThreadCallBack = function<void()>;
public:
    Thread(ThreadCallBack&& cb); // 移动语义是为了提高效率
    ~Thread();
    void start();
    void join();

private:
    static void* threadFunc(void* arg); // 线程的入口函数

    pthread_t _thid;     // 线程 id
    bool _isRunning;     // 线程运行的标志位
    ThreadCallBack _cb;  // 封装的任务
};

#endif

Thread.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "Thread.h"
#include <stdio.h>

Thread::Thread(ThreadCallBack&& cb)
: _thid(0)
, _isRunning(false)
, _cb(std::move(cb)) // 注册回调函数
{
}

Thread::~Thread()
{
    if(_isRunning)
    {
        // 让子线程与主线程分离，主线程不管子线程的回收
        pthread_detach(_thid);
        _isRunning = false;
    }
}

// 线程，启动！
void Thread::start()
{
    int ret = pthread_create(&_thid, nullptr, threadFunc, this);
    if(ret)
    {
        perror("pthread_create\n");
        return;
    }
    _isRunning = true;
}

void Thread::join()
{
    if(_isRunning)
    {
        int ret = pthread_join(_thid, nullptr);
        if(ret)
        {
            perror("pthread_join\n");
            return;
        }
        _isRunning = false;
    }
}

void* Thread::threadFunc(void* arg)
{
    Thread* pth = static_cast<Thread*>(arg);
    if(pth)
    {
        // threadFunc 是 static 的，没有 this 指针
        // 故在 pthread_create 中将 this 传进来
        pth->_cb();  // 执行回调函数
    }
    // 让子线程主动退出
    pthread_exit(nullptr);
}

testThread.cc :

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
#include "Thread.h"
#include <iostream>
#include <unistd.h>

class MyTask
{
public:
    void process()
    {
        // 具体逻辑根据需要书写
        while(1){
        std::cout << "My Thread is Running !" << std::endl;
        sleep(1);
        }
    }
};

int main() {
    MyTask task;
    Thread th(std::bind(&MyTask::process, &task));

    th.start();
    th.join();
    return 0;
}

互斥锁

Posix Thread 中定义了一套专门用于线程互斥的 mutex 函数。mutex 是一种简单的加锁的方法来控制对共享资源的存取，这个互斥锁只有两种状态（上锁和解锁），可以把互斥锁看作某种意义上的全局变量。

互斥锁的初始化

静态初始化与动态初始化：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <pthread.h>

//静态初始化
//pthread_mutex_t 锁的类型
//mutex锁的名字
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

//动态初始化（常用）
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *mutexattr);
//mutex：指向互斥锁的指针的名字
//mutexattr:互斥锁的属性，如果不需要设置锁的其他属性，可以设置为nullptr，用默认属性

//返回值：如果锁的初始化是正常的，就会返回0；否则会返回非0的值

互斥锁的销毁

1
2
3
4
#include <pthread.h>
int pthread_mutex_destroy(pthread_mutex_t *mutex);

//返回值：如果锁正常销毁就会返回0；否则返回错误码

加锁与解锁

注意：锁只有两种状态，要么加锁，要么解锁。

1
2
3
4
5
6
7
8
9
#include <pthread.h>
//加锁
int pthread_mutex_lock(pthread_mutex_t *mutex);

//解锁
int pthread_mutex_unlock(pthread_mutex_t *mutex);

//尝试加锁
int pthread_mutex_trylock(pthread_mutex_t *mutex);

上锁状态，资源一直被占用，不能直接回收或销毁：

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
35
36
37
#include <pthread.h>
#include <string.h>
#include <iostream>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void test()
{
    pthread_mutex_t mutex;
    int ret = pthread_mutex_init(&mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // ...

    ret = pthread_mutex_lock(&mutex);
    ERROR_CHECK("pthread_mutex_lock", ret);

    // ...

    ret = pthread_mutex_destroy(&mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

}

int main()
{
    test();
    return 0;
}
/*
pthread_mutex_init: Success
pthread_mutex_lock: Success
pthread_mutex_destory: Device or resource busy
*/

互斥锁不能多加：

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
35
36
37
38
#include <pthread.h>
#include <string.h>
#include <iostream>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void test()
{
    pthread_mutex_t mutex;
    int ret = pthread_mutex_init(&mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // ...

    ret = pthread_mutex_lock(&mutex);
    ERROR_CHECK("pthread_mutex_lock", ret);

    ret = pthread_mutex_lock(&mutex);
    ERROR_CHECK("pthread_mutex_lock", ret);

    // ...

    ret = pthread_mutex_destroy(&mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

}

int main()
{
    test();
    return 0;
}
/*
卡住
*/

正确的方法：

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
35
36
37
38
39
40
41
#include <pthread.h>
#include <string.h>
#include <iostream>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void test()
{
    pthread_mutex_t mutex;
    int ret = pthread_mutex_init(&mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // ...

    ret = pthread_mutex_lock(&mutex);
    ERROR_CHECK("pthread_mutex_lock", ret);

    ret = pthread_mutex_unlock(&mutex);
    ERROR_CHECK("pthread_mutex_unlock", ret);

    // ...

    ret = pthread_mutex_destroy(&mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

}

int main()
{
    test();
    return 0;
}
/*
pthread_mutex_init: Success
pthread_mutex_lock: Success
pthread_mutex_unlock: Success
pthread_mutex_destory: Success
*/

尝试加锁（若已加锁，则尝试上锁失败；否则成功）：

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
35
36
37
38
39
40
41
42
43
44
45
#include <pthread.h>
#include <string.h>
#include <iostream>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void test()
{
    pthread_mutex_t mutex;
    int ret = pthread_mutex_init(&mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // ...

    ret = pthread_mutex_lock(&mutex);
    ERROR_CHECK("pthread_mutex_lock", ret);

    ret = pthread_mutex_trylock(&mutex);
    ERROR_CHECK("pthread_mutex_trylock", ret);

    ret = pthread_mutex_unlock(&mutex);
    ERROR_CHECK("pthread_mutex_unlock", ret);

    // ...

    ret = pthread_mutex_destroy(&mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

}

int main()
{
    test();
    return 0;
}
/*
pthread_mutex_init: Success
pthread_mutex_lock: Success
pthread_mutex_trylock: Device or resource busy
pthread_mutex_unlock: Success
pthread_mutex_destory: Success
*/

两次 trylock ：

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
35
36
37
38
39
40
41
42
43
44
45
#include <pthread.h>
#include <string.h>
#include <iostream>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void test()
{
    pthread_mutex_t mutex;
    int ret = pthread_mutex_init(&mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // ...

    ret = pthread_mutex_trylock(&mutex);
    ERROR_CHECK("pthread_mutex_trylock", ret);

    ret = pthread_mutex_trylock(&mutex);
    ERROR_CHECK("pthread_mutex_trylock", ret);

    ret = pthread_mutex_unlock(&mutex);
    ERROR_CHECK("pthread_mutex_unlock", ret);

    // ...

    ret = pthread_mutex_destroy(&mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

}

int main()
{
    test();
    return 0;
}
/*
pthread_mutex_init: Success
pthread_mutex_trylock: Success
pthread_mutex_trylock: Device or resource busy
pthread_mutex_unlock: Success
pthread_mutex_destory: Success
*/

条件变量

条件变量是利用线程间共享的全局变量进行同步的一种机制， 主要包括两个动作：一个线程等待条件变量上的条件成立而挂起；另一个线程使条件成立（给出条件成立信号）。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。

条件变量的初始化

两种初始化的方式：静态初始化与动态初始化。

1
2
3
4
5
6
7
8
9
10
#include <pthread.h>

//静态初始化
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

//动态初始化
int pthread_cond_init(pthread_cond_t *cond, pthread_condattr_t *cond_attr);
//cond：条件变量的名字
//cond_attr:条件变量属性，默认情况可以使用nullptr传递默认值。
//返回值：初始化成功就返回0；否则就返回非0的错误码。

条件变量的销毁

1
2
3
#include <pthread.h>
int pthread_cond_destroy(pthread_cond_t *cond);
//返回值：销毁成功就返回0；否则就返回非0的错误码。

条件变量的等待

1
2
3
4
5
6
7
8
9
10
11
12
#include <pthread.h>

//无时间的等待，一直等待
//该函数会分为两个部分（至关重要）
//1、上半部：（在条件变量上）排队；解锁；睡眠；
//2、下半部：(从条件变量上)被唤醒；加锁；函数返回
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

//有时等待，超过设定的时间之后，就不会阻塞下去，而会返回
int pthread_cond_timedwait(pthread_cond_t *cond,
                           pthread_mutex_t *mutex,
                           const struct timespec *abstime);

条件变量的激发

1
2
3
4
5
6
7
8
#include <pthread.h>
// 《unix高级环境编程》
// 发送消息，让至少一个等待在条件变量上的线程唤醒。（唤醒的线程的个数是不一定的，但是至少有一个）

int pthread_cond_signal(pthread_cond_t *cond);

//发送广播消息，让所有等待在条件变量上的线程都被唤醒。
int pthread_cond_broadcast(pthread_cond_t *cond);

注意：POSIX 规范为了简化 pthread_cond_signal 的实现，允许它在实现的时候唤醒一个以上的线程。结果是，当一个线程调用 pthread_cond_signal 后，多个调用 pthread_cond_wait 或 pthread_cond_timedwait 的线程返回。 该现象被称为虚假唤醒。

使用示例

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <pthread.h>
#include <string.h>
#include <iostream>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

void test()
{
    // 互斥锁初始化
    pthread_mutex_t mutex;
    int ret = pthread_mutex_init(&mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // 条件变量初始化
    pthread_cond_t cond;
    ret = pthread_cond_init(&cond, nullptr);
    ERROR_CHECK("pthread_cond_init", ret);

    // 互斥锁加锁
    ret = pthread_mutex_lock(&mutex);
    ERROR_CHECK("pthread_mutex_lock", ret);

    // 互斥锁解锁
    ret = pthread_mutex_unlock(&mutex);
    ERROR_CHECK("pthread_mutex_unlock", ret);

    // 互斥锁销毁
    ret = pthread_mutex_destroy(&mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

    // 条件变量销毁
    ret = pthread_cond_destroy(&cond);
    ERROR_CHECK("pthread_cond_destory", ret);
}

int main()
{
    test();
    return 0;
}
/*
pthread_mutex_init: Success
pthread_cond_init: Success
pthread_mutex_lock: Success
pthread_mutex_unlock: Success
pthread_mutex_destory: Success
pthread_cond_destory: Success
*/

再来看一段稍显迷惑的代码：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <pthread.h>
#include <string.h>
#include <iostream>
#include <unistd.h>

#define ERROR_CHECK(msg, ret) \
        do{                   \
            printf("%s: %s\n", msg, strerror(ret)); \
        }while(0);

typedef struct
{
    int num;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
}Data_t;

void* threadFunc(void* arg)
{
    Data_t* p = (Data_t*) arg;

    // 互斥锁加锁
    int ret = pthread_mutex_lock(&p->mutex);
    ERROR_CHECK("pthread_mutex_lock2", ret);

    ret = pthread_cond_wait(&p->cond, &p->mutex);
    ERROR_CHECK("pthread_cond_wait", ret);

    // 互斥锁解锁
    ret = pthread_mutex_unlock(&p->mutex);
    ERROR_CHECK("pthread_mutex_unlock2", ret);

    pthread_exit(nullptr);
}

void test()
{
    Data_t data;
    data.num = 0;

    // 互斥锁初始化
    int ret = pthread_mutex_init(&data.mutex, nullptr);
    ERROR_CHECK("pthread_mutex_init", ret);

    // 条件变量初始化
    ret = pthread_cond_init(&data.cond, nullptr);
    ERROR_CHECK("pthread_cond_init", ret);

    // 创建子线程，让其等待在条件变量上
    pthread_t thid;
    ret = pthread_create(&thid, nullptr, threadFunc, &data);
    ERROR_CHECK("pthread_create", ret);

    // 让子线程先执行
    sleep(1);

    // 互斥锁加锁
    ret = pthread_mutex_lock(&data.mutex);
    ERROR_CHECK("pthread_mutex_lock1", ret);

    // 主线程唤醒子线程
    ret = pthread_cond_signal(&data.cond);
    ERROR_CHECK("pthread_cond_signal", ret);

    // 互斥锁解锁
    ret = pthread_mutex_unlock(&data.mutex);
    ERROR_CHECK("pthread_mutex_unlock1", ret);

    ret = pthread_join(thid, nullptr);
    ERROR_CHECK("pthread_join", ret);

    // 互斥锁销毁
    ret = pthread_mutex_destroy(&data.mutex);
    ERROR_CHECK("pthread_mutex_destory", ret);

    // 条件变量销毁
    ret = pthread_cond_destroy(&data.cond);
    ERROR_CHECK("pthread_cond_destory", ret);
}

int main()
{
    test();
    return 0;
}
/*
pthread_mutex_init: Success
pthread_cond_init: Success
pthread_create: Success
pthread_mutex_lock2: Success
pthread_mutex_lock1: Success
pthread_cond_signal: Success
pthread_mutex_unlock1: Success
pthread_cond_wait: Success
pthread_mutex_unlock2: Success
pthread_join: Success
pthread_mutex_destory: Success
pthread_cond_destory: Success
*/

// 为什么获得 lock2 后还能获得 lock1 ？
// 互斥锁不是不能多加吗？

代码最后注释的两个疑问，和 pthread_cond_wait 函数的特性有关。该函数会分为两个部分：

  • 上半部：在条件变量上排队；解锁；睡眠
  • 下半部：在条件变量上被唤醒；加锁；函数返回

生产者与消费者封装

简单情形

思路：

74-12.png

MutexLock.h :

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
#ifndef _MUTEXLOCK_H_
#define _MUTEXLOCK_H_

#include <pthread.h>

class MutexLock
{
public:
    MutexLock();
    ~MutexLock();
    void lock();
    void trylock();
    void unlock();

    pthread_mutex_t* get_mutex_ptr()
    {
        return &_mutex;
    }

private:
    pthread_mutex_t _mutex;
};


#endif

MutexLock.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "MutexLock.h"
#include <stdio.h>

MutexLock::MutexLock()
{
    int ret = pthread_mutex_init(&_mutex, nullptr);
    if(ret)
    {
        perror("pthread_mutex_init\n");
        return;
    }
}

MutexLock::~MutexLock()
{
    int ret = pthread_mutex_destroy(&_mutex);
    if(ret)
    {
        perror("pthread_mutex_destroy\n");
        return;
    }
}

void MutexLock::lock()
{
    int ret = pthread_mutex_lock(&_mutex);
    if(ret)
    {
        perror("pthread_mutex_lock\n");
        return;
    }
}

void MutexLock::trylock()
{
    int ret = pthread_mutex_trylock(&_mutex);
    if(ret)
    {
        perror("pthread_mutex_trylock\n");
        return;
    }
}

void MutexLock::unlock()
{
    int ret = pthread_mutex_unlock(&_mutex);
    if(ret)
    {
        perror("pthread_mutex_unlock\n");
        return;
    }
}

Condition.h :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef _CONDITION_H_
#define _CONDITION_H_

#include <pthread.h>

class MutexLock;

class Condition
{
public:
    Condition(MutexLock& mutex);
    ~Condition();
    void wait();
    void notify();
    void notifyAll();

private:
    MutexLock& _mutex;
    pthread_cond_t _cond;
};


#endif

Condition.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "Condition.h"
#include "MutexLock.h"
#include <stdio.h>

Condition::Condition(MutexLock& mutex)
: _mutex(mutex)
{
    int ret = pthread_cond_init(&_cond, nullptr);
    if(ret)
    {
        perror("pthread_cond_init\n");
        return;
    }
}
                                      
Condition::~Condition()
{
    int ret = pthread_cond_destroy(&_cond);
    if(ret)
    {
        perror("pthread_cond_destroy\n");
        return;
    }
}
                                      
void Condition::wait()
{
    int ret = pthread_cond_wait(&_cond, _mutex.get_mutex_ptr());
    if(ret)
    {
        perror("pthread_cond_wait\n");
        return;
    }
} 
                                      
void Condition::notify()
{
    int ret = pthread_cond_signal(&_cond);
    if(ret)
    {
        perror("pthread_cond_signal\n");
        return;
    }
}
                                      
void Condition::notifyAll()
{
    int ret = pthread_cond_broadcast(&_cond);
    if(ret)
    {
        perror("pthread_cond_broadcast\n");
        return;
    }
}

TaskQueue.h :

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
#ifndef _TASKQUEUE_H_
#define _TASKQUEUE_H_

#include "MutexLock.h"
#include "Condition.h"
#include <queue>

using std::queue;

class TaskQueue
{
public:
    TaskQueue(size_t queSize);
    ~TaskQueue();
    bool empty() const;
    bool full() const;
    void push(const int& value);
    int pop();

private:
    size_t _queSize;
    queue<int> _que;
    MutexLock _mutex;
    Condition _notEmpty;
    Condition _notFull;
};

#endif

TaskQueue.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "TaskQueue.h"

TaskQueue::TaskQueue(size_t queSize)
: _queSize(queSize)
, _que()
, _mutex()
, _notEmpty(_mutex)
, _notFull(_mutex)  // 注意要按照顺序初始化
{
}

// _queSize 和 _que 不用管
// _mutex, _notEmpty, _notFull 生命周期结束自动执行各自的析构函数
TaskQueue::~TaskQueue() = default;

bool TaskQueue::empty() const
{
    return 0 == _que.size();
}

bool TaskQueue::full() const
{
    return _que.size() == _queSize;
    // 这里的 _queSize 其实是指队列的最大容量
}

void TaskQueue::push(const int& value)
{
    _mutex.lock();

    if(full())
    {
        _notFull.wait();
        // 这个变量命名有点奇怪，可以这样理解：
        // 等待不满的时候
    }

    _que.push(value);
    _notEmpty.notify(); // 唤醒消费者
    _mutex.unlock();
}
    
int TaskQueue::pop()
{
    _mutex.lock();

    if(empty())
    {
        _notEmpty.wait();
    }

    int tmp = _que.front();
    _que.pop();
    _notFull.notify(); // 唤醒生产者
    _mutex.unlock();
    return tmp;
}

Thread.h :

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

#include <pthread.h>

class Thread {
public:
    Thread();
    virtual ~Thread();
    void start();
    void join();

private:
    static void* threadFunc(void* arg); // 线程的入口函数
    virtual void run() = 0;      // 线程的执行任务

    pthread_t _thid;  // 线程 id
    bool _isRunning; // 线程运行的标志位
};

#endif

Thread.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "Thread.h"
#include <stdio.h>

Thread::Thread()
: _thid(0)
, _isRunning(false)
{
}

Thread::~Thread()
{
    if(_isRunning)
    {
        // 让子线程与主线程分离，主线程不管子线程的回收
        pthread_detach(_thid);
        _isRunning = false;
    }
}

// 线程，启动！
void Thread::start()
{
    int ret = pthread_create(&_thid, nullptr, threadFunc, this);
    if(ret)
    {
        perror("pthread_create\n");
        return;
    }
    _isRunning = true;
}

void Thread::join()
{
    if(_isRunning)
    {
        int ret = pthread_join(_thid, nullptr);
        if(ret)
        {
            perror("pthread_join\n");
            return;
        }
        _isRunning = false;
    }
}

void* Thread::threadFunc(void* arg)
{
    Thread* pth = static_cast<Thread*>(arg);
    if(pth)
    {
        // threadFunc 是 static 的，没有 this 指针
        // 故在 pthread_create 中将 this 传进来
        pth->run(); // 体现多态
    }
    // 让子线程主动退出
    pthread_exit(nullptr);
}

Producer.h :

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
35
36
37
38
39
40
#ifndef _PRODUCER_H_
#define _PRODUCER_H_

#include "Thread.h"
#include "TaskQueue.h"
#include <stdlib.h>
#include <time.h>
#include <iostream>

using std::cout;
using std::endl;

class Producer
: public Thread
{
public:
    Producer(TaskQueue& taskQue)
    : _taskQue(taskQue)
    {}

    ~Producer()
    {}

    void run() override
    {
        ::srand(::clock());
        size_t cnt = 20;
        while(cnt--)
        {
            int number = ::rand()%100;
            _taskQue.push(number);
            cout << ">>Producer produce: " << number << endl;
        }
    }

private:
    TaskQueue& _taskQue;
};

#endif

Consumer.h :

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
35
36
37
38
#ifndef _CONSUMER_H_
#define _CONSUMER_H_

#include "Thread.h"
#include "TaskQueue.h"
#include <stdlib.h>
#include <time.h>
#include <iostream>

using std::cout;
using std::endl;

class Consumer
: public Thread
{
public:
    Consumer(TaskQueue& taskQue)
    : _taskQue(taskQue)
    {}

    ~Consumer()
    {}

    void run() override
    {
        size_t cnt = 20;
        while(cnt--)
        {
            int num = _taskQue.pop();
            cout << ">>Consumer consume: " << num << endl;
        }
    }

private:
    TaskQueue& _taskQue;
};

#endif

testFile.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include "TaskQueue.h"
#include "Producer.h"
#include "Consumer.h"
#include <memory>

using std::unique_ptr;

void test()
{
    TaskQueue task(10);
    Producer pro(task);
    Consumer con(task);

    pro.start();
    con.start();

    pro.join();
    con.join();
}

void test2()
{
    TaskQueue task(10);
    unique_ptr<Thread> pro(new Producer(task));
    unique_ptr<Thread> con(new Consumer(task));

    pro->start();
    con->start();

    pro->join();
    con->join();
}

int main()
{
    test();
    return 0;
}

// 某一次的运行结果

/*
>>Producer produce: 39
>>Producer produce: 71
>>Producer produce: 55
>>Producer produce: 9
>>Producer produce: 94
>>Producer produce: 0
>>Producer produce: 19
>>Producer produce: 71
>>Producer produce: 59
>>Producer produce: 90
>>Consumer consume: >>Producer produce: 4
39
>>Consumer consume: 71
>>Producer produce: 97
>>Producer produce: 0
>>Consumer consume: 55
>>Consumer consume: 9
>>Consumer consume: 94
>>Consumer consume: 0
>>Consumer consume: 19
>>Producer produce: >>Consumer consume: 5771
>>Consumer consume: 59
>>Consumer consume: 90
>>Consumer consume: 4
>>Consumer consume: 97
>>Consumer consume: 0
>>Consumer consume: 57

>>Producer produce: 23
>>Producer produce: 85
>>Producer produce: 95
>>Consumer consume: >>Producer produce: 29
23>>Producer produce: 
8>>Consumer consume: 85
>>Consumer consume: 95
>>Consumer consume: 29
>>Consumer consume: 8

>>Producer produce: 54
>>Consumer consume: 54
*/

/*
可以看到两线程交替运行
空行是之前还没来得及输出的换行
cout 不是原子操作
*/

// 类图设计的思路可以多回顾 D31_4

利用 RAII 优化

一个小改进，我们可以利用 RAII 的思想管理锁（以两个文件为例）：

MutexLock.h :

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
35
36
37
38
39
40
41
42
43
#ifndef _MUTEXLOCK_H_
#define _MUTEXLOCK_H_

#include <pthread.h>

class MutexLock
{
public:
    MutexLock();
    ~MutexLock();
    void lock();
    void trylock();
    void unlock();

    pthread_mutex_t* get_mutex_ptr()
    {
        return &_mutex;
    }

private:
    pthread_mutex_t _mutex;
};

// 利用 RAII 的思想
class MutexLockGuard
{
public:
    MutexLockGuard(MutexLock& mutex)
    : _mutex(mutex)
    {
        _mutex.lock();
    }

    ~MutexLockGuard()
    {
        _mutex.unlock();
    }

private:
    MutexLock& _mutex;
};

#endif

TaskQueue.cc :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include "TaskQueue.h"

TaskQueue::TaskQueue(size_t queSize)
: _queSize(queSize)
, _que()
, _mutex()
, _notEmpty(_mutex)
, _notFull(_mutex)  // 注意要按照顺序初始化
{
}

// _queSize 和 _que 不用管
// _mutex, _notEmpty, _notFull 生命周期结束自动执行各自的析构函数
TaskQueue::~TaskQueue() = default;

bool TaskQueue::empty() const
{
    return 0 == _que.size();
}

bool TaskQueue::full() const
{
    return _que.size() == _queSize;
    // 这里的 _queSize 其实是指队列的最大容量
}

void TaskQueue::push(const int& value)
{
    // RAII 的思想：
    // 在构造函数中初始化资源，析构函数中释放
    // 实质：用栈对象的生命周期管理资源
    MutexLockGuard autolock(_mutex);

    if(full())
    {
        _notFull.wait();
        // 这个变量命名有点奇怪，可以这样理解：
        // 等待不满的时候
    }

    _que.push(value);
    _notEmpty.notify(); // 唤醒消费者
}
    
int TaskQueue::pop()
{
    MutexLockGuard autolock(_mutex);

    if(empty())
    {
        _notEmpty.wait();
    }

    int tmp = _que.front();
    _que.pop();
    _notFull.notify(); // 唤醒生产者
    return tmp;
}

虚假唤醒

考虑这样的情况：
有多个生产者，生产者们的生产速度超过了消费者消费的速度，那么，仓库常常会处于满的状态，生产者线程被挂起（假设共有 3 个生产者）。现在，消费者消费了一个产品，调用 pthread_cond_signal 函数，由于 POSIX 规范允许它唤醒一个以上的线程（见之前笔记），如果此时唤醒了多个生产者线程（假设我们唤醒了 3 个线程），来看下面的代码逻辑：

1
2
3
4
5
6
7
8
9
if(full())
{
    _notFull.wait();
    // 这个变量命名有点奇怪，可以这样理解：
    // 等待不满的时候
}

_que.push(value);
_notEmpty.notify(); // 唤醒消费者

它们都会走出if(){}，并在 _que 里面塞点东西，这是我们不愿看见的。

使用虚假唤醒：

1
2
3
4
5
6
while(full())
{
    _notFull.wait();
}

_que.push(value);

禁止复制

这些代码仍然有问题。

锁、条件变量、线程是资源，不能进行复制或赋值，要体现对象语义。

解决方案：

  1. 将拷贝构造函数和赋值运算符函数设为 private. （C++98）
  2. 将拷贝构造函数和赋值运算符函数进行=delete （C++11）

我们沿用2的思路，使用一个对原有代码最少改动的方法。

编写文件NonCopyable.h：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef _NONCOPYABLE_H_
#define _NONCOPYABLE_H_

class NonCopyable
{
public:
    NonCopyable() {}
    ~NonCopyable() {}

    NonCopyable(const NonCopyable& rhs) = delete;
    NonCopyable& operator = (const NonCopyable& rhs) = delete;
};

#endif

然后让现有的一些类继承自此类（注意需要包含头文件NonCopyable.h）。

Condition.h :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Condition
: NonCopyable
{
public:
    Condition(MutexLock& mutex);
    ~Condition();
    void wait();
    void notify();
    void notifyAll();

private:
    MutexLock& _mutex;
    pthread_cond_t _cond;
};

MutexLock.h :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MutexLock
: NonCopyable
{
public:
    MutexLock();
    ~MutexLock();
    void lock();
    void trylock();
    void unlock();

    pthread_mutex_t* get_mutex_ptr()
    {
        return &_mutex;
    }

private:
    pthread_mutex_t _mutex;
};

Thread.h同理。

最终的代码：
https://github.com/dropsong/CPP_Code_Eaxmple/tree/master/pc_problem

线程池

任务量（并发量）较大时，频繁地创建、销毁线程开销也较大。我们可以提前创建好线程，有任务过来的时候，先放到任务队列中，之后子线程从任务队列中获取任务并执行。这样能提高程序的执行效率。

面向对象的线程池封装

类图：

74-13.jpg

我的一个通俗但未必严谨的理解：
ThreadPool 就是一个中介平台，本身并不做事情，它的手下有一堆干活小弟 Thread（这是一个抽象类，真正干活的是 WorkThread），中介平台会接一些外包任务 Task 分配给干活小弟干。具体来说，WorkThread 的run()方法去执行 ThreadPool 的任务threadFunc() .

代码参见： https://github.com/dropsong/CPP_Code_Eaxmple/tree/master/oo_threadPool

一些注意点写在了注释里。

一点调试经验：
如果线程池退不出来，可以使用ps -elLF | grep a.out查看进程状态。

时序图：

74-14.jpg

基于对象的线程池封装

类图：

74-15.JPG

代码参见：
https://github.com/dropsong/CPP_Code_Eaxmple/tree/master/bo_threadPool

线程属性

pthread_create 的第二个参数 attr 是一个结构体指针：

1
2
3
4
5
6
7
8
9
10
11
struct __pthread_attr
{
    struct sched_param __schedparam;
    void *__stackaddr;
    size_t __stacksize;
    size_t __guardsize;
    enum __pthread_detachstate __detachstate;
    enum __pthread_inheritsched __inheritsched;
    enum __pthread_contentionscope __contentionscope;
    int __schedpolicy;
};

结构中的元素分别指定新线程的运行属性，各成员属性为：

__detachstate 表示新线程是否与进程中其他线程脱离同步，如果置该属性则新线程不能用 pthread_join() 来等待，且在退出时自行释放所占用的资源。缺省为 PTHREAD_CREATE_JOINABLE 状态。这个属性也可以在线程创建并运行以后用 pthread_detach() 来设置，而一旦设置为 PTHREAD_CREATE_DETACHED 状态（不论是创建时设置还是运行时设置）则不能再恢复到 PTHREAD_CREATE_JOINABLE 状态。

__schedpolicy：表示新线程的调度策略，主要包括 SCHED_OTHER（分时调度策略）、SCHED_RR（实时、时间片轮转法）和 SCHED_FIFO（实时、 先到先服务）三种， 缺省为 SCHED_OTHER，后两种调度策略仅对超级用户有效。运行时可以用过 pthread_setschedparam() 来改变。

__schedparam：一个 sched_param 结构，目前仅有一个 sched_priority 整型变量表示线程的运行优先级。这个参数仅当调度策略为实时（即 SCHED_RR 或 SCHED_FIFO）时才有效，并可以在运行时通过 pthread_setschedparam() 函数来改变，缺省为 0 .

__inheritsched：有两种值可供选择：PTHREAD_EXPLICIT_SCHED 和 PTHREAD_INHERIT_SCHED，前者表示新线程使用显式指定调度策略和调度参数（即 attr 中的值），而后者表示继承调用者线程的值。缺省为 PTHREAD_INHERIT_SCHED .

__contentionscope：表示线程间竞争 CPU 的范围，也就是说线程优先级的有效范围。POSIX 的标准中定义了两个值： PTHREAD_SCOPE_SYSTEM 和 PTHREAD_SCOPE_PROCESS，前者表示与系统中所有线程一起竞争 CPU 时间，后者表示仅与同进程中的线程竞争 CPU. 目前 Linux 仅实现了 PTHREAD_SCOPE_SYSTEM 一值。

属性设置是由一些函数来完成的，通常调用 pthread_attr_init 函数进行初始化。设置绑定属性的函数为 pthread_attr_setscope，设置分离属性的函数是 pthread_attr_setdetachstate，设置线程优先级的相关函数 pthread_attr_getscehdparam（获取线程优先级）和 pthread_attr_setschedparam（设置线程优先级）。再设置完成属性后，调用 pthread_creat 函数创建线程。

1
2
3
4
#include <pthread.h>
int pthread_attr_init(pthread_attr_t *attr); //初始化线程属性
int pthread_attr_destroy(pthread_attr_t *attr); //销毁线程属性
int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate); //设置线程分离属性

设置线程分离属性示例（该代码并未测试）：

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 <head.h>

void* threadFunc(void* p)
{
    printf("i am child thread\n");
    pthread_exit(NULL);
}

int main(int argc, char** argv)
{
    int ret = 0;
    pthread_t thid;
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    //设置线程属性为可分离状态
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);

    ret = pthread_create(&thid, &attr, threadFunc, NULL);
    THREAD_ERROR_CHECK(ret, "pthread_create");

    printf("i am main thread\n");

    ret = pthread_join(thid, NULL);
    THREAD_ERROR_CHECK(ret, "pthread_join");
    return 0;
}

计算机网络基础

这部分内容参见 计算机网络笔记 。

三次握手、四次挥手的相关知识不再赘述。

SYN 攻击：
SYN 攻击就是 Client 在短时间内伪造大量不存在的 IP 地址，并向 Server 不断地发送 SYN 包，Server 回复确认包，并等待 Client 的确认，由于源地址是不存在的，因此，Server 需要不断重发直至超时，这些伪造的 SYN 包将长时间占用未连接队列（内核会为每个这样的连接分配资源的），导致正常的 SYN 请求因为队列满而被丢弃，从而引起网络堵塞甚至系统瘫痪。SYN 攻击是一种典型的 DDOS 攻击，检测 SYN 攻击的方式非常简单，即当 Server 上有大量半连接状态且源 IP 地址是随机的，则可以断定遭到 SYN 攻击了。

状态迁移图：

74-16.jpg

在上图中：

  • 粗实线：主动发起连接与主动关闭连接
  • 虚线：被动发起连接与被动关闭连接
  • 细实线：两端同时操作的部分

一个常用命令：

1
2
netstat -apn | grep 8888
# 8888 只是一个随便写的数字

具体作用试一下就知道了。

网络编程基础

前置知识

IP 地址可以在网络环境中唯一标识一台主机，端口号可以在主机中唯一标识一个进程。所以在网络环境中唯一标识一个进程可以使用 IP 地址与端口号 Port .

74-17.png

TCP/IP 协议规定，网络数据流应采用大端字节序。

大端：低地址存高位，高地址存低位。
小端：低地址存低位，高地址存高位（x86采用小端存储）。

网络字节序，就是在网络中进行传输的字节序列，采用的是大端法。主机字节序，就是本地计算机中存储数据采用的字节序列，采用的是小端法。

网络字节序与本机字节序的转换：

1
2
3
4
5
6
#include <arpa/inet.h>
//h = host n = network l = long s = short
uint32_t htonl(uint32_t hostlong);
uint16_t htons(uint16_t hostshort);
uint32_t ntohl(uint32_t netlong);
uint16_t ntohs(uint16_t netshort);

常用函数

网络套接字函数 socket ：

1
2
3
4
5
6
7
8
#include <sys/types.h>
#include <sys/socket.h>

int socket(int domain, int type, int protocol);
//domain：协议族，常用的三个AF_INET/AF_INET6/AF_UNIX,
//type:协议类型，SOCK_STREAM(TCP)/SOCK_DGRAM(UDP)
//protocol:默认情况就传0，代表使用的是tcp或者udp的默认协议
//返回值，如果成功的话，会返回一个文件描述符fd,如果失败的话，那么会返回-1.

bind 函数：

1
2
3
4
5
6
7
8
9
// 绑定服务器的ip与端口号
#include <sys/types.h>
#include <sys/socket.h>

int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);
//sockfd:就是上面socket函数的返回值。
//addr:传递包含ip与端口号的结构体。（服务器的ip与端口号）
//socklen_t:结构体的大小
//返回值：如果正确的话，会返回0；否则会返回-1.

在上面的代码中，一些结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct sockaddr
{
    sa_family_t  sa_family;
    char         sa_data[14];
};

struct sockaddr_in
{
    sa_family_t sin_family;  /* address family: AF_INET */
    in_port_t sin_port;      /* port in network byte order */  // port
    struct in_addr sin_addr; /* internet address */            // ip
};

struct in_addr
{
    uint32_t s_addr; /* address in network byte order */
};

typedef uint32_t in_addr_t;

listen 函数（让服务器处于监听状态）：

1
2
3
4
5
6
7
8
// listen - listen for connections on a socket
#include <sys/types.h>
#include <sys/socket.h>

int listen(int sockfd, int backlog);
//sockfd:就是上面socket函数的返回值。
//backlog：允许同时多少个客户端与服务器建立连接，默认128。
//返回值：如果正确的话，会返回0；否则会返回-1.

connect 函数，客户端调用该函数，连接到服务器上，主动发起连接：

1
2
3
4
5
6
7
8
#include <sys/types.h>
#include <sys/socket.h>

int connect(int sockfd, const struct sockaddr *addr, socklen_t addrlen);
//sockfd:就是上面socket函数的返回值。
//addr:该结构中包装的是服务器的ip与服务器的端口号。
//addrlen:结构体的长度。
//返回值：如果正确的话，会返回0；否则会返回-1.

accept 函数，接收连接请求的函数，阻塞等待客户端发起连接：

1
2
3
4
5
6
7
8
9
// accept, accept4 - accept a connection on a socket
#include <sys/types.h>
#include <sys/socket.h>

int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);
//sockfd:就是上面socket函数的返回值。
//addr:也是地址，但是在此处是将客户端的ip与端口号存放在这个addr中。
//addrlen:是addr对应的结构体的长度。
//返回值：成功返回一个新的socket文件描述符，用于和客户端通信，失败返回-1

read/recv 函数，从对应的文件描述符 fd 中读取数据到 buf 中，读的长度是 count :

1
2
3
4
5
6
7
8
#include <unistd.h>
ssize_t read(int fd, void *buf, size_t count);

#include <sys/types.h>
#include <sys/socket.h>

ssize_t recv(int sockfd, void *buf, size_t len, int flags);
//如果recv中的flags为0的话，那么read与recv是等价的。

write/send 函数，将 buf 中的 count 个字节写到 fd 对应的文件描述符中：

1
2
3
4
5
6
7
8
#include <unistd.h>
ssize_t write(int fd, const void *buf, size_t count);

#include <sys/types.h>
#include <sys/socket.h>

ssize_t send(int sockfd, const void *buf, size_t len, int flags);
//如果send中的flags为0的话，那么send与write是等价的。

close 函数，关闭文件描述符：

1
2
3
#include <unistd.h>
int close(int fd);
//在服务器端会关闭两个文件描述符，一个是socket的返回值，一个是accept的返回值。

实例

来看例子：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// server.cc
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char* argv[])
{
    // 服务器
    //1. 需要创建套接字，使用 socket 函数

    int listen_fd = socket(AF_INET, SOCK_STREAM, 0);
    if(listen_fd < 0)
    {
        perror("socket\n");
        close(listen_fd);
        return -1;
    }

    //2. 需要绑定服务器的 ip 和 port，使用 bind
    //   对应会有结构体 sockadd_in

    struct sockaddr_in seraddr;  // 这是 C 的写法
    memset(&seraddr, 0, sizeof(seraddr));  // 初始化

    seraddr.sin_family = AF_INET;
    // 本机字节序转换为网络字节序
    seraddr.sin_port = htons(atoi(argv[2]));
    // inet_addr 函数转换网络主机地址为网络字节序二进制值
    seraddr.sin_addr.s_addr = inet_addr(argv[1]); // 传 ip

    int ret = bind(listen_fd, (struct sockaddr*)&seraddr, sizeof(seraddr));
    if(ret < 0)
    {
        perror("bind\n");
        close(listen_fd);
        return -1;
    }

    //3. 使用 Listen 使服务器处于监听状态
    ret = listen(listen_fd, 128);
    if(ret < 0)
    {
        perror("listen\n");
        close(listen_fd);
        return -1;
    }
    printf("server is listening...\n");

    //4. 服务器调用 accept，阻塞等待客户端的连接
#if 0
    struct sockaddr_in clientaddr;  // 这是 C 的写法
    memset(&clientaddr, 0, sizeof(clientaddr));  // 初始化
    clientaddr.sin_family = AF_INET;
    socklen_t length = sizeof(clientaddr);
    accept(listen_fd, (struct sockaddr*)&clientaddr, &length);
#endif
    int connfd = accept(listen_fd, nullptr, nullptr);
    if(connfd < 0)
    {
        perror("accept\n");
        close(listen_fd);
        return -1;
    }

    //5. 连接成功之后，表明三次握手成功，可以进行
    //   数据的收发，也就是调用read/recv, 或者write/send
    while(1)
    {
        char buf[128] = {};
        int len = recv(connfd, buf, sizeof(buf), 0);
        if(len < 0)
        {
            printf("recive failed.\n");
        }
        else if(0 == len)
        {
            printf("len == 0\n");
        }
        else 
        {
            printf("rec msg from client: %s\n", buf);
        }

        printf("got some msg for the client: \n");
        char aa[128];
        scanf("%s", aa);
        int len2 = send(connfd, aa, strlen(aa), 0);
        if(len2 < 0) 
        {
            printf("sent failed.\n");
        }
        else if(0 == len2)
        {
            printf("len2 == 0\n");
        }
        else 
        {
            printf("sent succeeded.\n");
        }
    }

    //6. 关闭对应的文件描述符
    close(listen_fd);
    close(connfd);
    return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// client.cc
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char* argv[])
{
    // 客户端
    //1. 创建套接字，使用 socket 函数
    int listen_fd = socket(AF_INET, SOCK_STREAM, 0);
    if(listen_fd < 0)
    {
        perror("socket\n");
        close(listen_fd);
        return -1;
    }

    //2. 使用 connect 主动发起连接请求，但是需要知道
    //   服务器的 ip 和 port, 使用结构体 sockadd_in

    struct sockaddr_in seraddr;  // 这是 C 的写法
    memset(&seraddr, 0, sizeof(seraddr));  // 初始化
    seraddr.sin_family = AF_INET;
    // 本机字节序转换为网络字节序
    seraddr.sin_port = htons(atoi(argv[2]));
    // inet_addr 函数转换网络主机地址为网络字节序二进制值
    seraddr.sin_addr.s_addr = inet_addr(argv[1]); // 传 ip

    int ret = connect(listen_fd, (struct sockaddr*)&seraddr, sizeof(seraddr));
    if(ret < 0)
    {
        perror("connect\n");
        close(listen_fd);
        return -1;
    }

    //3. 如果 connect 返回值 ok，就表明三次握手成功,
    //   那么就可以进行数据收发，也就是 read/recv,
    //   或者 write/send 函数

    while(1)
    {
        printf("got some msg for the server: \n");
        char aa[128];
        scanf("%s", aa);
        int len2 = send(listen_fd, aa, strlen(aa), 0);
        if(len2 < 0) 
        {
            printf("sent failed.\n");
        }
        else if(0 == len2)
        {
            printf("len2 == 0\n");
        }
        else 
        {
            printf("sent succeeded.\n");
        }

        char buf[128] = {};
        int len = recv(listen_fd, buf, sizeof(buf), 0);
        if(len < 0)
        {
            printf("recive failed.\n");
        }
        else if(0 == len)
        {
            printf("len == 0\n");
        }
        else 
        {
            printf("rec msg from server: %s\n", buf);
        }
    }

    //4. 关闭文件描述符
    close(listen_fd);
    return 0;
}

接下来演示运行过程。

【terminal 1】启动 server： ./server 127.0.0.1 8888

1
server is listening...

【terminal 3】 netstat -apn |grep 8888

1
2
3
4
(Not all processes could be identified, non-owned process info
 will not be shown, you would have to be root to see it all.)
tcp        0      0 127.0.0.1:8888          0.0.0.0:*               LISTEN      42676/./server      
tcp        0      0 192.168.3.10:33508      120.232.240.71:8888     TIME_WAIT   -

【terminal 2】启动 client： ./client 127.0.0.1 8888

1
got some msg for the server:

【terminal 3】 netstat -apn |grep 8888

1
2
3
4
5
(Not all processes could be identified, non-owned process info
 will not be shown, you would have to be root to see it all.)
tcp        0      0 127.0.0.1:8888          0.0.0.0:*               LISTEN      42676/./server      
tcp        0      0 127.0.0.1:8888          127.0.0.1:49390         ESTABLISHED 42676/./server      
tcp        0      0 127.0.0.1:49390         127.0.0.1:8888          ESTABLISHED 43363/./client

【进行了一段富有建设性的对话后，terminal 2 按下 ctrl+c】

【terminal 3】 netstat -apn |grep 8888

1
2
3
4
5
(Not all processes could be identified, non-owned process info
 will not be shown, you would have to be root to see it all.)
tcp        0      0 127.0.0.1:8888          0.0.0.0:*               LISTEN      42676/./server      
tcp        0      0 127.0.0.1:8888          127.0.0.1:49390         CLOSE_WAIT  42676/./server      
tcp        0      0 127.0.0.1:49390         127.0.0.1:8888          FIN_WAIT2   -

【terminal 1 按下 ctrl+c，以迅雷不及掩耳之势在 terminal 3 中输入】 netstat -apn |grep 8888

1
2
3
(Not all processes could be identified, non-owned process info
 will not be shown, you would have to be root to see it all.)
tcp        0      0 127.0.0.1:53716         127.0.0.1:8888          TIME_WAIT   -

过一段时间之后在 terminal 3 中重复该命令：

1
2
(Not all processes could be identified, non-owned process info
 will not be shown, you would have to be root to see it all.)

有些时候图省事，也可以暂时不编写 client 程序：

74-18.png

一个有助于理解的视频：

端口复用

继续测试上面的程序，我们发现：
在运行过程中，如果我们先 ctrl+c 了 server, 再试图重新运行 server, 会提示：

1
2
bind
: Address already in use

这是因为，server 仍处于 timewait 状态。

现在，我们试图修改代码，使服务器的 IP 和 Port 可以重复使用。

为此，需要了解以下函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <sys/types.h>
#include <sys/socket.h>
int getsockopt(int sockfd, int level, int optname,
               void *optval, socklen_t *optlen);

int setsockopt(int sockfd, int level, int optname,
               const void *optval, socklen_t optlen);

//返回值：成功返回0，错误返回-1

int opt = 1;
setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));
int opt2 = 1;
setsockopt(listenfd, SOL_SOCKET, SO_REUSEPORT, &opt2, sizeof(opt2));

对 server.cc 作如下修改：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
// server.cc
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>

int main(int argc, char* argv[])
{
    // 服务器
    //1. 需要创建套接字，使用 socket 函数

    int listen_fd = socket(AF_INET, SOCK_STREAM, 0);
    if(listen_fd < 0)
    {
        perror("socket\n");
        close(listen_fd);
        return -1;
    }

    int opt = 1;
    int retval = setsockopt(listen_fd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));
    if(retval < 0)
    {
        perror("setsockopt\n");
        close(listen_fd);
        return -1;
    }

    int opt2 = 1;
    retval = setsockopt(listen_fd, SOL_SOCKET, SO_REUSEPORT, &opt2, sizeof(opt2));
    if(retval < 0)
    {
        perror("setsockopt\n");
        close(listen_fd);
        return -1;
    }

    //2. 需要绑定服务器的 ip 和 port，使用 bind
    //   对应会有结构体 sockadd_in

    struct sockaddr_in seraddr;  // 这是 C 的写法
    memset(&seraddr, 0, sizeof(seraddr));  // 初始化

    seraddr.sin_family = AF_INET;
    // 本机字节序转换为网络字节序
    seraddr.sin_port = htons(atoi(argv[2]));
    // inet_addr 函数转换网络主机地址为网络字节序二进制值
    seraddr.sin_addr.s_addr = inet_addr(argv[1]); // 传 ip

    int ret = bind(listen_fd, (struct sockaddr*)&seraddr, sizeof(seraddr));
    if(ret < 0)
    {
        perror("bind\n");
        close(listen_fd);
        return -1;
    }

    //3. 使用 Listen 使服务器处于监听状态
    ret = listen(listen_fd, 128);
    if(ret < 0)
    {
        perror("listen\n");
        close(listen_fd);
        return -1;
    }
    printf("server is listening...\n");

    //4. 服务器调用 accept，阻塞等待客户端的连接
#if 0
    struct sockaddr_in clientaddr;  // 这是 C 的写法
    memset(&clientaddr, 0, sizeof(clientaddr));  // 初始化
    clientaddr.sin_family = AF_INET;
    socklen_t length = sizeof(clientaddr);
    accept(listen_fd, (struct sockaddr*)&clientaddr, &length);
#endif
    int connfd = accept(listen_fd, nullptr, nullptr);
    if(connfd < 0)
    {
        perror("accept\n");
        close(listen_fd);
        return -1;
    }

    //5. 连接成功之后，表明三次握手成功，可以进行
    //   数据的收发，也就是调用read/recv, 或者write/send
    while(1)
    {
        char buf[128] = {};
        int len = recv(connfd, buf, sizeof(buf), 0);
        if(len < 0)
        {
            printf("recive failed.\n");
        }
        else if(0 == len)
        {
            printf("len == 0\n");
        }
        else 
        {
            printf("rec msg from client: %s\n", buf);
        }

        printf("got some msg for the client: \n");
        char aa[128];
        scanf("%s", aa);
        int len2 = send(connfd, aa, strlen(aa), 0);
        if(len2 < 0) 
        {
            printf("sent failed.\n");
        }
        else if(0 == len2)
        {
            printf("len2 == 0\n");
        }
        else 
        {
            printf("sent succeeded.\n");
        }
    }

    //6. 关闭对应的文件描述符
    close(listen_fd);
    close(connfd);
    return 0;
}

client.cc 保持不变。

IO多路复用

在上面的代码中，C/S 是一对一的，这不是我们想要的，我们希望一个 S 可以服务多个 C.

74-19.png

select

文件描述符从 0 开始排，如果文件描述符使用后被释放了，那么后面需要重复使用已经释放的文件描述符。

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
35
#include <sys/select.h>
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>

int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds,
           struct timeval *timeout);
//nfds：最大文件描述符加1
//readfds,writefds,exceptfds:可读，可写，异常。fd_set,位图
//timeout:
//1、nullptr，永远等下去
//2、设置timeval，等待固定时间
//3、设置timeval里时间均为0，检查描述字后立即返回，轮询

//返回：满足符合条件的文件描述符的个数。包括：可读的文件描述符的个数，可写文件描述符的个数，异常的文件描述符的个数。

//监听文件描述符的时候，往往都只是监听可读的属性。

struct timeval
{
    long tv_sec;      /* seconds */
    long tv_usec;     /* microseconds */
};

struct timespec
{
    long tv_sec;      /* seconds */
    long tv_nsec;     /* nanoseconds */
};

//clr = clear
void FD_CLR(int fd, fd_set *set); //将fd从set位图中删除
int FD_ISSET(int fd, fd_set *set);//判断fd是否在set位图中
void FD_SET(int fd, fd_set *set); //将fd加入到set位图中
void FD_ZERO(fd_set *set);        //将set位图进行初始化

74-20.png

select 函数的返回结果（例如上图返回 4）：位图中有多少个 1.

例子：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
// select.c
#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <sys/select.h>
#include <sys/time.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <ctype.h>

#define SERV_PORT 8888

int main()
{
    int listenfd, connfd, sockfd;
    struct sockaddr_in serv_addr, clie_addr;
    socklen_t clie_addr_len;
    int ret, maxfd, maxi, i, j, nready, nByte;
    fd_set rset, allset;

    // FD_SETSIZE 定义在 /usr/include/linux/posix_types.h
    // 1024
    // select 最多监听 1024 个（设计缺陷）
    int client[FD_SETSIZE];
    char buf[BUFSIZ], str[BUFSIZ];

    //1. 创建套接字
    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if(-1 == listenfd)
    {
        perror("socket error");
        exit(-1);
    }

    //2. 地址复用
    int opt = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));

    //3. 端口复用
    int opt2 = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt2, sizeof(opt2));

    //4. 绑定ip与端口号
    bzero(&serv_addr, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(SERV_PORT);
    serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);
    // INADDR_ANY : 本地随机的有效数字类型的 IP
    // 转换过来就是 0.0.0.0 , 泛指本机的所有 IP
    /*
       因为有些电脑不止一块网卡，如果某个应用程序只监听
       某个端口，那么其他端口过来的数据就接受不了。
    */

    ret = bind(listenfd, (struct sockaddr*)&serv_addr, sizeof(serv_addr));
    if(-1 == ret)
    {
        perror("bind error");
        close(listenfd);
        exit(-1);
    }

    //5. 服务器监听
    ret = listen(listenfd, 128);
    if(-1 == ret)
    {
        perror("listen error");
        close(listenfd);
        exit(-1);
    }

    printf("server is listening...\n");
    
    //6. select 类型 IO 多路复用
    maxfd = listenfd; // select 的第一个参数设置为 listenfd
    maxi = -1;

    // 初始化
    for(i = 0; i < FD_SETSIZE; ++i)
    {
        client[i] = -1;
    }

    FD_ZERO(&allset); // 清空 allset
    // 将 listenfd 放在 allset 中进行监听
    FD_SET(listenfd, &allset);

    while(1)
    {
        rset = allset; // 将 allset 拷贝给 rset
        //6.1. 使用 select 负责监听，如果返回值大于0，表明有
        //     满足条件的连接被监听到
        nready = select(maxfd+1, &rset, NULL, NULL, NULL);
        if(nready < 0)
        {
            perror("select error");
            close(listenfd);
            exit(-1);
        }

        //6.2. 如果 listenfd 被置位, 表示有新的请求进来
        if(FD_ISSET(listenfd, &rset))
        {
            clie_addr_len = sizeof(clie_addr);
            //7. 有新的连接，那么 accept 肯定有返回值
            connfd = accept(listenfd, (struct sockaddr*)&clie_addr, &clie_addr_len);
            if(-1 == connfd)
            {
                perror("accept error");
                close(listenfd);
                exit(-1);
            }
            printf("receive from %s from port %d\n",
                   inet_ntop(AF_INET, &clie_addr.sin_addr, str, sizeof(str)),
                   ntohs(clie_addr.sin_port));
            
            /*
               将新的连接加到数组 client 中，
               该数组就是为了存储建立连接的文件描述符
            */
            for(i = 0; i < FD_SETSIZE; ++i)
            {
                 if(client[i] < 0)
                 {
                     client[i] = connfd;
                     break;
                 }
            }

            // i 超过了能监听的最大的文件描述符数量
            if(i == FD_SETSIZE)
            {
                fputs("too many clients.\n", stderr);
                exit(1);
            }

            /*
            将建立了三次握手的文件描述符放在 allset 集合中
            进行继续监听，如果该文件描述符后续继续可读，
            表明有数据需要读写
            */
            FD_SET(connfd, &allset);

            if(connfd > maxfd)
            {
                maxfd = connfd;
            }
            if(i > maxi)
            {
                maxi = i;
            }

            /*
            如果 nready 等于 1，就继续 while 循环
            而不用走 6.3 出 for 循环，提示效率
            */
            if(--nready == 0)
            {
                continue;
            }
        }

        /* 6.3.
        遍历 client 数组，如果里面的元素为正，就表明该文件
        描述符被监听到，就是老的连接，可以进行数据的收发
        */
        for(i = 0; i <= maxi; ++i)
        {
            if((sockfd = client[i]) < 0)
            {
                continue;
            }

            // 如果老的连接上有数据，表明可以进行数据的传输
            // 可以进行 read/write 操作
            if(FD_ISSET(sockfd, &rset)) // 老的连接
            {
                if((nByte = read(sockfd, buf, sizeof(buf))) == 0)
                {
                    // 表明数据读完了（缓冲区已经没有数据）
                    // 连接即将断开
                    close(sockfd);
                    FD_CLR(sockfd, &allset);
                    client[i] = -1;
                }
                // 正常的操作
                else if(nByte > 0)
                {
                    for(j = 0; j < nByte; ++j)
                    {
                        buf[j] = toupper(buf[j]);
                    }
                    write(sockfd, buf, nByte);
                    write(STDOUT_FILENO, buf, nByte);
                }

                if(--nready == 0)
                {
                    break; // 若已处理完 connfd 直接退出循环
                }
            }
        }
    }

    close(listenfd);
    close(connfd);
    return 0;
}

上面的代码配合 client.cc 可以运行，观察到一个 S 可以服务于多个 C.

select 的特点：

  • 文件描述符上限（1024），同时监听的文件描述符 1024 个，历史原因，不好修改，除非重新编译 Linux 内核。
  • 当监听的文件描述符个数比较稀疏的时候，循环判断比较麻烦，需要自定义数据结构，例如数组。
  • 监听集合与满足监听条件的集合是同一个，需要将原有集合保存。

youtube 视频：

poll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <poll.h>

int poll(struct pollfd *fds, nfds_t nfds, int timeout);
//events/revents:POLLIN/POLLOUT/POLLERR
//timeout 毫秒级等待
//-1:阻塞等，#define INFTIM -1 Linux中没有定义此宏
//0:立即返回，不阻塞进程
//>0:等待指定毫秒数，如当前系统时间精度不够毫秒，向上取值。

//函数返回值：满足监听条件的文件描述符的数目

fds[1024]   fds[0].fd = listendfd;   fds[0].events = POLLIN;

struct pollfd
{
    int fd;   /* file descriptor */
    short events; /* requested events *///监听的事件类型，读事件，写事件，异常
    short revents;/* returned events */
};

代码（该代码并未测试）：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
// poll.c
#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <poll.h>
#include <errno.h>

#define SERV_PORT 8888
#define OPEN_MAX 1024

int main()
{
    int i, j, n, maxi;
    int nready, ret;
    int listenfd, connfd, sockfd;
    char buf[BUFSIZ], str[INET_ADDRSTRLEN];
    struct sockaddr_in serv_addr, clie_addr;
    socklen_t clie_addr_len;
    struct pollfd client[OPEN_MAX];

    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if(-1 == listenfd)
    {
        perror("socket error");
        exit(-1);
    }

    int opt = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));

    memset(&serv_addr, 0, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(SERV_PORT);//本地字节序port与ip都要转换为网络字节序
    serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);//因为要在网络上传输

    ret = bind(listenfd, (struct sockaddr *)&serv_addr, sizeof(serv_addr));
    if(-1 == ret)
    {
        perror("bind error");
        close(listenfd);
        exit(-1);
    }

    ret = listen(listenfd, 128);
    if(-1 == ret)
    {
        perror("listen error");
        close(listenfd);
        exit(-1);
    }
    printf("server is listening...\n");

    // poll 类型 IO 多路复用
    // 将 listenfd 放在数组中进行监听
    client[0].fd = listenfd;
    client[0].events = POLLIN;

    for(i = 1; i < OPEN_MAX; ++i)
    {
        client[i].fd = -1;//将数组初始化为-1
    }
    maxi = 0;
    
    while(1)
    {
        nready = poll(client, maxi + 1, -1);
        if(nready < 0)
        {
            perror("poll error");
            exit(-1);
        }

        if(client[0].revents & POLLIN)
        {
            clie_addr_len = sizeof(clie_addr);
            connfd = accept(listenfd, (struct sockaddr *)&clie_addr, &clie_addr_len);//立即连接，此时不会阻塞等
            if(-1 == connfd)
            {
                perror("accept error");
                exit(-1);
            }

            printf("received from %s at port %d\n",
                    inet_ntop(AF_INET, &clie_addr.sin_addr.s_addr, str,sizeof(str)),
                    ntohs(clie_addr.sin_port));

            for(i = 1; i < OPEN_MAX; ++i)
            {
                if(client[i].fd < 0)//因为初始化为-1,所以在此作为判断条件
                {
                    client[i].fd = connfd;
                    break;
                }
            }

            if(i == OPEN_MAX)//select监听的文件描述符有上限，最大只能监听1024个
            {
                fputs("too many clients\n", stderr);
                exit(1);
            }

            client[i].events = POLLIN;

            if(i > maxi)
            {
                maxi = i;
                //因为文件描述符有新增，导致自定义数组有变化，所以需要重新修改maxi的值
            }

            if(--nready == 0)
            {
                continue;
            }
        }

        for(i = 1; i <= maxi; ++i)
        {
            if((sockfd = client[i].fd) < 0)
            {
                continue;
            }
    
            if(client[i].revents & POLLIN)
            {
                if((n = read(sockfd, buf, sizeof(buf))) < 0)
                {
                    if(errno == ECONNRESET)
                    {
                        printf("client[%d] abort connect\n", i);
                        close(sockfd);
                        client[i].fd = -1;
                    }
                    else
                    {
                        perror("read n = 0 error");
                    }
                }

                else if(n > 0)
                {
                    for(j = 0; j < n; ++j)
                    {
                        buf[j] = toupper(buf[j]);
                    }
                    write(sockfd, buf, n);
                    write(STDOUT_FILENO, buf, n);
                }

                else
                {
                    close(sockfd);
                    client[i].fd = -1;
                }

                if(--nready == 0)
                {
                    break;
                }
            }
        }
    }

    close(listenfd);
    close(connfd);
    return 0;
}

优点：

  1. 突破文件描述符1024的上限
  2. 监听与返回的集合分离
  3. 搜索范围变小（已经知道是那几个数组）

缺点：

  • 例如：监听1000个文件描述符，但是只有3个满足条件，这样也需要全部遍历，效率依旧低。

youtube 视频：

epoll

epoll 是 Linux 下 IO 多路复用接口 select/poll 的增强版本，能显著提高程序在大量并发连接中只有少量活跃的情况下的系统 CPU 利用率，因为它会复用文件描述符集合来传递结果而不是迫使开发者每次等待事件之前都必须重新准备要侦听的文件描述符集合，另一个原因是获取事件的时候，它无须遍历整个被侦听的描述符集，只要遍历哪些被内核 IO 事件唤醒而加入 Ready 队列的描述符集合就行了。

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
35
36
37
38
39
40
41
42
43
44
#include <sys/epoll.h>
int epoll_create(int size);
//size:linux内核版本2.6.8之后，size可以忽略，但是要大于0
//返回值：成功返回非负整数，失败返回-1.
int epoll_create1(int flags);

#include <sys/epoll.h>
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
//epfd:是epoll_create函数的返回值，也就是文件描述符
//op:EPOLL_CTL_ADD/EPOLL_CTL_MOD/EPOLL_CTL_DEL
//fd:将哪个文件描述符以op的方式加在以epfd建立的树上
//event:告诉内核需要监听的事情,EPOLLIN/EPOLLOUT/EPOLLERR/...
struct epoll_event
{
    uint32_t events;   /* Epoll events */
    epoll_data_t data; /* User data variable */
};

typedef union epoll_data
{
    void     *ptr;  // 拓展性
    int       fd;
    uint32_t  u32;
    uint64_t  u64;
} epoll_data_t;


struct A  // 例如我们用 void* ptr 指向这个结构体
{
    int number;
    void* (pFunc)(void *);
};

#include <sys/epoll.h>
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);
//epfd:是epoll_create函数的返回值，也就是文件描述符
//events:满足条件的事件都在该结构体，只需遍历该结构体即可
//maxevents：告知内核这个events有多大.
//timeout 毫秒级等待
//-1:阻塞等，#define INFTIM -1 Linux中没有定义此宏
//0:立即返回，不阻塞进程
//>0:等待指定毫秒数，如当前系统时间精度不够毫秒，向上取值。

//返回值：成功，将满足条件的文件描述符的个数返回；失败就返回-1.

epoll 中涉及到两个数据结构： epoll_create 创建的红黑树的根节点，将满足条件的事件放在就绪链表，可以直接遍历就绪链表即可。

74-21.png

代码（下面两份代码没有实际运行验证）：

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// server.c
#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <sys/select.h>
#include <sys/time.h>
#include <sys/epoll.h>
#include <stdlib.h>
#include <strings.h>
#include <unistd.h>
#include <ctype.h>

#define SERV_PORT 8888
#define OPEN_MAX 5000

int main()
{
    int listenfd, connfd, sockfd, epfd;
    struct sockaddr_in serv_addr, clie_addr;
    socklen_t clie_addr_len;
    int ret, i, j, nready, nByte;
    char buf[BUFSIZ], str[BUFSIZ];
    struct epoll_event evt, ep[OPEN_MAX];

    listenfd = socket(AF_INET, SOCK_STREAM, 0);
    if(-1 == listenfd)
    {
        perror("socket error");
        exit(-1);
    }

    int opt = 1;
    setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, &opt, sizeof(opt));

    bzero(&serv_addr, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(SERV_PORT);
    serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

    ret = bind(listenfd, (struct sockaddr *)&serv_addr, sizeof(serv_addr));
    if(-1 == ret)
    {
        perror("bind error");
        close(listenfd);
        exit(-1);
    }

    ret = listen(listenfd, 128);
    if(-1 == ret)
    {
        perror("listen error");
        close(listenfd);
        exit(-1);
    }
    printf("server is listening...\n");

    // 创建红黑树的根节点（使用数据结构：红黑树+就绪链表）
    epfd = epoll_create(OPEN_MAX);
    if(-1 == epfd)
    {
        perror("epoll_create error");
        close(listenfd);
        exit(-1);
    }

    evt.events = EPOLLIN;
    evt.data.fd = listenfd;

    ret = epoll_ctl(epfd, EPOLL_CTL_ADD, listenfd, &evt);
    if(-1 == ret)
    {
        perror("epoll_ctl error");
        close(listenfd);
        exit(-1);
    }

    while(1)
    {
        // 使用 epoll_wait 监听。若返回值大于 0，表明有
        // 满足条件的连接被监听到
        nready = epoll_wait(epfd, ep, OPEN_MAX, -1);
        if(nready < 0)
        {
            perror("select error");
            exit(-1);
        }

        for(i = 0; i < nready; ++i)
        {
            if(!(ep[i].events & EPOLLIN))
            {
                continue;
            }

            // 如果监听到的是 listenfd, 表明有新的请求进来
            if(ep[i].data.fd == listenfd)//如果是连接事件
            {
                clie_addr_len = sizeof(clie_addr);
                connfd = accept(listenfd, (struct sockaddr *)&clie_addr, &clie_addr_len);
                if(-1 == connfd)
                {
                    perror("accept error");
                    close(listenfd);
                    exit(-1);
                }
                printf("receive from %s from port %d\n",
                        inet_ntop(AF_INET, &clie_addr.sin_addr, str, sizeof(str)),
                        ntohs(clie_addr.sin_port));

                // 将 connfd 放在红黑树上继续监听
                evt.events = EPOLLIN;
                evt.data.fd = connfd;
                epoll_ctl(epfd, EPOLL_CTL_ADD, connfd, &evt);
            }

            else //不是连接建立事件，而是读写事件(信息传递事件)
            {
                sockfd = ep[i].data.fd;
                nByte = read(sockfd, buf, sizeof(buf));
                if(nByte == 0)
                {
                    ret = epoll_ctl(epfd, EPOLL_CTL_DEL, sockfd, NULL);
                    if(-1 == ret)
                    {
                        perror("epoll_ctl error");
                    }
                    close(sockfd);
                    printf("client[%d] closed connection\n", sockfd);
                }
                else if(nByte < 0)
                {   /* 连接异常 */
                    perror("epoll_ctl error");
                    ret = epoll_ctl(epfd, EPOLL_CTL_DEL, sockfd, NULL);
                    if(-1 == ret)
                    {
                        perror("epoll_ctl error");
                    }
                    close(sockfd);
                }
                else
                { /*正常操作*/
                    for(j = 0; j < nByte; ++j)
                    {
                        buf[j] = toupper(buf[j]);
                    }
                    write(sockfd, buf, nByte);
                    write(STDOUT_FILENO, buf, nByte);
                }
            }
        }
    }
    close(listenfd);
    close(connfd);
    return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
// client.c
#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <unistd.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>

#define SERV_IP "127.0.0.1"
#define SERV_PORT 8888

int main()
{
    int cfd;
    struct sockaddr_in serv_addr;
    char buf[BUFSIZ];
    int nByte;

    cfd = socket(AF_INET, SOCK_STREAM, 0);
    if(-1 == cfd)
    {
        perror("socket error");
        exit(-1);
    }

    memset(&serv_addr, 0, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(SERV_PORT);
    serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);

    /* inet_pton(cfd, SERV_IP, &serv_addr.sin_addr.s_addr); */

    connect(cfd, (struct sockaddr *)&serv_addr, sizeof(serv_addr));

    while(1)
    {
        fgets(buf, sizeof(buf), stdin);//hello world ---->  hello world\n\0
        write(cfd, buf, strlen(buf));
        nByte = read(cfd, buf, sizeof(buf));
        write(STDOUT_FILENO, buf, nByte);
    }

    close(cfd);
    return 0;
}

优点：

  1. 文件描述符数目没有上限：通过 epoll_ctl() 来注册一个文件描述符，内核中使用红黑树的数据结构来管理所有需要监控的文件描述符。
  2. 基于事件就绪通知方式：一旦被监听的某个文件描述符就绪，内核会采用类似于 callback 的回调机制，迅速激活这个文件描述符，这样随着文件描述符数量的增加，也不会影响判定就绪的性能。
  3. 维护就绪队列：当文件描述符就绪，就会被放到内核中的一个就绪队列中，这样调用 epoll_weit 获取就绪文件描述符的时候，只要取队列中的元素即可，操作的时间复杂度恒为O(1).

类型区别

  • 水平触发(level-trggered)：只要文件描述符关联的读内核缓冲区非空，有数据可以读取，就一直发出可读信号进行通知；当文件描述符关联的内核写缓冲区不满，有空间可以写入，就一直发出可写信号进行通知 LT 模式支持阻塞和非阻塞两种方式。epoll 默认的模式是 LT.
  • 边缘触发(edge-triggered)：当文件描述符关联的读内核缓冲区由空转化为非空的时候，则发出可读信号进行通知；当文件描述符关联的内核写缓冲区由满转化为不满的时候，则发出可写信号进行通知。

水平触发和边缘触发的区别在哪里呢？
水平触发是只要读缓冲区有数据，就会一直触发可读信号，而边缘触发仅仅在空变为非空的时候通知一次。LT(level triggered) 是缺省的工作方式，并且同时支持 block 和 no-block socket. 在这种做法中，内核告诉你一个文件描述符是否就绪了，然后你可以对这个就绪的 fd 进行 IO 操作。如果你不作任何操作，内核还是会继续通知你的，所以，这种模式编程出错误可能性要小一点。传统的 select/poll 都是这种模型的代表．

74-22.png

当设置了边缘触发以后，以可读事件为例，对“有数据到来”这事件为触发。

74-23.png

select/poll/epoll 除了应用于 fd 外，像管道、文件也是可以的。

youtube 视频：


上面三个视频其实蛮多地方胡言乱语，建议看以下的总结视频，比较清晰。不过请注意，该视频的 epoll 讲解略有瑕疵。


如果后来者无法在 B 站看到视频，可以前往 youtube 观看备份视频

五种网络IO模型

阻塞式 IO

74-24.png

非阻塞式 IO

74-25.png

IO 多路复用

74-26.png

信号驱动式 IO

74-27.png

这里的原理，和操作系统那门课的 IO控制方式 相关知识点（轮询、中断）差不多。

异步 IO

74-28.png