Jiancong Li's Blog
0%

Posted on Edited on In

概述

首先我们对于乘法溢出的判断，先写测试用例：

1592715337389

由上图我们简化测试用例：

1592715602260

我们可以这样设计乘法溢出函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// 判断两入参相乘是否溢出，溢出返回true，否则返回false
bool is_multi_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 同为正号
      return x > INT_MAX/y;
  } else if (x < 0 && y < 0) {
    /// 同为负号
    if (y == INT_MIN && x <= -1) {
      return true;
    }
    return x < INT_MIN/-y;
  } else if (x > 0 && y<0 || (x < 0 && y > 0)) {
    /// 异号的情况稍等补上
    return false;
  } else {
    return false;
  }
}

接下来我们添加测试用例

1592727579022

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 <cassert>
#include <iostream>
#include <numeric>

/// 判断两入参相乘是否溢出，溢出返回true，否则返回false
bool is_multi_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 同为正号
      return x > INT_MAX/y;
  } else if (x < 0 && y < 0) {
    /// 同为负号
    if (y == INT_MIN && x <= -1) {
      return true;
    }
    return x < INT_MIN/-y;
  } else if (x > 0 && y<0 || (x < 0 && y > 0)) {
    /// 异号的情况稍等补上
    return false;
  } else {
    return false;
  }
}

int main() {
  int x = 0;
  int y = 0;
  int max_num = std::numeric_limits<int>::max();
  int min_num = std::numeric_limits<int>::min();

  /// case 1 #1
  x = 7;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));
  x = max_num - 1;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));

  /// case 1 #2
  x = 7;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));
  x = max_num - 1;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));

  /// case 2 #1
  x = -7;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));
  x = min_num + 1;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));

  /// case 2 #2
  x = -7;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));
  x = min_num + 1;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));
}

接下来为特殊数值来添加判断：

1592727736048

添加异号情况的判断：

1592730284047

把函数改为模板，一并添加测试用例：

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
#include <cassert>
#include <iostream>
#include <numeric>

/// 判断两入参相乘是否溢出，溢出返回true，否则返回false
template <typename T1, typename T2>
bool is_multi_overflow(T1 x, T2 y) {
  static_assert(std::is_same<T1, T2>::value,
                "is_multi_overflow need same type!");
  static_assert(std::is_integral<T1>::value,
                " is_multi_overflow need integral type!");
  int num_max = std::numeric_limits<T1>::max();
  int num_min = std::numeric_limits<T1>::min();
  if (x == 0 || y == 0 || x == 1 || y == 1) {
    return false;
  }
  if (x == -1) {
    return y == num_min;
  } else if (y == -1) {
    return x == num_min;
  }

  if (x > 0 && y > 0) {
    /// 同为正号
    return x > num_max / y;
  } else if (x < 0 && y < 0) {
    /// 同为负号
    if (y == num_min && x <= -1) {
      return true;
    }
    return x < num_min / -y;
  } else if (x > 0 && y < 0 || (x < 0 && y > 0)) {
    /// 异号的情况
    if (x > y) {
      std::swap(x, y);
    }
    return x < num_min / y;
  } else {
    return false;
  }
}

int main() {
  int x = 0;
  int y = 0;
  int max_num = std::numeric_limits<int>::max();
  int min_num = std::numeric_limits<int>::min();

  /// case 1 #1
  x = 7;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));
  x = max_num - 1;
  y = 1 + max_num / x;
  assert(is_multi_overflow(x, y));

  /// case 1 #2
  x = 7;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));
  x = max_num - 1;
  y = max_num / x;
  assert(!is_multi_overflow(x, y));

  /// case 2 #1
  x = -7;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));
  x = min_num + 1;
  y = -1 + min_num / -x;
  assert(is_multi_overflow(x, y));

  /// case 2 #2
  x = -7;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));
  x = min_num + 1;
  y = min_num / -x;
  assert(!is_multi_overflow(x, y));

  /// case 3
  x = 0;
  y = max_num;
  assert(!is_multi_overflow(x, y));
  x = min_num;
  y = 0;
  assert(!is_multi_overflow(x, y));
  x = 0;
  y = 0;
  assert(!is_multi_overflow(x, y));

  /// case 4
  x = 1;
  y = max_num;
  assert(!is_multi_overflow(x, y));
  x = INT_MIN;
  y = 1;
  assert(!is_multi_overflow(x, y));

  /// case 5
  x = -1;
  y = max_num;
  assert(!is_multi_overflow(x, y));
  x = -1;
  y = min_num;
  assert(is_multi_overflow(x, y));

  /// case 6
  x = 2;
  y = min_num / 2;
  assert(!is_multi_overflow(x, y));
  assert(!is_multi_overflow(y, x));
  x = 2;
  y = -1 + min_num / 2;
  assert(is_multi_overflow(x, y));
  assert(is_multi_overflow(y, x));
}

最后附上完整测试用例：

1592730393076

后记

我们既然有了判断乘法溢出的函数，我们可以借此封装一个带有检查溢出的乘法函数。

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

template <typename T1, typename T2>
std::optional<T1> multiplies_s(const T1 x, const T2 y) noexcept {
  static_assert(std::is_same<T1, T2>::value, "Multiplies_s need same type!");
  static_assert(std::is_integral<T1>::value,
                "Multiplies_s need integral type!");
  if (is_multi_overflow(x, y)) return {};
  return x * y;
}

int main()
{
  int x = 5;
  int y = 5;
  int result = multiplies_s(x, y).value_or(0);
}

Posted on Edited on In

虚析构函数问题

引用标准中原文： 一条有用的方针，是任何基类的析构函数必须为公开且虚， 或受保护且非虚。

虚析构这个概念被设计出来就是为了解决基类指针指向派生类实例的析构问题，当一个基类指针指向派生类实例然后进行delete该指针时，只会执行基类析构函数而派生类的析构函数不会被执行，这将导致派生类构造的资源不会被正确释放，造成内存泄漏。如下示例：

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 <iostream>

struct Base
{
     Base() { std::cout << "Base Construct!" << std::endl; }
     /// 该析构函数为错误示例，严禁这样写.
     ~Base() { std::cout << "Base Deconstruct!" << std::endl; }
};

struct Derived : public Base
{
    Derived()   { std::cout << "Derived Construct!" << std::endl; }
    ~Derived() { std::cout << "Derived Deconstruct!" << std::endl; }
};

