用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>時這會對性能（緩存漏洞利用位置）產生很大影響嗎？

2016-10-28 Joseph Stack

標準向量類應該與數組在很大程度上兼容，這意味着它分配的數據存儲在連續的內存塊中，就像數組一樣。如果你有一個'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喜歡訪問連續的內存位置）。

來源

2016-10-28 10:16:06

一個是否比另一個更有效取決於用例。如果你需要插入一些數據，那麼移動一些指針比複製所有數據要快得多。 – Meixner

一般來說，_measuring_是一件好事。但是，對緩存友好的結構往往對性能很好;由於緩存不友好，基於節點的結構往往對perf性能不佳。請注意，分頁的成本很高。相反，現代CPU喜歡訪問*連續*內存位置（這使得預取器很開心）。 –

對於d（< 10）的所述值，定義作爲Point將vector<int>幾乎兩倍由std::vector<Point>全存儲器使用並會帶來幾乎沒有優勢。

來源

2016-10-28 10:19:01 Leon

vector將存儲您的類型包含在連續內存中的任何內容。所以是的，如果這是一個array或tuple，或者可能更好，一個自定義類型，它將避免間接。

性能方面，一如既往，您必須對其進行測量。不要推測。至少就掃描而言。

但是，當您首先創建這些點時，肯定會有巨大的性能提升，因爲您將避免爲存儲點的每個vector不必要的內存分配。在C++中內存分配通常非常昂貴。

來源

2016-10-28 10:19:29

由於維度是固定的，所以我建議您使用一個使用維度作爲模板參數的模板。事情是這樣的：

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<...>>爲點，以獲得最佳性能的集合。

來源

2016-10-28 10:29:19

與std :: vector >相比，它有什麼不同？ –

「這比std :: vector >好嗎？」控制你可以對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)

來源

2016-11-01 21:29:07 user1656671

用C++編寫的矢量存儲器

回答

相關問題