Here is a new version compiling all your feedbacks.

     PR libstdc++/71181
     * include/tr1/hashtable_policy.h
     (_Prime_rehash_policy::_M_next_bkt): Make past-the-end iterator
     dereferenceable to avoid check on lower_bound result.
     (_Prime_rehash_policy::_M_bkt_for_elements): Call latter.
     (_Prime_rehash_policy::_M_need_rehash): Likewise.
     * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt):
     Always return a value greater than input value. Set _M_next_resize to
     max value when reaching highest prime number.
     * src/shared/hashtable-aux.cc (__prime_list): Add comment about 
sentinel
     being now useless.
     * testsuite/23_containers/unordered_set/hash_policy/71181.cc: New.
     * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc
     (test02): New.
     * 
testsuite/23_containers/unordered_set/hash_policy/prime_rehash.cc: New.
     * testsuite/23_containers/unordered_set/hash_policy/rehash.cc:
     Fix indentation.


On 15/06/2016 10:29, Jonathan Wakely wrote:
> On 14/06/16 22:34 +0200, François Dumont wrote:
>>>>    const unsigned long* __next_bkt =
>>>> -      std::lower_bound(__prime_list + 5, __prime_list + 
>>>> __n_primes, __n);
>>>> +      std::lower_bound(__prime_list + 6, __prime_list_end, __n);
>>>> +
>>>> +    if (*__next_bkt == __n && __next_bkt != __prime_list_end)
>>>> +      ++__next_bkt;
>>>
>>> Can we avoid this check by searching for __n + 1 instead of __n with
>>> the lower_bound call?
>>
>> Yes, that's another option, I will give it a try.
>
> I did some comparisons and this version seems to execute fewer
> instructions in some simple tests, according to cachegrind.
>
The only drawback is that calling _M_next_bkt(size_t(-1)) doesn't give 
the right result. But reaching this kind of value is not likely to 
happen in real use cases so it is acceptable.

Tested under Linux x86_64.

François