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