代码中的if…else杂谈2

if-else嵌套过深的几个解决方法-重载<为主要例子。

std::map是我们常用的容器,虽然c++11后引入std::unordered_map减少了其“出镜率”,但是在key有序或对内存使用有严格要求时,std::map仍有其用武之地;std::map的内部实现是红黑树std::unordered_map的实现方式是哈希表(也称散列表

std::map 是有序键值对容器,它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。

在每个标准库使用比较 (Compare) 概念的位置,以等价关系检验唯一性。不精确而言,若二个对象 a 与 b 互相比较不小于对方 : !comp(a, b) && !comp(b, a) ,则认为它们等价(非唯一)。

unordered_map 是关联容器,含有带唯一键的键-值 pair 。搜索、插入和元素移除拥有平均常数时间复杂度。

元素在内部不以任何特定顺序排序,而是组织进桶中。元素放进哪个桶完全依赖于其键的哈希。这允许对单独元素的快速访问,因为一旦计算哈希,则它准确指代元素所放进的桶。

–引自std::map - cppreference.comstd::unordered_map - cppreference.com

由上文总结可得:

名称 std::map std::unordered_map
有序性 有序 无序
内部实现 红黑树 哈希表
平均时间复杂度 O(logN) O(1)
内存占用 高,类似于vector,需要提前申请内存,用以存储哈希表
要求 实现 < 有哈希函数

重载 <

有如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Point3D
{
int x;
int y;
int z;
};

std::map<Point3D, double> pointMap;

int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
Point3D point1;
point1.x = 1;
point1.y = 2;
point1.z = 3;
pointMap.insert(std::pair<Point3D, double>(point1, 1.0));

return a.exec();
}

无法通过编译,在VS2017 X64下提示如下错误:

错误 C2678 二进制“<”: 没有找到接受“const _Ty”类型的左操作数的运算符(或没有可接受的转换)

很显然,Point3D需要重载<

第一次重载 <

记得第一次遇到这问题时,系统某个数据结构是个三段式,第一次写出了类似这样的代码:

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
struct Point3D
{
int x;
int y;
int z;
bool operator < (const Point3D& rhs) const
{
if (x <= rhs.x)
{
if (x < rhs.x)
{
return true;
}
else //相等
{
if (y <= rhs.y)
{
if (y < rhs.y)
{
return true;
}
else //相等
{
return z <= rhs.z;
}
}
else
{
return false;
}
}
}
else
{
return false;
}
}
};

工程中全文搜索operator <-复制-粘贴老代码-修改,一气呵成。

方法1:提前return

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Point3D
{
int x;
int y;
int z;
bool operator < (const Point3D& rhs) const
{
if (x > rhs.x)
return false;

if (x < rhs.x)
return true;

if (y > rhs.y)
return false;

if (y < rhs.y)
return true;

return z < rhs.z;
}
};

该方法降低了嵌套层数。

对于某些条件不符合需要立即返回的应立即返回,比如判断指针为nullptrComboBoxindex == -1std::vector::empty()等。

提交代码-颇费~

没想到C++11后,该方法又有点跟不上时代了

方法2:C++11方法

C++引入了std::tuple ,有时cppreference中文版真是难懂,这里贴出来其英文版上关于std::tuple的介绍

Class template std::tuple is a fixed-size collection of heterogeneous values. It is a generalization of std::pair.

std::tuple已经重载了如下操作符

1
2
3
4
5
6
7
operator==
operator!=
operator<
operator<=
operator>
operator>=
operator<=>(C++20)

关于 < 有如下介绍:

Compares lhs and rhs lexicographically by operator<, that is, compares the first elements, if they are equivalent, compares the second elements, if those are equivalent, compares the third elements, and so on.

For non-empty tuples, (3) is equivalent to

1
2
3
4
5
6
if (std::get<0>(lhs) < std::get<0>(rhs)) return true;
if (std::get<0>(rhs) < std::get<0>(lhs)) return false;
if (std::get<1>(lhs) < std::get<1>(rhs)) return true;
if (std::get<1>(rhs) < std::get<1>(lhs)) return false;
...
return std::get<N - 1>(lhs) < std::get<N - 1>(rhs);

可有看得出,他也是通过提前return实现的。

所以我们可以借助std::tie,创造两个临时的std::tuple ,让std::tuple们自己去比较大小。

std::tie:Creates a tuple of lvalue references to its arguments or instances of std::ignore.

所以在c++11 -c++17版本中,struct重载<,可以最终简化为:

1
2
3
4
5
6
7
8
9
10
11
struct Point3D
{
int x;
int y;
int z;

bool operator < (const Point3D& rhs) const
{
return std::tie(x, y, z) < std::tie(rhs.x, rhs.y, rhs.z);
}
};

C++20起,可以使用新操作符<=>代替被废弃的<

The <, <=, >, >=, and != operators are synthesized from operator<=> and operator== respectively. (since C++20)

防止嵌套过程其他方法:合并条件

对于可以合并的条件应该将其合并,这样能减少路径,降低阅读、维护、单元测试难度。特别是某些只有if没有else的语句,合并后不仅能减少路径,甚至还能减少嵌套层数,比如:

1
2
3
4
5
6
7
8
9
10
if (point1.x == 3)
{
if (point1.y == 4)
{
if (point1.z == 5)
{
...
}
}
}

可以合并为

1
2
3
4
if (point1.x == 3 && point1.y == 4 && point1.z == 5)
{
...
}

参考

cppreference-map

cppreference-unordered_map

cppreference-tuple

cppreference-tie


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!