int main()
{
    {
        /** 使用基类指针指向派生类实例 */
        Base* BasePtr = new Derived;
        delete BasePtr;
    }
    system("pause");
}

运行结果：

Virtual DeConstruct Debug

可以看到派生类没有被析构，如要解决该问题在基类析构函数处加上virtual关键字即可。

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 <iostream>

struct Base
{
     Base() { std::cout << "Base Construct!" << std::endl; }
     /** 正确写法： 加上关键字virtual， 后面函数体可写可不写，或者直接使用=default都行。 */
     virtual ~Base() { std::cout << "Base Deconstruct!" << std::endl; }
};

struct Derived : public Base
{
    Derived()   { std::cout << "Derived Construct!" << std::endl; }
    ~Derived() { std::cout << "Derived Deconstruct!" << std::endl; }
    /// 或者 virtual ~Derived() override {}
};

int main()
{
    {
        /** 使用基类指针指向派生类实例 */
        Base* BasePtr = new Derived;
        delete BasePtr;
    }
    system("pause");
}

运行结果：

Virtual DeConstruct Debug Correct

Posted on Edited on In

PlantUML语法学习

类图

类之间的关系

类之间的关系通过下面的符号定义:

类之间的关系

1
2
3
4
5
6
7
@startuml
Class01 <|-- Class02
Class03 *-- Class04
Class05 o-- Class06
Class07 .. Class08
Class09 -- Class10
@enduml

class1

1
2
3
4
5
6
7
@startuml
Class11 <|.. Class12
Class13 --> Class14
Class15 ..> Class16
Class17 ..|> Class18
Class19 <--* Class20
@enduml

class2

1
2
3
4
5
6
7
@startuml
Class21 #-- Class22
Class23 x-- Class24
Class25 }-- Class26
Class27 +-- Class28
Class29 ^-- Class30
@enduml

class3

关系上的标识

在关系之间使用标签来说明时, 使用: 后接标签文字。
对元素的说明，你可以在每一边使用”” 来说明.

1
2
3
4
5
@startuml
Class01 "1" *-- "many" Class02 : contains
Class03 o-- Class04 : aggregation
Class05 --> "1" Class06
@enduml

class4

在标签的开始或结束位置添加< 或> 以表明是哪个对象作用到哪个对象上。

1
2
3
4
5
6
@startuml
class Car
Driver - Car : drives >
Car *- Wheel : have 4 >
Car -- Person : < owns
@enduml

class5

添加方法

为了声明字段(对象属性）或者方法，你可以使用后接字段名或方法名。
系统检查是否有括号来判断是方法还是字段。

1
2
3
4
5
6
@startuml
Object <|-- ArrayList
Object : equals()
ArrayList : Object[] elementData
ArrayList : size()
@enduml

class6

也可以使用{} 把字段或者方法括起来
注意，这种语法对于类型/名字的顺序是非常灵活的。

1
2
3
4
5
6
7
8
9
10
@startuml
class Dummy {
String data
void methods()
}
class Flight {
flightNumber : Integer
departureTime : Date
}
@enduml

class7

你可以（显式地）使用{field} 和{method} 修饰符来覆盖解析器的对于字段和方法的默认行为

1
2
3
4
5
6
@startuml
class Dummy {
{field} A field (despite parentheses)
{method} Some method
}
@enduml

class8

定义可访问性

一旦你定义了域或者方法，你可以定义相应条目的可访问性质。
定义可访问性

1
2
3
4
5
6
7
8
@startuml
class Dummy {
-field1
#field2
~method1()
+method2()
}
@enduml

class9

你可以采用命令（skinparam classAttributeIconSize 0 ：)停用该特性

1
2
3
4
5
6
7
8
9
@startuml
skinparam classAttributeIconSize 0
class Dummy {
-field1
#field2
~method1()
+method2()
}
@enduml

class10

抽象与静态

通过修饰符{static} 或者{abstract}，可以定义静态或者抽象的方法或者属性。
这些修饰符可以写在行的开始或者结束。也可以使用{classifier} 这个修饰符来代替{static}.

1
2
3
4
5
6
@startuml
class Dummy {
{static} String id
{abstract} void methods()
}
@enduml

class11

高级类体

PlantUML 默认自动将方法和属性重新分组，你可以自己定义分隔符来重排方法和属性，下面的分隔符都
是可用的：– .. == __.
还可以在分隔符中添加标题

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
@startuml
class Foo1 {
You can use
several lines
..
as you want
and group
==
things together.
__
You can have as many groups
as you want
--
End of class
}
class User {
.. Simple Getter ..
+ getName()
+ getAddress()
.. Some setter ..
+ setName()
__ private data __
int age
-- encrypted --
String password
}
@enduml

class12

更多注释

可以在注释中使用部分html 标签：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@startuml
class Foo
note left: On last defined class
note top of Object
In java, <size:18>every</size> <u>class</u>
<b>extends</b>
<i>this</i> one.
end note
note as N1
This note is <u>also</u>
<b><color:royalBlue>on several</color>
<s>words</s> lines
And this is hosted by <img:sourceforge.jpg>
end note
@enduml

class13

对象图

对象的定义

使用关键字object 定义实例。

1
2
3
4
@startuml
object firstObject
object "My Second Object" as o2
@enduml

如下图生成：

object1

对象之间的关系

对象之间的关系可以用如下符号定义：

对象之间的关系

也可以用.. 来代替– 以使用点线。
知道了这些规则，就可以画下面的图：
可以用冒号给关系添加标签，标签内容紧跟在冒号之后。
用双引号在关系的两边添加基数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@startuml
object Object01
object Object02
object Object03
object Object04
object Object05
object Object06
object Object07
object Object08
Object01 <|-- Object02
Object03 *-- Object04
Object05 o-- "4" Object06
Object07 .. Object08 : some labels
@enduml

如下图生成：

object2

添加属性

用冒号加属性名的形式声明属性。

1
2
3
4
5
@startuml
object user
user : name = "Dummy"
user : id = 123
@enduml

如下图生成：

object3

活动图

简单活动

使用(*) 作为活动图的开始点和结束点。
有时，你可能想用(*top) 强制开始点位于图示的顶端。
使用–> 绘制箭头。

1
2
3
4
@startuml
(*) --> "First Activity"
"First Activity" --> (*)
@enduml

activity1

箭头上的标签

默认情况下，箭头开始于最接近的活动。
可以用[ 和 ] 放在箭头定义的后面来添加标签。

