Cpp_STL_iterator

发表于2022-03-07更新于2025-11-04阅读次数

内容

  1. iterator的分类
  2. iterator的属性
  3. advance–使迭代器移动n步
  4. 针对迭代器的类型萃取
  5. SGI萃取的写法
  6. distance–计算两迭代器之间的距离

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
#pragma once
namespace xcg
{
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
using ptrdiff_t = int;

template<class _C, class _Ty, class _D = ptrdiff_t, class _Pointer = _Ty*,
	class _Reference = _Ty&>
	struct iterator
{
	typedef _C			iterator_category;
	typedef _Ty			value_type;
	typedef _D			difference_type;
	typedef _Pointer	pointer;
	typedef _Reference	reference;
};
template<class _Ty, class _D = ptrdiff_t>
struct _Forit : public iterator<forward_iterator_tag, _Ty, _D> {};
template<class _Ty, class _D = ptrdiff_t>
struct _Bidit : public iterator<bidirectional_iterator_tag, _Ty, _D> {};
template<class _Ty, class _D = ptrdiff_t>
struct _Ranit : public iterator<random_access_iterator_tag, _Ty, _D> {};

template<class _II, class _D>
inline void __advance(_II& i, _D n, input_iterator_tag)
{
	while (n--) ++i;
}
template<class _BI, class _D>
inline void __advance(_BI& i, _D n, bidirectional_iterator_tag)
{
	if (n >= 0)
	{
		while (n--) ++i;
	}
	else
	{
		while (n++) --i;
	}
}
template<class _RAI, class _D>
inline void __advance(_RAI& i, _D n, input_iterator_tag)
{
	i += n;
}
template<class _II, class _D>
inline void advance(_II& i, _D n)
{

}
}
1
2
3
4
5
6
7
8
9
10
template<class _Iterator>
struct iterator_traits
{
    iterator_traits() {}
	typedef typename _Iterator::iterator_category	iterator_category;
	typedef typename _Iterator::value_type			value_type;
	typedef typename _Iterator::difference_type		difference_type;
	typedef typename _Iterator::pointer				pointer;
	typedef typename _Iterator::reference			reference;
};

advance

1
2
3
4
5
6
inline void advance(_II& i, _D n)
{
	iterator_traits<_II>();
	typedef typename iterator_traits<_II>::iterator_category cate;
	__advance(i, n, cate());
}

萃取器

首先是针对泛型iterator，其是标准的迭代器，重载了*和->运算符。这里的萃取器可容纳的不包括裸指针。

1
2
3
4
5
6
7
8
9
10
template<class _Iterator>
struct iterator_traits
{
    iterator_traits() {}
	typedef typename _Iterator::iterator_category	iterator_category;
	typedef typename _Iterator::value_type			value_type;
	typedef typename _Iterator::difference_type		difference_type;
	typedef typename _Iterator::pointer				pointer;
	typedef typename _Iterator::reference			reference;
};

接下来是针对裸指针作出的模板特化。裸指针可看作是可随机访问的迭代器。

1
2
3
4
5
6
7
8
9
10
template<class T>
struct iterator_traits<T*>
{
	iterator_traits() {}
	typedef typename random_access_iterator_tag		iterator_category;
	typedef typename T		value_type;
	typedef typename int	difference_type;
	typedef typename T*		pointer;
	typedef typename T&		reference;
};

接着再次对裸指针的萃取器模板作出部分特化，可处理常裸指针。

1
2
3
4
5
6
7
8
9
10
template<class T>
struct iterator_traits<const T*>
{
	iterator_traits() {}
	typedef typename random_access_iterator_tag		iterator_category;
	typedef typename T				value_type;
	typedef typename int			difference_type;
	typedef typename const T*		pointer;
	typedef typename const T&		reference;
};

