I think it's because of this line: auto &ref = ways[{from, now}]; I faced the same problem using gp hash table a few days ago. I think it will work if a temp variable is used instead of ref and later assigned, it worked for me. I asked chatpgt about why umap didnt have this problem, and it said its bcz unordered map uses the same pointer to the to the same node after rehashing. But gp hashtable doesnt.

Sorry for necroposting, but I personally find these kinds of issues to be a lot of fun.

I would like to preface this explanation by stating how annoying reading such docs becomes after getting used to cppreference, as generally the container clearly states invalidation behavior (see vector iterator invalidation). To get the same information for policy based data structures, you basically have to either read the GNU implementation code or (and perhaps a bit more reasonably) execute some compile time checks.

Anyways, the base idea is that GNU policy based data structures have something called invalidation guarantees. This basically states how modifications to the data structure affect pointers.

The three types are:

1. basic_invalidation_guarantee: a point iterator/pointer/reference will be valid as long as the parent data structure is not modified.
2. point_invalidation_guarantee (inherits basic_invalidation_guarantee): a point iterator/pointer/reference will be valid as long as its "entry" in the parent data structure isn't erased.
3. range_invalidation_guarantee (inherits point_invalidation_guarantee): a range iterator will maintain its relative position in the parent data structure as long as its "entry" in the parent data structure isn't erased.

That information can be found either in the previous link or here (in the ext/pb_ds/tag_and_trait.hpp file).

The way you determine the invalidation guarantee of a policy based data structure is by compile time querying typename container_traits<Cntnr>::invalidation_guarantee (where Cntnr is your policy based container...), and then running some static assert, constexpr if, etc, with is_same_v/is_base_of_v OR running a dispatch function akin to:

void impl(basic_invalidation_guarantee) { /* basic */ }
void impl(point_invalidation_guarantee) { /* point or range */ }

template<class C>
void dispatch() {
  using tag = typename container_traits<C>::invalidation_guarantee;
  impl(tag{});
}

Alternatively, you can also just read the GNU source (once again, in the ext/pb_ds/tag_and_trait.hpp file) to find the same information.

Finally, after having read through all that, we can finally see that (at least here), it states that cc_hash_table/map has a point_invalidation_guarantee, whilst the gp_hash_table/map has a basic_invalidation_guarantee.

This means that inserting into the cc_hash_table/map will not invalidate previous references (located on the stack because of your dfs), whilst the gp_hash_table/map might.

So yeah, the take away from this really is that studying the documentation of the libraries you use can really help you out. I personally enjoy just hopping onto cppreference and reading/learning about random features of the stl/language and then experimenting with them...