c++crossword

Data structure for a crossword puzzle grid?


I'd like to design a crossword puzzle editor in C++. It is a grid of blocks, each block containing a letter (or being black between two words), possibly a number and a thick or thin border line. The block is therefore a container class for them. The grid is a container of blocks. But how would I structure the grid?

  1. A raw 2d array: Block grid[row][column]?
  2. Vector of Vectors: vector<vector<Block>>?
  3. Two vectors, one for the rows and one for the columns: vector<Block> row; vector<Block> column?
  4. A map, which keys are the row/column pairs and the values are the blocks: map<int[2], Block>?

Solution

  • By default, plain static/dynamic arrays (or their wrappers) are the most preferable: they are the most comfortable for both the programmer (random access API etc) and the processor (memory locality etc).

    The easiest-to-implement Block layout in an array/a vector is [first row Blocks..., second row Blocks..., etc] - a 1D array which acts as a 2D array. It can be indexed like crossword[x + y * crossword.width()], which isn't pretty, so you might want to use a library/self-written wrapper with API like crossword(x, y) which performs that xy-to-i-index conversion under the hood.

    Maybe something like this:

    class Crossword {
        std::vector<Block> raw;
        size_t length{}; // can't name it "width" because there's a "width()" member function below
    
    public:
        Crossword() {}
        Crossword(size_t x, size_t y): raw(x * y), length{x} {}
        Crossword(Crossword&& other) noexcept { *this = std::move(other); }
        Crossword& operator=(Crossword&& other) noexcept {
            std::swap(raw, other.raw);
            std::swap(length, other.length);
            return *this;
        }
    
        auto size() const { return raw.size(); }
        auto width() const { return length; }
        auto height() const { return size() / length; }
        auto& operator()(size_t x, size_t y) const { return raw[x + y * length]; }
        auto& operator()(size_t x, size_t y) { return raw[x + y * length]; }
    };