c++ - 避免堆碎片的最佳 STL 容器

Question

我有一个程序可以分析 150,000 个文件。 Valgrind 报告没有内存泄漏，但程序会随着时间的推移而变慢。

一些问题与过于频繁地使用 std::string 和 mktime 花费太多时间有关。 (参见 C++ slows over time reading 70,000 files)

但它仍然会随着时间的推移而减慢。 Lotharyx建议容器使用导致堆碎片。

我阅读了关于不同 STL 容器优缺点的各种流程图，但我不太明白。

在下面的伪代码中，我不确定我是否做出了正确的选择来避免堆碎片。

fileList.clear()
scan all disks and build "fileList", a std::set of file paths matching a pattern.

// filepaths are named by date, eg 20160530.051000, so are intrinsically ordered 

foreach(filePath in fileList)
{
    if (alreadyHaveFileDetails(filePath))
        continue;

    // otherwise
    collect file details into a fileInfoStruct;  // like size, contents, mod 

    fileInfoMap[time_t date] = fileInfoStruct;
}

// fileInfoMap is ordered collection of information structs of about 100,000 files

// traverse the list in order
foreach (fileInfo in fileInfoMap)
{
    if (meetsCondition(fileInfo))
    {
        TEventInfo event = makeEventInfo()
        eventList.push_back(event);
    }
}

并且上面的序列永远重复。

所以对于容器的选择，我已经使用(或需要):

fileList -- 包含 150,000 个路径名的唯一字符串列表。
我选择 std::set 是因为它会自动处理重复项并自动维护排序顺序。没有随机访问，仅添加条目，对它们进行排序(手动或自动)，然后迭代它们。

fileInfoMap -- 一个结构数组，由对应于文件日期的 time_t 时间戳作为键控。我选择了 std::map。它也将有 150,000 个条目，因此占用大量内存。没有随机访问，只将条目添加到一端。必须遍历它们，如有必要，从中间删除条目。

eventList -- “事件”结构的一个小列表，比如 50 个项目。我选择了 std::vector。不知道为什么真的。没有随机访问，只向一端添加条目，然后迭代集合。

我是 C++ 的新手。感谢您的考虑。

Answer 1

关于内存管理，容器属于两个大家族:一个是将所有元素一起分配，一个是单独分配元素。

vector 和 deque 属于第一类，list、set 和 map 属于第二类。

在不支持全局重定位的容器中不断添加和删除元素时，会出现内存碎片。

避免此问题的一种方法是使用 vector，使用“reserve”来预测减少重定位所需的内存，并在插入时保持数据排序.

另一种方法是使用“基于链接的容器”(如列表、集合等)，为它们提供一个分配器，从较大的 block 中分配内存，回收它们，而不是为每个元素插入/删除调用原始 malloc/free。

查看std::allocator

您可以通过从 std::allocator 派生并覆盖 allocate/deallocate 函数添加所有必需的逻辑并传递 yourallocator< 来轻松编写分配器 作为您要使用的容器的可选模板参数。