1 
2 // Copyright 2005-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 #if defined(BOOST_MSVC)
7 #pragma warning(push)
8 #pragma warning(disable : 4100) // unreferenced formal parameter
9 #pragma warning(disable : 4610) // class can never be instantiated
10 #pragma warning(disable : 4510) // default constructor could not be generated
11 #endif
12 
13 #include <boost/concept_check.hpp>
14 
15 #if defined(BOOST_MSVC)
16 #pragma warning(pop)
17 #endif
18 
19 #include "../helpers/check_return_type.hpp"
20 #include <boost/core/pointer_traits.hpp>
21 #include <boost/limits.hpp>
22 #include <boost/predef.h>
23 #include <boost/static_assert.hpp>
24 #include <boost/type_traits/cv_traits.hpp>
25 #include <boost/type_traits/is_const.hpp>
26 #include <boost/type_traits/is_convertible.hpp>
27 #include <boost/type_traits/is_same.hpp>
28 #include <boost/utility/swap.hpp>
29 
30 typedef long double comparison_type;
31 
sink(T const &)32 template <class T> void sink(T const&) {}
rvalue(T const & v)33 template <class T> T rvalue(T const& v) { return v; }
rvalue_default()34 template <class T> T rvalue_default() { return T(); }
35 
36 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
implicit_construct()37 template <class T> T implicit_construct() { return {}; }
38 #else
implicit_construct()39 template <class T> int implicit_construct()
40 {
41   T x;
42   sink(x);
43   return 0;
44 }
45 #endif
46 
47 #if !defined(BOOST_NO_CXX11_NOEXCEPT)
48 #define TEST_NOEXCEPT_EXPR(x) BOOST_STATIC_ASSERT((BOOST_NOEXCEPT_EXPR(x)));
49 #else
50 #define TEST_NOEXCEPT_EXPR(x)
51 #endif
52 
container_test(X & r,T const &)53 template <class X, class T> void container_test(X& r, T const&)
54 {
55   typedef typename X::iterator iterator;
56   typedef typename X::const_iterator const_iterator;
57   typedef typename X::difference_type difference_type;
58   typedef typename X::size_type size_type;
59 
60   typedef
61     typename std::iterator_traits<iterator>::value_type iterator_value_type;
62   typedef typename std::iterator_traits<const_iterator>::value_type
63     const_iterator_value_type;
64   typedef typename std::iterator_traits<iterator>::difference_type
65     iterator_difference_type;
66   typedef typename std::iterator_traits<const_iterator>::difference_type
67     const_iterator_difference_type;
68 
69   typedef typename X::value_type value_type;
70   typedef typename X::reference reference;
71   typedef typename X::const_reference const_reference;
72 
73   typedef typename X::node_type node_type;
74 
75   typedef typename X::allocator_type allocator_type;
76 
77   // value_type
78 
79   BOOST_STATIC_ASSERT((boost::is_same<T, value_type>::value));
80   boost::function_requires<boost::CopyConstructibleConcept<X> >();
81 
82   // reference_type / const_reference_type
83 
84   BOOST_STATIC_ASSERT((boost::is_same<T&, reference>::value));
85   BOOST_STATIC_ASSERT((boost::is_same<T const&, const_reference>::value));
86 
87   // iterator
88 
89   boost::function_requires<boost::InputIteratorConcept<iterator> >();
90   BOOST_STATIC_ASSERT((boost::is_same<T, iterator_value_type>::value));
91   BOOST_STATIC_ASSERT((boost::is_convertible<iterator, const_iterator>::value));
92 
93   // const_iterator
94 
95   boost::function_requires<boost::InputIteratorConcept<const_iterator> >();
96   BOOST_STATIC_ASSERT((boost::is_same<T, const_iterator_value_type>::value));
97 
98   // node_type
99 
100   BOOST_STATIC_ASSERT((
101     boost::is_same<allocator_type, typename node_type::allocator_type>::value));
102 
103   // difference_type
104 
105   BOOST_STATIC_ASSERT(std::numeric_limits<difference_type>::is_signed);
106   BOOST_STATIC_ASSERT(std::numeric_limits<difference_type>::is_integer);
107   BOOST_STATIC_ASSERT(
108     (boost::is_same<difference_type, iterator_difference_type>::value));
109   BOOST_STATIC_ASSERT(
110     (boost::is_same<difference_type, const_iterator_difference_type>::value));
111 
112   // size_type
113 
114   BOOST_STATIC_ASSERT(!std::numeric_limits<size_type>::is_signed);
115   BOOST_STATIC_ASSERT(std::numeric_limits<size_type>::is_integer);
116 
117   // size_type can represent any non-negative value type of difference_type
118   // I'm not sure about either of these tests...
119   size_type max_diff =
120     static_cast<size_type>((std::numeric_limits<difference_type>::max)());
121   difference_type converted_diff(static_cast<difference_type>(max_diff));
122   BOOST_TEST((std::numeric_limits<difference_type>::max)() == converted_diff);
123 
124   BOOST_TEST(
125     static_cast<comparison_type>((std::numeric_limits<size_type>::max)()) >
126     static_cast<comparison_type>(
127       (std::numeric_limits<difference_type>::max)()));
128 
129 // Constructors
130 
131 // I don't test the runtime post-conditions here.
132 
133 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
134   // It isn't specified in the container requirements that the no argument
135   // constructor is implicit, but it is defined that way in the concrete
136   // container specification.
137   X u_implicit = {};
138   sink(u_implicit);
139 #endif
140 
141   X u;
142   BOOST_TEST(u.size() == 0);
143   BOOST_TEST(X().size() == 0);
144 
145   X a, b;
146   X a_const;
147 
148   sink(X(a));
149   X u2(a);
150   X u3 = a;
151   X u4(rvalue(a_const));
152   X u5 = rvalue(a_const);
153 
154   a.swap(b);
155   boost::swap(a, b);
156   test::check_return_type<X>::equals_ref(r = a);
157 
158   // Allocator
159 
160   test::check_return_type<allocator_type>::equals(a_const.get_allocator());
161 
162   allocator_type m = a.get_allocator();
163   sink(X(m));
164   X c(m);
165   sink(X(a_const, m));
166   X c2(a_const, m);
167   sink(X(rvalue(a_const), m));
168   X c3(rvalue(a_const), m);
169 
170   // node_type
171 
172   implicit_construct<node_type const>();
173 #if !BOOST_COMP_GNUC || BOOST_COMP_GNUC >= BOOST_VERSION_NUMBER(4, 8, 0)
174   TEST_NOEXCEPT_EXPR(node_type());
175 #endif
176 
177   node_type n1;
178   node_type n2(rvalue_default<node_type>());
179 #if !BOOST_COMP_GNUC || BOOST_COMP_GNUC >= BOOST_VERSION_NUMBER(4, 8, 0)
180   TEST_NOEXCEPT_EXPR(node_type(boost::move(n1)));
181 #endif
182   node_type n3;
183   n3 = boost::move(n2);
184   n1.swap(n3);
185   swap(n1, n3);
186   // TODO: noexcept for swap?
187   // value, key, mapped tests in map and set specific testing.
188 
189   node_type const n_const;
190   BOOST_TEST(n_const ? 0 : 1);
191   TEST_NOEXCEPT_EXPR(n_const ? 0 : 1);
192   test::check_return_type<bool>::equals(!n_const);
193   test::check_return_type<bool>::equals(n_const.empty());
194   TEST_NOEXCEPT_EXPR(!n_const);
195   TEST_NOEXCEPT_EXPR(n_const.empty());
196 
197   // Avoid unused variable warnings:
198 
199   sink(u);
200   sink(u2);
201   sink(u3);
202   sink(u4);
203   sink(u5);
204   sink(c);
205   sink(c2);
206   sink(c3);
207 }
208 
unordered_destructible_test(X &)209 template <class X> void unordered_destructible_test(X&)
210 {
211   typedef typename X::iterator iterator;
212   typedef typename X::const_iterator const_iterator;
213   typedef typename X::size_type size_type;
214 
215   X x1;
216 
217 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
218   X x2(rvalue_default<X>());
219   X x3 = rvalue_default<X>();
220 // This can only be done if propagate_on_container_move_assignment::value
221 // is true.
222 // x2 = rvalue_default<X>();
223 #endif
224 
225   X* ptr = new X();
226   X& a1 = *ptr;
227   (&a1)->~X();
228   ::operator delete((void*)(&a1));
229 
230   X a, b;
231   X const a_const;
232   test::check_return_type<iterator>::equals(a.begin());
233   test::check_return_type<const_iterator>::equals(a_const.begin());
234   test::check_return_type<const_iterator>::equals(a.cbegin());
235   test::check_return_type<const_iterator>::equals(a_const.cbegin());
236   test::check_return_type<iterator>::equals(a.end());
237   test::check_return_type<const_iterator>::equals(a_const.end());
238   test::check_return_type<const_iterator>::equals(a.cend());
239   test::check_return_type<const_iterator>::equals(a_const.cend());
240 
241   a.swap(b);
242   boost::swap(a, b);
243 
244   test::check_return_type<size_type>::equals(a.size());
245   test::check_return_type<size_type>::equals(a.max_size());
246   test::check_return_type<bool>::convertible(a.empty());
247 
248   // Allocator
249 
250   typedef typename X::allocator_type allocator_type;
251   test::check_return_type<allocator_type>::equals(a_const.get_allocator());
252 }
253 
unordered_set_test(X & r,Key const &)254 template <class X, class Key> void unordered_set_test(X& r, Key const&)
255 {
256   typedef typename X::value_type value_type;
257   typedef typename X::key_type key_type;
258 
259   BOOST_STATIC_ASSERT((boost::is_same<value_type, key_type>::value));
260 
261   // iterator pointer / const_pointer_type
262 
263   typedef typename X::iterator iterator;
264   typedef typename X::const_iterator const_iterator;
265   typedef typename X::local_iterator local_iterator;
266   typedef typename X::const_local_iterator const_local_iterator;
267   typedef typename std::iterator_traits<iterator>::pointer iterator_pointer;
268   typedef typename std::iterator_traits<const_iterator>::pointer
269     const_iterator_pointer;
270   typedef typename std::iterator_traits<local_iterator>::pointer
271     local_iterator_pointer;
272   typedef typename std::iterator_traits<const_local_iterator>::pointer
273     const_local_iterator_pointer;
274 
275   BOOST_STATIC_ASSERT(
276     (boost::is_same<value_type const*, iterator_pointer>::value));
277   BOOST_STATIC_ASSERT(
278     (boost::is_same<value_type const*, const_iterator_pointer>::value));
279   BOOST_STATIC_ASSERT(
280     (boost::is_same<value_type const*, local_iterator_pointer>::value));
281   BOOST_STATIC_ASSERT(
282     (boost::is_same<value_type const*, const_local_iterator_pointer>::value));
283 
284   // pointer_traits<iterator>
285 
286   BOOST_STATIC_ASSERT((boost::is_same<iterator,
287     typename boost::pointer_traits<iterator>::pointer>::value));
288   BOOST_STATIC_ASSERT((boost::is_same<value_type const,
289     typename boost::pointer_traits<iterator>::element_type>::value));
290   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
291     typename boost::pointer_traits<iterator>::difference_type>::value));
292 
293   // pointer_traits<const_iterator>
294 
295   BOOST_STATIC_ASSERT((boost::is_same<const_iterator,
296     typename boost::pointer_traits<const_iterator>::pointer>::value));
297   BOOST_STATIC_ASSERT((boost::is_same<value_type const,
298     typename boost::pointer_traits<const_iterator>::element_type>::value));
299   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
300     typename boost::pointer_traits<const_iterator>::difference_type>::value));
301 
302   // pointer_traits<local_iterator>
303 
304   BOOST_STATIC_ASSERT((boost::is_same<local_iterator,
305     typename boost::pointer_traits<local_iterator>::pointer>::value));
306   BOOST_STATIC_ASSERT((boost::is_same<value_type const,
307     typename boost::pointer_traits<local_iterator>::element_type>::value));
308   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
309     typename boost::pointer_traits<local_iterator>::difference_type>::value));
310 
311   // pointer_traits<const_local_iterator>
312 
313   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator,
314     typename boost::pointer_traits<const_local_iterator>::pointer>::value));
315   BOOST_STATIC_ASSERT((boost::is_same<value_type const,
316     typename boost::pointer_traits<const_local_iterator>::element_type>::
317       value));
318   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
319     typename boost::pointer_traits<const_local_iterator>::difference_type>::
320       value));
321 
322   typedef typename X::node_type node_type;
323   typedef typename node_type::value_type node_value_type;
324   BOOST_STATIC_ASSERT((boost::is_same<value_type, node_value_type>::value));
325 
326   // Call node_type functions.
327 
328   test::minimal::constructor_param v;
329   Key k_lvalue(v);
330   r.emplace(boost::move(k_lvalue));
331   node_type n1 = r.extract(r.begin());
332   test::check_return_type<value_type>::equals_ref(n1.value());
333 }
334 
335 template <class X, class Key, class T>
unordered_map_test(X & r,Key const & k,T const & v)336 void unordered_map_test(X& r, Key const& k, T const& v)
337 {
338   typedef typename X::value_type value_type;
339   typedef typename X::key_type key_type;
340 
341   BOOST_STATIC_ASSERT(
342     (boost::is_same<value_type, std::pair<key_type const, T> >::value));
343 
344   // iterator pointer / const_pointer_type
345 
346   typedef typename X::iterator iterator;
347   typedef typename X::const_iterator const_iterator;
348   typedef typename X::local_iterator local_iterator;
349   typedef typename X::const_local_iterator const_local_iterator;
350   typedef typename std::iterator_traits<iterator>::pointer iterator_pointer;
351   typedef typename std::iterator_traits<const_iterator>::pointer
352     const_iterator_pointer;
353   typedef typename std::iterator_traits<local_iterator>::pointer
354     local_iterator_pointer;
355   typedef typename std::iterator_traits<const_local_iterator>::pointer
356     const_local_iterator_pointer;
357 
358   BOOST_STATIC_ASSERT((boost::is_same<value_type*, iterator_pointer>::value));
359   BOOST_STATIC_ASSERT(
360     (boost::is_same<value_type const*, const_iterator_pointer>::value));
361   BOOST_STATIC_ASSERT(
362     (boost::is_same<value_type*, local_iterator_pointer>::value));
363   BOOST_STATIC_ASSERT(
364     (boost::is_same<value_type const*, const_local_iterator_pointer>::value));
365 
366   // pointer_traits<iterator>
367 
368   BOOST_STATIC_ASSERT((boost::is_same<iterator,
369     typename boost::pointer_traits<iterator>::pointer>::value));
370   BOOST_STATIC_ASSERT((boost::is_same<value_type,
371     typename boost::pointer_traits<iterator>::element_type>::value));
372   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
373     typename boost::pointer_traits<iterator>::difference_type>::value));
374 
375   // pointer_traits<const_iterator>
376 
377   BOOST_STATIC_ASSERT((boost::is_same<const_iterator,
378     typename boost::pointer_traits<const_iterator>::pointer>::value));
379   BOOST_STATIC_ASSERT((boost::is_same<value_type const,
380     typename boost::pointer_traits<const_iterator>::element_type>::value));
381   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
382     typename boost::pointer_traits<const_iterator>::difference_type>::value));
383 
384   // pointer_traits<local_iterator>
385 
386   BOOST_STATIC_ASSERT((boost::is_same<local_iterator,
387     typename boost::pointer_traits<local_iterator>::pointer>::value));
388   BOOST_STATIC_ASSERT((boost::is_same<value_type,
389     typename boost::pointer_traits<local_iterator>::element_type>::value));
390   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
391     typename boost::pointer_traits<local_iterator>::difference_type>::value));
392 
393   // pointer_traits<const_local_iterator>
394 
395   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator,
396     typename boost::pointer_traits<const_local_iterator>::pointer>::value));
397   BOOST_STATIC_ASSERT((boost::is_same<value_type const,
398     typename boost::pointer_traits<const_local_iterator>::element_type>::
399       value));
400   BOOST_STATIC_ASSERT((boost::is_same<std::ptrdiff_t,
401     typename boost::pointer_traits<const_local_iterator>::difference_type>::
402       value));
403 
404   typedef typename X::node_type node_type;
405   typedef typename node_type::key_type node_key_type;
406   typedef typename node_type::mapped_type node_mapped_type;
407 
408   BOOST_STATIC_ASSERT((boost::is_same<Key, node_key_type>::value));
409   BOOST_STATIC_ASSERT((boost::is_same<T, node_mapped_type>::value));
410   // Superfluous,but just to make sure.
411   BOOST_STATIC_ASSERT((!boost::is_const<node_key_type>::value));
412 
413   // Calling functions
414 
415   r.insert(std::pair<Key const, T>(k, v));
416   r.insert(r.begin(), std::pair<Key const, T>(k, v));
417   std::pair<Key const, T> const value(k, v);
418   r.insert(value);
419   r.insert(r.end(), value);
420 
421   Key k_lvalue(k);
422   T v_lvalue(v);
423 
424   // Emplace
425 
426   r.emplace(k, v);
427   r.emplace(k_lvalue, v_lvalue);
428   r.emplace(rvalue(k), rvalue(v));
429 
430   r.emplace(boost::unordered::piecewise_construct, boost::make_tuple(k),
431     boost::make_tuple(v));
432 
433   // Emplace with hint
434 
435   r.emplace_hint(r.begin(), k, v);
436   r.emplace_hint(r.begin(), k_lvalue, v_lvalue);
437   r.emplace_hint(r.begin(), rvalue(k), rvalue(v));
438 
439   r.emplace_hint(r.begin(), boost::unordered::piecewise_construct,
440     boost::make_tuple(k), boost::make_tuple(v));
441 
442   // Extract
443 
444   test::check_return_type<node_type>::equals(r.extract(r.begin()));
445 
446   r.emplace(k, v);
447   test::check_return_type<node_type>::equals(r.extract(k));
448 
449   r.emplace(k, v);
450   node_type n1 = r.extract(r.begin());
451   test::check_return_type<key_type>::equals_ref(n1.key());
452   test::check_return_type<T>::equals_ref(n1.mapped());
453 
454   node_type n2 = boost::move(n1);
455   r.insert(boost::move(n2));
456   r.insert(r.extract(r.begin()));
457   n2 = r.extract(r.begin());
458   r.insert(r.begin(), boost::move(n2));
459   r.insert(r.end(), r.extract(r.begin()));
460 
461   node_type n = r.extract(r.begin());
462   test::check_return_type<node_key_type>::equals_ref(n.key());
463   test::check_return_type<node_mapped_type>::equals_ref(n.mapped());
464 }
465 
equality_test(X & r)466 template <class X> void equality_test(X& r)
467 {
468   X const a = r, b = r;
469 
470   test::check_return_type<bool>::equals(a == b);
471   test::check_return_type<bool>::equals(a != b);
472   test::check_return_type<bool>::equals(boost::operator==(a, b));
473   test::check_return_type<bool>::equals(boost::operator!=(a, b));
474 }
475 
unordered_unique_test(X & r,T const & t)476 template <class X, class T> void unordered_unique_test(X& r, T const& t)
477 {
478   typedef typename X::iterator iterator;
479   test::check_return_type<std::pair<iterator, bool> >::equals(r.insert(t));
480   test::check_return_type<std::pair<iterator, bool> >::equals(r.emplace(t));
481 
482   typedef typename X::node_type node_type;
483   typedef typename X::insert_return_type insert_return_type;
484 
485   // insert_return_type
486 
487   // TODO;
488   // boost::function_requires<
489   //     boost::MoveConstructibleConcept<insert_return_type>
490   // >();
491   // TODO;
492   // boost::function_requires<
493   //     boost::MoveAssignableConcept<insert_return_type>
494   // >();
495   boost::function_requires<
496     boost::DefaultConstructibleConcept<insert_return_type> >();
497   // TODO:
498   // boost::function_requires<
499   //     boost::DestructibleConcept<insert_return_type>
500   // >();
501   insert_return_type insert_return, insert_return2;
502   test::check_return_type<bool>::equals(insert_return.inserted);
503   test::check_return_type<iterator>::equals(insert_return.position);
504   test::check_return_type<node_type>::equals_ref(insert_return.node);
505   boost::swap(insert_return, insert_return2);
506 }
507 
unordered_equivalent_test(X & r,T const & t)508 template <class X, class T> void unordered_equivalent_test(X& r, T const& t)
509 {
510   typedef typename X::iterator iterator;
511   test::check_return_type<iterator>::equals(r.insert(t));
512   test::check_return_type<iterator>::equals(r.emplace(t));
513 }
514 
515 template <class X, class Key, class T>
unordered_map_functions(X &,Key const & k,T const & v)516 void unordered_map_functions(X&, Key const& k, T const& v)
517 {
518   typedef typename X::mapped_type mapped_type;
519   typedef typename X::iterator iterator;
520 
521   X a;
522   test::check_return_type<mapped_type>::equals_ref(a[k]);
523   test::check_return_type<mapped_type>::equals_ref(a[rvalue(k)]);
524   test::check_return_type<mapped_type>::equals_ref(a.at(k));
525   test::check_return_type<std::pair<iterator, bool> >::equals(
526     a.try_emplace(k, v));
527   test::check_return_type<std::pair<iterator, bool> >::equals(
528     a.try_emplace(rvalue(k), v));
529   test::check_return_type<iterator>::equals(a.try_emplace(a.begin(), k, v));
530   test::check_return_type<iterator>::equals(
531     a.try_emplace(a.begin(), rvalue(k), v));
532   test::check_return_type<std::pair<iterator, bool> >::equals(
533     a.insert_or_assign(k, v));
534   test::check_return_type<std::pair<iterator, bool> >::equals(
535     a.insert_or_assign(rvalue(k), v));
536   test::check_return_type<iterator>::equals(
537     a.insert_or_assign(a.begin(), k, v));
538   test::check_return_type<iterator>::equals(
539     a.insert_or_assign(a.begin(), rvalue(k), v));
540 
541   X const b = a;
542   test::check_return_type<mapped_type const>::equals_ref(b.at(k));
543 }
544 
545 template <class X, class Key, class Hash, class Pred>
unordered_test(X & x,Key & k,Hash & hf,Pred & eq)546 void unordered_test(X& x, Key& k, Hash& hf, Pred& eq)
547 {
548   unordered_destructible_test(x);
549 
550   typedef typename X::key_type key_type;
551   typedef typename X::hasher hasher;
552   typedef typename X::key_equal key_equal;
553   typedef typename X::size_type size_type;
554 
555   typedef typename X::iterator iterator;
556   typedef typename X::const_iterator const_iterator;
557   typedef typename X::local_iterator local_iterator;
558   typedef typename X::const_local_iterator const_local_iterator;
559 
560   typedef typename std::iterator_traits<iterator>::iterator_category
561     iterator_category;
562   typedef typename std::iterator_traits<iterator>::difference_type
563     iterator_difference;
564   typedef typename std::iterator_traits<iterator>::pointer iterator_pointer;
565   typedef typename std::iterator_traits<iterator>::reference iterator_reference;
566 
567   typedef typename std::iterator_traits<local_iterator>::iterator_category
568     local_iterator_category;
569   typedef typename std::iterator_traits<local_iterator>::difference_type
570     local_iterator_difference;
571   typedef typename std::iterator_traits<local_iterator>::pointer
572     local_iterator_pointer;
573   typedef typename std::iterator_traits<local_iterator>::reference
574     local_iterator_reference;
575 
576   typedef typename std::iterator_traits<const_iterator>::iterator_category
577     const_iterator_category;
578   typedef typename std::iterator_traits<const_iterator>::difference_type
579     const_iterator_difference;
580   typedef typename std::iterator_traits<const_iterator>::pointer
581     const_iterator_pointer;
582   typedef typename std::iterator_traits<const_iterator>::reference
583     const_iterator_reference;
584 
585   typedef typename std::iterator_traits<const_local_iterator>::iterator_category
586     const_local_iterator_category;
587   typedef typename std::iterator_traits<const_local_iterator>::difference_type
588     const_local_iterator_difference;
589   typedef typename std::iterator_traits<const_local_iterator>::pointer
590     const_local_iterator_pointer;
591   typedef typename std::iterator_traits<const_local_iterator>::reference
592     const_local_iterator_reference;
593   typedef typename X::allocator_type allocator_type;
594 
595   BOOST_STATIC_ASSERT((boost::is_same<Key, key_type>::value));
596   // boost::function_requires<boost::CopyConstructibleConcept<key_type> >();
597   // boost::function_requires<boost::AssignableConcept<key_type> >();
598 
599   BOOST_STATIC_ASSERT((boost::is_same<Hash, hasher>::value));
600   test::check_return_type<std::size_t>::equals(hf(k));
601 
602   BOOST_STATIC_ASSERT((boost::is_same<Pred, key_equal>::value));
603   test::check_return_type<bool>::convertible(eq(k, k));
604 
605   boost::function_requires<boost::InputIteratorConcept<local_iterator> >();
606   BOOST_STATIC_ASSERT(
607     (boost::is_same<local_iterator_category, iterator_category>::value));
608   BOOST_STATIC_ASSERT(
609     (boost::is_same<local_iterator_difference, iterator_difference>::value));
610   BOOST_STATIC_ASSERT(
611     (boost::is_same<local_iterator_pointer, iterator_pointer>::value));
612   BOOST_STATIC_ASSERT(
613     (boost::is_same<local_iterator_reference, iterator_reference>::value));
614 
615   boost::function_requires<
616     boost::InputIteratorConcept<const_local_iterator> >();
617   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator_category,
618     const_iterator_category>::value));
619   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator_difference,
620     const_iterator_difference>::value));
621   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator_pointer,
622     const_iterator_pointer>::value));
623   BOOST_STATIC_ASSERT((boost::is_same<const_local_iterator_reference,
624     const_iterator_reference>::value));
625 
626   X a;
627   allocator_type m = a.get_allocator();
628 
629   // Constructors
630 
631   X(10, hf, eq);
632   X a1(10, hf, eq);
633   X(10, hf);
634   X a2(10, hf);
635   X(10);
636   X a3(10);
637   X();
638   X a4;
639 
640   X(10, hf, eq, m);
641   X a1a(10, hf, eq, m);
642   X(10, hf, m);
643   X a2a(10, hf, m);
644   X(10, m);
645   X a3a(10, m);
646   (X(m));
647   X a4a(m);
648 
649   test::check_return_type<size_type>::equals(a.erase(k));
650 
651   const_iterator q1 = a.cbegin(), q2 = a.cend();
652   test::check_return_type<iterator>::equals(a.erase(q1, q2));
653 
654   TEST_NOEXCEPT_EXPR(a.clear());
655   a.clear();
656 
657   X const b;
658 
659   test::check_return_type<hasher>::equals(b.hash_function());
660   test::check_return_type<key_equal>::equals(b.key_eq());
661 
662   test::check_return_type<iterator>::equals(a.find(k));
663   test::check_return_type<const_iterator>::equals(b.find(k));
664   test::check_return_type<size_type>::equals(b.count(k));
665   test::check_return_type<std::pair<iterator, iterator> >::equals(
666     a.equal_range(k));
667   test::check_return_type<std::pair<const_iterator, const_iterator> >::equals(
668     b.equal_range(k));
669   test::check_return_type<size_type>::equals(b.bucket_count());
670   test::check_return_type<size_type>::equals(b.max_bucket_count());
671   test::check_return_type<size_type>::equals(b.bucket(k));
672   test::check_return_type<size_type>::equals(b.bucket_size(0));
673 
674   test::check_return_type<local_iterator>::equals(a.begin(0));
675   test::check_return_type<const_local_iterator>::equals(b.begin(0));
676   test::check_return_type<local_iterator>::equals(a.end(0));
677   test::check_return_type<const_local_iterator>::equals(b.end(0));
678 
679   test::check_return_type<const_local_iterator>::equals(a.cbegin(0));
680   test::check_return_type<const_local_iterator>::equals(b.cbegin(0));
681   test::check_return_type<const_local_iterator>::equals(a.cend(0));
682   test::check_return_type<const_local_iterator>::equals(b.cend(0));
683 
684   test::check_return_type<float>::equals(b.load_factor());
685   test::check_return_type<float>::equals(b.max_load_factor());
686   a.max_load_factor((float)2.0);
687   a.rehash(100);
688 
689   a.merge(a2);
690 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
691   a.merge(rvalue_default<X>());
692 #endif
693 
694   // Avoid unused variable warnings:
695 
696   sink(a);
697   sink(a1);
698   sink(a2);
699   sink(a3);
700   sink(a4);
701   sink(a1a);
702   sink(a2a);
703   sink(a3a);
704   sink(a4a);
705 }
706 
707 template <class X, class Key, class T, class Hash, class Pred>
unordered_copyable_test(X & x,Key & k,T & t,Hash & hf,Pred & eq)708 void unordered_copyable_test(X& x, Key& k, T& t, Hash& hf, Pred& eq)
709 {
710   unordered_test(x, k, hf, eq);
711 
712   typedef typename X::iterator iterator;
713   typedef typename X::const_iterator const_iterator;
714   typedef typename X::allocator_type allocator_type;
715 
716   X a;
717   allocator_type m = a.get_allocator();
718 
719   typename X::value_type* i = 0;
720   typename X::value_type* j = 0;
721 
722   // Constructors
723 
724   X(i, j, 10, hf, eq);
725   X a5(i, j, 10, hf, eq);
726   X(i, j, 10, hf);
727   X a6(i, j, 10, hf);
728   X(i, j, 10);
729   X a7(i, j, 10);
730   X(i, j);
731   X a8(i, j);
732 
733   X(i, j, 10, hf, eq, m);
734   X a5a(i, j, 10, hf, eq, m);
735   X(i, j, 10, hf, m);
736   X a6a(i, j, 10, hf, m);
737   X(i, j, 10, m);
738   X a7a(i, j, 10, m);
739 
740 // Not specified for some reason (maybe ambiguity with another constructor?)
741 // X(i, j, m);
742 // X a8a(i, j, m);
743 // sink(a8a);
744 
745 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
746   std::size_t min_buckets = 10;
747   X({t});
748   X({t}, min_buckets);
749   X({t}, min_buckets, hf);
750   X({t}, min_buckets, hf, eq);
751   // X({t}, m);
752   X({t}, min_buckets, m);
753   X({t}, min_buckets, hf, m);
754   X({t}, min_buckets, hf, eq, m);
755 #endif
756 
757   X const b;
758   sink(X(b));
759   X a9(b);
760   a = b;
761 
762   sink(X(b, m));
763   X a9a(b, m);
764 
765   X b1;
766   b1.insert(t);
767   X a9b(b1);
768   sink(a9b);
769   X a9c(b1, m);
770   sink(a9c);
771 
772   const_iterator q = a.cbegin();
773 
774   test::check_return_type<iterator>::equals(a.insert(q, t));
775   test::check_return_type<iterator>::equals(a.emplace_hint(q, t));
776 
777   a.insert(i, j);
778 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
779   std::initializer_list<T> list = {t};
780   a.insert(list);
781   a.insert({t, t, t});
782 
783 #if !BOOST_WORKAROUND(BOOST_MSVC, < 1900) &&                                   \
784   (!defined(__clang__) || __clang_major__ >= 4 ||                              \
785     (__clang_major__ == 3 && __clang_minor__ >= 4))
786   a.insert({});
787   a.insert({t});
788   a.insert({t, t});
789 #endif
790 #endif
791 
792   X a10;
793   a10.insert(t);
794   q = a10.cbegin();
795   test::check_return_type<iterator>::equals(a10.erase(q));
796 
797   // Avoid unused variable warnings:
798 
799   sink(a);
800   sink(a5);
801   sink(a6);
802   sink(a7);
803   sink(a8);
804   sink(a9);
805   sink(a5a);
806   sink(a6a);
807   sink(a7a);
808   sink(a9a);
809 
810   typedef typename X::node_type node_type;
811   typedef typename X::allocator_type allocator_type;
812   node_type const n_const = a.extract(a.begin());
813   test::check_return_type<allocator_type>::equals(n_const.get_allocator());
814 }
815 
816 template <class X, class Key, class T, class Hash, class Pred>
unordered_movable_test(X & x,Key & k,T &,Hash & hf,Pred & eq)817 void unordered_movable_test(X& x, Key& k, T& /* t */, Hash& hf, Pred& eq)
818 {
819   unordered_test(x, k, hf, eq);
820 
821   typedef typename X::iterator iterator;
822   typedef typename X::const_iterator const_iterator;
823   typedef typename X::allocator_type allocator_type;
824 
825 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
826   X x1(rvalue_default<X>());
827   X x2(boost::move(x1));
828   x1 = rvalue_default<X>();
829   x2 = boost::move(x1);
830 #endif
831 
832   X a;
833   allocator_type m = a.get_allocator();
834 
835   test::minimal::constructor_param* i = 0;
836   test::minimal::constructor_param* j = 0;
837 
838   // Constructors
839 
840   X(i, j, 10, hf, eq);
841   X a5(i, j, 10, hf, eq);
842   X(i, j, 10, hf);
843   X a6(i, j, 10, hf);
844   X(i, j, 10);
845   X a7(i, j, 10);
846   X(i, j);
847   X a8(i, j);
848 
849   X(i, j, 10, hf, eq, m);
850   X a5a(i, j, 10, hf, eq, m);
851   X(i, j, 10, hf, m);
852   X a6a(i, j, 10, hf, m);
853   X(i, j, 10, m);
854   X a7a(i, j, 10, m);
855 
856   // Not specified for some reason (maybe ambiguity with another constructor?)
857   // X(i, j, m);
858   // X a8a(i, j, m);
859   // sink(a8a);
860 
861   const_iterator q = a.cbegin();
862 
863   test::minimal::constructor_param v;
864   a.emplace(v);
865   test::check_return_type<iterator>::equals(a.emplace_hint(q, v));
866 
867   T v1(v);
868   a.emplace(boost::move(v1));
869   T v2(v);
870   a.insert(boost::move(v2));
871   T v3(v);
872   test::check_return_type<iterator>::equals(a.emplace_hint(q, boost::move(v3)));
873   T v4(v);
874   test::check_return_type<iterator>::equals(a.insert(q, boost::move(v4)));
875 
876   a.insert(i, j);
877 
878   X a10;
879   T v5(v);
880   a10.insert(boost::move(v5));
881   q = a10.cbegin();
882   test::check_return_type<iterator>::equals(a10.erase(q));
883 
884   // Avoid unused variable warnings:
885 
886   sink(a);
887   sink(a5);
888   sink(a6);
889   sink(a7);
890   sink(a8);
891   sink(a5a);
892   sink(a6a);
893   sink(a7a);
894   sink(a10);
895 }
896 
unordered_set_member_test(X & x,T & t)897 template <class X, class T> void unordered_set_member_test(X& x, T& t)
898 {
899   X x1(x);
900   x1.insert(t);
901   x1.begin()->dummy_member();
902   x1.cbegin()->dummy_member();
903 }
904 
unordered_map_member_test(X & x,T & t)905 template <class X, class T> void unordered_map_member_test(X& x, T& t)
906 {
907   X x1(x);
908   x1.insert(t);
909   x1.begin()->first.dummy_member();
910   x1.cbegin()->first.dummy_member();
911   x1.begin()->second.dummy_member();
912   x1.cbegin()->second.dummy_member();
913 }
914