[libcxx] Fix order checking in unordered_multiset tests.

[amakc11]

Summary

Some tests assume that iteration through an unordered multiset elements will return them in the same order as at the container creation. This assumption is not true since the container is unordered, so that no specific order of elements is ever guaranteed for such container. This patch introduces checks verifying that any iteration will return elements exactly from a set of valid values and without repetition, but in no particular order.

[amakc11]

ping

[ldionne]

test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp

67 ↗

(On Diff #180867)

Wouldn't it be enough (and simpler) to do something like this:

std::map<int, int> counts;
for (C::const_iterator i = c.cbegin(), ie = c.cend(); i != ie; ++i) {
  counts[*i]++;
}
assert(counts[1] == 2);
assert(counts[2] == 2);
assert(counts[3] == 1);
assert(counts[4] == 1);
assert(counts.size() == 4);

I find the proposed patch difficult to follow.

[amakc11]

Wouldn't it be enough (and simpler) to do something like this

No, it definitely wouldn't. The proposed simplification throws the baby out with the bathwater and lowers the testing value of the code. Both the original and the patched code effectively test these requirements of the standard. The simplified code lacks the check of the following requirement: "In containers that support equivalent keys, elements with equivalent keys are adjacent to each other in the iteration order of the container".

I find the proposed patch difficult to follow.

It is not the difficulty of the testing code that should matter, but its effectiveness and completeness called "test coverage". Тhe more you sweat in testing the less you bleed in application.

[amakc11]

Is the patch rejected due to being "difficult to follow"?

[amakc11]

ping

[amakc11]

If you have any further questions, please ask. If not, please accept and commit.

[mclow.lists]

test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp

67 ↗

(On Diff #180867)

I too find this patch difficult to follow. I don't really see what building and destroying the set s adds.
However, I agree that louis' suggested change does not test what we want.

Maybe something like this:

C::const_iterator i = c.find(1);
assert(i != c.end());
assert(*i == 1);
++i;
assert(i != c.end());
assert(*i == 1);
++i;
assert(i == c.end() || *i != 1);

and then repeat that code block for the values 2, 3 and 4, checking for the correct number of elements of each value.

You could even pull that checking out into a function like this:

template <typename Iter>
void CheckConsecutiveValues(Iter pos, Iter end, typename Iter::value_type value, size_t count);

and then just have here:

CheckConsecutiveValues(c.find(1), c.end(), 1, 2);
CheckConsecutiveValues(c.find(2), c.end(), 1, 2);
CheckConsecutiveValues(c.find(3), c.end(), 1, 1);
CheckConsecutiveValues(c.find(4), c.end(), 1, 1);

which I think would be very clear.

[mclow.lists]

test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp

67 ↗

(On Diff #180867)

Duh. Those calls would be:

CheckConsecutiveValues(c.find(1), c.end(), 1, 2);
CheckConsecutiveValues(c.find(2), c.end(), 2, 2);
CheckConsecutiveValues(c.find(3), c.end(), 3, 1);
CheckConsecutiveValues(c.find(4), c.end(), 4, 1);

[amakc11]

Suggested simplification implemented. It also implemented for the associated patch D56498.

[amakc11]

More simplifications accepted and committed in D56498 are implemented here: common function moved to a separate header file. Now this patch can also be accepted and committed.

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_copy.pass.cpp

 #include <unordered_set>
 #include <algorithm>
 #include <cassert>
 #include <cfloat>
 #include <cmath>
 #include <cstddef>
 
 #include "test_macros.h"
+#include "../../../check_consecutive.h"
 #include "../../../test_compare.h"
 #include "../../../test_hash.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 
 int main(int, char**)
 {
     {
int main(int, char**)
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
         c = c0;
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(4));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
int main(int, char**)
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
         c = c0;
         assert(c.bucket_count() >= 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
#if TEST_STD_VER >= 11
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A()
            );
         c = c0;
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
     }
 #endif
 
   return 0;
 }

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/assign_move.pass.cpp

 
 #include <unordered_set>
 #include <cassert>
 #include <cfloat>
 #include <cmath>
 #include <cstddef>
 
 #include "test_macros.h"
+#include "../../../check_consecutive.h"
 #include "../../../test_compare.h"
 #include "../../../test_hash.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 
 int main(int, char**)
 {
     {
int main(int, char**)
             7,
             test_hash<std::hash<int> >(2),
             test_compare<std::equal_to<int> >(3),
             A(4)
            );
         c = std::move(c0);
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(4));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/copy.pass.cpp

 
 #include <unordered_set>
 #include <cassert>
 #include <cfloat>
 #include <cmath>
 #include <cstddef>
 
 #include "test_macros.h"
+#include "../../../check_consecutive.h"
 #include "../../../test_compare.h"
 #include "../../../test_hash.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 
 int main(int, char**)
 {
     {
int main(int, char**)
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<int>(10)
            );
         C c = c0;
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == test_allocator<int>(10));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
#if TEST_STD_VER >= 11
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             other_allocator<int>(10)
            );
         C c = c0;
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == other_allocator<int>(-2));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
#if TEST_STD_VER >= 11
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<int>()
            );
         C c = c0;
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == min_allocator<int>());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
     }
 #endif
 
   return 0;
 }

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/copy_alloc.pass.cpp

 
 #include <unordered_set>
 #include <cassert>
 #include <cfloat>
 #include <cmath>
 #include <cstddef>
 
 #include "test_macros.h"