1
2
3
4
5
@startuml
(*) --> "First Activity"
-->[You can put also labels] "Second Activity"
--> (*)
@enduml

activity2

改变箭头方向

你可以使用-> 定义水平方向箭头，还可以使用下列语法强制指定箭头的方向：

  • -down-> (default arrow)
  • -right-> or ->
  • -left->
  • -up->

activity3

分支

你可以使用关键字if/then/else 创建分支。

1
2
3
4
5
6
7
8
9
10
11
@startuml
(*) --> "Initialization"
if "Some Test" then
-->[true] "Some Activity"
--> "Another activity"
-right-> (*)
else
->[false] "Something else"
-->[Ending process] (*)
endif
@enduml

activity4

不过，有时你可能需要重复定义同一个活动：

1
2
3
4
5
6
7
8
9
10
@startuml
(*) --> "check input"
If "input is verbose" then
--> [Yes] "turn on verbosity"
--> "run command"
else
--> "run command"
Endif
-->(*)
@enduml

activity5

更多分支

默认情况下，一个分支连接上一个最新的活动，但是也可以使用if 关键字进行连接。
还可以嵌套定义分支。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@startuml
(*) --> if "Some Test" then
-->[true] "activity 1"
if "" then
-> "activity 3" as a3
else
if "Other test" then
-left-> "activity 5"
else
--> "activity 6"
endif
endif
else
->[false] "activity 2"
endif
a3 --> if "last test" then
--> "activity 7"
else
-> "activity 8"
endif
@enduml

activity6

注释

你可以在活动定义之后用note left, note right, note top or note bottom, 命令给活动添加注释。
如果想给开始点添加注释，只需把注释的定义放在活动图最开始的地方即可。
也可以用关键字endnote 定义多行注释。

1
2
3
4
5
6
7
8
9
@startuml
(*) --> "Some Activity"
note right: This activity has to be defined
"Some Activity" --> (*)
note left
This note is on
several lines
end note
@enduml

activity7

分区

用关键字partition 定义分区，还可以设置背景色(用颜色名或者颜色值)。
定义活动的时候，它自动被放置到最新的分区中。
用} 结束分区的定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
@startuml
partition Conductor {
(*) --> "Climbs on Platform"
--> === S1 ===
--> Bows
}
partition Audience #LightSkyBlue {
=== S1 === --> Applauds
}
partition Conductor {
Bows --> === S2 ===
--> WavesArmes
Applauds --> === S2 ===
}
partition Orchestra #CCCCEE {
WavesArmes --> Introduction
--> "Play music"
}
@enduml

activity8

一个完整的例子

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
@startuml
title Servlet Container
(*) --> "ClickServlet.handleRequest()"
--> "new Page"
if "Page.onSecurityCheck" then
->[true] "Page.onInit()"
if "isForward?" then
->[no] "Process controls"
if "continue processing?" then
-->[yes] ===RENDERING===
else
-->[no] ===REDIRECT_CHECK===
endif
else
-->[yes] ===RENDERING===
endif
if "is Post?" then
-->[yes] "Page.onPost()"
--> "Page.onRender()" as render
--> ===REDIRECT_CHECK===
else
-->[no] "Page.onGet()"
--> render
endif
else
-->[false] ===REDIRECT_CHECK===
endif
if "Do redirect?" then
->[yes] "redirect request"
--> ==BEFORE_DESTROY===
else
if "Do Forward?" then
-left->[yes] "Forward request"
--> ==BEFORE_DESTROY===
else
-right->[no] "Render page template"
--> ==BEFORE_DESTROY===
endif
endif
--> "Page.onDestroy()"
-->(*)
@enduml

activity9

界面格式相关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
@startuml
skinparam SequenceGroupBodyBackgroundColor #FFFFFF90

box "Internal Service" #LightBlue
    participant Bob
    participant Alice
end box

box "Other" #LightGreen
    participant Other
end box

group group
    Bob -> Alice : hello
    Alice -> Other : hello
end
@enduml

skinparam_uml_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
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
@startuml

!unquoted procedure $DrawColor($colour)

    skinparam rectangle {
            backgroundColor<<$colour>> $colour
            borderColor<<$colour>> $colour
            shadowing<<$colour>> true
            BorderThickness<<$colour>> 1
        }

    rectangle $colour <<$colour>> as "<color:$colour></color>"

!endprocedure

package HexCodes {
$DrawColor("00ff00")
$DrawColor("ff0000")
$DrawColor("0000ff")
$DrawColor("123456")
$DrawColor("654321")
$DrawColor("165432")
$DrawColor("ff22ff")
}

