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

Question

您是否还记得我之前的问题：What is causing data race in std::async here?
即使我成功并行化了这个程序，它仍然仍然跑得太慢而不切实际。
所以我试图改进代表康威的生命游戏模式的数据结构。
新结构的简要说明：

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单元，以及每个OFF单元具有一个或多个ON邻居单元。它也可以包含备用OFF单元。
cells_coor通过使用它们的坐标作为关键字直接存储单元格，并将它们映射到ON邻居单元格的数目（存储为int）以及它们是否为ON（存储为bool）。

cells_neigh and cells_onoff通过迭代器将它们作为关键字间接存储单元。
单元的ON邻居数始终为0或更大，8或更小，因此cells_neigh是9号阵列。
cells_neigh[0]用0 ON邻居小区存储小区，cells_neigh[1]用1个ON邻居小区存储小区，依此类推。
同样，单元总是OFF或ON，所以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())，这是从现有结构的时间复杂度很大improval。

但正如你所看到的，有一个问题：如何散列std::unordered_map::const_iterator？
std::hash禁止为他们专门化，所以我必须做一个自定义的。
考虑到他们的地址是行不通的，因为他们通常是作为右值或临时对象获得的。
取消引用它们也不起作用，因为有多个单元格有0个ON邻居单元，或多个单元关闭等。
那么，我该怎么做？如果我什么都做不了，cells_neigh和cells_onoff会是std::vector什么的，大大降低了时间复杂度。

Answer 1

短篇小说：这不行（真的很好）（* 1）。您可能要在地图cells_coor上执行的大多数操作都会使任何迭代器（but not pointers, as I learned）无效。

如果你想保留我在某些集合上所称的不同“视图”，那么存储实际数据的底层容器需要不被修改或不能使其迭代器（例如链表）失效。

也许我错过了一些东西，但为什么不保留9组细胞的邻居计数和2组细胞的开/关？ （* 2）换句话说：你真的需要那张地图吗？ （* 3）

---

（* 1）：地图仅重散列时发生失效指针和迭代器。可以检查的是：

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

（* 2）：9套可以减少到8：如果一个细胞（X，Y）是在没有任何8组，那么这将是在第9集。因此存储该信息是不必要的。开/关相同：存储单元格就足够了。所有其他都关闭。

（* 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; 
} 

在组中重复查找当然可以摧毁实际性能，你需要分析。 （渐近运行时不受影响）