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