package Colours {
$DrawColor("APPLICATION")
$DrawColor("AliceBlue")
$DrawColor("AntiqueWhite")
$DrawColor("Aqua")
$DrawColor("Aquamarine")
$DrawColor("Azure")
$DrawColor("BUSINESS")
$DrawColor("Beige")
$DrawColor("Bisque")
$DrawColor("Black")
$DrawColor("BlanchedAlmond")
$DrawColor("Blue")
$DrawColor("BlueViolet")
$DrawColor("Brown")
$DrawColor("BurlyWood")
$DrawColor("CadetBlue")
$DrawColor("Chartreuse")
$DrawColor("Chocolate")
$DrawColor("Coral")
$DrawColor("CornflowerBlue")
$DrawColor("Cornsilk")
$DrawColor("Crimson")
$DrawColor("Cyan")
$DrawColor("DarkBlue")
$DrawColor("DarkCyan")
$DrawColor("DarkGoldenRod")
$DrawColor("DarkGray")
$DrawColor("DarkGreen")
$DrawColor("DarkGrey")
$DrawColor("DarkKhaki")
$DrawColor("DarkMagenta")
$DrawColor("DarkOliveGreen")
$DrawColor("DarkOrchid")
$DrawColor("DarkRed")
$DrawColor("DarkSalmon")
$DrawColor("DarkSeaGreen")
$DrawColor("DarkSlateBlue")
$DrawColor("DarkSlateGray")
$DrawColor("DarkSlateGrey")
$DrawColor("DarkTurquoise")
$DrawColor("DarkViolet")
$DrawColor("Darkorange")
$DrawColor("DeepPink")
$DrawColor("DeepSkyBlue")
$DrawColor("DimGray")
$DrawColor("DimGrey")
$DrawColor("DodgerBlue")
$DrawColor("FireBrick")
$DrawColor("FloralWhite")
$DrawColor("ForestGreen")
$DrawColor("Fuchsia")
$DrawColor("Gainsboro")
$DrawColor("GhostWhite")
$DrawColor("Gold")
$DrawColor("GoldenRod")
$DrawColor("Gray")
$DrawColor("Green")
$DrawColor("GreenYellow")
$DrawColor("Grey")
$DrawColor("HoneyDew")
$DrawColor("HotPink")
$DrawColor("IMPLEMENTATION")
$DrawColor("IndianRed")
$DrawColor("Indigo")
$DrawColor("Ivory")
$DrawColor("Khaki")
$DrawColor("Lavender")
$DrawColor("LavenderBlush")
$DrawColor("LawnGreen")
$DrawColor("LemonChiffon")
$DrawColor("LightBlue")
$DrawColor("LightCoral")
$DrawColor("LightCyan")
$DrawColor("LightGoldenRodYellow")
$DrawColor("LightGray")
$DrawColor("LightGreen")
$DrawColor("LightGrey")
$DrawColor("LightPink")
$DrawColor("LightSalmon")
$DrawColor("LightSeaGreen")
$DrawColor("LightSkyBlue")
$DrawColor("LightSlateGray")
$DrawColor("LightSlateGrey")
$DrawColor("LightSteelBlue")
$DrawColor("LightYellow")
$DrawColor("Lime")
$DrawColor("LimeGreen")
$DrawColor("Linen")
$DrawColor("MOTIVATION")
$DrawColor("Magenta")
$DrawColor("Maroon")
$DrawColor("MediumAquaMarine")
$DrawColor("MediumBlue")
$DrawColor("MediumOrchid")
$DrawColor("MediumPurple")
$DrawColor("MediumSeaGreen")
$DrawColor("MediumSlateBlue")
$DrawColor("MediumSpringGreen")
$DrawColor("MediumTurquoise")
$DrawColor("MediumVioletRed")
$DrawColor("MidnightBlue")
$DrawColor("MintCream")
$DrawColor("MistyRose")
$DrawColor("Moccasin")
$DrawColor("NavajoWhite")
$DrawColor("Navy")
$DrawColor("OldLace")
$DrawColor("Olive")
$DrawColor("OliveDrab")
$DrawColor("Orange")
$DrawColor("OrangeRed")
$DrawColor("Orchid")
$DrawColor("PHYSICAL")
$DrawColor("PaleGoldenRod")
$DrawColor("PaleGreen")
$DrawColor("PaleTurquoise")
$DrawColor("PaleVioletRed")
$DrawColor("PapayaWhip")
$DrawColor("PeachPuff")
$DrawColor("Peru")
$DrawColor("Pink")
$DrawColor("Plum")
$DrawColor("PowderBlue")
$DrawColor("Purple")
$DrawColor("Red")
$DrawColor("RosyBrown")
$DrawColor("RoyalBlue")
$DrawColor("STRATEGY")
$DrawColor("SaddleBrown")
$DrawColor("Salmon")
$DrawColor("SandyBrown")
$DrawColor("SeaGreen")
$DrawColor("SeaShell")
$DrawColor("Sienna")
$DrawColor("Silver")
$DrawColor("SkyBlue")
$DrawColor("SlateBlue")
$DrawColor("SlateGray")
$DrawColor("SlateGrey")
$DrawColor("Snow")
$DrawColor("SpringGreen")
$DrawColor("SteelBlue")
$DrawColor("TECHNOLOGY")
$DrawColor("Tan")
$DrawColor("Teal")
$DrawColor("Thistle")
$DrawColor("Tomato")
$DrawColor("Turquoise")
$DrawColor("Violet")
$DrawColor("Wheat")
$DrawColor("White")
$DrawColor("WhiteSmoke")
$DrawColor("Yellow")
$DrawColor("YellowGreen")

}
@enduml

color_uml

附注

PlantUML资料

Posted on Edited on In

progschj/thread_pool

Github上这个库(progschj/thread_pool)的点赞最多，学习一下。

接口定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class ThreadPool {
 public:
  ThreadPool(size_t);
  /// 任务入列
  template <class F, class... Args>
  auto enqueue(F&& f, Args&&... args)
      -> std::future<typename std::invoke_result<F(Args...)>::type>;
  ~ThreadPool();

 private:
  /// 所有的工作线程
  std::vector<std::thread> workers;
  /// 任务队列
  std::queue<std::function<void()> > tasks;

  /// 用于同步的互斥锁和条件变量
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;  ///< 用于判断所有线程是否需要结束
};

构造函数和消费者实现

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
/// @name     ThreadPool
/// @brief    用于创建若干个线程，并规定消费者函数
///
/// @param    threads   [in]    要创建的线程数量
///
/// @return   NONE
///
/// @date     2020-06-27 16:17:50
/// @warning  线程安全
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i)
    workers.emplace_back([this] {
      for (;;) {
        std::function<void()> task;

        {
          /// 获取同步锁
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          /// 阻塞等待获取任务，直到任务队列不为空
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          /// 如果stop标志位为true，且任务列表都执行完毕后，该线程退出
          if (this->stop && this->tasks.empty()) return;
          /// 从任务队列中拿出来一个任务
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }  ///< 这里释放锁

        /// 执行该任务函数
        task();
      }
    });
}

析构函数

1
2
3
4
5
6
7
8
9
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  /// 在stop位, 置为true后通知所有线程执行一次，然后等待所有线程处理完任务后join()
  condition.notify_all();
  for (std::thread& worker : workers) worker.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
/// @name     enqueue
/// @brief    用于添加任务函数到任务队列中
///
/// @param    f     [in]    任务函数
/// @param    args  [in]    任务函数的入参列表
///
/// @return   取决于任务函数的返回值
///
/// @date     2020-06-27 16:06:30
/// @warning  线程安全
template <class F, class... Args>
auto ThreadPool::enqueue(F&& f, Args&&... args)
    -> std::future<typename std::invoke_result<F(Args...)>::type> {
  using return_type = typename std::invoke_result<F(Args...)>::type;

  /// 这里封装一个异步的线程并执行刚刚传入的函数，这个函数通过bind改类型为void()
  auto task = std::make_shared<std::packaged_task<return_type()> >(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  /// 创建一个这个函数的未来的值， 这个未来值不获取就不会进行计算
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);

    /// 假如说没有让这个线程停止则继续，否则抛出异常阻止线程池结束后在入列
    if (stop) throw std::runtime_error("enqueue on stopped ThreadPool");
    /// 这个封装好的函数放入任务列表中
    tasks.emplace([task]() { (*task)(); });
  }
  /// 通知一个阻塞中的线程，任务队列中有任务了
  condition.notify_one();
  return res;
}