至此代码版本v1

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
#pragma once
namespace xcg
{
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
using ptrdiff_t = int;

template<class _C, class _Ty, class _D = ptrdiff_t, class _Pointer = _Ty*,
	class _Reference = _Ty&>
	struct iterator
{
	typedef _C			iterator_category;
	typedef _Ty			value_type;
	typedef _D			difference_type;
	typedef _Pointer	pointer;
	typedef _Reference	reference;
};

template<class _Iterator>
struct iterator_traits
{
	iterator_traits() {}
	typedef typename _Iterator::iterator_category	iterator_category;
	typedef typename _Iterator::value_type			value_type;
	typedef typename _Iterator::difference_type		difference_type;
	typedef typename _Iterator::pointer				pointer;
	typedef typename _Iterator::reference			reference;
};

template<class T>
struct iterator_traits<T*>
{
	iterator_traits() {}
	typedef typename random_access_iterator_tag		iterator_category;
	typedef typename T		value_type;
	typedef typename int	difference_type;
	typedef typename T*		pointer;
	typedef typename T&		reference;
};
template<class T>
struct iterator_traits<const T*>
{
	iterator_traits() {}
	typedef typename random_access_iterator_tag		iterator_category;
	typedef typename T				value_type;
	typedef typename int			difference_type;
	typedef typename const T*		pointer;
	typedef typename const T&		reference;
};

template<class _Ty, class _D = ptrdiff_t>
struct _Forit : public iterator<forward_iterator_tag, _Ty, _D> {};
template<class _Ty, class _D = ptrdiff_t>
struct _Bidit : public iterator<bidirectional_iterator_tag, _Ty, _D> {};
template<class _Ty, class _D = ptrdiff_t>
struct _Ranit : public iterator<random_access_iterator_tag, _Ty, _D> {};

template<class _II, class _D>
inline void __advance(_II& i, _D n, input_iterator_tag)
{
	while (n--) ++i;
}
template<class _BI, class _D>
inline void __advance(_BI& i, _D n, bidirectional_iterator_tag)
{
	if (n >= 0)
	{
		while (n--) ++i;
	}
	else
	{
		while (n++) --i;
	}
}
template<class _RAI, class _D>
inline void __advance(_RAI& i, _D n, input_iterator_tag)
{
	i += n;
}
template<class _II, class _D>
inline void advance(_II& i, _D n)
{
	iterator_traits<_II>();
	typedef typename iterator_traits<_II>::iterator_category cate;
	__advance(i, n, cate());
}
}

SGI的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//以下三个函数是SGI比较重要的写法模式
template<class _II>
inline typename iterator_traits<_II>::iterator_category
iterator_category(const _II&)
{
	typedef typename iterator_traits<_II>::iterator_category cate;
	return cate();
}
template<class _II>
inline typename iterator_traits<_II>::value_type*
value_type(const _II&)
{
	return static_cast<typename iterator_traits<_II>::value_type*>(0);
}
template<class _II>
inline typename iterator_traits<_II>::difference_type*
difference_type(const _II &)
{
	return static_cast<typename iterator_traits<_II>::difference_type*>(0);
}
1
2
3
4
5
6
template<class _II, class _D>
inline void advance(_II& i, _D n)
{
    //这里是SGI的写法，使代码更加灵活。
	__advance(i, n, iterator_category(i));
}

distance

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
template<class _II>
inline typename iterator_traits<_II>::difference_type
__distance(_II _F, _II _L, input_iterator_tag)
{
	typename iterator_traits<_II>::difference_type n = 0;
	while (_F != _L)
	{
		++_F;
		++n;
	}
	return n;
}
template<class _RAI>
inline typename iterator_traits<_RAI>::difference_type
__distance(_RAI _F, _RAI _L, input_iterator_tag)
{
	typename iterator_traits<_RAI>::difference_type n = 0;
	return _L - _F;
}

template<class _II>
inline typename iterator_traits<_II>::difference_type
distance(_II _F, _II _L, input_iterator_tag)
{
	return __distance(_F, _L, iterator_category(_F));
}