+#include "../../../check_consecutive.h"
 #include "../../../test_compare.h"
 #include "../../../test_hash.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 
 int main(int, char**)
 {
     {
int main(int, char**)
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             test_allocator<int>(10)
            );
         C c(c0, test_allocator<int>(5));
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == test_allocator<int>(5));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
#if TEST_STD_VER >= 11
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             min_allocator<int>()
            );
         C c(c0, min_allocator<int>());
         LIBCPP_ASSERT(c.bucket_count() == 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == min_allocator<int>());
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);
     }
 #endif
 
   return 0;
 }

libcxx/trunk/test/std/containers/unord/unord.multiset/unord.multiset.cnstr/move_alloc.pass.cpp

 
 #include <unordered_set>
 #include <cassert>
 #include <cfloat>
 #include <cmath>
 #include <cstddef>
 
 #include "test_macros.h"
+#include "../../../check_consecutive.h"
 #include "../../../test_compare.h"
 #include "../../../test_hash.h"
 #include "test_allocator.h"
 #include "min_allocator.h"
 
 int main(int, char**)
 {
     {
int main(int, char**)
             7,
             test_hash<std::hash<int> >(8),
             test_compare<std::equal_to<int> >(9),
             A(10)
            );
         C c(std::move(c0), A(12));
         assert(c.bucket_count() >= 7);
         assert(c.size() == 6);
-        C::const_iterator i = c.cbegin();
-        assert(*i == 1);
-        ++i;
-        assert(*i == 1);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 2);
-        ++i;
-        assert(*i == 3);
-        ++i;
-        assert(*i == 4);
+        CheckConsecutiveValues<C::const_iterator>(c.find(1), c.end(), 1, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(2), c.end(), 2, 2);
+        CheckConsecutiveValues<C::const_iterator>(c.find(3), c.end(), 3, 1);
+        CheckConsecutiveValues<C::const_iterator>(c.find(4), c.end(), 4, 1);
         assert(c.hash_function() == test_hash<std::hash<int> >(8));
         assert(c.key_eq() == test_compare<std::equal_to<int> >(9));
         assert(c.get_allocator() == A(12));
         assert(!c.empty());
         assert(static_cast<std::size_t>(std::distance(c.begin(), c.end())) == c.size());
         assert(static_cast<std::size_t>(std::distance(c.cbegin(), c.cend())) == c.size());
         assert(std::fabs(c.load_factor() - (float)c.size()/c.bucket_count()) < FLT_EPSILON);
         assert(c.max_load_factor() == 1);