Comment créer une grille 2D efficace en C++?

Question

Je veux créer une grille 2D vraiment facile à utiliser. Chaque cellule de la grille doit être capable de stocker une charge de données. Idéalement, je voudrais être capable de traverser la grille une cellule à la fois, ainsi que d'obtenir les voisins immédiats de l'une des cellules de la grille. Ma première pensée a été de stocker un vecteur de pointeurs sur les voisins d'une cellule (4 au total), puis de créer des fonctions de commodité pour leftNeighbour, rightNeighbour, etc. Raccorder la grille après l'initialisation. Le std :: vector est supposé être un tableau dynamiquement redimensionnable, ce qui me semble plutôt inutile si je ne fais que coder en dur les positions des pointeurs (0 == left, 1 == right , etc). Cependant, cela permet une meilleure façon de parcourir les voisins d'une cellule. L'autre chose que je dois considérer est si la cellule est sur une frontière avec le bord de la grille (si pour tester ceci ou simplement étendre implicitement la grille par une cellule de sorte que ceci n'arrivera jamais).

Quelqu'un peut-il suggérer une meilleure alternative, ou est-ce que cela sonne comme un design raisonnable?

Merci, Dan

Answer 1

Si vous voulez un iterator-quatre directions, faire votre propre:

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

Vous voudrez peut-être détecter si vous appuyez sur le bord de votre grille, entre autres, et qui devrait être mis en œuvre.

Answer 2

Je pencherais pour Boost.MultiArray

Answer 3

Je suppose que vous ne voulez pas que je-me-penser-de-ce-première méthode de std::vector<std::vector<T> >, mais plutôt quelque chose qui permet structures plus compliquées.

Dans ce cas, pourquoi ne pas faire une classe Node (ou struct):

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]; 
}; 

C'est itérable (qui est l'un de vos critères) et ne pas utiliser l'allocation dynamique pour le stockage des voisins.

Answer 4

Jetez un oeil à la GIL, qui est une bibliothèque générique de traitement d'image. Entre autres choses, il a des itérateurs 2D pour l'itération sur les images, et étant vraiment générique, vous pourrez peut-être aussi l'utiliser directement pour vos trucs. Il vaut sûrement au moins la peine de voir comment cela pourrait être mis en œuvre.