Posted on Edited on In

std::async介绍

下面是一个很好的并行计算的例子。

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 <future>
#include <iostream>
#include <string>

bool is_prime(int x)
{
    for (int i = 2; i < x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}

int main()
{
    /** is_prime(700020007)这个函数调用隐藏于主线程，异步执行 */
    std::future<bool> fut = std::async(is_prime, 700020007);
    std::cout << "please wait";
    std::chrono::milliseconds span(100);
    /** 这个异步调用函数等待100ms，如果没有计算完就继续等待 */
    while (fut.wait_for(span) != std::future_status::ready)
        std::cout << ".";
    std::cout << std::endl;

    /** 计算完毕后，获取函数返回值 */
    std::cout << "final result: " << std::boolalpha << fut.get() << std::endl;

    system("pause");
    return 0;
}

std::async中的第一个参数是启动策略，它控制std::async的异步行为，我们可以用三种不同的启动策略来创建std::async
·std::launch::async
保证异步行为，即传递函数将在单独的线程中执行
·std::launch::deferred
当其他线程调用get()来访问共享状态时，将调用非异步行为
·std::launch::async | std::launch::deferred
默认行为。有了这个启动策略，它可以异步运行或不运行，这取决于系统的负载，但我们无法控制它。

见下面例子：

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
#include <iostream>
#include <string>
#include <chrono>
#include <thread>
#include <future>

using namespace std::chrono;

std::string fetchDataFromDB(std::string recvData)
{
    //确保函数要5秒才能执行完成
    std::this_thread::sleep_for(seconds(5));

    //处理创建数据库连接、获取数据等事情
    return "DB_" + recvData;
}

std::string fetchDataFromFile(std::string recvData)
{
    //确保函数要5秒才能执行完成
    std::this_thread::sleep_for(seconds(5));

    //处理获取文件数据
    return "File_" + recvData;
}

int main()
{
    //获取开始时间
    system_clock::time_point start = system_clock::now();

    /** 使用std::launch::async，来指定其异步执行 */
    std::future<std::string> resultFromDB = std::async(std::launch::async,
                                                    fetchDataFromDB, "Data");

    //从文件获取数据
    std::string fileData = fetchDataFromFile("Data");

    //从DB获取数据
    //数据在future<std::string>对象中可获取之前，将一直阻塞
    std::string dbData = resultFromDB.get();

    //获取结束时间
    auto end = system_clock::now();

    auto diff = duration_cast<std::chrono::seconds>(end - start).count();
    std::cout << "Total Time taken= " << diff << "Seconds" << std::endl;

    //组装数据
    std::string data = dbData + " :: " + fileData;

    //输出组装的数据
    std::cout << "Data = " << data << std::endl;

    return 0;
}

std::promise介绍

std::promise的作用就是提供一个不同线程之间的数据同步机制，它可以存储一个某种类型的值，并将其传递给对应的future， 即使这个future不在同一个线程中也可以安全的访问到这个值

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
#include <iostream>       // std::cout
#include <functional>     // std::ref
#include <thread>         // std::thread
#include <future>         // std::promise, std::future

void print_int (std::future<int>& fut)
{
    std::cout << "Enter print_int: " << std::endl;
    int x = fut.get();  ///< 在这里会等待外部std::promise变量set_value进来，否则会一致阻塞在这里
    std::cout << "value: " << x << '\n';
}

int main ()
{
    std::promise<int> prom;                      // 创建一个std::promise变量

    std::future<int> fut = prom.get_future();    // 创建一个std::future变量

    std::thread th1 (print_int, std::ref(fut));  // 创建一个线程执行函数print_int

    std::this_thread::sleep_for(std::chrono::seconds(3));
    prom.set_value (10);                         // 传值进入线程th1

    th1.join();
    system("pause");
    return 0;
}

std::packaged_task介绍

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>     // std::cout
#include <future>       // std::packaged_task, std::future
#include <chrono>       // std::chrono::seconds
#include <thread>       // std::thread, std::this_thread::sleep_for

// count down taking a second for each value:
int countdown (int from, int to)
{
    for (int i = from; i != to; --i)
    {
        std::cout << i << '\n';
        std::this_thread::sleep_for(std::chrono::seconds(1));
    }
    std::cout << "Lift off!\n";
    return from - to;
}

int main ()
{
    // 创建一个std::packaged_task对象
    std::packaged_task<int(int, int)> tsk (countdown);
    // 创建一个std::future对象，用于跨线程异步获取该线程返回的值
    std::future<int> ret = tsk.get_future();
	// 把线程对象移动进一个可运行的线程中
    std::thread th (std::move(tsk), 10, 0);
    // 让该线程从主线程中分离
    th.detach();
    // ...
    // 利用std::future对象来获取已经分离开的线程运行是否结束的返回的值
    int value = ret.get();
    std::cout << "The countdown lasted for " << value << " seconds.\n";

    system("pause");
    return 0;
}

硬件支持的线程数量

由于硬件支持的并行线程数量有限，如果创建线程的数量比硬件支持的数量要多，那么CPU进行的上下文切换可能会浪费大量时间，所以了解硬件支持的线程数量是高效并行编程的重点。

使用std::thread::hardware_concurrency()来获取硬件支持的线程数量。

1
2
3
4
5
6
7
#include <iostream>
#include <thread>

int main() {
    unsigned int n = std::thread::hardware_concurrency();
    std::cout << n << " concurrent threads are supported.\n";
}

std::thread::yield介绍

关于std::thread::yield 和 std::sleep_for的比较

例子：

1
2
3
4
5
6
7
8
9
10
11
12
void worker_thread() {
    while (true) {
        std::function<void()> task;
        if (work_queue.try_pop(task)) {
            /// 获取到任务就运行
            task();
        } else {
            /// 没有获取到就休息一下
            std::this_thread::yield();
        }
    }
}

Posted on Edited on In

thread_pool 源码学习

源码定义

我们先概览一下spdlog-thread_pool定义

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
class SPDLOG_API thread_pool
{
public:
    using item_type = async_msg;
    using q_type = details::mpmc_blocking_queue<item_type>;

    thread_pool(size_t q_max_items, size_t threads_n,
                std::function<void()> on_thread_start);
    thread_pool(size_t q_max_items, size_t threads_n);
    ~thread_pool();

    thread_pool(const thread_pool &) = delete;
    thread_pool &operator=(thread_pool &&) = delete;

    void post_log(async_logger_ptr &&worker_ptr, const details::log_msg &msg,
                  async_overflow_policy overflow_policy);
    void post_flush(async_logger_ptr &&worker_ptr,
                    async_overflow_policy overflow_policy);
    size_t overrun_counter();

private:
    q_type q_; ///< 任务队列
    std::vector<std::thread> threads_;  ///< 线程池

    void post_async_msg_(async_msg &&new_msg,
                         async_overflow_policy overflow_policy);
    void worker_loop_();
    bool process_next_msg_();
};

基本成员函数

首先我们从thread_pll中最基本的五个成员函数开始看。

1
2
3
4
5
6
7
8
9
thread_pool(size_t q_max_items, size_t threads_n,
            std::function<void()> on_thread_start);
thread_pool(size_t q_max_items, size_t threads_n);

// message all threads to terminate gracefully join them
~thread_pool();

thread_pool(const thread_pool &) = delete;
thread_pool &operator=(thread_pool &&) = delete;

可以看到该类删除了拷贝构造，移动构造，标志该类不可以被拷贝和移动。
其中有两个构造函数，我们来详细看看它们的实现。

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
/// @name     thread_pool
/// @brief    构造函数，创建了一定数量的线程，并规定执行哪个函数
///
/// @param    q_max_item      [in] 用于初始化任务队列最大的数量
/// @param    thread_n        [in] 用于初始化最大线程数量
/// @param    on_thread_start [in] 每个线程执行的初始化函数(只执行一次)
///
/// @return   NONE
///
/// @date     2020-06-27 13:32:47
inline thread_pool(size_t q_max_items, size_t threads_n,
                   std::function<void()> on_thread_start)
    : q_(q_max_items) ///< 任务队列的最大数目
{
  if (threads_n == 0 || threads_n > 1000) {
    throw(
        "spdlog::thread_pool(): invalid threads_n param (valid "
        "range is 1-1000)");
  }
  for (size_t i = 0; i < threads_n; i++) {
    threads_.emplace_back([this, on_thread_start] {
      /// 线程开始时候需要执行的初始函数
      on_thread_start();
      /// 主任务循环
      this->thread_pool::worker_loop_();
    });
  }
}

/// 委托构造函数，用于输入默认入参 std::function<void()>
inline thread_pool::thread_pool(size_t q_max_items, size_t threads_n)
    : thread_pool(q_max_items, threads_n, [] {}) {}

接着我们来看一下析构函数执行了什么

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// 告诉所有线程中止，并且执行join()
~thread_pool() {
  try {
    for (size_t i = 0; i < threads_.size(); i++) {
      /// 对每一个线程池发送一个中止消息
      post_async_msg_(async_msg(async_msg_type::terminate),
                      async_overflow_policy::block);
    }

    for (auto &t : threads_) {
      /// 等待每一个线程的结束时的join
      t.join();
    }
  } catch (...) {
    /// 析构函数中不能有异常，所以在这里做一个全捕获
  }
}

生产者逻辑

接着我们来看公有的两个接口函数的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// 用于发送任务消息，并判断是否需要打印到命令行或写入文件
void post_log(async_logger_ptr &&worker_ptr, const log_msg &msg,
              async_overflow_policy overflow_policy) {
  async_msg async_m(std::move(worker_ptr), async_msg_type::log, msg);
  post_async_msg_(std::move(async_m), overflow_policy);
}

/// 用于发送任务消息，并判断是否需要马上写入文件
void post_flush(async_logger_ptr &&worker_ptr,
                async_overflow_policy overflow_policy) {
  post_async_msg_(async_msg(std::move(worker_ptr), async_msg_type::flush),
                  overflow_policy);
}

/// 用于返回任务队列溢出了多少条
size_t overrun_counter() { return q_.overrun_counter(); }

post_log 和 post_flush 执行了一个差不多的任务，就是写日志，这两个函数都调用了post_async_msg_()来执行具体的任务们就来看看post_async_msg_()到底执行了什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/// @name     post_async_msg_
/// @brief    用于从队列中插入消息, 相当于生产者
///
/// @param    new_msg         [in] 用于传入异步日志消息(使用右值方便移动)
/// @param    overflow_policy [in] 消息数量溢出的策略
///
/// @return   NONE
///
/// @date     2020-06-27 13:42:18
void post_async_msg_(async_msg &&new_msg,
                     async_overflow_policy overflow_policy) {
  if (overflow_policy == async_overflow_policy::block) {
    /// 阻塞至消息队列中有空间来插入消息
    q_.enqueue(std::move(new_msg));
  } else {
    /// 立即插入队列且队列满时丢弃老的消息
    q_.enqueue_nowait(std::move(new_msg));
  }
}

消费者逻辑

如上面的实现，我们知道这是一个生产者，从外部插入到本对象内的任务队列，等待消费者来处理这些消息
我们来看看消费者到底执行了什么。

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
/// @name     worker_loop_
/// @brief    用于每个线程执行的死循环，当process_next_msg_返回false时候
///           线程自己退出
///
/// @param    NONE
///
/// @return   NONE
///
/// @date     2020-06-27 13:51:13
void worker_loop_() {
  /// 如果处理消息没有返回false，就一致执行该函数
  while (process_next_msg_()) {
  }
}

/// @name     process_next_msg_
/// @brief    处理队列中的下一个消息，相当于消费者
///
/// @param    NONE
///
/// @return   如果不是中止线程消息，则返回true, 反之返回false
///
/// @date     2020-06-27 13:53:45
bool process_next_msg_() {
  async_msg incoming_async_msg;
  /// 从任务消息队列中取消息，如果没有任务则等待获取任务,
  /// 如十秒后仍然没有获取到则直接返回
  bool dequeued =
      q_.dequeue_for(incoming_async_msg, std::chrono::seconds(10));
  /// 如果获取任务消息失败则直接返回true
  if (!dequeued) {
    return true;
  }

  /// 获取到消息后则进行处理
  switch (incoming_async_msg.msg_type) {
    case async_msg_type::log: {
      /// 打印消息到命令行且判断是否要马上刷新文件
      incoming_async_msg.worker_ptr->backend_sink_it_(incoming_async_msg);
      return true;
    }
    case async_msg_type::flush: {
      /// 刷新文件
      incoming_async_msg.worker_ptr->backend_flush_();
      return true;
    }

    case async_msg_type::terminate: {
      /// 用于终止本线程池的信号
      return false;
    }

    default: {
      assert(false);
    }
  }
  return true;
}

上面代码的逻辑我们可以看到：首先由worker_loop()函数来不停的执行消费者函数。
而消费者函数在不停地去任务队列中获取任务最后由backend_sink_it_() 和 backend_flush_()两个函数来执行真正地任务。

任务队列

很简单的一个消费者和生产者的队列，但最核心的部分被一个任务队列mpmc_blocking_queue<async_msg>给封装了，让我们继续深入来看看这个任务队列。

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
template <typename T>
class mpmc_blocking_queue {
 public:
  using item_type = T;
  explicit mpmc_blocking_queue(size_t max_items) : q_(max_items) {}

  /// 尝试入列，如果空间不足则阻塞
  void enqueue(T &&item) {
    {
      std::unique_lock<std::mutex> lock(queue_mutex_);
      pop_cv_.wait(lock, [this] { return !this->q_.full(); });
      q_.push_back(std::move(item));
    }
    push_cv_.notify_one();
  }

  /// 马上入列，如果没有空间则丢弃队列中老的消息
  void enqueue_nowait(T &&item) {
    {
      std::unique_lock<std::mutex> lock(queue_mutex_);
      q_.push_back(std::move(item));
    }
    push_cv_.notify_one();
  }

  /// 尝试出列。如果队列中没有消息，则等待到超时然后再次尝试
  /// 假如出列成功则返回true, 否则返回false
  bool dequeue_for(T &popped_item, std::chrono::milliseconds wait_duration) {
    {
      std::unique_lock<std::mutex> lock(queue_mutex_);
      if (!push_cv_.wait_for(lock, wait_duration,
                             [this] { return !this->q_.empty(); })) {
        return false;
      }
      popped_item = std::move(q_.front());
      q_.pop_front();
    }
    pop_cv_.notify_one();
    return true;
  }

  size_t overrun_counter() {
    std::unique_lock<std::mutex> lock(queue_mutex_);
    return q_.overrun_counter();
  }

 private:
  std::mutex queue_mutex_;           ///< 用于控制整个对象的锁
  std::condition_variable push_cv_;  ///< 用于入列的条件变量
  std::condition_variable pop_cv_;   ///< 用于出列的条件变量
  circular_q<T> q_;                  ///< 用于保存信息的队列
};

我们来看看这个队列是怎么实现线程安全的。
其中q_这个循环队列不是线程安全的，所以加上了一个queue_mutex 这个互斥锁用来同步所有成员函数的顺序并配合条件变量实现等待获取的功能。

spdlog-thread_pool 的实现逻辑很清晰，我们可以对比一下Github上另一个thread-pool: progschj/ThreadPool 的实现。
由于需要写入的任务很明确，就是处理异步日志，所以任务的队列直接写死了处理异步日志消息。而progschj/ThreadPool的实现则更加灵活。我们可以看看我的另一篇博客阅读progschj/thread_pool源码对progschj/ThreadPool的介绍

Posted on Edited on In

分析问题

首先我们知道整型是由有符号和无符号整型所组成。由于有符号整型的判断包含了无符号整型的计算，所以我们现在先讨论有符号整型。

1592040132570

有符号整型的加法包括以下几种情况：

1592042113575

由上图我们可以知道我们只用考虑两个操作数拥有相同符号的情况就行了。我们显而易见的可以知道，两数相加的结果一定大于任一操作数，写出以下函数。

1
2
3
4
5
6
7
8
9
10
/// 溢出了返回true，否则返回false
bool is_plus_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 计算正溢出的情况
    int result = x + y;
    return result < x;
  }

  return false;
}

