[v3] libstdc++/41975

[Paolo Carlini]

Hi,
> There is however an other potential issue with shrinking the unordered 
> container when elements are erased. Iterators can remain valid but the 
> following code won't have the expected behavior:
>
> template <typename _Pred>
> void erase_if(std::unordered_set<int> c, _Pred pred)
> {
>     std::unordered_set<int>::iterator it = c.begin();
>     while (it != c.end())
>     {
>         if (pred(*it))
>             it = c.erase(it);
>         else
>             ++it;
>     }
> }
>
> As soon as an iterator is erased and the container is rehashed the 
> returned (valid) iterator might become the iterator just before the 
> container end skipping a lot of elements that won't be tested with 
> pred. Is erase returned iterator purpose this one ? If so it means 
> that the container can't be rehash when shrinking and I won't have any 
> solution for 41975.
I have yet to digest your entire message but frankly I don't think we 
want to rehash upon erase (note, among other things that the hash 
function is allowed to throw in general and that's why I think we want 
unconditionally to store the hash, among other things). As regards the 
above, Table 103 in the FDIS for a.erase(q) seems pretty clear to me: 
"Return value is the iterator immediately following q prior to the 
erasure". Is your implementation conforming to the latter requirement?

Otherwise, the idea of having a single linked list of course is right + 
some other details which I figured out time ago and can dig out for you, 
if you want. But anyway, hash stored + single linked list is most of that.

Paolo.