迭代器失效的场景

可以指向元素的工具：迭代器、指针和引用。有时，虽然迭代器失效，但指针和引用不一定失效。

除了元素的迭代器失效的问题，还要考虑容器end这个迭代器是否失效的问题。end() 特性：只要元素数变了，之前拿到的 end() 立刻失效。

vector、string

  1. 只要涉及到扩容，全部迭代器都会失效（包括迭代器、指针和引用）。
  2. insert、push_back：之后，插入点（插入后，放的是新元素）到末尾，这一范围全失效（迭代器、指针和引用）。插入点之前的不受影响。
    1. end() 迭代器失效
  3. erase：之后，删除点（删除后，放的是下一个元素）到末尾，这一范围全失效（迭代器、指针和引用）。删除点之前的不受影响。
    1. end() 迭代器失效

deque

deque 不是一整块连续内存，而是多块定长缓冲区 + 一张“块索引表”(map)。
插入可能导致扩容（新分配一个连续内存段）。

迭代器里不仅有元素指针，还带着指向块及索引表的位置；一旦在两端扩展需要改动索引表，所有迭代器都会失效。但元素本身通常没搬家，所以引用/指针多数仍然有效（除非你删的就是它，或在中间插入/删除导致元素搬动）。这正是它与 vector/list 最大的差异。

  1. 插入
    1. 首尾插入
      1. 规定所有的迭代器失效（不包括指针、引用）。
      2. 引用/指针通常仍指向原元素，不失效！
        1. 无论是否扩容，其他的元素都是保留在原位置的，因此其他元素的引用/指针不受影响。
    2. 在中间插入
      1. 所有全失效（包括迭代器、指针和引用）。
  2. 删除
    1. 首尾元素
      1. 被删除元素的迭代器、指针和引用失效。其他元素不影响！
      2. 如果删除的是首元素，容器的end迭代器不失效（不包括指针、引用）。
        1. 只有这一种情况不使 end() 失效，其他情况都不要用旧的end。
          1. 但是，有可能虽然是pop_front，但恰好容器中只有一个元素，此时end也会失效。
      3. 如果删除的是尾元素，容器的end迭代器会失效（不包括指针、引用）。
    2. 删除中间元素
      1. 所有全失效（包括迭代器、指针和引用）。

list

  1. insert：不会让迭代器失效（所有元素，包括新插入的，都不会失效）。
    1. 但是，插入后，插入点放的是新元素，原来位置的元素被挤到了右边。如果需要继续向右遍历，记得在插入之后单独做一次++。
  2. erase：之后，仅对删除的元素的迭代器失效。其他仍有效。

map、multimap、set、multiset

  1. insert：无影响：不会让迭代器、指针、引用失效（所有元素，包括新插入的，都不会失效）。
  2. erase：仅对删除的元素的迭代器、指针、引用失效。其他元素仍有效。

unordered_map、unordered_set

哈希表的插入，可能会存在容器增长导致重新哈希。
插入后，新容器的尺寸超过其容量阈值（计算方式为容器的 bucket_count 乘以其 max_load_factor），则会强制执行重新哈希。删除不涉及重新哈希。
在重新哈希后，容器中的所有迭代器都会失效。（指针、引用仍有效，即使重新哈希）

  1. insert：
    1. 如果不涉及到重新哈希。不会让迭代器、指针、引用失效（所有元素，包括新插入的，都不会失效）。
    2. 如果重新哈希，容器中的所有迭代器失效。（但指针、引用仍有效，即使重新哈希）
    3. 元素的指针、引用在所有情况下都保持有效，即使在重新哈希之后也是如此。
  2. erase：仅对删除的元素的迭代器、指针、引用失效。其他元素仍有效。

其他如queue、stack、priority_queue​

没有提供迭代器。不用谈失效的概念。

