0

对于一个非常具体的应用程序，我想使用一个容器，其中的元素具有可变大小并且在内存中是连续的。基本原理是访问将主要是顺序的，因此将所有数据放在同一个线性数据结构中应该有助于缓存行为。

当然随机访问是不可能的，但数据结构应该使用矢量样式的push_back方法动态调整大小。

这样的容器存在吗？怎么称呼？

编辑以解决 Arne Mertz 的评论：

我要表示的结构是一个图表。容器将包含节点列表，每个节点都有边列表，可能表示为指向其他（先前）节点的指针列表。

struct Node {
  //various fixed size fields about the node itself
  ...

  unsigned short n_edges;
  Node * edges[n_edges]; // schematically
};
4

4 回答 4

1

您可以创建一个std::vector<char> v与std::list<size_t> l. v将充当可增长的字符缓冲区，l并将包含对象的偏移量。

现在您需要编写自己的 push_back ，它将当前偏移量插入 std::list 并将对象复制到位置： &v[offset] （记得事先增加 v ）。

template <class T>
void push_back(T t)
{
    size_t vectorSize = v.size());
    size_t objectSize = sizeof(T);

    l.pushback(vectorSize);

    v.reserve(vectorSize + objectSize);
    st::memcpy(&v[vectorSize], &t, objectSize);
}
于 2013-06-19T09:02:09.460 回答
1

解决此问题的一种方法是使用内部 void 指针。然后，每个元素都存储在该内存中。每个元素都以它的大小开始。对容器进行迭代将使字节指针增加当前元素的大小。如果您想要随机访问，您可以使用包含指向所有元素的指针的目录。

于 2013-06-19T09:03:58.177 回答
1

Boost Intrusive 单链表怎么样。您需要自己实现自己的分配。您可以简单地分配一个大区域（char[] 类型）并在该区域内创建具有递增地址的对象（不要忘记对齐）。如果您的区域已满，您可以简单地再创建一个。但是您必须自己进行所有分配并管理对象生命周期。此外，您可以使用 astd::vector作为 O(1) 访问的支持结构。

于 2013-06-19T09:05:07.260 回答
0

用一块动态内存实现一个类。编写一个函数以在块的末尾推送一个可变长度的结构。将块的偏移量放在一个向量中，以便您轻松迭代块，并随机访问块。

当动态内存区域变满时，重新分配更大的内存并将旧的块数据复制到其中。

冲洗重复。

于 2013-06-19T08:56:34.797 回答