how to model a grid data type?

How can I model a grid(minesweeper problem) as a data type in the best possible way? Is it better to use a vector as 2 dimensional entity. The 开发者_Go百科reason for a vector is because of its bounds checking capabilities. Is my assumption right?

Thanks :)

---

Since the grid-size is (I presume!) fixed, a vector gives you little advantage over an array. So I recommend going with a 2D array.

While not necessary, you might find it useful to add sentinel values around the boundary of the grid to remove the need for implicit bounds checking. An example is placing 0's all around the grid for when you're summing the number of neighbouring mines. Read this article for some simpler examples to begin with.

---

I personally think that the vest option is to use a specialized class that acts like a multidimensional array while giving you the benefits of the STL vector (size-aware, no implicit conversions to pointers, etc.). Boost's multi_array class might be a good candidate here, and more generally whenever you need a multidimensional array. It handles all of the weirdness normally associated with raw C++ arrays without sacrificing performance.

---

Alternatively, if you have a large grid which is mostly empty you could use a std::map keyed with a std::pair. You would only use this approach if you are more concerned about memory than time taken to access the elements. As the memory would be linear in the number of non-empty cells O(n) and access would be O(log n) where using a matrix would be O(mp) in memory (where m and p are your matrix dimensions) and O(1) to access.