具有可变大小元素的 C++ "vector"

Question

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

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

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

编辑以解决 Arne Mertz 的评论:

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

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

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

Answer 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);
}