如何散列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; 
} 

在組中重複查找當然可以摧毀實際性能，你需要分析。 （漸近運行時不受影響）