我如何散列 std::unordered_map::const_iterator？

Question

你还记得我之前的问题吗：
即使我成功地并行化了这个程序，它仍然运行太慢而不实用。
所以我尝试改进表示康威生命游戏模式的数据结构。
新结构简述：

class pattern {
    // NDos::Lifecell represents a cell by x and y coordinates.
    // NDos::Lifecell is equality comparable, and has std::hash specialization.
private:
    std::unordered_map<NDos::Lifecell, std::pair<int, bool>> cells_coor;
    std::unordered_set<decltype(cells_coor)::const_iterator> cells_neigh[9];
    std::unordered_set<decltype(cells_coor)::const_iterator> cells_onoff[2];
public:
    void insert(int x, int y) {
        // if coordinate (x,y) isn't already ON,
        // turns it ON and increases the neighbor's neighbor count by 1.
    }
    void erase(int x, int y) {
        // if coordinate (x,y) isn't already OFF,
        // turns it OFF and decreases the neighbor's neighbor count by 1.
    }
    pattern generate(NDos::Liferule rule) {
        // this advances the generation by 1, according to the rule.
        // (For example here, B3/S23)
        pattern result;
        // inserts every ON cell with 3 neighbors to result.
        // inserts every OFF cell with 2 or 3 neighbors to result.
        return result;
    }
    // etc...
};

简而言之，pattern 包含单元格。它包含每个 ON 单元格，以及具有 1 个或多个 ON 相邻单元格的每个 OFF 单元格。它还可以包含备用 OFF 单元格。
cells_coor 直接存储单元格，通过使用它们的坐标作为键，并将它们映射到它们的 ON 邻居单元格数（存储为 int）以及它们是否打开（存储为 bool） .

cells_neigh 和 cells_onoff 间接存储单元格，通过迭代器将它们作为键。
单元格的 ON 邻居数始终为 0 或更大且 8 或更小，因此 cells_neigh 是一个大小为 9 的数组。
cells_neigh[0] 存储相邻单元格为 0 的单元格，cells_neigh[1] 存储相邻单元格为 1 的单元格，依此类推。
同样，单元格总是关闭或打开，因此 cells_onoff 是一个大小为 2 的数组。
cells_onoff[false] 存储 OFF 单元格，cells_onoff[true] 存储 ON 单元格。
必须在 cells_coor、cells_neigh 和 cells_onoff 中插入或删除单元格。换句话说，如果一个单元格被插入或从其中一个中删除，那么其他单元格也必须如此。因此，cells_neigh 和 cells_onoff 的元素是 std::unordered_set 将迭代器存储到实际单元格中，从而可以通过邻居计数或 OFF/ON 状态快速访问单元格。

如果这个结构有效，插入函数的平均时间复杂度为O(1)，擦除函数的平均时间复杂度为O(1)，生成函数的时间复杂度为O(cells_coor.size())，时间复杂度有很大的提高来自先前的结构。

但是如您所见，有一个问题：我如何散列一个 std::unordered_map::const_iterator？
std::hash 禁止对他们进行专业化，所以我必须定制一个。
获取它们的地址是行不通的，因为它们通常是作为右值或临时值获取的。
取消引用它们也不起作用，因为有多个单元格的相邻单元格为 0，或者多个单元格为 OFF，等等。
那我该怎么办？如果我什么都做不了，cells_neigh 和 cells_onoff 将是 std::vector 之类的，这会大大降低时间复杂度。

Answer 1

短篇小说：这行不通（真的很好）(*1)。您可能要在地图 cells_coor 上执行的大多数操作都会使其元素的任何迭代器 () 失效。

如果你想在某些集合上保持我所说的不同 "views"，那么存储实际数据的底层容器需要不被修改或不能使其迭代器无效（链表用于例如）。

也许我遗漏了什么，但为什么不保留 9 组单元格用于邻居计数和 2 组单元格用于 on/off？ (*2) 换句话说：您真正需要那张地图有什么用？ (*3)

(*1)：映射仅在发生重新散列时使 ~~指针和~~ 迭代器无效。您可以检查一下：

// Before inserting
(map.max_load_factor() * map.bucket_count()) > (map.size() + 1)

(*2)：9组可以减为8组：如果一个cell(x,y)在8组中的none，那么它将在第9盘。因此不需要存储该信息。 on/off 相同：足以存储打开的单元格。其他都关闭。

(*3)：在不使用地图的情况下访问邻居的数量，但仅使用单元格集，一种伪代码：

unsigned number_of_neighbours(Cell const & cell) {
  for (unsigned neighbours = 9; neighbours > 0; --neighbours) {
    if (set_of_cells_with_neighbours(neighbours).count() == 1) {
      return neighbours;
    }
  }
  return 0;
}

集合中的重复查找当然会破坏实际性能，您需要对其进行概要分析。（渐近运行时不受影响）

我如何散列 std::unordered_map::const_iterator？

How can I hash a std::unordered_map::const_iterator?

c++

hash

unordered-map

const-iterator

c++11