使用std::map和std::list存放数据，消耗内存比实际数据大得多

使用std::map和std::list存放数据，消耗内存比实际数据大得多

        场景：项目中需要存储一个结构，如下程序段中TEST_DATA_STRU，结构占24B。但是使用代码中的std::list<DataListMap>类存储4000个DataListMap，每个DataListMap中有4个pairs，每个pair中的DataList中有6000个items时，消耗掉的内存几乎是我们存放TEST_DATA_STRU的2倍。

#include <iostream>
#include <map>
#include <list>
#include <vector>

typedef struct TEST_DATA_STRU
{
	int Data_A;
	int Data_B;
	int Data_C;
	int Data_D;
}TEST_DATA_STRU;

typedef std::list<TEST_DATA_STRU> DataList;
typedef std::map<int, DataList> DataListMap;

int main(int argc,  char **argv)
{
	std::cout << "create a map" << std::endl;
	DataListMap dataListMap;
	// there are 100 pairs in the dataListMap
	for(int i=0; i<100; ++i)
	{
		DataList dataList;
		// there are 1000 items in a dataList
		for(int j=0; j<1000; ++j)
		{
			TEST_DATA_STRU testStru = {i, j, i+j, i-j};
			dataList.push_back(testStru);
		}
		dataListMap.insert(make_pair(i, dataList));
	}

	std::cout << "data size of DataListMap: " << sizeof(TEST_DATA_STRU) * 1000 + sizeof(int) * 100 << std::endl;

	std::cout << "testing..." << std::endl;
	std::list<DataListMap> mapList;
	for(int i=0; i<4000; ++i)
	{
		mapList.push_back(dataListMap);
	}

	// finally the memory of mapList is about double of the data we want to save
	return 0;
}

        最后通过分析，排除了内存泄露等情况后，将原因锁定在DataListMap类上。进一步分析后才找到原因：我们存放的结构占用24B，但是std::map和std::list中的指针就会占用24B以上，所以最终std::map和std::list自身所需的内存几乎和我们存储的数据一样大，甚至更大。

        深入分析：std::list和std::map属于散列容器，容器的空间之间是通过指针来关联的，所以指针会占用一部分内存，当自身存放的数据较2*8（std::list，双向链表）差别不大时，会有很大的额外内存开销。为了避免此开销，可以使用线性容器，std::vector。

        修改代码如下：使用std::vector取代std::list

#include <iostream>
#include <map>
#include <list>
#include <vector>

typedef struct TEST_DATA_STRU
{
	int Data_A;
	int Data_B;
	int Data_C;
	int Data_D;
}TEST_DATA_STRU;

typedef std::list<TEST_DATA_STRU> DataList;
typedef std::map<int, DataList> DataListMap;

typedef std::vector<TEST_DATA_STRU> DataVec;
typedef std::map<int, DataVec> DataVecMap;

int main(int argc,  char **argv)
{
	std::cout << "create a map" << std::endl;
	//DataListMap dataListMap;
	DataVecMap dataVecMap;
	// there are 100 pairs in the dataListMap
	for(int i=0; i<100; ++i)
	{
		//DataList dataList;
		DataVec dataVec;
		dataVec.reserve(1000);
		// there are 1000 items in a dataList
		for(int j=0; j<1000; ++j)
		{
			TEST_DATA_STRU testStru = {i, j, i+j, i-j};
			//dataList.push_back(testStru);
			dataVec.push_back(testStru);
		}
		//dataListMap.insert(make_pair(i, dataList));
		dataVecMap.insert(make_pair(i, dataVec));
	}

	std::cout << "data size of DataListMap: " << sizeof(TEST_DATA_STRU) * 1000 + sizeof(int) * 100 << std::endl;

	std::cout << "testing..." << std::endl;
	//std::list<DataListMap> mapList;
	std::list<DataVecMap> mapList;
	for(int i=0; i<4000; ++i)
	{
		//mapList.push_back(dataListMap);
		mapList.push_back(dataVecMap);
	}

	// finally the memory of mapList is almost same with the data we want to save
	return 0;
}

        最终省去了额外的内存开销。

        记于2016.04.14 22:28:24。