[libcxx][test][NFC] Add tests for backward iteration over associative containers

[kboyarinov]

Summary

Add test cases for iteration over the ordered associative container from end to begin using operator--

[kboyarinov]

libcxx/test/std/containers/associative/map/map.ops/count.pass.cpp

110–145 ↗

(On Diff #402800)

This test case is intended to improve code coverage of the libc++ implementation of map. The implementation uses helper class __map_value_compare for EBO:

template <class _Key, class _CP, class _Compare,
                  bool = is_empty_v<_Compare> && !is_final_v<_Compare>>
class __map_value_compare : private _Compare { /*...*/};

template <class _Key, class _CP, class _Compare>
class __map_value_compare<_Key, _CP, _Compare, false>
{
  _Compare comp;
  /*...*/
};

To test both generic template and the specialization, we need additional test-case for final comparator.
Do you think such testing should be organized in this manner or something should be added or changed?

[• Quuxplusone]

libcxx/test/std/containers/associative/map/map.ops/count.pass.cpp

110–145 ↗

(On Diff #402800)

Having not looked closely at all, I suggest we pull the whole body of main out into void test() { ~~~ } so that main becomes a two-liner; and then we make test into a template.

template<class Compare>
void test() {
    ~~~
}

int main(int, char**)
{
    test<std::less<int>>();
#if TEST_STD_VER >= 11
    test<FinalCompare<int>>();
#endif
#if TEST_STD_VER > 11
    test<std::less<>>();
#endif
}

Or do all the different tests here use different key types so this idea would end up being complicated?

Might also make sense to move this discussion/diff into its own separate PR, on the assumption that every other diff here is uncontroversial. (Every other diff is just testing backward iteration, right?)

[kboyarinov]

Remove test-case for the comparator marked final (moved to D118232)

[• Quuxplusone]

LGTM if CI is green. Some nitpicks.

libcxx/test/std/containers/associative/map/map.access/iterator.pass.cpp

88

Perhaps, after line 88, assert(i == m.begin()); . Ditto throughout.

libcxx/test/std/containers/associative/multiset/iterator.pass.cpp

125

220

For consistency with line 213.

[kboyarinov]

Add assert(i == end()) and rename variables for consistency

libcxx/test/std/containers/associative/map/map.access/iterator.pass.cpp

int main(int, char**)
         assert(i == k);
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
         {
             assert(i->first == j);
             assert(i->second == 1);
             i->second = 2.5;
             assert(i->second == 2.5);
         }
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j)
+        {
+            --i;
+            assert(i->first == j);
+            assert(i->second == 2.5);
+            i->second = 1;
+            assert(i->second == 1);
+        }
+        assert(i == m.begin());
     }
     {
         typedef std::pair<const int, double> V;
         V ar[] =
         {
             V(1, 1),
             V(1, 1.5),
             V(1, 2),
int main(int, char**)
         assert(static_cast<std::size_t>(std::distance(m.crbegin(), m.crend())) == m.size());
         std::map<int, double>::const_iterator i;
         i = m.begin();
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
         {
             assert(i->first == j);
             assert(i->second == 1);
         }
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j)
+        {
+            --i;
+            assert(i->first == j);
+            assert(i->second == 1);
+        }
+        assert(i == m.begin());
     }
 #if TEST_STD_VER >= 11
     {
         typedef std::pair<const int, double> V;
         V ar[] =
         {
             V(1, 1),
             V(1, 1.5),
#if TEST_STD_VER >= 11
         assert(i == k);
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
         {
             assert(i->first == j);
             assert(i->second == 1);
             i->second = 2.5;
             assert(i->second == 2.5);
         }
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j)
+        {
+            --i;
+            assert(i->first == j);
+            assert(i->second == 2.5);
+            i->second = 1;
+            assert(i->second == 1);
+        }
+        assert(i == m.begin());
     }
     {
         typedef std::pair<const int, double> V;
         V ar[] =
         {
             V(1, 1),
             V(1, 1.5),
             V(1, 2),
#if TEST_STD_VER >= 11
         assert(static_cast<std::size_t>(std::distance(m.crbegin(), m.crend())) == m.size());
         std::map<int, double, std::less<int>, min_allocator<V>>::const_iterator i;
         i = m.begin();
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
         {
             assert(i->first == j);
             assert(i->second == 1);
         }
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j)
+        {
+            --i;
+            assert(i->first == j);
+            assert(i->second == 1);
+        }
+        assert(i == m.begin());
     }
 #endif
 #if TEST_STD_VER > 11
     { // N3644 testing
         typedef std::map<int, double> C;
         C::iterator ii1{}, ii2{};
         C::iterator ii4 = ii1;
         C::const_iterator cii{};

libcxx/test/std/containers/associative/multimap/iterator.pass.cpp

int main(int, char**)
         for (int j = 1; j <= 8; ++j)
             for (double d = 1; d <= 2; d += .5, ++i)
             {
                 assert(i->first == j);
                 assert(i->second == d);
                 i->second = 2.5;
                 assert(i->second == 2.5);
             }
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (double d = 1; d <= 2; d += .5)
+            {
+                --i;
+                assert(i->first == j);
+                assert(i->second == 2.5);
+                i->second = d;
+                assert(i->second == d);
+            }
+        assert(i == m.begin());
     }
     {
         typedef std::pair<const int, double> V;
         V ar[] =
         {
             V(1, 1),
             V(1, 1.5),
             V(1, 2),
int main(int, char**)
         std::multimap<int, double>::const_iterator i;
         i = m.begin();
         for (int j = 1; j <= 8; ++j)
             for (double d = 1; d <= 2; d += .5, ++i)
             {
                 assert(i->first == j);
                 assert(i->second == d);
             }
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (double d = 2; d >= 1; d -= .5)
+            {
+                --i;
+                assert(i->first == j);
+                assert(i->second == d);
+            }
+        assert(i == m.begin());
     }
 #if TEST_STD_VER >= 11
     {
         typedef std::pair<const int, double> V;
         V ar[] =
         {
             V(1, 1),
             V(1, 1.5),
#if TEST_STD_VER >= 11
         for (int j = 1; j <= 8; ++j)
             for (double d = 1; d <= 2; d += .5, ++i)
             {
                 assert(i->first == j);
                 assert(i->second == d);
                 i->second = 2.5;
                 assert(i->second == 2.5);
             }
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (double d = 1; d <= 2; d += .5)
+            {
+                --i;
+                assert(i->first == j);
+                assert(i->second == 2.5);
+                i->second = d;
+                assert(i->second == d);
+            }
+        assert(i == m.begin());
     }
     {
         typedef std::pair<const int, double> V;
         V ar[] =
         {
             V(1, 1),
             V(1, 1.5),
             V(1, 2),
#if TEST_STD_VER >= 11
         std::multimap<int, double, std::less<int>, min_allocator<V>>::const_iterator i;
         i = m.begin();
         for (int j = 1; j <= 8; ++j)
             for (double d = 1; d <= 2; d += .5, ++i)
             {
                 assert(i->first == j);
                 assert(i->second == d);
             }
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (double d = 2; d >= 1; d -= .5)
+            {
+                --i;
+                assert(i->first == j);
+                assert(i->second == d);
+            }
+        assert(i == m.begin());
     }
 #endif
 #if TEST_STD_VER > 11
     { // N3644 testing
         typedef std::multimap<int, double> C;
         C::iterator ii1{}, ii2{};
         C::iterator ii4 = ii1;
         C::const_iterator cii{};

libcxx/test/std/containers/associative/multiset/iterator.pass.cpp

int main(int, char**)
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         std::multiset<int>::iterator i;
         i = m.begin();
         std::multiset<int>::const_iterator k = i;
         assert(i == k);
         for (int j = 1; j <= 8; ++j)
             for (int n = 0; n < 3; ++n, ++i)
                 assert(*i == j);
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (int n = 0; n < 3; ++n) {
+                --i;
+                assert(*i == j);
+            }
+        assert(i == m.begin());
     }
     {
         typedef int V;
         V ar[] =
         {
             1,
             1,
             1,
int main(int, char**)
         assert(static_cast<std::size_t>(std::distance(m.cbegin(), m.cend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.crbegin(), m.crend())) == m.size());
         std::multiset<int>::const_iterator i;
         i = m.begin();
         for (int j = 1; j <= 8; ++j)
             for (int k = 0; k < 3; ++k, ++i)
                 assert(*i == j);
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (int k = 0; k < 3; ++k) {
+                --i;
+                assert(*i == j);
+            }
+        assert(i == m.begin());
     }
 #if TEST_STD_VER >= 11
     {
         typedef int V;
         V ar[] =
         {
             1,
             1,
#if TEST_STD_VER >= 11
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         std::multiset<int, std::less<int>, min_allocator<int>>::iterator i;
         i = m.begin();
         std::multiset<int, std::less<int>, min_allocator<int>>::const_iterator k = i;
         assert(i == k);
         for (int j = 1; j <= 8; ++j)
             for (int n = 0; n < 3; ++n, ++i)
                 assert(*i == j);
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (int n = 0; n < 3; ++n) {
+                --i;
+                assert(*i == j);
+            }
+        assert(i == m.begin());
     }
     {
         typedef int V;
         V ar[] =
         {
             1,
             1,
             1,
#if TEST_STD_VER >= 11
         assert(static_cast<std::size_t>(std::distance(m.cbegin(), m.cend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.crbegin(), m.crend())) == m.size());
         std::multiset<int, std::less<int>, min_allocator<int>>::const_iterator i;
         i = m.begin();
         for (int j = 1; j <= 8; ++j)
             for (int k = 0; k < 3; ++k, ++i)
                 assert(*i == j);
+        assert(i == m.end());
+        for (int j = 8; j >= 1; --j)
+            for (int k = 0; k < 3; ++k) {
+                --i;
+                assert(*i == j);
+            }
+        assert(i == m.begin());
     }
 #endif
 #if TEST_STD_VER > 11
     { // N3644 testing
         typedef std::multiset<int> C;
         C::iterator ii1{}, ii2{};
         C::iterator ii4 = ii1;
         C::const_iterator cii{};

libcxx/test/std/containers/associative/set/iterator.pass.cpp

int main(int, char**)
         assert(static_cast<std::size_t>(std::distance(m.begin(), m.end())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         std::set<int>::iterator i;
         i = m.begin();
         std::set<int>::const_iterator k = i;
         assert(i == k);
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
             assert(*i == j);
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j) {
+            --i;
+            assert(*i == j);
+        }
+        assert(i == m.begin());
     }
     {
         typedef int V;
         V ar[] =
         {
             1,
             1,
             1,
int main(int, char**)
         assert(static_cast<std::size_t>(std::distance(m.begin(), m.end())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.cbegin(), m.cend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.crbegin(), m.crend())) == m.size());
         std::set<int>::const_iterator i;
         i = m.begin();
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
             assert(*i == j);
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j) {
+            --i;
+            assert(*i == j);
+        }
+        assert(i == m.begin());
     }
 #if TEST_STD_VER >= 11
     {
         typedef int V;
         V ar[] =
         {
             1,
             1,
#if TEST_STD_VER >= 11
         assert(static_cast<std::size_t>(std::distance(m.begin(), m.end())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         std::set<int, std::less<int>, min_allocator<int>>::iterator i;
         i = m.begin();
         std::set<int, std::less<int>, min_allocator<int>>::const_iterator k = i;
         assert(i == k);
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
             assert(*i == j);
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j) {
+            --i;
+            assert(*i == j);
+        }
+        assert(i == m.begin());
     }
     {
         typedef int V;
         V ar[] =
         {
             1,
             1,
             1,
#if TEST_STD_VER >= 11
         assert(static_cast<std::size_t>(std::distance(m.begin(), m.end())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.cbegin(), m.cend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.rbegin(), m.rend())) == m.size());
         assert(static_cast<std::size_t>(std::distance(m.crbegin(), m.crend())) == m.size());
         std::set<int, std::less<int>, min_allocator<int>>::const_iterator i;
         i = m.begin();
         for (int j = 1; static_cast<std::size_t>(j) <= m.size(); ++j, ++i)
             assert(*i == j);
+        assert(i == m.end());
+        for (int j = m.size(); j >= 1; --j) {
+            --i;
+            assert(*i == j);
+        }
+        assert(i == m.begin());
     }
 #endif
 #if TEST_STD_VER > 11
     { // N3644 testing
         typedef std::set<int> C;
         C::iterator ii1{}, ii2{};
         C::iterator ii4 = ii1;
         C::const_iterator cii{};