The number of buckets is currently limited to ~2^32 (see X<>::primes). This is a serious issue: for correctness, rehash(n) for n > 2^32 should throw and do nothing, in order not to violate the post-conditions in Table 21. We have various options: as suggested by Howard off-line, we could well compute at run-time prime-numbers. Otherwise, mid-term, if we cannot extend the maximum number of bucket we have to add throws to the rehashing functions.
Just curious: is the assumption of prime-size buckets hardwired in the TR? Otherwise, the obvious alternative would be to use power-of-two sizes, which are much faster in access.
(In reply to comment #1) > Just curious: is the assumption of prime-size buckets hardwired in the TR? > Otherwise, the obvious alternative would be to use power-of-two sizes, which > are much faster in access. Yes. Really, I have yet to study the issue in detail (Knuth...), I'm going to do that. For sure TR1 doesn't mandate a specific policy, but we have got a default policy, prime_rehash_policy, which is definitely well known and used elsewhere, it would be nice to fix it, to begin with ;)
... something considered "obvious" in the literature is that the size policy goes together with the range-hashing function: e.g., an exponential size-policy would not work well together with our default modulo range-hashing function.
Working on it.
Subject: Bug 26424 Author: paolo Date: Wed Apr 19 22:58:23 2006 New Revision: 113100 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=113100 Log: 2006-04-19 Paolo Carlini <pcarlini@suse.de> PR libstdc++/26424 * include/tr1/hashtable (X<>::primes): Extend for 64-bit machines. (X<>::n_primes): Adjust. (prime_rehash_policy::next_bkt, bkt_for_elements, need_rehash): Adjust. Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/tr1/hashtable
Subject: Bug 26424 Author: paolo Date: Fri Apr 21 17:49:48 2006 New Revision: 113143 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=113143 Log: 2006-04-21 Paolo Carlini <pcarlini@suse.de> PR libstdc++/26424 * include/tr1/hashtable (X<>::primes): Extend for 64-bit machines. (X<>::n_primes): Adjust. (prime_rehash_policy::next_bkt, bkt_for_elements, need_rehash): Adjust. Modified: branches/gcc-4_1-branch/libstdc++-v3/ChangeLog branches/gcc-4_1-branch/libstdc++-v3/include/tr1/hashtable
Fixed for 4.1.1.