Array

  1. 固定大小；不会插/删；
  2. 修改元素值不使迭代器失效。
  3. swap(array) 不失效迭代器（指向同一块内存）。

练习_Cpp_多线程

发表于2022-03-05更新于2025-11-04阅读次数

内容

  1. 打印奇偶数
  2. 打印0~100
  3. 三线程依次打印A、B、C

两线程交替打印奇偶数

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<thread>
#include<mutex>
#include<condition_variable>
#include<iostream>
std::mutex data_mutex;
std::condition_variable data_cv;
bool oddtag = true;
void printodd()//打印奇数
{
    std::unique_lock<std::mutex> ulock(data_mutex);
    for(int odd = 1; odd <= 100; odd+=2)
    {
        while(oddtag != true)
        {
            data_cv.wait(ulock);
        }
        std::cout << "odd: " << odd << std::endl;
        oddtag = false;
        data_cv.notify_all();
    }
}
void printeven()//打印偶数
{
    std::unique_lock<std::mutex> ulock(data_mutex);
    for(int even = 2; even <= 100; even+=2)
    {
        while(oddtag == true)
        {
            data_cv.wait(ulock);
        }
        std::cout << "even: " << even << std::endl;
        oddtag = true;
        data_cv.notify_all();
    }
}
int main()
{
    std::thread thodd(printodd);
    std::thread theven(printeven);

    thodd.join();
    theven.join();
    return 0;
}

三线程打印0~100

最原始的忙等待版本

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>
using namespace std;
std::mutex g_mtx;
std::condition_variable cv;
int number = 0;
void fun0()
{
    while(number <= 100)
    {
        while(number%3 == 0 && number <= 100)
        {
            cout << "fun0 : " << number << endl;
            number += 1;
        }
    }
}
void fun1()
{
    while(number <= 100)
    {
        while(number%3 == 1 && number <= 100)
        {
            cout << "fun0 : " << number << endl;
            number += 1;
        }
    }
}
void fun2()
{
    while(number <= 100)
    {
        while(number%3 == 2 && number <= 100)
        {
            cout << "fun0 : " << number << endl;
            number += 1;
        }
    }
}

以上虽然也可以达到多线程打印0~100，但是存在忙等待问题。

尝试加锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
std::mutex g_mtx;
std::condition_variable cv;
int number = 0;
void fun0()
{
    unique_lock<std::mutex> locker(g_mtx);
    while(number <= 100)
    {
        while(number%3==0 && number <= 100)
        {
            cout << "fun : 0" << number << endl;
            number += 1;
            cv.notify_one();
        }
        cv.wait(locker);
    }
}
//...

但是这里又有问题了，有时候程序可以正常地打印完毕，而有时候则会死在某个位置。

因为notify_one有可能没有叫醒那个让程序正常运行下去的线程。

所以需要用到notify_all()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
std::mutex g_mtx;
std::condition_variable cv;
int number = 0;
void fun0()
{
    unique_lock<std::mutex> locker(g_mtx);
    while(number <= 100)
    {
        while(number%3==0 && number <= 100)
        {
            cout << "fun : 0" << number << endl;
            number += 1;
            cv.notify_all();
        }
        cv.wait(locker);
    }
}
//...

又有了新问题，为什么程序结束不了了？

最后一个人（其实是线程fun1）把自己wait挂起了，睡在了那里。因为它是最后打印的，wait了。别人都因为while退出了，没人去管他了。

所以需要在fun0或fun2线程退出外层while循环时进行再次notify_all进行解除。

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<iostream>
#include<thread>
#include<mutex>
#include<condition_variable>
using namespace std;
mutex mtx;
condition_variable cv;
int count = 1;

