C++开发填字游戏编辑器的网格数据结构选型问题

方案选型结论 #

优先选择向量嵌套向量（方案2），四类方案的适配性分析如下： #

方案1：原生二维数组 Block grid[row][column] #

不推荐使用。栈上分配的原生二维数组要求行列值为编译期常量，无法支持编辑器常用的用户自定义网格尺寸需求；若使用堆上动态分配的原生二维数组，需要手动管理内存、自行实现边界校验和行列调整逻辑，开发成本远高于标准库容器，没有使用必要。

方案2：vector<vector<Block>>（推荐） #

完全适配你的需求：

• 天然支持运行时动态调整行列尺寸，用户修改网格大小时直接调用resize方法即可，内存自动管理
• 元素访问语法和原生数组一致，grid[i][j]写法直观易读，使用at()方法还能获得标准库自带的越界访问校验
• 整行增删操作可以直接通过操作外层vector的erase/insert方法实现，开发效率高

唯一不足是不同行的内存不连续，但对填字游戏的性能需求完全没有影响，足够覆盖绝大多数场景。如果后续需要优化性能，可以改成单一维vector vector<Block>，通过i * 总列数 + j计算索引获得连续内存的访问效率，初期开发用嵌套vector性价比最高。

方案3：两个一维向量分别存储行和列 vector<Block> row; vector<Block> column #

完全不可行。单个Block对应唯一的二维坐标(i,j)，用两个一维向量会产生数据冗余，修改单个块属性需要同时更新两个向量的对应位置，很容易出现数据不一致的问题，没有任何使用价值。

方案4：以行列对为键的map #

仅适合网格极度稀疏（90%以上为黑遮挡块）的特殊场景，普通填字游戏场景不推荐：

• 首先C++原生数组int[2]不能直接作为map的键，需要替换为pair<int, int>才能正常使用
• map的元素访问时间复杂度为O(logn)，远低于vector的O(1)，遍历全网格的效率也更差
• 需要额外处理键不存在的边界情况，开发复杂度更高

内容的提问来源于stack exchange，提问作者Thomas Benko