2 // Copyright 2006-2009 Daniel James.
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 // This header contains metafunctions/functions to get the equivalent
7 // associative container for an unordered container, and compare the contents.
9 #if !defined(BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER)
10 #define BOOST_UNORDERED_TEST_HELPERS_INVARIANT_HEADER
12 #include "./helpers.hpp"
13 #include "./metafunctions.hpp"
17 #if defined(BOOST_MSVC)
19 #pragma warning(disable : 4127) // conditional expression is constant
20 #pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int',
21 // possible loss of data
25 template <class X> void check_equivalent_keys(X const& x1)
27 BOOST_DEDUCED_TYPENAME X::key_equal eq = x1.key_eq();
28 typedef BOOST_DEDUCED_TYPENAME X::key_type key_type;
29 std::set<key_type, std::less<key_type> > found_;
31 BOOST_DEDUCED_TYPENAME X::const_iterator it = x1.begin(), end = x1.end();
32 BOOST_DEDUCED_TYPENAME X::size_type size = 0;
34 // First test that the current key has not occurred before, required
35 // to test either that keys are unique or that equivalent keys are
36 // adjacent. (6.3.1/6)
37 key_type key = get_key<X>(*it);
38 if (!found_.insert(key).second)
39 BOOST_ERROR("Elements with equivalent keys aren't adjacent.");
41 // Iterate over equivalent keys, counting them.
42 unsigned int count = 0;
47 } while (it != end && eq(get_key<X>(*it), key));
49 // If the container has unique keys, test that there's only one.
50 // Since the previous test makes sure that all equivalent keys are
51 // adjacent, this is all the equivalent keys - so the test is
52 // sufficient. (6.3.1/6 again).
53 if (test::has_unique_keys<X>::value && count != 1)
54 BOOST_ERROR("Non-unique key.");
56 if (x1.count(key) != count) {
57 BOOST_ERROR("Incorrect output of count.");
58 std::cerr << x1.count(key) << "," << count << "\n";
61 // Check that the keys are in the correct bucket and are
62 // adjacent in the bucket.
63 BOOST_DEDUCED_TYPENAME X::size_type bucket = x1.bucket(key);
64 BOOST_DEDUCED_TYPENAME X::const_local_iterator lit = x1.begin(bucket),
65 lend = x1.end(bucket);
67 unsigned int count_checked = 0;
68 for (; lit != lend && !eq(get_key<X>(*lit), key); ++lit) {
73 BOOST_ERROR("Unable to find element with a local_iterator");
74 std::cerr << "Checked: " << count_checked << " elements" << std::endl;
76 unsigned int count2 = 0;
77 for (; lit != lend && eq(get_key<X>(*lit), key); ++lit)
80 BOOST_ERROR("Element count doesn't match local_iterator.");
81 for (; lit != lend; ++lit) {
82 if (eq(get_key<X>(*lit), key)) {
83 BOOST_ERROR("Non-adjacent element with equivalent key "
91 // Check that size matches up.
93 if (x1.size() != size) {
94 BOOST_ERROR("x1.size() doesn't match actual size.");
95 std::cout << x1.size() << "/" << size << std::endl;
98 // Check the load factor.
100 float load_factor = size == 0 ? 0
101 : static_cast<float>(size) /
102 static_cast<float>(x1.bucket_count());
104 if (fabs(x1.load_factor() - load_factor) > x1.load_factor() / 64)
105 BOOST_ERROR("x1.load_factor() doesn't match actual load_factor.");
107 // Check that size in the buckets matches up.
109 BOOST_DEDUCED_TYPENAME X::size_type bucket_size = 0;
111 for (BOOST_DEDUCED_TYPENAME X::size_type i = 0; i < x1.bucket_count();
113 for (BOOST_DEDUCED_TYPENAME X::const_local_iterator begin2 = x1.begin(i),
115 begin2 != end2; ++begin2) {
120 if (x1.size() != bucket_size) {
121 BOOST_ERROR("x1.size() doesn't match bucket size.");
122 std::cout << x1.size() << "/" << bucket_size << std::endl;
127 #if defined(BOOST_MSVC)