接下来为了测试这个函数能否正确运行，我们添加如下测试用例：case 1.

1592044663011

完整验证程序：

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 <cassert>
#include <iostream>
#include <limits>

/// 溢出了返回true，否则返回false
bool is_plus_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 计算正溢出的情况
    int result = x + y;
    return result < x;
  }

  return false;
}

int main() {
  /// 获取int类型的最大值和最小值
  const int int_min = std::numeric_limits<int>::min();
  const int int_max = std::numeric_limits<int>::max();

  /// case 1
  assert(!is_plus_overflow(1, 1));  ///< 没有溢出
  assert(is_plus_overflow(int_max, 1));  ///< 溢出了
}

接下来考虑两数都为负数，判断负溢出的情况，同样我们知道两负数相加结果一定小于任一操作数, 对函数加以补充，并添加两个测试用例：case 2.

1592044894101

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 <cassert>
#include <iostream>
#include <limits>

/// 溢出了返回true，否则返回false
bool is_plus_overflow(int x, int y) {
  if (x > 0 && y > 0) {
    /// 计算正溢出的情况
    int result = x + y;
    return result < x;
  } else if (x < 0 && y < 0) {
    /// 计算负溢出的情况
    int result = x + y;
    return result > x;
  }

  return false;
}

int main() {
  /// 获取int类型的最大值和最小值
  const int int_min = std::numeric_limits<int>::min();
  const int int_max = std::numeric_limits<int>::max();

  /// case 1
  assert(!is_plus_overflow(1, 1));  ///< 没有溢出
  assert(is_plus_overflow(int_max, 1));  ///< 溢出了

  /// case 2
  assert(!is_plus_overflow(-1, -1));  ///< 没有溢出
  assert(is_plus_overflow(int_min, -1));  ///< 溢出了
}

