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

source code of boost/libs/unordered/test/unordered/erase_tests.cpp