samedi 4 mars 2017

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

Do you remember my prior question: What is causing data race in std::async here?
Even though I successfully parallelized this program, it still ran too slowly to be practical.
So I tried to improve the data structure representing a Conway's Game of Life pattern.
Brief explanation of the new structure:

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, const std::pair<int, bool>> cells_coor;
    std::unordered_map<decltype(cells_coor)::const_iterator> cells_neigh[9];
    std::unordered_map<decltype(cells_coor)::const_iterator> cells_onoff[2];
public:
    // insertion function : makes a cell ON.
    // erasure function : makes a cell OFF.
    // generation function : advances the pattern to the next generation.
    // etc...
};

In brief, pattern contains the cells. It contains every ON cells, every OFF cells that has 1 or more ON neighbor cells. It can also contain spare OFF cells.
cells_coor directly stores the cells, by using their coordinates as keys, and maps them to their number of ON neighbor cells (stored as int) and whether they are ON (stored as bool).
cells_neigh and cells_onoff indirectly stores the cells, by the iterators to them as keys.
cells_neigh[0] stores the cells with 0 ON neighbor cells, cells_neigh[1] stores the cells with 1 ON neighbor cell, and to on.
cells_onoff[false] stores the OFF cells, and cells_onoff[true] stores the ON cells.

If this structure works, the insertion function will have average time complexity of O(1), the erasure also O(1), and the generation O(cells_coor.size()), which are great improval of time complexity from the prior structure.

But as you see, there is a problem: How can I hash a std::unordered_map::const_iterator?
std::hash prohibits a specialization for them, so I have to make a custom one.
Taking their address won't work, as they are usually acquired as rvalues or temporaries.
Dereferencing them also won't work, as there are multiple cells that have 0 ON neighbor cells, or multiple cells that is OFF, etc.
So what can I do? If I can't do anything, cells_neigh and cells_onoff will be std::vector or something, sharply degrading the time complexity.

Aucun commentaire:

Enregistrer un commentaire