c++ - 骑士巡演。选择容器

Question

我最近一直在阅读 C++，尤其是 STL，我决定再做一次骑士巡回赛的问题。我正在考虑实现这一点的最佳方法，我正在寻求帮助。

只是为了好玩和练习，我想我会从一个“Piece”基类开始，“Knight”类可以从中继承。我想这样做，以便稍后我可以尝试添加其他部分（即使大多数部分无法遍历整个电路板并完成问题）。

因此，“棋子类”将需要某种容器来存储棋子在棋盘上的坐标以及它在该特定步骤中所做的移动次数。

我想我需要一个包含 64 (8 * 8) 个位置的链表来最有效地执行此操作，其中包含 x、y 和移动。

查看 STL 容器，除了可以容纳一种以上类型的 map 之外，我找不到任何东西。

我可以做些什么来存储坐标对和一个容器中移动次数的 int？有比使用矢量、列表或地图更有效的方法吗？我需要自定义容器吗？

谢谢！

score 2 · Accepted Answer

您可以使用

struct CellInfo
{
    int x, y, move_count;
}

并将其存储起来以std::vector供持续访问。

score 0 · Accepted Answer

C++ STL 现在也有静态数组。如果要存储给定 x,y 坐标移动到的次数，可以创建一个数组数组，如下所示：

using container_type = std::array<std::array<int, 8>, 8>;

// ...

container_type c;
int moves = c[x][y]; // constant-time access.

如果您不需要基于 x,y 查找向上移动，并且只想有效存储数据，请使用大小为 8x8 = 64 的平面数组。

如果您的编译器已过时，请考虑改用 std::vector。

score 0 · Accepted Answer

除了 STL 和封装之外，一个非常有效的方法是使用数组：

pair<int, int> piece_pos[N];
int piece_move[N];

这避免了内存泄漏的开销，并且比动态分配更快。

如果你想使用 STL，那么：

vector<pair<int, int> > piece_pos(N);
vector<int> piece(N);

3 回答 3