当上面的程序顺利执行完毕后我们可以继续往下看。接着我们能不能使用模板来扩展到其他类型的加法.

当然可以我们只需要把int换为模板参数T就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
bool is_plus_overflow_t(T x, T y) {
  if (x > 0 && y > 0) {
    /// 计算正溢出的情况
    T result = x + y;
    return result < x;
  } else if (x < 0 && y < 0) {
    /// 计算负溢出的情况
    T result = x + y;
    return result > x;
  }

  return false;
}

接下来我们为模板函数添加上类型限定和静态编译检查。然后同样使用测试用例:case 1 和 case 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
#include <cassert>
#include <iostream>
#include <limits>

template <typename T1, typename T2>
bool is_plus_overflow_t(const T1& x, const T2& y) {
  /// 编译时判断两个入参的类型是否一致
  static_assert(std::is_same<T1, T2>::value,
                "is_plus_overflow need same type!");
  /// 编译时判断两个入参类型都为整数类型
  static_assert(std::is_integral<T1>::value,
                "is_plus_overflow need integral type!");

  T1 result = x + y;
  if (x > 0 && y > 0) {
    return result < x;
  } else if (x < 0 && y < 0) {
    return result > x;
  } else {
    return false;
  }
}

int main() {
  /// 获取int类型的最大值和最小值
  constexpr auto int_min = std::numeric_limits<int>::min();
  constexpr auto int_max = std::numeric_limits<int>::max();

  /// case 1
  assert(!is_plus_overflow_t(1, 1));  ///< 没有溢出
  assert(is_plus_overflow_t(int_max, 1));  ///< 溢出了

  /// case 2
  assert(!is_plus_overflow_t(-1, -1));  ///< 没有溢出
  assert(is_plus_overflow_t(int_min, -1));  ///< 溢出了
}