void print_1()
{
    unique_lock<mutex> locker(mtx);
    while(count <= 100)
    {
        while(count%3 == 1 && count <= 100)
        {
            cout << "print_1 : " << count << endl;
            count += 1;
            cv.notify_all();
        }
        cv.wait(locker);
    }
}
void print_2()
{
    unique_lock<mutex> locker(mtx);
    while(count <= 100)
    {
        while(count%3 == 2 && count <= 100)
        {
            cout << "print_2 : " << count << endl;
            count += 1;
            cv.notify_all();
        }
        cv.wait(locker);
    }
}
void print_3()
{
    unique_lock<mutex> locker(mtx);
    while(count <= 100)
    {
        while(count%3 == 0 && count <= 100)
        {
            cout << "print_3 : " << count << endl;
            count += 1;
            cv.notify_all();
        }
        cv.wait(locker);
    }
    cv.notify_all();
}
int main()
{
    thread t1(print_1);
    thread t2(print_2);
    thread t3(print_3);
    t1.join();
    t2.join();
    t3.join();
}

问题代码 - 未过滤边界, 造成数据溢出

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
#include<iostream>
#include<thread>
#include<mutex>
#include<condition_variable>
using namespace std;
mutex mtx;
condition_variable cv;
int count = 1;

void print_1()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 1)
        {
            cv.wait(locker);
        }
        cout << count << endl;
        ++count;
        cv.notify_all();
    }
}
void print_2()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 2)
        {
            cv.wait(locker);
        }
        cout << count << endl;
        ++count;
        cv.notify_all();
    }
}
void print_3()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 0)
        {
            cv.wait(locker);
        }
        cout << count << endl;
        ++count;
        cv.notify_all();
    }
}
int main()
{
    thread t1(print_1);
    thread t2(print_2);
    thread t3(print_3);
    t1.join();
    t2.join();
    t3.join();
}

运行结果是打印1到102。为什么呢？因为在while(count%3 != x){cv.wait(locker)}跳出后没有过滤count的大小是否超过了100。最外层的while(count <= 100)时，count==99时，线程1、线程2、线程3都进入其中，线程1顺利执行完毕，线程2、线程3被唤醒后，由于没有判断、过滤count的大小是否超过了100，则顺利走到下面打印代码部分，相当于漏网之鱼。

问题代码 - 某线程退出时未及时更新标识变量导致其他线程阻塞

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
#include<iostream>
#include<thread>
#include<mutex>
#include<condition_variable>
using namespace std;
mutex mtx;
condition_variable cv;
int count = 1;

void print_1()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 1)
        {
            cv.wait(locker);
        }
        if(count <= 100)
        {
            cout << count << endl;
            ++count;
        }
        cv.notify_all();
    }
}
void print_2()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 2)
        {
            cv.wait(locker);
        }
        if(count <= 100)
        {
            cout << count << endl;
            ++count;
        }
        cv.notify_all();
    }
}
void print_3()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 0)
        {
            cv.wait(locker);
        }
        if(count <= 100)
        {
            cout << count << endl;
            ++count;
        }
        cv.notify_all();
    }
}
int main()
{
    thread t1(print_1);
    thread t2(print_2);
    thread t3(print_3);
    t1.join();
    t2.join();
    t3.join();
}

这次的打印效果是：1到100，数目是正确的，不多不少。但是，更尴尬的问题来了，居然在打印100之后阻塞死了！这说明有的线程再也跳不出条件变量上的等待队列了。

关键的解决方法：把每条线程中最后的++count语句放到if(count <= 100)语句外边。

为什么呢？因为如果++count在if(count <= 100)才能执行时，就会造成一个问题：线程1判断count <= 100通过，可以打印100，之后，++count，此时count为101；此时关键处：线程2，判断count <= 100不通过，那么，++count未能执行；这给线程3造成了很大的麻烦：来到了线程3，由于它处在while(count%3 != x){cv.wait(locker)}语句中，被线程2唤醒后判断count%3 == 0，由于count在上个线程没有更新，所以count%3 != 0，这让线程3没能够跳出wait的魔爪。之后，线程1、线程2开心的自己走了，丢下线程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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<thread>
#include<mutex>
#include<condition_variable>
using namespace std;
mutex mtx;
condition_variable cv;
int count = 1;

