c++的map的内存布局

发布时间:2024年01月09日

以下均基于x86平台64位CentOS或Ubuntu,g++8。

有一个指针偶尔会置成0xffffffff,大佬查了几天发现是由于对map的end迭代器进行了错误操作导致的。简化代码如下:

struct s_t
{
	std::map<long, int> m;
	void *p;
};
int main()
{
	s_t s;
	auto it = s.m.end();
	it->second = -1;
	printf("%p\n", s.p); // 0xffffffff
	return 0;
}

要理解具体缘由,先要了解map的内存结构。map的声明是:

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map;

具体的实现委托是:

struct _Rb_tree_impl : public _Node_allocator
	, public _Rb_tree_key_compare<_Compare>
	, public _Rb_tree_header

如果使用默认的内存分配器,_Node_allocator里没有成员变量,不占空间
_Rb_tree_key_compare里有一个_Compare类型的成员变量,std::less没有成员变量,_Rb_tree_key_compare<std::less>的大小为1
_Rb_tree_header的成员变量有:

_Rb_tree_node_base _M_header; // 指向红黑树
size_t _M_node_count; // 节点数目

红黑树的一个节点包括header(_Rb_tree_node_base类型)和数据(包括_Key和_Tp)两部分,_Rb_tree_node_base的成员变量有:

_Rb_tree_color		_M_color; // 枚举类型,表示节点是红还是黑
_Rb_tree_node_base*	_M_parent; // 指向红黑树根节点
_Rb_tree_node_base*	_M_left; // 指向红黑树最左节点
_Rb_tree_node_base*	_M_right; // 指向红黑树最右节点

当红黑树为空时,_M_parent为空,_M_left和_M_right都指向_M_header自身,可通过如下代码验证:

	std::map<int, int> m;
	std::_Rb_tree_node_base *p = (std::_Rb_tree_node_base*)((char*)&m+8);
	cout << p << endl;
	cout << p->_M_parent << endl;
	cout << p->_M_left << endl;
	cout << p->_M_right << endl;

所以map<K,V>的内存布局是:

std::less
rb_head
	color
	parent
	left
	right
count

内存对齐后共占用48字节的空间,但如果指定1字节对齐后,总共占用37字节,可通过如下代码输出:

#include <iostream>
#pragma pack(1)
#include <map>
int main()
{
	std::cout << sizeof(std::less<int>) << std::endl; //1
	std::cout << sizeof(std::_Rb_tree_color) << std::endl; //4
	std::cout << sizeof(std::_Rb_tree_node_base) << std::endl; //28
	std::cout << sizeof(size_t) << std::endl; //8
	std::cout << sizeof(std::map<int, int>) << std::endl; //37
	return 0;
}

最后end()指向的是_M_header,其数据部分正好从_M_node_count的位置开始,it->first正好是_M_node_count的位置,it->second则是p的低4字节。

g++的标准库有一个 debug模式,编译时增加编译选项-D_GLIBCXX_DEBUG即可,可在运行时检测迭代器的有效性,能轻松检查出该问题。


用这个“特性”可以写出“防御性代码”:

int multiply2(int a)
{
	// 栈往低地址方向增长,所以int要在map前边
	int b = a;
	std::map<size_t, int> c;
	auto it = c.begin();
	it->second = b * 2;
	return b;
}

不了解的人,谁能想到这个函数的作用是乘2。

文章来源:https://blog.csdn.net/liuyuan185442111/article/details/135431267
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。