0%

STL容器的一些细节问题

vector通常保证强异常安全性

当 push_back、insert、reserve、resize 等函数导致内存重分配时,或当insert、erase 导致元素位置移动时,vector 会试图把元素“移动”到新的内存区域。vector通常会保证强异常安全性,如果元素类型没有提供一个保证不抛异常的移动构造函数,vector通常会使用拷贝构造函数。因此对于拷贝代价较高的自定义元素类型,我们应定义移动构造函数,并标其为noexcept,或只在容器内放置对象的只能指针。

考虑以下一段代码

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
class Obj1
{
public:
Obj1()
{
std::cout << "Obj1()\n";
}

Obj1(const Obj1 &)
{
std::cout << "Obj1(const Obj1&)\n";
}

Obj1(Obj1 &&)
{
std::cout << "Obj1(Obj1&&)\n";
}
};

class Obj2
{
public:
Obj2()
{
std::cout << "Obj2()\n";
}

Obj2(const Obj2 &)
{
std::cout << "Obj2(const Obj2&)\n";
}

Obj2(Obj2 &&) noexcept
{
std::cout << "Obj2(Obj2&&)\n";
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

std::vector<Obj1> vec1;
vec1.reserve(2);
vec1.emplace_back();
vec1.emplace_back();
vec1.emplace_back();

std::cout << std::endl;

std::vector<Obj2> vec2;
vec2.reserve(2);
vec2.emplace_back();
vec2.emplace_back();
vec2.emplace_back();
return 0;
}

输出:

1
2
3
4
5
6
7
8
9
10
11
Obj1()
Obj1()
Obj1()
Obj1(const Obj1&)
Obj1(const Obj1&)

Obj2()
Obj2()
Obj2()
Obj2(Obj2&&)
Obj2(Obj2&&)

Obj1和Obj2仅仅相差了一个noexcept,但这个小小的差异会导致vector是否会移动对象,这点非常重要。

将main函数中的代码稍微更改一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

std::vector<Obj1> vec1;
vec1.reserve(2);
vec1.push_back(Obj1());//这种写法会被clangd检查建议优化,这里只是刚好需要这种写法。
vec1.push_back(Obj1());
vec1.push_back(Obj1());

std::cout << std::endl;

std::vector<Obj2> vec2;
vec2.reserve(2);
vec2.push_back(Obj2());
vec2.push_back(Obj2());
vec2.push_back(Obj2());
return 0;
}

输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Obj1()
Obj1(Obj1&&)
Obj1()
Obj1(Obj1&&)
Obj1()
Obj1(Obj1&&)
Obj1(const Obj1&)
Obj1(const Obj1&)

Obj2()
Obj2(Obj2&&)
Obj2()
Obj2(Obj2&&)
Obj2()
Obj2(Obj2&&)
Obj2(Obj2&&)
Obj2(Obj2&&)

可以看出由于Obj1()/Obj2()只是个临时对象,即使移动时出现异常也不会有什么损失,因此push_back时会调用移动构造函数,但对于vector内部元素移动的情况,如果出现异常可能会导致vector的状态彻底混乱了,所以在不保证不出现异常的情况下会调用拷贝构造函数。

stack/queue为什么pop函数返回值为void

在《C++ Concurrency In Action》书中有一段描述:

假设有一个stack<vector>,vector是一个动态容器,当你拷贝一个vector时,标准库会从堆上分配很多内存来完成这次拷贝。当这个系统处在重度负荷,或有严重的资源限制的情况下,这种内存分配就会失败,所以vector的拷贝构造函数可能会抛出一个std::bad_alloc异常。当vector中存有大量元素时,这种情况发生的可能性更大。当pop()函数返回“弹出值”时(也就是从栈中将这个值移除),会有一个潜在的问题:这个值被返回到调用函数的时候,栈才被改变;但当拷贝数据的时候,调用函数抛出一个异常会怎么样?如果事情真的发生了,要弹出的数据将会丢失;它的确从栈上移出了,但是拷贝失败了!std::stack的设计人员将这个操作分为两个部分:先获取顶部元素(top()),然后从栈中移除元素(pop())。这样,在不能安全的将元素拷贝出去的情况下,栈中的这个数据还依旧存在,没有丢失。当问题是堆空间不足时,应用可能会释放一些内存,然后再进行尝试。

C++98里没有移动构造的概念,返回数据类型可能会出现异常安全问题,这是C++98时设计的接口。