void print_1()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 1)
        {
            cv.wait(locker);
        }
        if(count <= 100)
        {
            cout << count << endl;
        }
        ++count;
        cv.notify_all();
    }
}
void print_2()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 2)
        {
            cv.wait(locker);
        }
        if(count <= 100)
        {
            cout << count << endl;
        }
        ++count;
        cv.notify_all();
    }
}
void print_3()
{
    unique_lock<mutex> locker(mtx);
    while(count<= 100)
    {
        while(count%3 != 0)
        {
            cv.wait(locker);
        }
        if(count <= 100)
        {
            cout << count << endl;
        }
        ++count;
        cv.notify_all();
    }
}
int main()
{
    thread t1(print_1);
    thread t2(print_2);
    thread t3(print_3);
    t1.join();
    t2.join();
    t3.join();
}

三线程循环打印若干次ABC

如果不加任何控制，则代码如下

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<thread>
#include<mutex>
#include<condition_variable>
using namespace std;
void print_a()
{
    for(int i = 0; i < 10; ++i)
    {
        cout << "A";
    }
}
void print_b()
{
    for(int i = 0; i < 10; ++i)
    {
        cout << "B";
    }
}
void print_c()
{
    for(int i = 0; i < 10; ++i)
    {
        cout << "C";
    }
}
int main()
{
    thread t1(print_a);
    thread t2(print_b);
    thread t3(print_c);
    t1.join();
    t2.join();
    t3.join();
}

这样的打印将会错乱无章。

需要加线程控制。

下面来说一种方案 - 互斥量+条件变量+标记

1
2
3
std::mutex mtx;
std::condition_variable cv;
int isReady = 0;	//标记该打印第几个字母了

常犯的错误

没有初始化locker

应在三个函数最开始初始化locker。

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
mutex mtx;
void print_a()
{
    unique_lock<mutex> locker(mtx);	// must have
    for(int i = 0; i<10; ++i)
    {
        ...
    }
}
void print_b()
{
    unique_lock<mutex> locker(mtx);	// must have
    for(int i = 0; i<10; ++i)
    {
        ...
    }
}
void print_c()
{
    unique_lock<mutex> locker(mtx);	// must have
    for(int i = 0; i<10; ++i)
    {
        ...
    }
}

wait外围的条件写的是if而不是while

以print_a函数举例。

1
2
3
4
if(isReady%3 != 0)
{
    cv.wait(locker);
}

这是错误的，因为一共有三个线程，每次唤醒时，另外两个人不一定谁能抢到锁，如果唤醒后就直接退出wait，则无法保证线程同步。

最终正确的代码

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
#include<iostream>
#include<thread>
#include<mutex>
#include<condition_variable>
using namespace std;
mutex mtx;
condition_variable cv;
int isReady = 0;

void print_a()
{
    unique_lock<mutex> locker(mtx);
    for(int i = 0; i < 10; ++i)
    {
        while(isReady != 0)
        {
            cv.wait(locker);
        }
        cout << "A";
        isReady = 1;
        cv.notify_all();
    }
}
void print_b()
{
    unique_lock<mutex> locker(mtx);
    for(int i = 0; i < 10; ++i)
    {
        while(isReady != 1)
        {
            cv.wait(locker);
        }
        cout << "B";
        isReady = 2;
        cv.notify_all();
    }
}
void print_c()
{
    unique_lock<mutex> locker(mtx);
    for(int i = 0; i < 10; ++i)
    {
        while(isReady != 2)
        {
            cv.wait(locker);
        }
        cout << "C";
        isReady = 0;
        cv.notify_all();
    }
}
int main()
{
    thread t1(print_a);
    thread t2(print_b);
    thread t3(print_c);
    t1.join();
    t2.join();
    t3.join();
}

