用C++编写的矢量存储器

问题描述：

我希望存储d维点的大矢量（d fixed and small：< 10）。用C++编写的矢量存储器

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

但是，如果定义一个Point作为固定大小的物体，如： std::tuple<int,int,...,int>或std::array<int, d>，将程序存储在连续的存储器所有的点或将附加了间接水平保持？

如果答案是数组避免了额外的间接寻址，那么在扫描vector<Point>时这会对性能（缓存漏洞利用位置）产生很大影响吗？

标准向量类应该与数组在很大程度上兼容，这意味着它分配的数据存储在连续的内存块中，就像数组一样。如果你有一个'std :: vector '，那么所有'Point'对象都会连续存储。如果Point类有自己的指针（直接或间接（就像它有一个向量时那样）），那么不是所有的数据都会连续存储。 –

是的，我会去元组路线或更好的，只是使用普通的C风格的结构（我仍然发现烦恼使用元组，即std :: get （）并不是那么直观）。 – Robinson

答

如果你定义Point为具有连续的数据存储（例如struct Point { int a; int b; int c; }或使用std::array），然后std::vector<Point>将存储Point S IN的连续存储单元，所以你的内存布局将是：

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 s，但不是整个结构。

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

一个是否比另一个更有效取决于用例。如果你需要插入一些数据，那么移动一些指针比复制所有数据要快得多。 – Meixner

一般来说，_measuring_是一件好事。但是，对缓存友好的结构往往对性能很好;由于缓存不友好，基于节点的结构往往对perf性能不佳。请注意，分页的成本很高。相反，现代CPU喜欢访问*连续*内存位置（这使得预取器很开心）。 –

答

对于d（< 10）的所述值，定义作为Point将vector<int>几乎两倍由std::vector<Point>全存储器使用并会带来几乎没有优势。

答

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

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

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

答

由于维度是固定的，所以我建议您使用一个使用维度作为模板参数的模板。事情是这样的：

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<...>>为点，以获得最佳性能的集合。

与std :: vector <:array>>相比，它有什么不同？ –

“这比std :: vector <:array>>好吗？”控制你可以对ndpoint执行的操作（例如，添加一个'norm'方法或'distanceTo'等）。性能方面，它是一样的。只是不要使用元组或向量作为你的ND点的存储。 –

答

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

但是，有很多库实现矩阵和矩阵操作，你可以检查出来。一些已经记录了关于连续内存，重塑等信息（例如OpenCV Mat）。

请注意，一般来说，您不能相信Point的阵列将是连续的。这是由于排列，分配块头等。例如考虑

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

Point array_of_points[3];

现在，如果你尝试“重塑”，也就是点元素中继的事实是点在容器相邻之间的迭代 - 比它很可能会失败：

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

用C++编写的矢量存储器

相关推荐