c++ - 用于处理 3 个整数列表的数据结构

Question

我目前正在编写一个关于格子的物理模拟，我有兴趣描述这个格子中的环，它们是由格子单元的边缘组成的闭合曲线。我将有关此格子单元的信息(我所说的信息是指一个 bool 变量，表示该边是否对构成一个循环有值(value))存储在一个 3 维 bool 数组中。

我现在正在考虑一个好的结构来处理这个循环。它们基本上是一个边列表，所以我需要一些类似 3d 整数 vector 数组的东西，每个边在我当前的参数化中由 3 个坐标定义。我已经在考虑围绕这个“列表”对象构建一个类，因为我将需要计算环直径的方法，并且将来可能需要更多。

但是，我绝对不是很清楚我必须这样做的结构选择，我的物理背景没有教我足够的 C++。因此，我想听听您对塑造这段代码的建议。我真的很乐意发现一些新的方法来为这个 child 编写代码。

Answer 1

你想要两个不同的东西。一种是跟踪所有边缘并允许通过 (int,int,int) 索引快速查找边缘对象(您可能不希望那里有 int，而是类似 size_t 左右的东西)。这完全独立于您的第二个目标，即创建这些的有序子集。

总集(一)

由于您的边缘数据库将是稀疏的(即只有少数可能的索引将实际识别为特定边缘)，我之前使用 3d 矩阵的建议是不合适的。相反，您可能想要使用 HashMap 查找边。

这有多容易取决于各个整数的预期大小。也就是说，你能否设法让每个整数不超过 21 位(例如，如果你的整数是 short int 值，只有 16 位)，那么你可以将它们连接到一个 64 位值，它已经有一个 std::hash 实现。否则，您将不得不为例如 std::hash<std::array<uint32_t,3>>(这也很容易，并且高度 stackable )实现自己的哈希特化。

一旦您可以对 key 进行哈希处理，就可以将其放入 std::unordered_map 并完成处理。那东西很快。

循环检测(二)

然后你想要有一个短暂的数据结构来识别循环，所以你想要一个在一端扩展但永远不会在另一端扩展的数据结构。这意味着如果您有非常大的实例，您可能可以使用 std::vector 或 std::deque (但请先尝试 vector !)。

我建议只将索引保持在局部 vector 的边缘。您始终可以在 unordered_map 中查找边缘对象。那么问题就是如何表示索引。如果 Int 表示您的整数类型(例如 int 、 size_t 、 short ……)，使用 std::array<Int,3> 可能是最一致的——如果整数类型不同，您将需要 std::tuple<...> 。