另外，还有一个容易出错的地方，必须notify_all()，而不能notify_one()。因为如果只唤醒1个的话，有可能是A打印完之后唤醒C，这样C线程不符合条件，继续沉睡，而B线程再也没人唤醒它了，之后三人就都沉睡下去了。

打印奇偶数进阶版

现有函数printNumber可以用一个整数参数调用，并输出该整数到控制台。
例如，调用printNumber(7)将会输出7到控制台。

给你类ZeroEvenOdd的一个实例，该类中有三个函数：zero、even和odd。ZeroEvenOdd的相同实例将会传递给三个不同线程：

线程A：调用zero()，只输出0
线程B：调用even()，只输出偶数
线程C：调用odd()，只输出奇数
修改给出的类，以输出序列010203040506070809010011012...，其中总共打印的数字数目必须为2n。

实现ZeroEvenOdd类：

ZeroEvenOdd(int n)用数字n初始化对象，表示需要输出的数。
void zero(printNumber)调用printNumber以输出一个0。
void even(printNumber)调用printNumber以输出偶数。
void odd(printNumber)调用printNumber以输出奇数。

示例1：

1
2
3
输入：n = 2
输出："0102"
解释：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。

示例 2：

1
2
输入：n = 5
输出："0102030405"

提示：1 <= n <= 1000

Leet-code AC版代码

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
class ZeroEvenOdd {
private:
    int n;
    mutex mtx;
    condition_variable cv;
    int num = 1;
    bool flag = true;
public:
    ZeroEvenOdd(int n) {
        this->n = n;
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber)
    {
        unique_lock<mutex> locker(mtx);
        while(num <= n)
        {
            while(flag != true)
            {
                cv.wait(locker);
            }
            if(num <= n)
            {
                printNumber(0);
            }
            flag = false;
            cv.notify_all();
        }
    }
    // 偶数
    void even(function<void(int)> printNumber)
    {
        unique_lock<mutex> locker(mtx);
        while(num <= n)
        {
            while(flag == true || num%2 != 0)
            {
                cv.wait(locker);
            }
            if(num <= n)
            {
                printNumber(num);
            }
            ++num;
            flag = true;
            cv.notify_all();
        }
    }
    // 奇数
    void odd(function<void(int)> printNumber)
    {
        unique_lock<mutex> locker(mtx);
        while(num <= n)
        {
            while(flag == true || num%2 != 1)
            {
                cv.wait(locker);
            }
            if(num <= n)
            {
                printNumber(num);
            }
            ++num;
            flag = true;
            cv.notify_all();
        }
    }
};

自测试版代码

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
#include<thread>
#include<mutex>
#include<condition_variable>
#include<functional>
#include<iostream>
using namespace std;
int n = 100;
mutex mtx;
condition_variable cv;
int num = 1;
bool flag = true;

void zero()
{
    unique_lock<mutex> locker(mtx);
    while (num <= n)
    {
        while (flag != true)
        {
            cv.wait(locker);
        }
        if (num <= n)
        {
            cout << 0;
        }
        flag = false;
        cv.notify_all();
    }
}
// 偶数
void even()
{
    unique_lock<mutex> locker(mtx);
    while (num <= n)
    {
        while (flag == true || num % 2 != 0)
        {
            cv.wait(locker);
        }
        if (num <= n)
        {
            cout << num;
        }
        ++num;
        flag = true;
        cv.notify_all();
    }
}
// 奇数
void odd()
{
    unique_lock<mutex> locker(mtx);
    while (num <= n)
    {
        while (flag == true || num % 2 != 1)
        {
            cv.wait(locker);
        }
        if (num <= n)
        {
            cout << num;
        }
        ++num;
        flag = true;
        cv.notify_all();
    }
}
int main()
{
    thread t0(zero);
    thread t1(odd);
    thread t2(even);

    t0.join();
    t1.join();
    t2.join();
}

结果

image-20220525193318608