接下来添加上详细的测试用例就大功告成了。

1592130012130

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 <cassert>
#include <iostream>
#include <limits>

template <typename T1, typename T2>
bool is_plus_overflow_t(const T1& x, const T2& y) {
  /// 编译时判断两个入参的类型是否一致
  static_assert(std::is_same<T1, T2>::value,
                "is_plus_overflow need same type!");
  /// 编译时判断两个入参类型都为整数类型
  static_assert(std::is_integral<T1>::value,
                "is_plus_overflow need integral type!");

  T1 result = x + y;
    if (x > 0 && y > 0) {
      return result < x;
    } else if (x < 0 && y < 0) {
      return result > x;
    } else {
      return false;
    }
}

int main() {
  /// 获取int类型的最大值和最小值
  constexpr auto min_num = std::numeric_limits<int>::min();
  constexpr auto max_num = std::numeric_limits<int>::max();

  /// case 1
  assert(!is_plus_overflow_t(1, 1));       ///< 没有溢出
  assert(is_plus_overflow_t(max_num, 1));  ///< 溢出了

  /// case 2
  assert(!is_plus_overflow_t(-1, -1));      ///< 没有溢出
  assert(is_plus_overflow_t(min_num, -1));  ///< 溢出了

  /// case 3
  assert(!is_plus_overflow_t(max_num, 0));
  /// case 4
  assert(!is_plus_overflow_t(max_num, min_num));
  /// case 5
  assert(!is_plus_overflow_t(0, max_num));
  /// case 6
  assert(!is_plus_overflow_t(0, 0));
  /// case 7
  assert(!is_plus_overflow_t(0, min_num));
  /// case 8
  assert(!is_plus_overflow_t(min_num, max_num));
  /// case 9
  assert(!is_plus_overflow_t(min_num, 0));
}

后记

这个函数也可以用作检查减法是否溢出，只需要对第二个入参求相反数即可。但需要注意一个情况。

就是int值的负数个数(- 2^31)是比正数个数(2^31 - 1)多一个的, 所以在转化为相反数的时候可能在函数入参时出现溢出，导致计算没有溢出。

1
2
3
4
5
6
7
int x = 2;
int y = 1;
is_plus_overflow_t(x, y);	/// 正确：等价与计算 2-1 表达式会不会溢出

x = 2;
y = INT_MIN;
is_plus_overflow_t(x, -y);	/// 错误：当y等于int的最小值的时候，无法求其相反数，会直接溢出

Posted on Edited on In

关于数值极限

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

int main()
{
    std::cout << "type\t\t\tlowest()\t\tmin()\t\t\tmax()\n\n";

    std::cout << "short\t\t\t"
              << std::numeric_limits<short>::lowest() << "\t\t\t"
              << std::numeric_limits<short>::min() << "\t\t\t"
              << std::numeric_limits<short>::max() << "\n";
    std::cout << "int\t\t\t"
              << std::numeric_limits<int>::lowest() << "\t\t"
              << std::numeric_limits<int>::min() << "\t\t"
              << std::numeric_limits<int>::max() << "\n";
    std::cout << "long\t\t\t"
              << std::numeric_limits<long>::lowest() << "\t\t"
              << std::numeric_limits<long>::min() << "\t\t"
              << std::numeric_limits<long>::max() << "\n";
    std::cout << "long long\t\t"
              << std::numeric_limits<long long>::lowest() << "\t"
              << std::numeric_limits<long long>::min() << "\t"
              << std::numeric_limits<long long>::max() << "\n";
    std::cout << "unsigned short\t\t"
              << std::numeric_limits<unsigned short>::lowest() << "\t\t\t"
              << std::numeric_limits<unsigned short>::min() << "\t\t\t"
              << std::numeric_limits<unsigned short>::max() << "\n";
    std::cout << "unsigned int\t\t"
              << std::numeric_limits<unsigned int>::lowest() << "\t\t\t"
              << std::numeric_limits<unsigned int>::min() << "\t\t\t"
              << std::numeric_limits<unsigned int>::max() << "\n";
    std::cout << "unsigned long\t\t"
              << std::numeric_limits<unsigned long>::lowest() << "\t\t\t"
              << std::numeric_limits<unsigned long>::min() << "\t\t\t"
              << std::numeric_limits<unsigned long>::max() << "\n";
    std::cout << "unsigned long long\t"
              << std::numeric_limits<unsigned long long>::lowest() << "\t\t\t"
              << std::numeric_limits<unsigned long long>::min() << "\t\t\t"
              << std::numeric_limits<unsigned long long>::max() << "\n";


    system("pause");
}

64 位

在64位系统上Visual Studio 输出结果：

1592038101047

换为2的幂级数表示为（64位系统下）：

type lowest() min() max()
short -32768 -32768 32767
int -2147483648 -2147483648 2147483647
long -2147483648 -2147483648 2147483647
long long -9223372036854775808 -9223372036854775808 9223372036854775807
unsigned short 0 0 65535
unsigned int 0 0 4294967295
unsigned long 0 0 4294967295
unsigned long long 0 0 18446744073709551615

32 位

在32位系统上Visual Studio 输出结果：

1592038101047

type lowest() min() max()
short -32768 -32768 32767
int -2147483648 -2147483648 2147483647
long -2147483648 -2147483648 2147483647
long long -9223372036854775808 -9223372036854775808 9223372036854775807
unsigned short 0 0 65535
unsigned int 0 0 4294967295
unsigned long 0 0 4294967295
unsigned long long 0 0 18446744073709551615