libs/unordered/test/unordered/erase_tests.cpp

   1
   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)
   5
   6 // clang-format off
   7 #include "../helpers/prefix.hpp"
   8 #include <boost/unordered_set.hpp>
   9 #include <boost/unordered_map.hpp>
  10 #include "../helpers/postfix.hpp"
  11 // clang-format on
  12
  13 #include "../helpers/test.hpp"
  14 #include "../objects/test.hpp"
  15 #include "../helpers/random_values.hpp"
  16 #include "../helpers/tracker.hpp"
  17 #include "../helpers/equivalent.hpp"
  18 #include "../helpers/helpers.hpp"
  19 #include "../helpers/invariants.hpp"
  20 #include <vector>
  21 #include <iostream>
  22 #include <cstdlib>
  23
  24 namespace erase_tests {
  25
  26 test::seed_t initialize_seed(85638);
  27
  28 template <class Container>
  29 void erase_tests1(Container*, test::random_generator generator)
  30 {
  31     typedef BOOST_DEDUCED_TYPENAME Container::iterator iterator;
  32     typedef BOOST_DEDUCED_TYPENAME Container::const_iterator c_iterator;
  33
  34     std::cerr << "Erase by key.\n";
  35     {
  36         test::check_instances check_;
  37
  38         test::random_values<Container> v(1000, generator);
  39         Container x(v.begin(), v.end());
  40         int iterations = 0;
  41         for (BOOST_DEDUCED_TYPENAME test::random_values<Container>::iterator
  42                  it = v.begin();
  43              it != v.end(); ++it) {
  44             std::size_t count = x.count(test::get_key<Container>(*it));
  45             std::size_t old_size = x.size();
  46             BOOST_TEST(count == x.erase(test::get_key<Container>(*it)));
  47             BOOST_TEST(x.size() == old_size - count);
  48             BOOST_TEST(x.count(test::get_key<Container>(*it)) == 0);
  49             BOOST_TEST(x.find(test::get_key<Container>(*it)) == x.end());
  50             if (++iterations % 20 == 0)
  51                 test::check_equivalent_keys(x);
  52         }
  53     }
  54
  55     std::cerr << "erase(begin()).\n";
  56     {
  57         test::check_instances check_;
  58
  59         test::random_values<Container> v(1000, generator);
  60         Container x(v.begin(), v.end());
  61         std::size_t size = x.size();
  62         int iterations = 0;
  63         while (size > 0 && !x.empty()) {
  64             BOOST_DEDUCED_TYPENAME Container::key_type key =
  65                 test::get_key<Container>(*x.begin());
  66             std::size_t count = x.count(key);
  67             iterator pos = x.erase(x.begin());
  68             --size;
  69             BOOST_TEST(pos == x.begin());
  70             BOOST_TEST(x.count(key) == count - 1);
  71             BOOST_TEST(x.size() == size);
  72             if (++iterations % 20 == 0)
  73                 test::check_equivalent_keys(x);
  74         }
  75         BOOST_TEST(x.empty());
  76     }
  77
  78     std::cerr << "erase(random position).\n";
  79     {
  80         test::check_instances check_;
  81
  82         test::random_values<Container> v(1000, generator);
  83         Container x(v.begin(), v.end());
  84         std::size_t size = x.size();
  85         int iterations = 0;
  86         while (size > 0 && !x.empty()) {
  87             std::size_t index = test::random_value(x.size());
  88             c_iterator prev, pos, next;
  89             if (index == 0) {
  90                 prev = pos = x.begin();
  91             } else {
  92                 prev = test::next(x.begin(), index - 1);
  93                 pos = test::next(prev);
  94             }
  95             next = test::next(pos);
  96             BOOST_DEDUCED_TYPENAME Container::key_type key =
  97                 test::get_key<Container>(*pos);
  98             std::size_t count = x.count(key);
  99             BOOST_TEST(count > 0);
 100             BOOST_TEST(next == x.erase(pos));
 101             --size;
 102             if (size > 0)
 103                 BOOST_TEST(
 104                     index == 0 ? next == x.begin() : next == test::next(prev));
 105             BOOST_TEST(x.count(key) == count - 1);
 106             if (x.count(key) != count - 1) {
 107                 std::cerr << count << " => " << x.count(key) << std::endl;
 108             }
 109             BOOST_TEST(x.size() == size);
 110             if (++iterations % 20 == 0)
 111                 test::check_equivalent_keys(x);
 112         }
 113         BOOST_TEST(x.empty());
 114     }
 115
 116     std::cerr << "erase(ranges).\n";
 117     {
 118         test::check_instances check_;
 119
 120         test::random_values<Container> v(500, generator);
 121         Container x(v.begin(), v.end());
 122
 123         std::size_t size = x.size();
 124
 125         // I'm actually stretching it a little here, as the standard says it
 126         // returns 'the iterator immediately following the erase elements'
 127         // and if nothing is erased, then there's nothing to follow. But I
 128         // think this is the only sensible option...
 129         BOOST_TEST(x.erase(x.end(), x.end()) == x.end());
 130         BOOST_TEST(x.erase(x.begin(), x.begin()) == x.begin());
 131         BOOST_TEST(x.size() == size);
 132         test::check_equivalent_keys(x);
 133
 134         BOOST_TEST(x.erase(x.begin(), x.end()) == x.end());
 135         BOOST_TEST(x.empty());
 136         BOOST_TEST(x.begin() == x.end());
 137         test::check_equivalent_keys(x);
 138
 139         BOOST_TEST(x.erase(x.begin(), x.end()) == x.begin());
 140         test::check_equivalent_keys(x);
 141     }
 142
 143     std::cerr << "erase(random ranges).\n";
 144     {
 145         test::check_instances check_;
 146         Container x;
 147
 148         for (int i = 0; i < 100; ++i) {
 149             test::random_values<Container> v(1000, generator);
 150             x.insert(v.begin(), v.end());
 151
 152             // Note that erase only invalidates the erased iterators.
 153             std::vector<c_iterator> iterators;
 154             for (c_iterator it = x.cbegin(); it != x.cend(); ++it) {
 155                 iterators.push_back(it);
 156             }
 157             iterators.push_back(x.cend());
 158
 159             while (iterators.size() > 1) {
 160                 std::size_t start = test::random_value(iterators.size());
 161                 std::size_t length =
 162                     test::random_value(iterators.size() - start);
 163                 x.erase(iterators[start], iterators[start + length]);
 164                 iterators.erase(test::next(iterators.begin(), start),
 165                     test::next(iterators.begin(), start + length));
 166
 167                 BOOST_TEST(x.size() == iterators.size() - 1);
 168                 BOOST_DEDUCED_TYPENAME std::vector<c_iterator>::const_iterator
 169                     i2 = iterators.begin();
 170                 for (c_iterator i1 = x.cbegin(); i1 != x.cend(); ++i1) {
 171                     BOOST_TEST(i1 == *i2);
 172                     ++i2;
 173                 }
 174                 BOOST_TEST(x.cend() == *i2);
 175
 176                 test::check_equivalent_keys(x);
 177             }
 178             BOOST_TEST(x.empty());
 179         }
 180     }
 181
 182     std::cerr << "quick_erase(begin()).\n";
 183     {
 184         test::check_instances check_;
 185
 186         test::random_values<Container> v(1000, generator);
 187         Container x(v.begin(), v.end());
 188         std::size_t size = x.size();
 189         int iterations = 0;
 190         while (size > 0 && !x.empty()) {
 191             BOOST_DEDUCED_TYPENAME Container::key_type key =
 192                 test::get_key<Container>(*x.begin());
 193             std::size_t count = x.count(key);
 194             x.quick_erase(x.begin());
 195             --size;
 196             BOOST_TEST(x.count(key) == count - 1);
 197             BOOST_TEST(x.size() == size);
 198             if (++iterations % 20 == 0)
 199                 test::check_equivalent_keys(x);
 200         }
 201         BOOST_TEST(x.empty());
 202     }
 203
 204     std::cerr << "quick_erase(random position).\n";
 205     {
 206         test::check_instances check_;
 207
 208         test::random_values<Container> v(1000, generator);
 209         Container x(v.begin(), v.end());
 210         std::size_t size = x.size();
 211         int iterations = 0;
 212         while (size > 0 && !x.empty()) {
 213             std::size_t index = test::random_value(x.size());
 214             BOOST_DEDUCED_TYPENAME Container::const_iterator prev, pos, next;
 215             if (index == 0) {
 216                 prev = pos = x.begin();
 217             } else {
 218                 prev = test::next(x.begin(), index - 1);
 219                 pos = test::next(prev);
 220             }
 221             next = test::next(pos);
 222             BOOST_DEDUCED_TYPENAME Container::key_type key =
 223                 test::get_key<Container>(*pos);
 224             std::size_t count = x.count(key);
 225             BOOST_TEST(count > 0);
 226             x.quick_erase(pos);
 227             --size;
 228             if (size > 0)
 229                 BOOST_TEST(
 230                     index == 0 ? next == x.begin() : next == test::next(prev));
 231             BOOST_TEST(x.count(key) == count - 1);
 232             if (x.count(key) != count - 1) {
 233                 std::cerr << count << " => " << x.count(key) << std::endl;
 234             }
 235             BOOST_TEST(x.size() == size);
 236             if (++iterations % 20 == 0)
 237                 test::check_equivalent_keys(x);
 238         }
 239         BOOST_TEST(x.empty());
 240     }
 241
 242     std::cerr << "clear().\n";
 243     {
 244         test::check_instances check_;
 245
 246         test::random_values<Container> v(500, generator);
 247         Container x(v.begin(), v.end());
 248         x.clear();
 249         BOOST_TEST(x.empty());
 250         BOOST_TEST(x.begin() == x.end());
 251     }
 252
 253     std::cerr << "\n";
 254 }
 255
 256 boost::unordered_set<test::object, test::hash, test::equal_to,
 257     test::allocator1<test::object> >* test_set;
 258 boost::unordered_multiset<test::object, test::hash, test::equal_to,
 259     test::allocator2<test::object> >* test_multiset;
 260 boost::unordered_map<test::object, test::object, test::hash, test::equal_to,
 261     test::allocator1<test::object> >* test_map;
 262 boost::unordered_multimap<test::object, test::object, test::hash,
 263     test::equal_to, test::allocator2<test::object> >* test_multimap;
 264
 265 using test::default_generator;
 266 using test::generate_collisions;
 267 using test::limited_range;
 268
 269 UNORDERED_TEST(
 270     erase_tests1, ((test_set)(test_multiset)(test_map)(test_multimap))(
 271                       (default_generator)(generate_collisions)(limited_range)))
 272 }
 273
 274 RUN_TESTS()