Changeset 44919


Ignore:
Timestamp:
Apr 30, 2008, 7:57:04 AM (11 years ago)
Author:
Daniel James
Message:

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).

........

Location:
trunk
Files:
21 edited
1 copied

Legend:

Unmodified
Added
Removed
  • trunk

  • trunk/boost/unordered/detail/hash_table_impl.hpp

    r44738 r44919  
    11291129
    11301130
    1131             typedef boost::unordered_detail::buffered_functions<Hash, Pred> buffered_functions;
    1132             typedef BOOST_DEDUCED_TYPENAME buffered_functions::functions functions;
    1133             typedef BOOST_DEDUCED_TYPENAME buffered_functions::functions_ptr functions_ptr;
    1134 
    1135             buffered_functions functions_;
     1131            typedef boost::unordered_detail::buffered_functions<Hash, Pred>
     1132                function_store;
     1133            typedef BOOST_DEDUCED_TYPENAME function_store::functions functions;
     1134            typedef BOOST_DEDUCED_TYPENAME function_store::functions_ptr
     1135                functions_ptr;
     1136
     1137            function_store functions_;
    11361138            float mlf_;
    11371139            size_type max_load_;
     
    13771379
    13781380            // no throw
     1381#if defined(BOOST_HAS_RVALUE_REFS) && defined(BOOST_HAS_VARIADIC_TMPL)
    13791382            node_allocator get_allocator() const
    13801383            {
    13811384                return data_.allocators_.node_alloc_;
    13821385            }
     1386#else
     1387            value_allocator get_allocator() const
     1388            {
     1389                return data_.allocators_.value_alloc_;
     1390            }
     1391#endif
    13831392
    13841393            // no throw
     
    21372146            }
    21382147
     2148            //
     2149            // equals
     2150            //
     2151
     2152private:
     2153#if BOOST_UNORDERED_EQUIVALENT_KEYS
     2154            static inline bool group_equals(link_ptr it1, link_ptr it2,
     2155                    type_wrapper<key_type>*)
     2156            {
     2157                return data::group_count(it1) == data::group_count(it2);
     2158            }
     2159
     2160            static inline bool group_equals(link_ptr it1, link_ptr it2, void*)
     2161            {
     2162                link_ptr end1 = data::next_group(it1);
     2163                link_ptr end2 = data::next_group(it2);
     2164                do {
     2165                    if(data::get_value(it1).second != data::get_value(it2).second) return false;
     2166                    it1 = it1->next_;
     2167                    it2 = it2->next_;
     2168                } while(it1 != end1 && it2 != end2);
     2169                return it1 == end1 && it2 == end2;
     2170            }
     2171#else
     2172            static inline bool group_equals(link_ptr it1, link_ptr it2,
     2173                    type_wrapper<key_type>*)
     2174            {
     2175                return true;
     2176            }
     2177
     2178            static inline bool group_equals(link_ptr it1, link_ptr it2, void*)
     2179            {
     2180                return data::get_value(it1).second == data::get_value(it2).second;
     2181            }
     2182#endif
     2183
     2184public:
     2185            bool equals(BOOST_UNORDERED_TABLE const& other) const
     2186            {
     2187                if(size() != other.size()) return false;
     2188
     2189                for(bucket_ptr i = data_.cached_begin_bucket_,
     2190                        j = data_.buckets_end(); i != j; ++i)
     2191                {
     2192                    for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
     2193                    {
     2194                        link_ptr other_pos = other.find_iterator(other.extract_key(data::get_value(it)));
     2195                        if(!BOOST_UNORDERED_BORLAND_BOOL(other_pos) ||
     2196                            !group_equals(it, other_pos, (type_wrapper<value_type>*)0))
     2197                            return false;
     2198                    }
     2199                }
     2200
     2201                return true;
     2202            }
     2203
     2204            inline std::size_t group_hash(link_ptr it, type_wrapper<key_type>*) const
     2205            {
     2206                std::size_t seed = data::group_count(it);
     2207                std::size_t hashed_key = hash_function()(data::get_value(it));
     2208                boost::hash_combine(seed, hashed_key);
     2209                return seed;
     2210            }
     2211
     2212            inline std::size_t group_hash(link_ptr it, void*) const
     2213            {
     2214                std::size_t seed = hash_function()(data::get_value(it).first);
     2215
     2216                link_ptr end = data::next_group(it);
     2217
     2218                do {
     2219                    boost::hash_combine(seed, data::get_value(it).second);
     2220                    it = it->next_;
     2221                } while(it != end);
     2222
     2223                return seed;
     2224            }
     2225
     2226            std::size_t hash_value() const
     2227            {
     2228                std::size_t seed = 0;
     2229
     2230                for(bucket_ptr i = data_.cached_begin_bucket_,
     2231                        j = data_.buckets_end(); i != j; ++i)
     2232                {
     2233                    for(link_ptr it(i->next_); BOOST_UNORDERED_BORLAND_BOOL(it); it = data::next_group(it))
     2234                        seed ^= group_hash(it, (type_wrapper<value_type>*)0);
     2235                }
     2236
     2237                return seed;
     2238            }
     2239
    21392240        private:
    21402241
  • trunk/boost/unordered_map.hpp

    r44738 r44919  
    1919#include <memory>
    2020
     21#include <boost/functional/hash.hpp>
    2122#include <boost/unordered/detail/hash_table.hpp>
    22 #include <boost/functional/hash.hpp>
    2323
    2424#if !defined(BOOST_HAS_RVALUE_REFS)
     
    388388            base.rehash(n);
    389389        }
     390       
     391        friend bool operator==(unordered_map const& m1, unordered_map const& m2)
     392        {
     393            return m1.base.equals(m2.base);
     394        }
     395
     396        friend bool operator!=(unordered_map const& m1, unordered_map const& m2)
     397        {
     398            return !m1.base.equals(m2.base);
     399        }
     400
     401        friend std::size_t hash_value(unordered_map const& m)
     402        {
     403            return m.base.hash_value();
     404        }
    390405    }; // class template unordered_map
    391406
     
    740755            base.rehash(n);
    741756        }
     757
     758        friend bool operator==(unordered_multimap const& m1, unordered_multimap const& m2)
     759        {
     760            return m1.base.equals(m2.base);
     761        }
     762
     763        friend bool operator!=(unordered_multimap const& m1, unordered_multimap const& m2)
     764        {
     765            return !m1.base.equals(m2.base);
     766        }
     767
     768        friend std::size_t hash_value(unordered_multimap const& m)
     769        {
     770            return m.base.hash_value();
     771        }
    742772    }; // class template unordered_multimap
    743773
  • trunk/boost/unordered_set.hpp

    r44738 r44919  
    1919#include <memory>
    2020
     21#include <boost/functional/hash.hpp>
    2122#include <boost/unordered/detail/hash_table.hpp>
    22 #include <boost/functional/hash.hpp>
    2323
    2424#if !defined(BOOST_HAS_RVALUE_REFS)
     
    359359            base.rehash(n);
    360360        }
     361
     362        friend bool operator==(unordered_set const& m1, unordered_set const& m2)
     363        {
     364            return m1.base.equals(m2.base);
     365        }
     366
     367        friend bool operator!=(unordered_set const& m1, unordered_set const& m2)
     368        {
     369            return !m1.base.equals(m2.base);
     370        }
     371
     372        friend std::size_t hash_value(unordered_set const& m)
     373        {
     374            return m.base.hash_value();
     375        }
    361376    }; // class template unordered_set
    362377
     
    696711            base.rehash(n);
    697712        }
     713
     714        friend bool operator==(unordered_multiset const& m1, unordered_multiset const& m2)
     715        {
     716            return m1.base.equals(m2.base);
     717        }
     718
     719        friend bool operator!=(unordered_multiset const& m1, unordered_multiset const& m2)
     720        {
     721            return !m1.base.equals(m2.base);
     722        }
     723
     724        friend std::size_t hash_value(unordered_multiset const& m)
     725        {
     726            return m.base.hash_value();
     727        }
    698728    }; // class template unordered_multiset
    699729
  • trunk/libs/unordered/doc/ref.xml

    r44738 r44919  
    658658            </method>
    659659          </method-group>
     660          <free-function-group name="Equality Comparisons">
     661            <function name="operator==">
     662              <template>
     663                <template-type-parameter name="Value">
     664                </template-type-parameter>
     665                <template-type-parameter name="Hash">
     666                </template-type-parameter>
     667                <template-type-parameter name="Pred">
     668                </template-type-parameter>
     669                <template-type-parameter name="Alloc">
     670                </template-type-parameter>
     671              </template>
     672              <parameter name="x">
     673                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     674              </parameter>
     675              <parameter name="y">
     676                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     677              </parameter>
     678              <type>bool</type>
     679              <notes>
     680                <para>This is a boost extension.</para>
     681              </notes>
     682            </function>
     683            <function name="operator!=">
     684              <template>
     685                <template-type-parameter name="Value">
     686                </template-type-parameter>
     687                <template-type-parameter name="Hash">
     688                </template-type-parameter>
     689                <template-type-parameter name="Pred">
     690                </template-type-parameter>
     691                <template-type-parameter name="Alloc">
     692                </template-type-parameter>
     693              </template>
     694              <parameter name="x">
     695                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     696              </parameter>
     697              <parameter name="y">
     698                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     699              </parameter>
     700              <type>bool</type>
     701              <notes>
     702                <para>This is a boost extension.</para>
     703              </notes>
     704            </function>
     705            <function name="hash_value">
     706              <template>
     707                <template-type-parameter name="Value">
     708                </template-type-parameter>
     709                <template-type-parameter name="Hash">
     710                </template-type-parameter>
     711                <template-type-parameter name="Pred">
     712                </template-type-parameter>
     713                <template-type-parameter name="Alloc">
     714                </template-type-parameter>
     715              </template>
     716              <parameter name="x">
     717                <paramtype>unordered_set&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     718              </parameter>
     719              <type>std::size_t</type>
     720              <notes>
     721                <para>This is a boost extension.</para>
     722              </notes>
     723            </function>
     724          </free-function-group>
    660725          <free-function-group name="swap">
    661726            <function name="swap">
     
    13401405            </method>
    13411406          </method-group>
     1407          <free-function-group name="Equality Comparisons">
     1408            <function name="operator==">
     1409              <template>
     1410                <template-type-parameter name="Value">
     1411                </template-type-parameter>
     1412                <template-type-parameter name="Hash">
     1413                </template-type-parameter>
     1414                <template-type-parameter name="Pred">
     1415                </template-type-parameter>
     1416                <template-type-parameter name="Alloc">
     1417                </template-type-parameter>
     1418              </template>
     1419              <parameter name="x">
     1420                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     1421              </parameter>
     1422              <parameter name="y">
     1423                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     1424              </parameter>
     1425              <type>bool</type>
     1426              <notes>
     1427                <para>This is a boost extension.</para>
     1428              </notes>
     1429            </function>
     1430            <function name="operator!=">
     1431              <template>
     1432                <template-type-parameter name="Value">
     1433                </template-type-parameter>
     1434                <template-type-parameter name="Hash">
     1435                </template-type-parameter>
     1436                <template-type-parameter name="Pred">
     1437                </template-type-parameter>
     1438                <template-type-parameter name="Alloc">
     1439                </template-type-parameter>
     1440              </template>
     1441              <parameter name="x">
     1442                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     1443              </parameter>
     1444              <parameter name="y">
     1445                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     1446              </parameter>
     1447              <type>bool</type>
     1448              <notes>
     1449                <para>This is a boost extension.</para>
     1450              </notes>
     1451            </function>
     1452            <function name="hash_value">
     1453              <template>
     1454                <template-type-parameter name="Value">
     1455                </template-type-parameter>
     1456                <template-type-parameter name="Hash">
     1457                </template-type-parameter>
     1458                <template-type-parameter name="Pred">
     1459                </template-type-parameter>
     1460                <template-type-parameter name="Alloc">
     1461                </template-type-parameter>
     1462              </template>
     1463              <parameter name="x">
     1464                <paramtype>unordered_multiset&lt;Value, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     1465              </parameter>
     1466              <type>std::size_t</type>
     1467              <notes>
     1468                <para>This is a boost extension.</para>
     1469              </notes>
     1470            </function>
     1471          </free-function-group>
    13421472          <free-function-group name="swap">
    13431473            <function name="swap">
     
    20712201            </method>
    20722202          </method-group>
     2203          <free-function-group name="Equality Comparisons">
     2204            <function name="operator==">
     2205              <template>
     2206                <template-type-parameter name="Key">
     2207                </template-type-parameter>
     2208                <template-type-parameter name="Mapped">
     2209                </template-type-parameter>
     2210                <template-type-parameter name="Hash">
     2211                </template-type-parameter>
     2212                <template-type-parameter name="Pred">
     2213                </template-type-parameter>
     2214                <template-type-parameter name="Alloc">
     2215                </template-type-parameter>
     2216              </template>
     2217              <parameter name="x">
     2218                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2219              </parameter>
     2220              <parameter name="y">
     2221                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2222              </parameter>
     2223              <type>bool</type>
     2224              <notes>
     2225                <para>This is a boost extension.</para>
     2226              </notes>
     2227            </function>
     2228            <function name="operator!=">
     2229              <template>
     2230                <template-type-parameter name="Key">
     2231                </template-type-parameter>
     2232                <template-type-parameter name="Mapped">
     2233                </template-type-parameter>
     2234                <template-type-parameter name="Hash">
     2235                </template-type-parameter>
     2236                <template-type-parameter name="Pred">
     2237                </template-type-parameter>
     2238                <template-type-parameter name="Alloc">
     2239                </template-type-parameter>
     2240              </template>
     2241              <parameter name="x">
     2242                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2243              </parameter>
     2244              <parameter name="y">
     2245                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2246              </parameter>
     2247              <type>bool</type>
     2248              <notes>
     2249                <para>This is a boost extension.</para>
     2250              </notes>
     2251            </function>
     2252            <function name="hash_value">
     2253              <template>
     2254                <template-type-parameter name="Key">
     2255                </template-type-parameter>
     2256                <template-type-parameter name="Mapped">
     2257                </template-type-parameter>
     2258                <template-type-parameter name="Hash">
     2259                </template-type-parameter>
     2260                <template-type-parameter name="Pred">
     2261                </template-type-parameter>
     2262                <template-type-parameter name="Alloc">
     2263                </template-type-parameter>
     2264              </template>
     2265              <parameter name="x">
     2266                <paramtype>unordered_map&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2267              </parameter>
     2268              <type>std::size_t</type>
     2269              <notes>
     2270                <para>This is a boost extension.</para>
     2271              </notes>
     2272            </function>
     2273          </free-function-group>
    20732274          <free-function-group name="swap">
    20742275            <function name="swap">
     
    27632964            </method>
    27642965          </method-group>
     2966          <free-function-group name="Equality Comparisons">
     2967            <function name="operator==">
     2968              <template>
     2969                <template-type-parameter name="Key">
     2970                </template-type-parameter>
     2971                <template-type-parameter name="Mapped">
     2972                </template-type-parameter>
     2973                <template-type-parameter name="Hash">
     2974                </template-type-parameter>
     2975                <template-type-parameter name="Pred">
     2976                </template-type-parameter>
     2977                <template-type-parameter name="Alloc">
     2978                </template-type-parameter>
     2979              </template>
     2980              <parameter name="x">
     2981                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2982              </parameter>
     2983              <parameter name="y">
     2984                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     2985              </parameter>
     2986              <type>bool</type>
     2987              <notes>
     2988                <para>This is a boost extension.</para>
     2989              </notes>
     2990            </function>
     2991            <function name="operator!=">
     2992              <template>
     2993                <template-type-parameter name="Key">
     2994                </template-type-parameter>
     2995                <template-type-parameter name="Mapped">
     2996                </template-type-parameter>
     2997                <template-type-parameter name="Hash">
     2998                </template-type-parameter>
     2999                <template-type-parameter name="Pred">
     3000                </template-type-parameter>
     3001                <template-type-parameter name="Alloc">
     3002                </template-type-parameter>
     3003              </template>
     3004              <parameter name="x">
     3005                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     3006              </parameter>
     3007              <parameter name="y">
     3008                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     3009              </parameter>
     3010              <type>bool</type>
     3011              <notes>
     3012                <para>This is a boost extension.</para>
     3013              </notes>
     3014            </function>
     3015            <function name="hash_value">
     3016              <template>
     3017                <template-type-parameter name="Key">
     3018                </template-type-parameter>
     3019                <template-type-parameter name="Mapped">
     3020                </template-type-parameter>
     3021                <template-type-parameter name="Hash">
     3022                </template-type-parameter>
     3023                <template-type-parameter name="Pred">
     3024                </template-type-parameter>
     3025                <template-type-parameter name="Alloc">
     3026                </template-type-parameter>
     3027              </template>
     3028              <parameter name="x">
     3029                <paramtype>unordered_multimap&lt;Key, Mapped, Hash, Pred, Alloc&gt; const&amp;</paramtype>
     3030              </parameter>
     3031              <type>std::size_t</type>
     3032              <notes>
     3033                <para>This is a boost extension.</para>
     3034              </notes>
     3035            </function>
     3036          </free-function-group>
    27653037          <free-function-group name="swap">
    27663038            <function name="swap">
  • trunk/libs/unordered/test/helpers/equivalent.hpp

    r43895 r44919  
    99#include <boost/unordered_map.hpp>
    1010#include <boost/unordered_set.hpp>
    11 #include <vector>
    1211#include <algorithm>
    1312#include "./metafunctions.hpp"
    1413#include "./fwd.hpp"
     14#include "./list.hpp"
    1515
    1616namespace test
     
    5757        float max_load_factor_;
    5858
    59         typedef BOOST_DEDUCED_TYPENAME non_const_value_type<Container>::type value_type;
    60         std::vector<value_type> values_;
     59        typedef test::list<BOOST_DEDUCED_TYPENAME Container::value_type>
     60            value_list;
     61        value_list values_;
    6162    public:
    6263        unordered_equivalence_tester(Container const &x)
     
    6465            hasher_(x.hash_function()), key_equal_(x.key_eq()),
    6566            max_load_factor_(x.max_load_factor()),
    66             values_()
     67            values_(x.begin(), x.end())
    6768        {
    68             // Can't initialise values_ straight from x because of Visual C++ 6
    69             values_.reserve(x.size());
    70             std::copy(x.begin(), x.end(), std::back_inserter(values_));
    71            
    72             std::sort(values_.begin(), values_.end());
     69            values_.sort();
    7370        }
    7471
     
    8178                (values_.size() == x.size()))) return false;
    8279
    83             std::vector<value_type> copy;
    84             copy.reserve(x.size());
    85             std::copy(x.begin(), x.end(), std::back_inserter(copy));
    86             std::sort(copy.begin(), copy.end());
    87             return(std::equal(values_.begin(), values_.end(), copy.begin()));
     80            value_list copy(x.begin(), x.end());
     81            copy.sort();
     82            return values_ == copy;
    8883        }
    8984    private:
  • trunk/libs/unordered/test/helpers/metafunctions.hpp

    r44488 r44919  
    7676                == sizeof(no_type));
    7777    };
    78 
    79     // Non Const Value Type
    80 
    81     template <bool IsMap>
    82     struct non_const_value_type_impl
    83     {
    84         template <class Container>
    85         struct apply {
    86             typedef std::pair<
    87                 BOOST_DEDUCED_TYPENAME Container::key_type,
    88                 BOOST_DEDUCED_TYPENAME Container::mapped_type> type;
    89         };
    90     };
    91 
    92     template<>
    93     struct non_const_value_type_impl<false>
    94     {
    95         template <class Container>
    96         struct apply {
    97             typedef BOOST_DEDUCED_TYPENAME Container::value_type type;
    98         };
    99     };
    100    
    101     template <class Container>
    102     struct non_const_value_type
    103         : non_const_value_type_impl< ::test::is_map<Container>::value>::
    104             BOOST_NESTED_TEMPLATE apply<Container>
    105     {
    106     };
    10778}
    10879
  • trunk/libs/unordered/test/helpers/random_values.hpp

    r43895 r44919  
    77#define BOOST_UNORDERED_TEST_HELPERS_RANDOM_VALUES_HEADER
    88
    9 #include <list>
     9#include "./list.hpp"
    1010#include <algorithm>
    1111#include <boost/mpl/if.hpp>
     
    9898    template <class X>
    9999    struct random_values
    100         : public std::list<BOOST_DEDUCED_TYPENAME X::value_type>
     100        : public test::list<BOOST_DEDUCED_TYPENAME X::value_type>
    101101    {
    102102        random_values(int count, test::random_generator const& generator =
  • trunk/libs/unordered/test/helpers/strong.hpp

    r43895 r44919  
    88
    99#include <boost/config.hpp>
    10 #include <vector>
    1110#include <iterator>
    1211#include "./metafunctions.hpp"
    1312#include "./equivalent.hpp"
     13#include "./list.hpp"
    1414#include "../objects/exception.hpp"
    1515
     
    1919    class strong
    2020    {
    21         typedef std::vector<BOOST_DEDUCED_TYPENAME non_const_value_type<X>::type> values_type;
     21        typedef test::list<BOOST_DEDUCED_TYPENAME X::value_type> values_type;
    2222        values_type values_;
    2323    public:
     
    2525            DISABLE_EXCEPTIONS;
    2626            values_.clear();
    27             values_.reserve(x.size());
    28             std::copy(x.cbegin(), x.cend(), std::back_inserter(values_));
     27            values_.insert(x.cbegin(), x.cend());
    2928        }
    3029
    3130        void test(X const& x) const {
    3231            if(!(x.size() == values_.size() &&
    33                         std::equal(x.cbegin(), x.cend(), values_.begin(), test::equivalent)))
     32                    std::equal(x.cbegin(), x.cend(), values_.begin(),
     33                        test::equivalent)))
    3434                BOOST_ERROR("Strong exception safety failure.");
    3535        }
  • trunk/libs/unordered/test/helpers/test.hpp

    r44487 r44919  
    6262                i->run();
    6363        }
    64     };
     64    }
    6565}
    6666
  • trunk/libs/unordered/test/helpers/tracker.hpp

    r44487 r44919  
    1212#include <set>
    1313#include <map>
    14 #include <vector>
    1514#include <iterator>
    1615#include <algorithm>
     
    2322#include "./helpers.hpp"
    2423#include "./equivalent.hpp"
     24#include "./list.hpp"
    2525
    2626namespace test
     
    4545    void compare_range(X1 const& x1, X2 const& x2)
    4646    {
    47         std::vector<BOOST_DEDUCED_TYPENAME non_const_value_type<X1>::type> values1, values2;
    48         values1.reserve(x1.size());
    49         values2.reserve(x2.size());
    50         std::copy(x1.begin(), x1.end(), std::back_inserter(values1));
    51         std::copy(x2.begin(), x2.end(), std::back_inserter(values2));
    52         std::sort(values1.begin(), values1.end());
    53         std::sort(values2.begin(), values2.end());
     47        typedef test::list<BOOST_DEDUCED_TYPENAME X1::value_type> value_list;
     48        value_list values1(x1.begin(), x1.end());
     49        value_list values2(x2.begin(), x2.end());
     50        values1.sort();
     51        values2.sort();
    5452        BOOST_CHECK(values1.size() == values2.size() &&
    55                 std::equal(values1.begin(), values1.end(), values2.begin(), test::equivalent));
     53                std::equal(values1.begin(), values1.end(), values2.begin(),
     54                    test::equivalent));
    5655    }
    5756
     
    5958    void compare_pairs(X1 const& x1, X2 const& x2, T*)
    6059    {
    61         std::vector<T> values1, values2;
    62         values1.reserve(std::distance(x1.first, x1.second));
    63         values2.reserve(std::distance(x2.first, x2.second));
    64         std::copy(x1.first, x1.second, std::back_inserter(values1));
    65         std::copy(x2.first, x2.second, std::back_inserter(values2));
    66         std::sort(values1.begin(), values1.end());
    67         std::sort(values2.begin(), values2.end());
     60        test::list<T> values1(x1.first, x1.second);
     61        test::list<T> values2(x2.first, x2.second);
     62        values1.sort();
     63        values2.sort();
    6864        BOOST_CHECK(values1.size() == values2.size() &&
    6965                std::equal(values1.begin(), values1.end(), values2.begin(), test::equivalent));
     
    124120                x.equal_range(get_key<X>(val)),
    125121                this->equal_range(get_key<X>(val)),
    126                 (BOOST_DEDUCED_TYPENAME non_const_value_type<X>::type*) 0
    127                 );
     122                (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
    128123        }
    129124
  • trunk/libs/unordered/test/objects/minimal.hpp

    r44738 r44919  
    2323{
    2424    class copy_constructible;
     25    class copy_constructible_equality_comparable;
    2526    class default_copy_constructible;
    2627    class assignable;
     
    4243        copy_constructible() {}
    4344    };
     45
     46    class copy_constructible_equality_comparable
     47    {
     48    public:
     49        static copy_constructible_equality_comparable create() { return copy_constructible_equality_comparable(); }
     50        copy_constructible_equality_comparable(copy_constructible_equality_comparable const&) {}
     51        ~copy_constructible_equality_comparable() {}
     52    private:
     53        copy_constructible_equality_comparable& operator=(copy_constructible_equality_comparable const&);
     54        copy_constructible_equality_comparable() {}
     55    };
     56
     57    bool operator==(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
     58        return true;
     59    }
     60
     61    bool operator!=(copy_constructible_equality_comparable, copy_constructible_equality_comparable) {
     62        return false;
     63    }
    4464
    4565    class default_copy_constructible
     
    247267}
    248268
     269#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
     270namespace boost {
     271#else
     272namespace test {
     273namespace minimal {
     274#endif
     275    std::size_t hash_value(test::minimal::copy_constructible_equality_comparable) {
     276        return 1;
     277    }
     278#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
     279}}
     280#else
     281}
     282#endif
     283
     284
    249285#if defined(BOOST_MSVC)
    250286#pragma warning(pop)
  • trunk/libs/unordered/test/unordered/Jamfile.v2

    r44486 r44919  
    3434        [ run load_factor_tests.cpp ]
    3535        [ run rehash_tests.cpp ]
     36        [ run equality_tests.cpp ]
    3637        [ run swap_tests.cpp : : : <define>BOOST_UNORDERED_SWAP_METHOD=2 ]
    3738    ;
  • trunk/libs/unordered/test/unordered/compile_map.cpp

    r43895 r44919  
    2323
    2424    std::cout<<"Test unordered_map.\n";
     25
     26    boost::unordered_map<int, int> int_map;
     27
    2528    boost::unordered_map<
    2629        test::minimal::assignable,
     
    3033        test::minimal::allocator<value_type> > map;
    3134
     35    container_test(int_map, std::pair<int const, int>(0, 0));
    3236    container_test(map, value);
    3337
    3438    std::cout<<"Test unordered_multimap.\n";
     39
     40    boost::unordered_multimap<int, int> int_multimap;
     41
    3542    boost::unordered_multimap<
    3643        test::minimal::assignable,
     
    4047        test::minimal::allocator<value_type> > multimap;
    4148
     49    container_test(int_multimap, std::pair<int const, int>(0, 0));
    4250    container_test(multimap, value);
     51}
     52
     53UNORDERED_AUTO_TEST(equality_tests) {
     54    typedef std::pair<test::minimal::assignable const,
     55            test::minimal::copy_constructible> value_type;
     56
     57    boost::unordered_map<int, int> int_map;
     58
     59    boost::unordered_map<
     60        test::minimal::assignable,
     61        test::minimal::copy_constructible_equality_comparable,
     62        test::minimal::hash<test::minimal::assignable>,
     63        test::minimal::equal_to<test::minimal::assignable>,
     64        test::minimal::allocator<value_type> > map;
     65
     66    equality_test(int_map);
     67    equality_test(map);
     68
     69    boost::unordered_multimap<int, int> int_multimap;
     70
     71    boost::unordered_multimap<
     72        test::minimal::assignable,
     73        test::minimal::copy_constructible_equality_comparable,
     74        test::minimal::hash<test::minimal::assignable>,
     75        test::minimal::equal_to<test::minimal::assignable>,
     76        test::minimal::allocator<value_type> > multimap;
     77
     78    equality_test(int_multimap);
     79    equality_test(multimap);
    4380}
    4481
  • trunk/libs/unordered/test/unordered/compile_set.cpp

    r43895 r44919  
    1919
    2020    std::cout<<"Test unordered_set.\n";
     21    boost::unordered_set<int> int_set;
    2122    boost::unordered_set<
    2223        test::minimal::assignable,
     
    2526        test::minimal::allocator<test::minimal::assignable> > set;
    2627
     28    container_test(int_set, 0);
    2729    container_test(set, assignable);
    2830
    2931    std::cout<<"Test unordered_multiset.\n";
     32    boost::unordered_multiset<int> int_multiset;
    3033    boost::unordered_multiset<
    3134        test::minimal::assignable,
     
    3437        test::minimal::allocator<test::minimal::assignable> > multiset;
    3538
     39    container_test(int_multiset, 0);
    3640    container_test(multiset, assignable);
     41}
     42
     43UNORDERED_AUTO_TEST(equality_tests) {
     44    typedef test::minimal::assignable value_type;
     45
     46    boost::unordered_set<int> int_set;
     47
     48    boost::unordered_set<
     49        test::minimal::assignable,
     50        test::minimal::hash<test::minimal::assignable>,
     51        test::minimal::equal_to<test::minimal::assignable>,
     52        test::minimal::allocator<value_type> > set;
     53
     54    equality_test(int_set);
     55    equality_test(set);
     56
     57    boost::unordered_multiset<int> int_multiset;
     58
     59    boost::unordered_multiset<
     60        test::minimal::assignable,
     61        test::minimal::hash<test::minimal::assignable>,
     62        test::minimal::equal_to<test::minimal::assignable>,
     63        test::minimal::allocator<value_type> > multiset;
     64
     65    equality_test(int_multiset);
     66    equality_test(multiset);
    3767}
    3868
  • trunk/libs/unordered/test/unordered/compile_tests.hpp

    r44738 r44919  
    2929
    3030template <class X, class T>
    31 void container_test(X& r, T&)
     31void container_test(X& r, T const&)
    3232{
    3333    typedef BOOST_DEDUCED_TYPENAME X::iterator iterator;
     
    122122    test::check_return_type<const_iterator>::equals(a_const.cend());
    123123
    124     // No tests for ==, != since they're not required for unordered containers.
    125 
    126124    a.swap(b);
    127125    test::check_return_type<X>::equals_ref(r = a);
     
    159157    r.emplace(k_lvalue, v_lvalue);
    160158    r.emplace(rvalue(k), rvalue(v));
     159#endif
     160}
     161
     162template <class X>
     163void equality_test(X& r)
     164{
     165    X const a = r, b = r;
     166
     167    test::check_return_type<bool>::equals(a == b);
     168    test::check_return_type<bool>::equals(a != b);
     169#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
     170    test::check_return_type<std::size_t>::equals(boost::hash_value(a));
     171#else
     172    test::check_return_type<std::size_t>::equals(hash_value(a));
    161173#endif
    162174}
  • trunk/libs/unordered/test/unordered/constructor_tests.cpp

    r44487 r44919  
    258258    std::cerr<<"map_constructor_test\n";
    259259
    260     typedef std::list<std::pair<BOOST_DEDUCED_TYPENAME T::key_type, BOOST_DEDUCED_TYPENAME T::mapped_type> > list;
     260    typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME T::key_type, BOOST_DEDUCED_TYPENAME T::mapped_type> > list;
    261261    test::random_values<T> v(1000);
    262     list l;
    263     std::copy(v.begin(), v.end(), std::back_inserter(l));
    264 
     262    list l(v.begin(), v.end());
    265263    T x(l.begin(), l.end());
    266264
  • trunk/libs/unordered/test/unordered/equivalent_keys_tests.cpp

    r43895 r44919  
    99#include <algorithm>
    1010#include <map>
    11 #include <list>
     11#include "../helpers/list.hpp"
    1212#include "../helpers/tracker.hpp"
    1313#include "../helpers/invariants.hpp"
     
    5858UNORDERED_AUTO_TEST(map_tests)
    5959{
    60     typedef std::list<std::pair<int const, int> > values_type;
     60    typedef test::list<std::pair<int const, int> > values_type;
    6161    values_type v[5];
    6262    v[0].push_back(std::pair<int const, int>(1,1));
  • trunk/libs/unordered/test/unordered/erase_equiv_tests.cpp

    r44487 r44919  
    99#include <boost/unordered_map.hpp>
    1010#include "../helpers/test.hpp"
    11 #include <list>
     11#include "../helpers/list.hpp"
    1212#include <set>
    1313#include <iostream>
     
    5151    test::allocator<std::pair<int const, int> > > collide_map2;
    5252typedef collide_map::value_type collide_value;
    53 typedef std::list<collide_value> collide_list;
     53typedef test::list<collide_value> collide_list;
    5454
    5555UNORDERED_AUTO_TEST(empty_range_tests)
     
    109109bool compare(Range1 const& x, Range2 const& y)
    110110{
    111     collide_list a;
    112     collide_list b;
    113     std::copy(x.begin(), x.end(), std::back_inserter(a));
    114     std::copy(y.begin(), y.end(), std::back_inserter(b));
     111    collide_list a(x.begin(), x.end());
     112    collide_list b(y.begin(), y.end());
    115113    a.sort();
    116114    b.sort();
     
    121119bool general_erase_range_test(Container& x, int start, int end)
    122120{
    123     collide_list l;
    124     std::copy(x.begin(), x.end(), std::back_inserter(l));
     121    collide_list l(x.begin(), x.end());
    125122    l.erase(boost::next(l.begin(), start), boost::next(l.begin(), end));
    126123    x.erase(boost::next(x.begin(), start), boost::next(x.begin(), end));
     
    134131        for(std::size_t position = 0; position < x.size() - length; ++position) {
    135132            Container y(x);
    136             collide_list init;
    137             std::copy(y.begin(), y.end(), std::back_inserter(init));
     133            collide_list init(y.begin(), y.end());
    138134            if(!general_erase_range_test(y, position, position + length)) {
    139135                BOOST_ERROR("general_erase_range_test failed.");
  • trunk/libs/unordered/test/unordered/find_tests.cpp

    r44487 r44919  
    4444            test::compare_pairs(x.equal_range(key),
    4545                    tracker.equal_range(key),
    46                     (BOOST_DEDUCED_TYPENAME test::non_const_value_type<X>::type*) 0);
     46                    (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
    4747            test::compare_pairs(x_const.equal_range(key),
    4848                    tracker.equal_range(key),
    49                     (BOOST_DEDUCED_TYPENAME test::non_const_value_type<X>::type*) 0);
     49                    (BOOST_DEDUCED_TYPENAME X::value_type*) 0);
    5050        }
    5151
  • trunk/libs/unordered/test/unordered/insert_tests.cpp

    r44738 r44919  
    319319    std::cerr<<"associative_insert_range_test\n";
    320320
    321     typedef std::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type, BOOST_DEDUCED_TYPENAME X::mapped_type> > list;
    322     test::random_values<X> v(1000, generator);
    323     list l;
    324     std::copy(v.begin(), v.end(), std::back_inserter(l));
     321    typedef test::list<std::pair<BOOST_DEDUCED_TYPENAME X::key_type, BOOST_DEDUCED_TYPENAME X::mapped_type> > list;
     322    test::random_values<X> v(1000, generator);
     323    list l(v.begin(), v.end());
    325324
    326325    X x; x.insert(l.begin(), l.end());
Note: See TracChangeset for help on using the changeset viewer.