如何在C++中創建高效的2D網格？

我想創建一個非常容易使用的2D網格。網格中的每個單元都需要能夠存儲大量數據。理想情況下，我希望能夠一次遍歷網格中的一個單元格，以及獲取任何網格單元的直接鄰居。如何在C++中創建高效的2D網格？

我的第一個想法是存儲一個指向Cell的鄰居的指針矢量（總共4個），然後爲leftNeighbour，rightNeighbour等創建便利函數。初始化後連接網格。

std :: vector應該是一個動態調整大小的數組，所以如果我只是硬編碼指針的位置（0 == left，1 == right等）。但是，它確實允許更好地遍歷單元格的鄰居。另一件事，我必須考慮的是，如果單元位於網格邊緣的邊界上（無論是測試此網格，還是僅隱式地將網格擴展爲一個網格，以避免這種情況發生）。

任何人都可以提出一個更好的選擇，或者這聽起來像一個合理的設計？

感謝，丹

來源

2009-01-25 Dan

如果你想有一個四方向迭代器，使你自己：

template<typename T, int width, int height> 
class Grid { 
    public: 
     T data[width * height]; 

     iterator begin() { 
      return iterator(data); 
     } 

     iterator end() { 
      return iterator(data + width * height); 
     } 

     class iterator { 
      public: 
       iterator(const iterator &other) : 
        ptr(other.ptr) 
       { 
       } 

       iterator &left() const { 
        return iterator(ptr - 1); 
       } 

       iterator &right() const { 
        return iterator(ptr + 1); 
       } 

       iterator &up() const { 
        return iterator(ptr - width); 
       } 

       iterator &down() const { 
        return iterator(ptr + width); 
       } 

       iterator &operator++() { 
        ++ptr; 
        return *this; 
       } 

       iterator &operator--() { 
        --ptr; 
        return *this; 
       } 

       iterator operator++(int) { 
        ++*this; 
        return iterator(ptr + 1); 
       } 

       iterator operator--(int) { 
        --*this; 
        return iterator(ptr - 1); 
       } 

       T operator*() const { 
        return *ptr; 
       } 

      private: 
       iterator(); 
       iterator(T *ptr_) : 
        ptr(ptr_) 
       { 
       } 

       T *ptr; 

       friend class Grid; 
     }; 
};

您可能需要檢測，如果你打你的網格，除其他事項外的邊緣，這將必須實施。

來源

2009-01-25 20:57:49 strager

我會去Boost.MultiArray的

來源

2009-01-25 20:18:52

我假設你不希望我 - 會 - 思考 - 的 - 這 - 第一的std::vector<std::vector<T> >方法，而是一些東西，讓結構更復雜。

在這種情況下，爲什麼不能讓一個Node類（或結構）：

template<typename T> 
class Node { 
    public: 
     typedef Node<T> *iterator; 
     // and const_iterator 

     T data; 

     Node(T data_ = T()) : 
      data(data_) 
     { 
     } 

     Node<T> *&left() { 
      return neighbors[0]; 
     } 

     // etc. 

     iterator begin() { 
      return neighbors; 
     } 

     iterator end() { 
      return neighbors + 4; 
     } 

    private: 
     Node<T> *neighbors[4]; 
};

這是迭代（這是你的標準之一），並且不使用動態分配存儲的鄰居。

來源

2009-01-25 20:28:40 strager

不要使用矢量>，由於沒有緩存局部性，它的性能很差。改爲使用平面矢量，並用y * w + x對其進行索引（這可以輕鬆封裝）。 – 2009-01-25 20:32:43

@Iraimbilanja，我同意，但在這種情況下，在X方向上調整地圖的尺寸將非常昂貴。如果大小是靜態的，平面陣列可能是最好的。 – strager 2009-01-25 20:36:31

看看GIL這是一個通用的圖像處理庫。除此之外，它有用於迭代圖像的2D迭代器，並且非常通用，您可能也可以直接將它用於您的東西。毫無疑問，這至少值得一看。

來源

2009-01-25 21:28:48 Anteru

如何在C++中創建高效的2D網格？

回答

相關問題