C++中的向量存储

Question

我希望存储一个大的d维点向量（d固定且小：<10）。

如果我将 Point 定义为 vector<int>，我认为 vector<Point> 会在每个位置存储一个指向点的指针。

但是如果将 Point 定义为固定大小的对象，例如： std::tuple<int,int,...,int> 或 std::array<int, d>, 程序会将所有点存储在连续内存中还是会保留额外的间接级别？

如果答案是数组避免了额外的间接寻址，这是否会对扫描 vector<Point> 时的性能（缓存利用局部性）产生很大影响？

Answer 1

如果您将 Point 定义为具有连续数据存储（例如 struct Point { int a; int b; int c; } 或使用 std::array），则 std::vector<Point> 将存储 Points在连续的内存位置，所以你的内存布局将是：

p0.a, p0.b, p0.c, p1.a, p1.b, p1.c, ..., p(N-1).a, p(N-1).b, p(N-1).c

另一方面，如果将 Point 定义为 vector<int>，则 vector<Point> 的布局为 vector<vector<int>>，即不连续，因为vector 将指针存储到动态分配的内存中。所以你有单个 Point 的连续性，但不是整个结构的连续性。

第一个解决方案比第二个更有效（因为现代 CPU 喜欢访问连续的内存位置）。

Answer 2

对于d（<10）的上述值，将Point定义为vector<int>几乎会使全部内存使用量增加一倍std::vector<Point>并且几乎不会带来任何影响优势。

Answer 3

vector 会将您的类型包含的任何内容存储在连续内存中。所以是的，如果那是 array 或 tuple，或者可能更好的自定义类型，它将避免间接访问。

就性能而言，一如既往，您必须对其进行衡量。不要猜测。至少就扫描而言。

但是，当您首先创建这些点时肯定会获得巨大的性能提升，因为您将避免为每个存储点的 vector 分配不必要的内存。内存分配在 C++ 中通常非常昂贵。

Answer 4

由于尺寸是固定的，我建议您使用将尺寸用作模板参数的模板。像这样：

template <typename R, std::size_t N> class ndpoint 
{
public:
  using elem_t=
    typename std::enable_if<std::is_arithmetic<R>::value, R>::type;

  static constexpr std::size_t DIM=N;

  ndpoint() = default;

  // e.g. for copying from a tuple
  template <typename... coordt> ndpoint(coordt... x) : elems_ {static_cast<R>(x)...} {
  }
  ndpoint(const ndpoint& other) : elems_() {
    *this=other;
  }

  template <typename PointType> ndpoint(const PointType& other) : elems_() {
    *this = other;
  }

  ndpoint& operator=(const ndpoint& other) {
    for(size_t i=0; i<N; i++) {
      this->elems_[i]=other.elems_[i];
    }
    return *this;
  }

  // this will allow you to assign from any source which defines the
  // [](size_t i) operator
  template <typename PointT> ndpoint& operator=(const PointT& other) {
    for(size_t i=0; i<N; i++) {
      this->elems_[i]=static_cast<R>(other[i]);
    }
  }

  const R& operator[](std::size_t i) const { return this->elems_[i]; }

  R& operator[](std::size_t i) { return this->elems_[i]; }

private:
  R elems_[N];
};

然后使用 std::vector<ndpoint<...>> 收集点以获得最佳性能。

Answer 5

100% 确定数据结构的唯一方法是完全实现自己的内存处理。

但是，您可以查看许多实现矩阵和矩阵运算的库。一些记录了有关连续内存、重塑等的信息（例如 OpenCV Mat）。

请注意，通常您不能相信点的数组是连续的。这是由于对齐、分配块头等。例如考虑

struct Point {
   char x,y,z;
};

Point array_of_points[3];

现在，如果您尝试 'reshape'，即根据点在容器中相邻这一事实在 Point 元素之间进行迭代，那么它很可能会失败：

(char *)(&array_of_points[0].z) != (char *)(&array_of_points[1].x)

C++中的向量存储

Vector storage in C++

c++

memory

stdvector