|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r86728 - in branches/release: . boost boost/functional boost/functional/hash boost/unordered libs libs/functional libs/functional/hash/doc libs/unordered libs/unordered/doc libs/unordered/test/unordered
From: dnljms_at_[hidden]
Date: 2013-11-16 15:36:27
Author: danieljames
Date: 2013-11-16 15:36:27 EST (Sat, 16 Nov 2013)
New Revision: 86728
URL: http://svn.boost.org/trac/boost/changeset/86728
Log:
Merge unordered and hash from trunk.
- Only use Visual C++ pragma with appropriate compilers.
- Working link for Thomas Wang's hash function.
- Updated unordered rationale.
- Fix `unnecessary_copy_tests` for Visual C++ 12.
- Some extra insert tests.
Properties modified:
branches/release/ (props changed)
branches/release/boost/ (props changed)
branches/release/boost/functional/ (props changed)
branches/release/boost/unordered/ (props changed)
branches/release/libs/ (props changed)
branches/release/libs/functional/ (props changed)
branches/release/libs/unordered/ (props changed)
Text files modified:
branches/release/boost/functional/hash/hash.hpp | 4 ++++
branches/release/libs/functional/hash/doc/rationale.qbk | 2 +-
branches/release/libs/unordered/doc/rationale.qbk | 23 ++++++++++++++---------
branches/release/libs/unordered/test/unordered/insert_tests.cpp | 39 +++++++++++++++++++++++++++++++++++++++
branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp | 2 +-
5 files changed, 59 insertions(+), 11 deletions(-)
Modified: branches/release/boost/functional/hash/hash.hpp
==============================================================================
--- branches/release/boost/functional/hash/hash.hpp Sat Nov 16 15:13:39 2013 (r86727)
+++ branches/release/boost/functional/hash/hash.hpp 2013-11-16 15:36:27 EST (Sat, 16 Nov 2013) (r86728)
@@ -29,11 +29,15 @@
#if defined(BOOST_MSVC)
#pragma warning(push)
+
+#if BOOST_MSVC >= 1400
#pragma warning(disable:6295) // Ill-defined for-loop : 'unsigned int' values
// are always of range '0' to '4294967295'.
// Loop executes infinitely.
#endif
+#endif
+
#if BOOST_WORKAROUND(__GNUC__, < 3) \
&& !defined(__SGI_STL_PORT) && !defined(_STLPORT_VERSION)
#define BOOST_HASH_CHAR_TRAITS string_char_traits
Modified: branches/release/libs/functional/hash/doc/rationale.qbk
==============================================================================
--- branches/release/libs/functional/hash/doc/rationale.qbk Sat Nov 16 15:13:39 2013 (r86727)
+++ branches/release/libs/functional/hash/doc/rationale.qbk 2013-11-16 15:36:27 EST (Sat, 16 Nov 2013) (r86728)
@@ -34,7 +34,7 @@
then neither the standard hash function or `boost::hash` are appropriate.
There are several options
available. One is to use a second hash on the output of this hash
-function, such as [@http://www.concentric.net/~ttwang/tech/inthash.htm
+function, such as [@http://web.archive.org/web/20121102023700/http://www.concentric.net/~Ttwang/tech/inthash.htm
Thomas Wang's hash function]. This this may not work as
well as a hash algorithm tailored for the input.
Modified: branches/release/libs/unordered/doc/rationale.qbk
==============================================================================
--- branches/release/libs/unordered/doc/rationale.qbk Sat Nov 16 15:13:39 2013 (r86727)
+++ branches/release/libs/unordered/doc/rationale.qbk 2013-11-16 15:36:27 EST (Sat, 16 Nov 2013) (r86728)
@@ -3,7 +3,7 @@
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) ]
[def __wang__
- [@http://www.concentric.net/~Ttwang/tech/inthash.htm
+ [@http://web.archive.org/web/20121102023700/http://www.concentric.net/~Ttwang/tech/inthash.htm
Thomas Wang's article on integer hash functions]]
[section:rationale Implementation Rationale]
@@ -85,7 +85,8 @@
Using a prime number of buckets, and choosing a bucket by using the modulus
of the hash function's result will usually give a good result. The downside
-is that the required modulus operation is fairly expensive.
+is that the required modulus operation is fairly expensive. This is what the
+containers do in most cases.
Using a power of 2 allows for much quicker selection of the bucket
to use, but at the expense of loosing the upper bits of the hash value.
@@ -95,12 +96,16 @@
To avoid this a transformation could be applied to the hash function, for an
example see __wang__. Unfortunately, a transformation like Wang's requires
-knowledge of the number of bits in the hash value, so it isn't portable enough.
-This leaves more expensive methods, such as Knuth's Multiplicative Method
-(mentioned in Wang's article). These don't tend to work as well as taking the
-modulus of a prime, and the extra computation required might negate
-efficiency advantage of power of 2 hash tables.
-
-So, this implementation uses a prime number for the hash table size.
+knowledge of the number of bits in the hash value, so it isn't portable enough
+to use as a default. It can applicable in certain cases so the containers
+have a policy based implementation that can use this alternative technique.
+
+Currently this is only done on 64 bit architecures, where prime number
+modulus can be expensive. Although this varies depending on the architecture,
+so I probably should revisit it.
+
+I'm also thinking of introducing a mechanism whereby a hash function can
+indicate that it's safe to be used directly with power of 2 buckets, in
+which case a faster plain power of 2 implementation can be used.
[endsect]
Modified: branches/release/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/insert_tests.cpp Sat Nov 16 15:13:39 2013 (r86727)
+++ branches/release/libs/unordered/test/unordered/insert_tests.cpp 2013-11-16 15:36:27 EST (Sat, 16 Nov 2013) (r86728)
@@ -576,6 +576,21 @@
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+struct initialize_from_two_ints
+{
+ int a, b;
+
+ friend std::size_t hash_value(initialize_from_two_ints const& x)
+ {
+ return x.a + x.b;
+ }
+
+ bool operator==(initialize_from_two_ints const& x) const
+ {
+ return a == x.a && b == x.b;
+ }
+};
+
UNORDERED_AUTO_TEST(insert_initializer_list_set)
{
boost::unordered_set<int> set;
@@ -583,6 +598,30 @@
BOOST_TEST_EQ(set.size(), 3u);
BOOST_TEST(set.find(1) != set.end());
BOOST_TEST(set.find(4) == set.end());
+
+ boost::unordered_set<initialize_from_two_ints> set2;
+
+ set2.insert({1, 2});
+ BOOST_TEST(set2.size() == 1);
+ BOOST_TEST(set2.find({1,2}) != set2.end());
+ BOOST_TEST(set2.find({2,1}) == set2.end());
+
+ set2.insert({{3,4},{5,6},{7,8}});
+ BOOST_TEST(set2.size() == 4);
+ BOOST_TEST(set2.find({1,2}) != set2.end());
+ BOOST_TEST(set2.find({3,4}) != set2.end());
+ BOOST_TEST(set2.find({5,6}) != set2.end());
+ BOOST_TEST(set2.find({7,8}) != set2.end());
+ BOOST_TEST(set2.find({8,7}) == set2.end());
+
+ set2.insert({{2, 1}, {3,4}});
+ BOOST_TEST(set2.size() == 5);
+ BOOST_TEST(set2.find({1,2}) != set2.end());
+ BOOST_TEST(set2.find({2,1}) != set2.end());
+ BOOST_TEST(set2.find({3,4}) != set2.end());
+ BOOST_TEST(set2.find({5,6}) != set2.end());
+ BOOST_TEST(set2.find({7,8}) != set2.end());
+ BOOST_TEST(set2.find({8,7}) == set2.end());
}
UNORDERED_AUTO_TEST(insert_initializer_list_multiset)
Modified: branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp
==============================================================================
--- branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp Sat Nov 16 15:13:39 2013 (r86727)
+++ branches/release/libs/unordered/test/unordered/unnecessary_copy_tests.cpp 2013-11-16 15:36:27 EST (Sat, 16 Nov 2013) (r86728)
@@ -374,7 +374,7 @@
// COPY_COUNT(1) would be okay here.
reset();
x.emplace();
-# if BOOST_WORKAROUND(BOOST_MSVC, >= 1700)
+# if BOOST_WORKAROUND(BOOST_MSVC, == 1700)
// This is a little odd, Visual C++ 11 seems to move the pair, which
// results in one copy (for the const key) and one move (for the
// non-const mapped value). Since 'emplace(boost::move(a))' (see below)
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk