std::vector、std::map和内存问题

Question

我正在编写代码，将数据库中的行插入到向量中。然后将这些向量存储在std::map中。这种架构允许我根据映射键逻辑地分区数据集（向量）。

在我的代码中，我将从std::map中检索数据集（即向量），向其中添加/删除行或对其执行其他逻辑，然后将向量重新放入映射中（所有这些都在while()循环中进行）。

我有两个问题，这两个问题都与向量中存储的（可能）大量元素有关。向量可以容纳从几十个到数万个元素的任何内容。我无法事先知道从数据库中检索到多少条记录。因此，std::vector的内存管理方案（即alloc/dealloc）变得非常重要，以便有效地使用内存，并避免不必要的（内存）碎片：

我的问题是：

1. 鉴于一行可能存储的大量元素，理想情况下，我希望从内存池中分配/释放。但是我不知道如何使用带有内存池的std::vector，也不知道是否会过于复杂。如果这是过度设计（或过于复杂），那么我的另一个想法是在创建向量时预先分配固定大小的内存块。但是这也很可能过于简单，因为元素的数量很可能从一个向量实例到另一个向量实例变化很大-导致（内存）碎片等问题，更不用说内存的低效使用了。

这里推荐的方法是什么？

2. 鉴于std::map（所有STL容器，如果我没记错）存储值元素的副本，复制包含几万个元素的向量的前景是完全错误的。因此，我考虑编写一个SmartPointerMap包装器，将指针存储到向量而不是实际向量中。

我是否正确？如果不是，有更好的解决方案吗？如果是，是否有我可以使用的boost库（而不是编写我的SmartPointerMap类模板）？

- Stick it to THE MAN

Answer 1

假设您在使用 vector 作为地图的 data_type 而不是 key_type，那么您可以直接修改数据而无需复制它。 std::map::operator[]() 返回对非常量 data_type 的引用，非常量版本的 std::map::find() 返回的迭代器允许您修改数据。

如果需要在更改数据时更改键怎么办？您可以使用 std::swap() 将数据从一个向量移动到另一个向量而无需复制。

请注意，当您删除元素时，vector 不会减少其 capacity()。此外，vector 通常会分配比所需更多的 capacity()，以使 push_back() 具有摊销恒定时间。对于非常大的向量，如果不小心处理，这些行为可能会显着增加程序的内存使用量。

如果您正在使用 vector 作为地图的 key_type，并且地图具有极大的键，则指针或智能指针可能会有所帮助。但是，如果是这种情况，则必须确保不要修改由地图值之一指向的键的内容，因为 std::map 并不设计用于处理这种情况。

至于自定义分配器的想法，请先使用标准分配器使您的代码正常工作，然后再看它是否足够快。使用标准分配器可能会很好。如果您的代码在使用标准分配器时速度不够快，请进行分析以查看实际花费时间的地方（可能是其他地方，例如数据库代码）。如果编写自定义分配器并且从未将其与标准分配器进行比较，则无法知道自定义分配器是否真正改进了；它可能比标准分配器慢得多。

- bk1e

---

请参考以下关于减少向量容量的问题：https://dev59.com/4HNA5IYBdhLWcg3wC5Th - Emile Cormier

Answer 2

对于问题#1，GCC/Linux中默认的堆实现（ptmalloc）将使用一个自由列表（也称为内存池）来处理小对象（默认情况下小于等于64个字节）。如果您仍然想使用自定义分配器，则Boost.Pool库具有满足标准分配器要求的分配器。正如bk1e所建议的那样，请在之前和之后进行基准测试，以确定是否值得这样做。

当从数据库填充向量时，如果可能/实用，尝试使用vector<T>::reserve()来使向量从开始就分配足够的内存并避免重新分配。

希望这可以帮助到您。

- Emile Cormier

Answer 3

回答问题2：

using namespace std;

map<string, vector<int>* > foo;
vector<int>* pointer= foo["thekey"];

如果使用智能（引用计数）指针是必需的：

#include<tr1/shared_ptr.h>
using namespace std::tr1;
using namespace std;

map<string, shared_ptr<vector<int> > > foo;
shared_ptr<vector<int> > pointer= foo["thekey"];

回答问题1，您可以编写一个新的分配器模板类并声明您的向量使用该分配器，但我不太了解如何编写分配器。

map<string, vector<int, myallocator<int> >* > foo;

特别是我不知道如何设计一个分配器来避免碎片化你的内存池。（但如果你已经解决了这个问题，编写一个自定义的分配器将是正确的方法。）

- Ken Bloom

Answer 4

我将建议一种更通用的方法来处理C/C++中的数据库查询集。

执行数据库查询并将行放入结构体数组中。如果您没有足够的物理内存，请使用内存映射文件，它将返回指向基于结构体数组的指针，处理器芯片上的MMU会在需要时将其保留在内存中。

现在，您可以对此结构体数组按键进行sort()排序，这将为您提供ISAM访问，在关系教条中是异端邪说，但正是游标所提供的。这是数据访问方法＃1

现在，如果您仍然需要以其他方式查看该数据，则只需创建一个或多个索引/映射，其中映射的键是结构体数组中适当的（列值/结构体成员），而映射的数据值是指向内存映射文件中该结构体位置的指针。这提供了与db索引完全相同的功能。通过给定行的struct.member值对地图进行下标操作，将使您立即回到该行。

您可以拥有多个映射，用于多个索引，指向数组中相同的结构体/行，使用不同的struct.member数据作为不同索引的键。

我忽略了您提出的添加新行/结构的要求，因为似乎您只是从数据库中读取一次行，并且实际上不需要添加新行/结构。

然而，如果我错了，您确实需要添加新的结构/行，则可以通过malloc()和realloc()适当大小的结构数组，并将它们挂在作为映射“数据”的指针。这样做会失去真正的ISAM访问，因为结构体在内存中不是物理相邻的，但您会获得realloc()功能。这是一个权衡。可以通过迭代映射来模拟ISAM访问，但与从内存顺序读取结构体数组相比，速度会慢一些。

- user2548100