From: daniel_james_at_[hidden]
Date: 2008-04-30 03:57:07
Author: danieljames
Date: 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
New Revision: 44919
URL: http://svn.boost.org/trac/boost/changeset/44919
Log:
Merge in support for equality operators for the unordered containers and
hopefully better cross-platform support.
Merged revisions 44778-44835,44837-44918 via svnmerge from
https://svn.boost.org/svn/boost/branches/unordered/trunk
........
r44778 | danieljames | 2008-04-26 17:15:44 +0100 (Sat, 26 Apr 2008) | 2 lines
Remove a trailing comma.
........
r44779 | danieljames | 2008-04-26 17:23:51 +0100 (Sat, 26 Apr 2008) | 1 line
Merge in support for equality operators.
........
r44780 | danieljames | 2008-04-26 17:28:44 +0100 (Sat, 26 Apr 2008) | 1 line
Use my own list container to avoid working around STL container bugs.
........
r44833 | danieljames | 2008-04-28 08:03:43 +0100 (Mon, 28 Apr 2008) | 1 line
Better equality tests.
........
r44834 | danieljames | 2008-04-28 08:04:03 +0100 (Mon, 28 Apr 2008) | 1 line
Remove a superfluous check.
........
r44835 | danieljames | 2008-04-28 08:04:21 +0100 (Mon, 28 Apr 2008) | 1 line
Add equality reference documentation.
........
r44916 | danieljames | 2008-04-30 08:16:52 +0100 (Wed, 30 Apr 2008) | 1 line
New version of list.hpp
........
r44917 | danieljames | 2008-04-30 08:18:31 +0100 (Wed, 30 Apr 2008) | 1 line
Support compilers without ADL in the compile tests.
........
r44918 | danieljames | 2008-04-30 08:25:20 +0100 (Wed, 30 Apr 2008) | 7 lines
Change the typedef of buffered functions as it was confusing MSVC 6.5
get_allocator wasn't compiling when the allocator workaround is used because it
couldn't cast from the wrapped allocator to an allocator of another type. So
use value_alloc_ when it's available (it's only unavailable on compilers with
C++0x support, which don't require the workaround).
........
Added:
trunk/libs/unordered/test/unordered/equality_tests.cpp
- copied unchanged from r44835, /branches/unordered/trunk/libs/unordered/test/unordered/equality_tests.cpp
Properties modified:
trunk/ (props changed)
Text files modified:
trunk/boost/unordered/detail/hash_table_impl.hpp | 109 +++++++++++++++
trunk/boost/unordered_map.hpp | 32 ++++
trunk/boost/unordered_set.hpp | 32 ++++
trunk/libs/unordered/doc/ref.xml | 272 ++++++++++++++++++++++++++++++++++++++++
trunk/libs/unordered/test/helpers/equivalent.hpp | 23 +--
trunk/libs/unordered/test/helpers/metafunctions.hpp | 29 ----
trunk/libs/unordered/test/helpers/random_values.hpp | 4
trunk/libs/unordered/test/helpers/strong.hpp | 10
trunk/libs/unordered/test/helpers/test.hpp | 2
trunk/libs/unordered/test/helpers/tracker.hpp | 31 +--
trunk/libs/unordered/test/objects/minimal.hpp | 36 +++++
trunk/libs/unordered/test/unordered/Jamfile.v2 | 1
trunk/libs/unordered/test/unordered/compile_map.cpp | 37 +++++
trunk/libs/unordered/test/unordered/compile_set.cpp | 30 ++++
trunk/libs/unordered/test/unordered/compile_tests.hpp | 18 ++
trunk/libs/unordered/test/unordered/constructor_tests.cpp | 6
trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp | 4
trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp | 16 -
trunk/libs/unordered/test/unordered/find_tests.cpp | 4
trunk/libs/unordered/test/unordered/insert_tests.cpp | 5
20 files changed, 602 insertions(+), 99 deletions(-)
Modified: trunk/boost/unordered/detail/hash_table_impl.hpp
==============================================================================
--- trunk/boost/unordered/detail/hash_table_impl.hpp (original)
+++ trunk/boost/unordered/detail/hash_table_impl.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -1128,11 +1128,13 @@
private:
- typedef boost::unordered_detail::buffered_functions<Hash, Pred> buffered_functions;
- typedef BOOST_DEDUCED_TYPENAME buffered_functions::functions functions;
- typedef BOOST_DEDUCED_TYPENAME buffered_functions::functions_ptr functions_ptr;
+ typedef boost::unordered_detail::buffered_functions<Hash, Pred>
+ function_store;
+ typedef BOOST_DEDUCED_TYPENAME function_store::functions functions;
+ typedef BOOST_DEDUCED_TYPENAME function_store::functions_ptr
+ functions_ptr;
- buffered_functions functions_;
+ function_store functions_;
float mlf_;
size_type max_load_;
@@ -1376,10 +1378,17 @@
// accessors
// no throw
+#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
node_allocator get_allocator() const
{
return data_.allocators_.node_alloc_;
}
+#else
+ value_allocator get_allocator() const
+ {
+ return data_.allocators_.value_alloc_;
+ }
+#endif
// no throw
hasher const& hash_function() const
@@ -2136,6 +2145,98 @@
}
}
+ //
+ // equals
+ //
+
+private:
+#if BOOST_UNORDERED_EQUIVALENT_KEYS
+ static inline bool group_equals(link_ptr it1, link_ptr it2,
+ type_wrapper<key_type>*)
+ {
+ return data::group_count(it1) == data::group_count(it2);
+ }
+
+ static inline bool group_equals(link_ptr it1, link_ptr it2, void*)
+ {
+ link_ptr end1 = data::next_group(it1);
+ link_ptr end2 = data::next_group(it2);
+ do {
+ if(data::get_value(it1).second != data::get_value(it2).second) return false;
+ it1 = it1->next_;
+ it2 = it2->next_;
+ } while(it1 != end1 && it2 != end2);
+ return it1 == end1 && it2 == end2;
+ }
+#else
+ static inline bool group_equals(link_ptr it1, link_ptr it2,
+ type_wrapper<key_type>*)
+ {
+ return true;
+ }
+
+ static inline bool group_equals(link_ptr it1, link_ptr it2, void*)
+ {
+ return data::get_value(it1).second == data::get_value(it2).second;
+ }
+#endif
+
+public:
+ bool equals(BOOST_UNORDERED_TABLE const& other) const
+ {
+ if(size() != other.size()) return false;
+
+ for(bucket_ptr i = data_.cached_begin_bucket_,
+ j = data_.buckets_end(); i != j; ++i)
+ {
+ for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
+ {
+ link_ptr other_pos = other.find_iterator(other.extract_key(data::get_value(it)));
+ if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
+ !group_equals(it, other_pos, (type_wrapper<value_type>*)0))
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ inline std::size_t group_hash(link_ptr it, type_wrapper<key_type>*) const
+ {
+ std::size_t seed = data::group_count(it);
+ std::size_t hashed_key = hash_function()(data::get_value(it));
+ boost::hash_combine(seed, hashed_key);
+ return seed;
+ }
+
+ inline std::size_t group_hash(link_ptr it, void*) const
+ {
+ std::size_t seed = hash_function()(data::get_value(it).first);
+
+ link_ptr end = data::next_group(it);
+
+ do {
+ boost::hash_combine(seed, data::get_value(it).second);
+ it = it->next_;
+ } while(it != end);
+
+ return seed;
+ }
+
+ std::size_t hash_value() const
+ {
+ std::size_t seed = 0;
+
+ for(bucket_ptr i = data_.cached_begin_bucket_,
+ j = data_.buckets_end(); i != j; ++i)
+ {
+ for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
+ seed ^= group_hash(it, (type_wrapper<value_type>*)0);
+ }
+
+ return seed;
+ }
+
private:
// strong exception safety, no side effects
Modified: trunk/boost/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered_map.hpp (original)
+++ trunk/boost/unordered_map.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -18,8 +18,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
#if !defined(BOOST_HAS_RVALUE_REFS)
#include <boost/unordered/detail/move.hpp>
@@ -387,6 +387,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_map const& m1, unordered_map const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_map const& m1, unordered_map const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_map const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_map
template <class K, class T, class H, class P, class A>
@@ -739,6 +754,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_multimap const& m1, unordered_multimap const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_multimap const& m1, unordered_multimap const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_multimap const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_multimap
template <class K, class T, class H, class P, class A>
Modified: trunk/boost/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered_set.hpp (original)
+++ trunk/boost/unordered_set.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -18,8 +18,8 @@
#include <functional>
#include <memory>
-#include <boost/unordered/detail/hash_table.hpp>
#include <boost/functional/hash.hpp>
+#include <boost/unordered/detail/hash_table.hpp>
#if !defined(BOOST_HAS_RVALUE_REFS)
#include <boost/unordered/detail/move.hpp>
@@ -358,6 +358,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_set const& m1, unordered_set const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_set const& m1, unordered_set const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_set const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_set
template <class T, class H, class P, class A>
@@ -695,6 +710,21 @@
{
base.rehash(n);
}
+
+ friend bool operator==(unordered_multiset const& m1, unordered_multiset const& m2)
+ {
+ return m1.base.equals(m2.base);
+ }
+
+ friend bool operator!=(unordered_multiset const& m1, unordered_multiset const& m2)
+ {
+ return !m1.base.equals(m2.base);
+ }
+
+ friend std::size_t hash_value(unordered_multiset const& m)
+ {
+ return m.base.hash_value();
+ }
}; // class template unordered_multiset
template <class T, class H, class P, class A>
Modified: trunk/libs/unordered/doc/ref.xml
==============================================================================
--- trunk/libs/unordered/doc/ref.xml (original)
+++ trunk/libs/unordered/doc/ref.xml 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -657,6 +657,71 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_set<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
@@ -1339,6 +1404,71 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Value">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multiset<Value, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
@@ -2070,6 +2200,77 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_map<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
@@ -2762,6 +2963,77 @@
</throws>
</method>
</method-group>
+ <free-function-group name="Equality Comparisons">
+ <function name="operator==">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="operator!=">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <parameter name="y">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>bool</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ <function name="hash_value">
+ <template>
+ <template-type-parameter name="Key">
+ </template-type-parameter>
+ <template-type-parameter name="Mapped">
+ </template-type-parameter>
+ <template-type-parameter name="Hash">
+ </template-type-parameter>
+ <template-type-parameter name="Pred">
+ </template-type-parameter>
+ <template-type-parameter name="Alloc">
+ </template-type-parameter>
+ </template>
+ <parameter name="x">
+ <paramtype>unordered_multimap<Key, Mapped, Hash, Pred, Alloc> const&</paramtype>
+ </parameter>
+ <type>std::size_t</type>
+ <notes>
+ <para>This is a boost extension.</para>
+ </notes>
+ </function>
+ </free-function-group>
<free-function-group name="swap">
<function name="swap">
<template>
Modified: trunk/libs/unordered/test/helpers/equivalent.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/equivalent.hpp (original)
+++ trunk/libs/unordered/test/helpers/equivalent.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -8,10 +8,10 @@
#include <boost/unordered_map.hpp>
#include <boost/unordered_set.hpp>
-#include <vector>
#include <algorithm>
#include "./metafunctions.hpp"
#include "./fwd.hpp"
+#include "./list.hpp"
namespace test
{
@@ -56,20 +56,17 @@
BOOST_DEDUCED_TYPENAME Container::key_equal key_equal_;
float max_load_factor_;
- typedef BOOST_DEDUCED_TYPENAME non_const_value_type<Container>::type value_type;
- std::vector<value_type> values_;
+ typedef test::list<BOOST_DEDUCED_TYPENAME Container::value_type>
+ value_list;
+ value_list values_;
public:
unordered_equivalence_tester(Container const &x)
: size_(x.size()),
hasher_(x.hash_function()), key_equal_(x.key_eq()),
max_load_factor_(x.max_load_factor()),
- values_()
+ values_(x.begin(), x.end())
{
- // Can't initialise values_ straight from x because of Visual C++ 6
- values_.reserve(x.size());
- std::copy(x.begin(), x.end(), std::back_inserter(values_));
-
- std::sort(values_.begin(), values_.end());
+ values_.sort();
}
bool operator()(Container const& x) const
@@ -80,11 +77,9 @@
(max_load_factor_ == x.max_load_factor()) &&
(values_.size() == x.size()))) return false;
- std::vector<value_type> copy;
- copy.reserve(x.size());
- std::copy(x.begin(), x.end(), std::back_inserter(copy));
- std::sort(copy.begin(), copy.end());
- return(std::equal(values_.begin(), values_.end(), copy.begin()));
+ value_list copy(x.begin(), x.end());
+ copy.sort();
+ return values_ == copy;
}
private:
unordered_equivalence_tester();
Modified: trunk/libs/unordered/test/helpers/metafunctions.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/metafunctions.hpp (original)
+++ trunk/libs/unordered/test/helpers/metafunctions.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -75,35 +75,6 @@
sizeof(has_unique_key_impl((Container const*)0))
== sizeof(no_type));
};
-
- // Non Const Value Type
-
- template <bool IsMap>
- struct non_const_value_type_impl
- {
- template <class Container>
- struct apply {
- typedef std::pair<
- BOOST_DEDUCED_TYPENAME Container::key_type,
- BOOST_DEDUCED_TYPENAME Container::mapped_type> type;
- };
- };
-
- template<>
- struct non_const_value_type_impl<false>
- {
- template <class Container>
- struct apply {
- typedef BOOST_DEDUCED_TYPENAME Container::value_type type;
- };
- };
-
- template <class Container>
- struct non_const_value_type
- : non_const_value_type_impl< ::test::is_map<Container>::value>::
- BOOST_NESTED_TEMPLATE apply<Container>
- {
- };
}
#endif
Modified: trunk/libs/unordered/test/helpers/random_values.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/random_values.hpp (original)
+++ trunk/libs/unordered/test/helpers/random_values.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -6,7 +6,7 @@
#if !defined(BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER)
#define BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER
-#include <list>
+#include "./list.hpp"
#include <algorithm>
#include <boost/mpl/if.hpp>
#include "./generators.hpp"
@@ -97,7 +97,7 @@
template <class X>
struct random_values
- : public std::list<BOOST_DEDUCED_TYPENAME X::value_type>
+ : public test::list<BOOST_DEDUCED_TYPENAME X::value_type>
{
random_values(int count, test::random_generator const& generator =
test::default_generator)
Modified: trunk/libs/unordered/test/helpers/strong.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/strong.hpp (original)
+++ trunk/libs/unordered/test/helpers/strong.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -7,10 +7,10 @@
#define BOOST_UNORDERED_TEST_HELPERS_STRONG_HEADER
#include <boost/config.hpp>
-#include <vector>
#include <iterator>
#include "./metafunctions.hpp"
#include "./equivalent.hpp"
+#include "./list.hpp"
#include "../objects/exception.hpp"
namespace test
@@ -18,19 +18,19 @@
template <class X>
class strong
{
- typedef std::vector<BOOST_DEDUCED_TYPENAME non_const_value_type<X>::type> values_type;
+ typedef test::list<BOOST_DEDUCED_TYPENAME X::value_type> values_type;
values_type values_;
public:
void store(X const& x) {
DISABLE_EXCEPTIONS;
values_.clear();
- values_.reserve(x.size());
- std::copy(x.cbegin(), x.cend(), std::back_inserter(values_));
+ values_.insert(x.cbegin(), x.cend());
}
void test(X const& x) const {
if(!(x.size() == values_.size() &&
- std::equal(x.cbegin(), x.cend(), values_.begin(), test::equivalent)))
+ std::equal(x.cbegin(), x.cend(), values_.begin(),
+ test::equivalent)))
BOOST_ERROR("Strong exception safety failure.");
}
};
Modified: trunk/libs/unordered/test/helpers/test.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/test.hpp (original)
+++ trunk/libs/unordered/test/helpers/test.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -61,7 +61,7 @@
for(registered_test_base* i = first(); i; i = i->next)
i->run();
}
- };
+ }
}
#endif
Modified: trunk/libs/unordered/test/helpers/tracker.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/tracker.hpp (original)
+++ trunk/libs/unordered/test/helpers/tracker.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -11,7 +11,6 @@
#include <set>
#include <map>
-#include <vector>
#include <iterator>
#include <algorithm>
#include <boost/mpl/if.hpp>
@@ -22,6 +21,7 @@
#include "./metafunctions.hpp"
#include "./helpers.hpp"
#include "./equivalent.hpp"
+#include "./list.hpp"
namespace test
{
@@ -44,27 +44,23 @@
template <class X1, class X2>
void compare_range(X1 const& x1, X2 const& x2)
{
- std::vector<BOOST_DEDUCED_TYPENAME non_const_value_type<X1>::type> values1, values2;
- values1.reserve(x1.size());
- values2.reserve(x2.size());
- std::copy(x1.begin(), x1.end(), std::back_inserter(values1));
- std::copy(x2.begin(), x2.end(), std::back_inserter(values2));
- std::sort(values1.begin(), values1.end());
- std::sort(values2.begin(), values2.end());
+ typedef test::list<BOOST_DEDUCED_TYPENAME X1::value_type> value_list;
+ value_list values1(x1.begin(), x1.end());
+ value_list values2(x2.begin(), x2.end());
+ values1.sort();
+ values2.sort();
BOOST_CHECK(values1.size() == values2.size() &&
- std::equal(values1.begin(), values1.end(), values2.begin(), test::equivalent));
+ std::equal(values1.begin(), values1.end(), values2.begin(),
+ test::equivalent));
}
template <class X1, class X2, class T>
void compare_pairs(X1 const& x1, X2 const& x2, T*)
{
- std::vector<T> values1, values2;
- values1.reserve(std::distance(x1.first, x1.second));
- values2.reserve(std::distance(x2.first, x2.second));
- std::copy(x1.first, x1.second, std::back_inserter(values1));
- std::copy(x2.first, x2.second, std::back_inserter(values2));
- std::sort(values1.begin(), values1.end());
- std::sort(values2.begin(), values2.end());
+ test::list<T> values1(x1.first, x1.second);
+ test::list<T> values2(x2.first, x2.second);
+ values1.sort();
+ values2.sort();
BOOST_CHECK(values1.size() == values2.size() &&
std::equal(values1.begin(), values1.end(), values2.begin(), test::equivalent));
}
@@ -123,8 +119,7 @@
compare_pairs(
x.equal_range(get_key<X>(val)),
this->equal_range(get_key<X>(val)),
- (BOOST_DEDUCED_TYPENAME non_const_value_type<X>::type*) 0
- );
+ (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
}
template <class It>
Modified: trunk/libs/unordered/test/objects/minimal.hpp
==============================================================================
--- trunk/libs/unordered/test/objects/minimal.hpp (original)
+++ trunk/libs/unordered/test/objects/minimal.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -22,6 +22,7 @@
namespace minimal
{
class copy_constructible;
+ class copy_constructible_equality_comparable;
class default_copy_constructible;
class assignable;
@@ -42,6 +43,25 @@
copy_constructible() {}
};
+ class copy_constructible_equality_comparable
+ {
+ public:
+ static copy_constructible_equality_comparable create() { return copy_constructible_equality_comparable(); }
+ copy_constructible_equality_comparable(copy_constructible_equality_comparable const&) {}
+ ~copy_constructible_equality_comparable() {}
+ private:
+ copy_constructible_equality_comparable& operator=(copy_constructible_equality_comparable const&);
+ copy_constructible_equality_comparable() {}
+ };
+
+ bool operator==(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
+ return true;
+ }
+
+ bool operator!=(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
+ return false;
+ }
+
class default_copy_constructible
{
public:
@@ -246,6 +266,22 @@
}
}
+#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+namespace boost {
+#else
+namespace test {
+namespace minimal {
+#endif
+ std::size_t hash_value(test::minimal::copy_constructible_equality_comparable) {
+ return 1;
+ }
+#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+}}
+#else
+}
+#endif
+
+
#if defined(BOOST_MSVC)
#pragma warning(pop)
#endif
Modified: trunk/libs/unordered/test/unordered/Jamfile.v2
==============================================================================
--- trunk/libs/unordered/test/unordered/Jamfile.v2 (original)
+++ trunk/libs/unordered/test/unordered/Jamfile.v2 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -33,5 +33,6 @@
[ run bucket_tests.cpp ]
[ run load_factor_tests.cpp ]
[ run rehash_tests.cpp ]
+ [ run equality_tests.cpp ]
[ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
;
Modified: trunk/libs/unordered/test/unordered/compile_map.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/compile_map.cpp (original)
+++ trunk/libs/unordered/test/unordered/compile_map.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -22,6 +22,9 @@
test::minimal::copy_constructible::create());
std::cout<<"Test unordered_map.\n";
+
+ boost::unordered_map<int, int> int_map;
+
boost::unordered_map<
test::minimal::assignable,
test::minimal::copy_constructible,
@@ -29,9 +32,13 @@
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<value_type> > map;
+ container_test(int_map, std::pair<int const, int>(0, 0));
container_test(map, value);
std::cout<<"Test unordered_multimap.\n";
+
+ boost::unordered_multimap<int, int> int_multimap;
+
boost::unordered_multimap<
test::minimal::assignable,
test::minimal::copy_constructible,
@@ -39,9 +46,39 @@
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<value_type> > multimap;
+ container_test(int_multimap, std::pair<int const, int>(0, 0));
container_test(multimap, value);
}
+UNORDERED_AUTO_TEST(equality_tests) {
+ typedef std::pair<test::minimal::assignable const,
+ test::minimal::copy_constructible> value_type;
+
+ boost::unordered_map<int, int> int_map;
+
+ boost::unordered_map<
+ test::minimal::assignable,
+ test::minimal::copy_constructible_equality_comparable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > map;
+
+ equality_test(int_map);
+ equality_test(map);
+
+ boost::unordered_multimap<int, int> int_multimap;
+
+ boost::unordered_multimap<
+ test::minimal::assignable,
+ test::minimal::copy_constructible_equality_comparable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > multimap;
+
+ equality_test(int_multimap);
+ equality_test(multimap);
+}
+
UNORDERED_AUTO_TEST(test1) {
boost::hash<int> hash;
std::equal_to<int> equal_to;
Modified: trunk/libs/unordered/test/unordered/compile_set.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/compile_set.cpp (original)
+++ trunk/libs/unordered/test/unordered/compile_set.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -18,24 +18,54 @@
test::minimal::assignable assignable = test::minimal::assignable::create();
std::cout<<"Test unordered_set.\n";
+ boost::unordered_set<int> int_set;
boost::unordered_set<
test::minimal::assignable,
test::minimal::hash<test::minimal::assignable>,
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<test::minimal::assignable> > set;
+ container_test(int_set, 0);
container_test(set, assignable);
std::cout<<"Test unordered_multiset.\n";
+ boost::unordered_multiset<int> int_multiset;
boost::unordered_multiset<
test::minimal::assignable,
test::minimal::hash<test::minimal::assignable>,
test::minimal::equal_to<test::minimal::assignable>,
test::minimal::allocator<test::minimal::assignable> > multiset;
+ container_test(int_multiset, 0);
container_test(multiset, assignable);
}
+UNORDERED_AUTO_TEST(equality_tests) {
+ typedef test::minimal::assignable value_type;
+
+ boost::unordered_set<int> int_set;
+
+ boost::unordered_set<
+ test::minimal::assignable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > set;
+
+ equality_test(int_set);
+ equality_test(set);
+
+ boost::unordered_multiset<int> int_multiset;
+
+ boost::unordered_multiset<
+ test::minimal::assignable,
+ test::minimal::hash<test::minimal::assignable>,
+ test::minimal::equal_to<test::minimal::assignable>,
+ test::minimal::allocator<value_type> > multiset;
+
+ equality_test(int_multiset);
+ equality_test(multiset);
+}
+
UNORDERED_AUTO_TEST(test1)
{
boost::hash<int> hash;
Modified: trunk/libs/unordered/test/unordered/compile_tests.hpp
==============================================================================
--- trunk/libs/unordered/test/unordered/compile_tests.hpp (original)
+++ trunk/libs/unordered/test/unordered/compile_tests.hpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -28,7 +28,7 @@
template <class T> T rvalue(T const& v) { return v; }
template <class X, class T>
-void container_test(X& r, T&)
+void container_test(X& r, T const&)
{
typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
typedef BOOST_DEDUCED_TYPENAME X::const_iterator const_iterator;
@@ -121,8 +121,6 @@
test::check_return_type<const_iterator>::equals(a.cend());
test::check_return_type<const_iterator>::equals(a_const.cend());
- // No tests for ==, != since they're not required for unordered containers.
-
a.swap(b);
test::check_return_type<X>::equals_ref(r = a);
test::check_return_type<size_type>::equals(a.size());
@@ -161,6 +159,20 @@
#endif
}
+template <class X>
+void equality_test(X& r)
+{
+ X const a = r, b = r;
+
+ test::check_return_type<bool>::equals(a == b);
+ test::check_return_type<bool>::equals(a != b);
+#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
+ test::check_return_type<std::size_t>::equals(boost::hash_value(a));
+#else
+ test::check_return_type<std::size_t>::equals(hash_value(a));
+#endif
+}
+
template <class X, class T>
void unordered_unique_test(X& r, T const& t)
{
Modified: trunk/libs/unordered/test/unordered/constructor_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/constructor_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/constructor_tests.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -257,11 +257,9 @@
{
std::cerr<<"map_constructor_test\n";
- typedef std::list<std::pair<BOOST_DEDUCED_TYPENAME T::key_type, BOOST_DEDUCED_TYPENAME T::mapped_type> > list;
+ typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME T::key_type, BOOST_DEDUCED_TYPENAME T::mapped_type> > list;
test::random_values<T> v(1000);
- list l;
- std::copy(v.begin(), v.end(), std::back_inserter(l));
-
+ list l(v.begin(), v.end());
T x(l.begin(), l.end());
test::check_container(x, v);
Modified: trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -8,7 +8,7 @@
#include "../helpers/test.hpp"
#include <algorithm>
#include <map>
-#include <list>
+#include "../helpers/list.hpp"
#include "../helpers/tracker.hpp"
#include "../helpers/invariants.hpp"
@@ -57,7 +57,7 @@
UNORDERED_AUTO_TEST(map_tests)
{
- typedef std::list<std::pair<int const, int> > values_type;
+ typedef test::list<std::pair<int const, int> > values_type;
values_type v[5];
v[0].push_back(std::pair<int const, int>(1,1));
v[1].push_back(std::pair<int const, int>(28,34));
Modified: trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -8,7 +8,7 @@
#include <boost/unordered_map.hpp>
#include "../helpers/test.hpp"
-#include <list>
+#include "../helpers/list.hpp"
#include <set>
#include <iostream>
#include <iterator>
@@ -50,7 +50,7 @@
collision2_hash, std::equal_to<int>,
test::allocator<std::pair<int const, int> > > collide_map2;
typedef collide_map::value_type collide_value;
-typedef std::list<collide_value> collide_list;
+typedef test::list<collide_value> collide_list;
UNORDERED_AUTO_TEST(empty_range_tests)
{
@@ -108,10 +108,8 @@
template<class Range1, class Range2>
bool compare(Range1 const& x, Range2 const& y)
{
- collide_list a;
- collide_list b;
- std::copy(x.begin(), x.end(), std::back_inserter(a));
- std::copy(y.begin(), y.end(), std::back_inserter(b));
+ collide_list a(x.begin(), x.end());
+ collide_list b(y.begin(), y.end());
a.sort();
b.sort();
return a == b;
@@ -120,8 +118,7 @@
template <class Container>
bool general_erase_range_test(Container& x, int start, int end)
{
- collide_list l;
- std::copy(x.begin(), x.end(), std::back_inserter(l));
+ collide_list l(x.begin(), x.end());
l.erase(boost::next(l.begin(), start), boost::next(l.begin(), end));
x.erase(boost::next(x.begin(), start), boost::next(x.begin(), end));
return compare(l, x);
@@ -133,8 +130,7 @@
for(std::size_t length = 0; length < x.size(); ++length) {
for(std::size_t position = 0; position < x.size() - length; ++position) {
Container y(x);
- collide_list init;
- std::copy(y.begin(), y.end(), std::back_inserter(init));
+ collide_list init(y.begin(), y.end());
if(!general_erase_range_test(y, position, position + length)) {
BOOST_ERROR("general_erase_range_test failed.");
std::cout<<"Erase: ["<<position<<","<<position + length<<")\n";
Modified: trunk/libs/unordered/test/unordered/find_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/find_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/find_tests.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -43,10 +43,10 @@
test::compare_pairs(x.equal_range(key),
tracker.equal_range(key),
- (BOOST_DEDUCED_TYPENAME test::non_const_value_type<X>::type*) 0);
+ (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
test::compare_pairs(x_const.equal_range(key),
tracker.equal_range(key),
- (BOOST_DEDUCED_TYPENAME test::non_const_value_type<X>::type*) 0);
+ (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
}
test::random_values<X> v2(500, generator);
Modified: trunk/libs/unordered/test/unordered/insert_tests.cpp
==============================================================================
--- trunk/libs/unordered/test/unordered/insert_tests.cpp (original)
+++ trunk/libs/unordered/test/unordered/insert_tests.cpp 2008-04-30 03:57:04 EDT (Wed, 30 Apr 2008)
@@ -318,10 +318,9 @@
{
std::cerr<<"associative_insert_range_test\n";
- typedef std::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type, BOOST_DEDUCED_TYPENAME X::mapped_type> > list;
+ typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type, BOOST_DEDUCED_TYPENAME X::mapped_type> > list;
test::random_values<X> v(1000, generator);
- list l;
- std::copy(v.begin(), v.end(), std::back_inserter(l));
+ list l(v.begin(), v.end());
X x; x.insert(l.begin(), l.end());