ceph/src/boost/libs/unordered/include/boost/unordered/detail/allocate.hpp

   1
   2 // Copyright 2005-2011 Daniel James.
   3 // Copyright 2009 Pablo Halpern.
   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 //  See http://www.boost.org/libs/unordered for documentation
   8
   9 #ifndef BOOST_UNORDERED_ALLOCATE_HPP
  10 #define BOOST_UNORDERED_ALLOCATE_HPP
  11
  12 #include <boost/config.hpp>
  13 #if defined(BOOST_HAS_PRAGMA_ONCE)
  14 #pragma once
  15 #endif
  16
  17 // Some of these includes are required for other detail headers.
  18 #include <boost/unordered/detail/fwd.hpp>
  19 #include <boost/move/move.hpp>
  20 #include <boost/preprocessor/cat.hpp>
  21 #include <boost/preprocessor/repetition/enum.hpp>
  22 #include <boost/preprocessor/repetition/enum_params.hpp>
  23 #include <boost/preprocessor/repetition/enum_binary_params.hpp>
  24 #include <boost/preprocessor/repetition/repeat_from_to.hpp>
  25 #include <boost/type_traits/is_class.hpp>
  26 #include <boost/type_traits/add_lvalue_reference.hpp>
  27 #include <boost/type_traits/aligned_storage.hpp>
  28 #include <boost/type_traits/alignment_of.hpp>
  29 #include <boost/type_traits/is_nothrow_move_constructible.hpp>
  30 #include <boost/type_traits/is_nothrow_move_assignable.hpp>
  31 #include <boost/tuple/tuple.hpp>
  32 #include <boost/utility/enable_if.hpp>
  33 #include <boost/utility/addressof.hpp>
  34 #include <boost/detail/no_exceptions_support.hpp>
  35 #include <boost/detail/select_type.hpp>
  36 #include <boost/swap.hpp>
  37 #include <boost/assert.hpp>
  38 #include <boost/limits.hpp>
  39 #include <iterator>
  40 #include <utility>
  41 #include <cmath>
  42
  43 #if !defined(BOOST_NO_CXX11_HDR_TUPLE)
  44 #include <tuple>
  45 #endif
  46
  47 #if defined(BOOST_MSVC)
  48 #pragma warning(push)
  49 #pragma warning(disable:4512) // assignment operator could not be generated.
  50 #pragma warning(disable:4345) // behavior change: an object of POD type
  51                               // constructed with an initializer of the form ()
  52                               // will be default-initialized.
  53 #endif
  54
  55 #define BOOST_UNORDERED_EMPLACE_LIMIT 10
  56
  57 namespace boost { namespace unordered { namespace detail {
  58
  59     ////////////////////////////////////////////////////////////////////////////
  60     // Bits and pieces for implementing traits
  61
  62     template <typename T> typename boost::add_lvalue_reference<T>::type make();
  63     struct choice9 { typedef char (&type)[9]; };
  64     struct choice8 : choice9 { typedef char (&type)[8]; };
  65     struct choice7 : choice8 { typedef char (&type)[7]; };
  66     struct choice6 : choice7 { typedef char (&type)[6]; };
  67     struct choice5 : choice6 { typedef char (&type)[5]; };
  68     struct choice4 : choice5 { typedef char (&type)[4]; };
  69     struct choice3 : choice4 { typedef char (&type)[3]; };
  70     struct choice2 : choice3 { typedef char (&type)[2]; };
  71     struct choice1 : choice2 { typedef char (&type)[1]; };
  72     choice1 choose();
  73
  74     typedef choice1::type yes_type;
  75     typedef choice2::type no_type;
  76
  77     struct private_type
  78     {
  79        private_type const &operator,(int) const;
  80     };
  81
  82     template <typename T>
  83     no_type is_private_type(T const&);
  84     yes_type is_private_type(private_type const&);
  85
  86     struct convert_from_anything {
  87         template <typename T>
  88         convert_from_anything(T const&);
  89     };
  90
  91     namespace func {
  92         // This is a bit nasty, when constructing the individual members
  93         // of a std::pair, need to cast away 'const'. For modern compilers,
  94         // should be able to use std::piecewise_construct instead.
  95         template <typename T> T* const_cast_pointer(T* x) { return x; }
  96         template <typename T> T* const_cast_pointer(T const* x) {
  97             return const_cast<T*>(x);
  98         }
  99     }
 100
 101     ////////////////////////////////////////////////////////////////////////////
 102     // emplace_args
 103     //
 104     // Either forwarding variadic arguments, or storing the arguments in
 105     // emplace_args##n
 106
 107 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 108
 109 #define BOOST_UNORDERED_EMPLACE_ARGS1(a0) a0
 110 #define BOOST_UNORDERED_EMPLACE_ARGS2(a0, a1) a0, a1
 111 #define BOOST_UNORDERED_EMPLACE_ARGS3(a0, a1, a2) a0, a1, a2
 112
 113 #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
 114 #define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
 115 #define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)...
 116
 117 #else
 118
 119 #define BOOST_UNORDERED_EMPLACE_ARGS1 create_emplace_args
 120 #define BOOST_UNORDERED_EMPLACE_ARGS2 create_emplace_args
 121 #define BOOST_UNORDERED_EMPLACE_ARGS3 create_emplace_args
 122
 123 #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args
 124 #define BOOST_UNORDERED_EMPLACE_ARGS Args const& args
 125 #define BOOST_UNORDERED_EMPLACE_FORWARD args
 126
 127 #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
 128
 129 #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _)                               \
 130     typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n);         \
 131     BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
 132
 133 #else
 134
 135 #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _)                               \
 136     typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type  \
 137         BOOST_PP_CAT(Arg, n);                                               \
 138     BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
 139
 140 #endif
 141
 142 template <typename A0>
 143 struct emplace_args1
 144 {
 145     BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
 146
 147     emplace_args1(Arg0 b0) : a0(b0) {}
 148 };
 149
 150 template <typename A0>
 151 inline emplace_args1<A0> create_emplace_args(
 152         BOOST_FWD_REF(A0) b0)
 153 {
 154     emplace_args1<A0> e(b0);
 155     return e;
 156 }
 157
 158 template <typename A0, typename A1>
 159 struct emplace_args2
 160 {
 161     BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
 162     BOOST_UNORDERED_EARGS_MEMBER(1, 1, _)
 163
 164     emplace_args2(Arg0 b0, Arg1 b1) : a0(b0), a1(b1) {}
 165 };
 166
 167 template <typename A0, typename A1>
 168 inline emplace_args2<A0, A1> create_emplace_args(
 169         BOOST_FWD_REF(A0) b0,
 170         BOOST_FWD_REF(A1) b1)
 171 {
 172     emplace_args2<A0, A1> e(b0, b1);
 173     return e;
 174 }
 175
 176 template <typename A0, typename A1, typename A2>
 177 struct emplace_args3
 178 {
 179     BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
 180     BOOST_UNORDERED_EARGS_MEMBER(1, 1, _)
 181     BOOST_UNORDERED_EARGS_MEMBER(1, 2, _)
 182
 183     emplace_args3(Arg0 b0, Arg1 b1, Arg2 b2) : a0(b0), a1(b1), a2(b2) {}
 184 };
 185
 186 template <typename A0, typename A1, typename A2>
 187 inline emplace_args3<A0, A1, A2> create_emplace_args(
 188         BOOST_FWD_REF(A0) b0,
 189         BOOST_FWD_REF(A1) b1,
 190         BOOST_FWD_REF(A2) b2)
 191 {
 192     emplace_args3<A0, A1, A2> e(b0, b1, b2);
 193     return e;
 194 }
 195
 196 #define BOOST_UNORDERED_FWD_PARAM(z, n, a) \
 197     BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n)
 198
 199 #define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \
 200     boost::forward<BOOST_PP_CAT(A,i)>(BOOST_PP_CAT(a,i))
 201
 202 #define BOOST_UNORDERED_EARGS_INIT(z, n, _)                                 \
 203 BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
 204
 205 #define BOOST_UNORDERED_EARGS(z, n, _)                                      \
 206     template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)>                     \
 207     struct BOOST_PP_CAT(emplace_args, n)                                    \
 208     {                                                                       \
 209         BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _)             \
 210         BOOST_PP_CAT(emplace_args, n) (                                     \
 211             BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b)                     \
 212         ) : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _)             \
 213         {}                                                                  \
 214                                                                             \
 215     };                                                                      \
 216                                                                             \
 217     template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)>                     \
 218     inline BOOST_PP_CAT(emplace_args, n) <                                  \
 219         BOOST_PP_ENUM_PARAMS_Z(z, n, A)                                     \
 220     > create_emplace_args(                                                  \
 221         BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b)                  \
 222     )                                                                       \
 223     {                                                                       \
 224         BOOST_PP_CAT(emplace_args, n) <                                     \
 225             BOOST_PP_ENUM_PARAMS_Z(z, n, A)                                 \
 226         > e(BOOST_PP_ENUM_PARAMS_Z(z, n, b));                               \
 227         return e;                                                           \
 228     }
 229
 230 BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EARGS,
 231     _)
 232
 233 #undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS
 234 #undef BOOST_UNORDERED_EARGS_MEMBER
 235 #undef BOOST_UNORDERED_EARGS_INIT
 236
 237 #endif
 238
 239 }}}
 240
 241 ////////////////////////////////////////////////////////////////////////////////
 242 //
 243 // Pick which version of allocator_traits to use
 244 //
 245 // 0 = Own partial implementation
 246 // 1 = std::allocator_traits
 247 // 2 = boost::container::allocator_traits
 248
 249 #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
 250 #   if !defined(BOOST_NO_CXX11_ALLOCATOR)
 251 #       define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1
 252 #   elif defined(BOOST_MSVC)
 253 #       if BOOST_MSVC < 1400
 254             // Use container's allocator_traits for older versions of Visual
 255             // C++ as I don't test with them.
 256 #           define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
 257 #       endif
 258 #   endif
 259 #endif
 260
 261 #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
 262 #   define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
 263 #endif
 264
 265 ////////////////////////////////////////////////////////////////////////////////
 266 //
 267 // Some utilities for implementing allocator_traits, but useful elsewhere so
 268 // they're always defined.
 269
 270 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
 271 #  include <type_traits>
 272 #endif
 273
 274 namespace boost { namespace unordered { namespace detail {
 275
 276     ////////////////////////////////////////////////////////////////////////////
 277     // Integral_constrant, true_type, false_type
 278     //
 279     // Uses the standard versions if available.
 280
 281 #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
 282
 283     using std::integral_constant;
 284     using std::true_type;
 285     using std::false_type;
 286
 287 #else
 288
 289     template <typename T, T Value>
 290     struct integral_constant { enum { value = Value }; };
 291
 292     typedef boost::unordered::detail::integral_constant<bool, true> true_type;
 293     typedef boost::unordered::detail::integral_constant<bool, false> false_type;
 294
 295 #endif
 296
 297     ////////////////////////////////////////////////////////////////////////////
 298     // Explicitly call a destructor
 299
 300 #if defined(BOOST_MSVC)
 301 #pragma warning(push)
 302 #pragma warning(disable:4100) // unreferenced formal parameter
 303 #endif
 304
 305     namespace func {
 306         template <class T>
 307         inline void destroy(T* x) {
 308             x->~T();
 309         }
 310     }
 311
 312 #if defined(BOOST_MSVC)
 313 #pragma warning(pop)
 314 #endif
 315
 316     ////////////////////////////////////////////////////////////////////////////
 317     // Expression test mechanism
 318     //
 319     // When SFINAE expressions are available, define
 320     // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is
 321     // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which
 322     // can detect if a class has the specified member, but not that it has the
 323     // correct type, this is good enough for a passable impression of
 324     // allocator_traits.
 325
 326 #if !defined(BOOST_NO_SFINAE_EXPR)
 327
 328     template <typename T, long unsigned int> struct expr_test;
 329     template <typename T> struct expr_test<T, sizeof(char)> : T {};
 330
 331 #   define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression)      \
 332         template <typename U>                                               \
 333         static typename boost::unordered::detail::expr_test<                \
 334             BOOST_PP_CAT(choice, result),                                   \
 335             sizeof(for_expr_test((                                          \
 336                 (expression),                                               \
 337             0)))>::type test(                                               \
 338             BOOST_PP_CAT(choice, count))
 339
 340 #   define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result)                \
 341         template <typename U>                                               \
 342         static BOOST_PP_CAT(choice, result)::type test(                     \
 343             BOOST_PP_CAT(choice, count))
 344
 345 #   define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _)               \
 346     struct BOOST_PP_CAT(has_, name)                                         \
 347     {                                                                       \
 348         template <typename U> static char for_expr_test(U const&);          \
 349         BOOST_UNORDERED_CHECK_EXPRESSION(1, 1,                              \
 350             boost::unordered::detail::make< thing >().name args);           \
 351         BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2);                           \
 352                                                                             \
 353         enum { value = sizeof(test<T>(choose())) == sizeof(choice1::type) };\
 354     }
 355
 356 #else
 357
 358     template <typename T> struct identity { typedef T type; };
 359
 360 #   define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member)        \
 361                                                                             \
 362     typedef typename boost::unordered::detail::identity<member>::type       \
 363         BOOST_PP_CAT(check, count);                                         \
 364                                                                             \
 365     template <BOOST_PP_CAT(check, count) e>                                 \
 366     struct BOOST_PP_CAT(test, count) {                                      \
 367         typedef BOOST_PP_CAT(choice, result) type;                          \
 368     };                                                                      \
 369                                                                             \
 370     template <class U> static typename                                      \
 371         BOOST_PP_CAT(test, count)<&U::name>::type                           \
 372         test(BOOST_PP_CAT(choice, count))
 373
 374 #   define BOOST_UNORDERED_DEFAULT_MEMBER(count, result)                    \
 375     template <class U> static BOOST_PP_CAT(choice, result)::type            \
 376         test(BOOST_PP_CAT(choice, count))
 377
 378 #   define BOOST_UNORDERED_HAS_MEMBER(name)                                 \
 379     struct BOOST_PP_CAT(has_, name)                                         \
 380     {                                                                       \
 381         struct impl {                                                       \
 382             struct base_mixin { int name; };                                \
 383             struct base : public T, public base_mixin {};                   \
 384                                                                             \
 385             BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*);    \
 386             BOOST_UNORDERED_DEFAULT_MEMBER(2, 2);                           \
 387                                                                             \
 388             enum { value = sizeof(choice2::type) ==                         \
 389                 sizeof(test<base>(choose()))                                \
 390             };                                                              \
 391         };                                                                  \
 392                                                                             \
 393         enum { value = impl::value };                                       \
 394     }
 395
 396 #endif
 397
 398 }}}
 399
 400 ////////////////////////////////////////////////////////////////////////////////
 401 //
 402 // Allocator traits
 403 //
 404 // First our implementation, then later light wrappers around the alternatives
 405
 406 #if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0
 407
 408 #   include <boost/limits.hpp>
 409 #   include <boost/utility/enable_if.hpp>
 410 #   include <boost/pointer_to_other.hpp>
 411 #   if defined(BOOST_NO_SFINAE_EXPR)
 412 #       include <boost/type_traits/is_same.hpp>
 413 #   endif
 414
 415 #   if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && \
 416         !defined(BOOST_NO_SFINAE_EXPR)
 417 #       define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
 418 #   else
 419 #       define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
 420 #   endif
 421
 422 namespace boost { namespace unordered { namespace detail {
 423
 424     template <typename Alloc, typename T>
 425     struct rebind_alloc;
 426
 427 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 428
 429     template <template<typename, typename...> class Alloc,
 430         typename U, typename T, typename... Args>
 431     struct rebind_alloc<Alloc<U, Args...>, T>
 432     {
 433         typedef Alloc<T, Args...> type;
 434     };
 435
 436 #else
 437
 438     template <
 439         template<typename> class Alloc,
 440         typename U, typename T>
 441     struct rebind_alloc<Alloc<U>, T>
 442     {
 443         typedef Alloc<T> type;
 444     };
 445
 446     template <
 447         template<typename, typename> class Alloc,
 448         typename U, typename T,
 449         typename A0>
 450     struct rebind_alloc<Alloc<U, A0>, T>
 451     {
 452         typedef Alloc<T, A0> type;
 453     };
 454
 455     template <
 456         template<typename, typename, typename> class Alloc,
 457         typename U, typename T,
 458         typename A0, typename A1>
 459     struct rebind_alloc<Alloc<U, A0, A1>, T>
 460     {
 461         typedef Alloc<T, A0, A1> type;
 462     };
 463
 464 #endif
 465
 466     template <typename Alloc, typename T>
 467     struct rebind_wrap
 468     {
 469         template <typename X>
 470         static choice1::type test(choice1,
 471             typename X::BOOST_NESTED_TEMPLATE rebind<T>::other* = 0);
 472         template <typename X>
 473         static choice2::type test(choice2, void* = 0);
 474
 475         enum { value = (1 == sizeof(test<Alloc>(choose()))) };
 476
 477         struct fallback {
 478             template <typename U>
 479             struct rebind {
 480                 typedef typename rebind_alloc<Alloc, T>::type other;
 481             };
 482         };
 483
 484         typedef typename boost::detail::if_true<value>::
 485             BOOST_NESTED_TEMPLATE then<Alloc, fallback>
 486             ::type::BOOST_NESTED_TEMPLATE rebind<T>::other type;
 487     };
 488
 489 #   if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
 490
 491 #       define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname)                    \
 492     template <typename Tp, typename Default>                                \
 493     struct default_type_ ## tname {                                         \
 494                                                                             \
 495         template <typename X>                                               \
 496         static choice1::type test(choice1, typename X::tname* = 0);         \
 497                                                                             \
 498         template <typename X>                                               \
 499         static choice2::type test(choice2, void* = 0);                      \
 500                                                                             \
 501         struct DefaultWrap { typedef Default tname; };                      \
 502                                                                             \
 503         enum { value = (1 == sizeof(test<Tp>(choose()))) };                 \
 504                                                                             \
 505         typedef typename boost::detail::if_true<value>::                    \
 506             BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap>                     \
 507             ::type::tname type;                                             \
 508     }
 509
 510 #   else
 511
 512     template <typename T, typename T2>
 513     struct sfinae : T2 {};
 514
 515 #       define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname)                    \
 516     template <typename Tp, typename Default>                                \
 517     struct default_type_ ## tname {                                         \
 518                                                                             \
 519         template <typename X>                                               \
 520         static typename boost::unordered::detail::sfinae<                   \
 521                 typename X::tname, choice1>::type                           \
 522             test(choice1);                                                  \
 523                                                                             \
 524         template <typename X>                                               \
 525         static choice2::type test(choice2);                                 \
 526                                                                             \
 527         struct DefaultWrap { typedef Default tname; };                      \
 528                                                                             \
 529         enum { value = (1 == sizeof(test<Tp>(choose()))) };                 \
 530                                                                             \
 531         typedef typename boost::detail::if_true<value>::                    \
 532             BOOST_NESTED_TEMPLATE then<Tp, DefaultWrap>                     \
 533             ::type::tname type;                                             \
 534     }
 535
 536 #   endif
 537
 538 #   define BOOST_UNORDERED_DEFAULT_TYPE(T,tname, arg)                   \
 539     typename default_type_ ## tname<T, arg>::type
 540
 541     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer);
 542     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer);
 543     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer);
 544     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer);
 545     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type);
 546     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type);
 547     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_copy_assignment);
 548     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_move_assignment);
 549     BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap);
 550
 551 #   if !defined(BOOST_NO_SFINAE_EXPR)
 552
 553     template <typename T>
 554     BOOST_UNORDERED_HAS_FUNCTION(
 555         select_on_container_copy_construction, U const, (), 0
 556     );
 557
 558     template <typename T>
 559     BOOST_UNORDERED_HAS_FUNCTION(
 560         max_size, U const, (), 0
 561     );
 562
 563 #       if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 564
 565     template <typename T, typename ValueType, typename... Args>
 566     BOOST_UNORDERED_HAS_FUNCTION(
 567     construct, U, (
 568         boost::unordered::detail::make<ValueType*>(),
 569         boost::unordered::detail::make<Args const>()...), 2
 570     );
 571
 572 #       else
 573
 574     template <typename T, typename ValueType>
 575     BOOST_UNORDERED_HAS_FUNCTION(
 576     construct, U, (
 577         boost::unordered::detail::make<ValueType*>(),
 578         boost::unordered::detail::make<ValueType const>()), 2
 579     );
 580
 581 #       endif
 582
 583     template <typename T, typename ValueType>
 584     BOOST_UNORDERED_HAS_FUNCTION(
 585         destroy, U, (boost::unordered::detail::make<ValueType*>()), 1
 586     );
 587
 588 #   else
 589
 590     template <typename T>
 591     BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction);
 592
 593     template <typename T>
 594     BOOST_UNORDERED_HAS_MEMBER(max_size);
 595
 596     template <typename T, typename ValueType>
 597     BOOST_UNORDERED_HAS_MEMBER(construct);
 598
 599     template <typename T, typename ValueType>
 600     BOOST_UNORDERED_HAS_MEMBER(destroy);
 601
 602 #   endif
 603
 604     namespace func
 605     {
 606
 607     template <typename Alloc>
 608     inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
 609         typename boost::enable_if_c<
 610             boost::unordered::detail::
 611             has_select_on_container_copy_construction<Alloc>::value, void*
 612         >::type = 0)
 613     {
 614         return rhs.select_on_container_copy_construction();
 615     }
 616
 617     template <typename Alloc>
 618     inline Alloc call_select_on_container_copy_construction(const Alloc& rhs,
 619         typename boost::disable_if_c<
 620             boost::unordered::detail::
 621             has_select_on_container_copy_construction<Alloc>::value, void*
 622         >::type = 0)
 623     {
 624         return rhs;
 625     }
 626
 627     template <typename SizeType, typename Alloc>
 628     inline SizeType call_max_size(const Alloc& a,
 629         typename boost::enable_if_c<
 630             boost::unordered::detail::has_max_size<Alloc>::value, void*
 631         >::type = 0)
 632     {
 633         return a.max_size();
 634     }
 635
 636     template <typename SizeType, typename Alloc>
 637     inline SizeType call_max_size(const Alloc&, typename boost::disable_if_c<
 638             boost::unordered::detail::has_max_size<Alloc>::value, void*
 639         >::type = 0)
 640     {
 641         return (std::numeric_limits<SizeType>::max)();
 642     }
 643
 644     } // namespace func.
 645
 646     template <typename Alloc>
 647     struct allocator_traits
 648     {
 649         typedef Alloc allocator_type;
 650         typedef typename Alloc::value_type value_type;
 651
 652         typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, pointer, value_type*)
 653             pointer;
 654
 655         template <typename T>
 656         struct pointer_to_other : boost::pointer_to_other<pointer, T> {};
 657
 658         typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer,
 659             typename pointer_to_other<const value_type>::type)
 660             const_pointer;
 661
 662         //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer,
 663         //    typename pointer_to_other<void>::type)
 664         //    void_pointer;
 665         //
 666         //typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer,
 667         //    typename pointer_to_other<const void>::type)
 668         //    const_void_pointer;
 669
 670         typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, difference_type,
 671             std::ptrdiff_t) difference_type;
 672
 673         typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, size_type, std::size_t)
 674             size_type;
 675
 676 #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
 677         template <typename T>
 678         using rebind_alloc = typename rebind_wrap<Alloc, T>::type;
 679
 680         template <typename T>
 681         using rebind_traits =
 682             boost::unordered::detail::allocator_traits<rebind_alloc<T> >;
 683 #endif
 684
 685         static pointer allocate(Alloc& a, size_type n)
 686             { return a.allocate(n); }
 687
 688         // I never use this, so I'll just comment it out for now.
 689         //
 690         //static pointer allocate(Alloc& a, size_type n,
 691         //        const_void_pointer hint)
 692         //    { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); }
 693
 694         static void deallocate(Alloc& a, pointer p, size_type n)
 695             { a.deallocate(p, n); }
 696
 697     public:
 698
 699 #   if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
 700
 701         template <typename T, typename... Args>
 702         static typename boost::enable_if_c<
 703                 boost::unordered::detail::has_construct<Alloc, T, Args...>
 704                 ::value>::type
 705             construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x)
 706         {
 707             a.construct(p, boost::forward<Args>(x)...);
 708         }
 709
 710         template <typename T, typename... Args>
 711         static typename boost::disable_if_c<
 712                 boost::unordered::detail::has_construct<Alloc, T, Args...>
 713                 ::value>::type
 714             construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x)
 715         {
 716             new (static_cast<void*>(p)) T(boost::forward<Args>(x)...);
 717         }
 718
 719         template <typename T>
 720         static typename boost::enable_if_c<
 721                 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
 722             destroy(Alloc& a, T* p)
 723         {
 724             a.destroy(p);
 725         }
 726
 727         template <typename T>
 728         static typename boost::disable_if_c<
 729                 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
 730             destroy(Alloc&, T* p)
 731         {
 732             boost::unordered::detail::func::destroy(p);
 733         }
 734
 735 #   elif !defined(BOOST_NO_SFINAE_EXPR)
 736
 737         template <typename T>
 738         static typename boost::enable_if_c<
 739                 boost::unordered::detail::has_construct<Alloc, T>::value>::type
 740             construct(Alloc& a, T* p, T const& x)
 741         {
 742             a.construct(p, x);
 743         }
 744
 745         template <typename T>
 746         static typename boost::disable_if_c<
 747                 boost::unordered::detail::has_construct<Alloc, T>::value>::type
 748             construct(Alloc&, T* p, T const& x)
 749         {
 750             new (static_cast<void*>(p)) T(x);
 751         }
 752
 753         template <typename T>
 754         static typename boost::enable_if_c<
 755                 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
 756             destroy(Alloc& a, T* p)
 757         {
 758             a.destroy(p);
 759         }
 760
 761         template <typename T>
 762         static typename boost::disable_if_c<
 763                 boost::unordered::detail::has_destroy<Alloc, T>::value>::type
 764             destroy(Alloc&, T* p)
 765         {
 766             boost::unordered::detail::func::destroy(p);
 767         }
 768
 769 #   else
 770
 771         // If we don't have SFINAE expressions, only call construct for the
 772         // copy constructor for the allocator's value_type - as that's
 773         // the only construct method that old fashioned allocators support.
 774
 775         template <typename T>
 776         static void construct(Alloc& a, T* p, T const& x,
 777             typename boost::enable_if_c<
 778                     boost::unordered::detail::has_construct<Alloc, T>::value &&
 779                     boost::is_same<T, value_type>::value,
 780                     void*>::type = 0)
 781         {
 782             a.construct(p, x);
 783         }
 784
 785         template <typename T>
 786         static void construct(Alloc&, T* p, T const& x,
 787             typename boost::disable_if_c<
 788                 boost::unordered::detail::has_construct<Alloc, T>::value &&
 789                 boost::is_same<T, value_type>::value,
 790                 void*>::type = 0)
 791         {
 792             new (static_cast<void*>(p)) T(x);
 793         }
 794
 795         template <typename T>
 796         static void destroy(Alloc& a, T* p,
 797             typename boost::enable_if_c<
 798                 boost::unordered::detail::has_destroy<Alloc, T>::value &&
 799                 boost::is_same<T, value_type>::value,
 800                 void*>::type = 0)
 801         {
 802             a.destroy(p);
 803         }
 804
 805         template <typename T>
 806         static void destroy(Alloc&, T* p,
 807             typename boost::disable_if_c<
 808                 boost::unordered::detail::has_destroy<Alloc, T>::value &&
 809                 boost::is_same<T, value_type>::value,
 810                 void*>::type = 0)
 811         {
 812             boost::unordered::detail::func::destroy(p);
 813         }
 814
 815 #   endif
 816
 817         static size_type max_size(const Alloc& a)
 818         {
 819             return boost::unordered::detail::func::
 820                 call_max_size<size_type>(a);
 821         }
 822
 823         // Allocator propagation on construction
 824
 825         static Alloc select_on_container_copy_construction(Alloc const& rhs)
 826         {
 827             return boost::unordered::detail::func::
 828                 call_select_on_container_copy_construction(rhs);
 829         }
 830
 831         // Allocator propagation on assignment and swap.
 832         // Return true if lhs is modified.
 833         typedef BOOST_UNORDERED_DEFAULT_TYPE(
 834             Alloc, propagate_on_container_copy_assignment, false_type)
 835             propagate_on_container_copy_assignment;
 836         typedef BOOST_UNORDERED_DEFAULT_TYPE(
 837             Alloc,propagate_on_container_move_assignment, false_type)
 838             propagate_on_container_move_assignment;
 839         typedef BOOST_UNORDERED_DEFAULT_TYPE(
 840             Alloc,propagate_on_container_swap,false_type)
 841             propagate_on_container_swap;
 842     };
 843 }}}
 844
 845 #   undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
 846 #   undef BOOST_UNORDERED_DEFAULT_TYPE
 847
 848 ////////////////////////////////////////////////////////////////////////////////
 849 //
 850 // std::allocator_traits
 851
 852 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
 853
 854 #   include <memory>
 855
 856 #   define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 1
 857
 858 namespace boost { namespace unordered { namespace detail {
 859
 860     template <typename Alloc>
 861     struct allocator_traits : std::allocator_traits<Alloc> {};
 862
 863     template <typename Alloc, typename T>
 864     struct rebind_wrap
 865     {
 866         typedef typename std::allocator_traits<Alloc>::
 867             template rebind_alloc<T> type;
 868     };
 869 }}}
 870
 871 ////////////////////////////////////////////////////////////////////////////////
 872 //
 873 // boost::container::allocator_traits
 874
 875 #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
 876
 877 #   include <boost/container/allocator_traits.hpp>
 878
 879 #   define BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT 0
 880
 881 namespace boost { namespace unordered { namespace detail {
 882
 883     template <typename Alloc>
 884     struct allocator_traits :
 885         boost::container::allocator_traits<Alloc> {};
 886
 887     template <typename Alloc, typename T>
 888     struct rebind_wrap :
 889         boost::container::allocator_traits<Alloc>::
 890             template portable_rebind_alloc<T>
 891     {};
 892
 893 }}}
 894
 895 #else
 896
 897 #error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value."
 898
 899 #endif
 900
 901
 902 namespace boost { namespace unordered { namespace detail { namespace func {
 903
 904     ////////////////////////////////////////////////////////////////////////////
 905     // call_construct
 906
 907 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 908
 909 #   if BOOST_UNORDERED_DETAIL_FULL_CONSTRUCT
 910
 911     template <typename Alloc, typename T, typename... Args>
 912     inline void call_construct(Alloc& alloc, T* address,
 913         BOOST_FWD_REF(Args)... args)
 914     {
 915         boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
 916             address, boost::forward<Args>(args)...);
 917     }
 918
 919     template <typename Alloc, typename T>
 920     inline void call_destroy(Alloc& alloc, T* x) {
 921         boost::unordered::detail::allocator_traits<Alloc>::destroy(alloc, x);
 922     }
 923
 924
 925 #   else
 926
 927     template <typename Alloc, typename T, typename... Args>
 928     inline void call_construct(Alloc&, T* address,
 929         BOOST_FWD_REF(Args)... args)
 930     {
 931         new((void*) address) T(boost::forward<Args>(args)...);
 932     }
 933
 934     template <typename Alloc, typename T>
 935     inline void call_destroy(Alloc&, T* x) {
 936         boost::unordered::detail::func::destroy(x);
 937     }
 938
 939
 940 #   endif
 941
 942 #else
 943     template <typename Alloc, typename T>
 944     inline void call_construct(Alloc&, T* address)
 945     {
 946         new ((void*) address) T();
 947     }
 948
 949     template <typename Alloc, typename T, typename A0>
 950     inline void call_construct(Alloc&, T* address,
 951         BOOST_FWD_REF(A0) a0)
 952     {
 953         new ((void*) address) T(boost::forward<A0>(a0));
 954     }
 955
 956     template <typename Alloc, typename T>
 957     inline void call_destroy(Alloc&, T* x) {
 958         boost::unordered::detail::func::destroy(x);
 959     }
 960
 961 #endif
 962
 963     ////////////////////////////////////////////////////////////////////////////
 964     // Construct from tuple
 965     //
 966     // Used for piecewise construction.
 967
 968 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 969
 970 #   define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_)              \
 971     template<typename Alloc, typename T>                                    \
 972     void construct_from_tuple(Alloc& alloc, T* ptr, namespace_ tuple<>)     \
 973     {                                                                       \
 974         boost::unordered::detail::func::call_construct(alloc, ptr);         \
 975     }                                                                       \
 976                                                                             \
 977     BOOST_PP_REPEAT_FROM_TO(1, n,                                           \
 978         BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
 979
 980 #   define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_)      \
 981     template<typename Alloc, typename T,                                    \
 982         BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)>                           \
 983     void construct_from_tuple(Alloc& alloc, T* ptr,                         \
 984             namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x)     \
 985     {                                                                       \
 986         boost::unordered::detail::func::call_construct(alloc, ptr,          \
 987             BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
 988         );                                                                  \
 989     }
 990
 991 #   define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_)                  \
 992     namespace_ get<n>(x)
 993
 994 #elif !defined(__SUNPRO_CC)
 995
 996 #   define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_)              \
 997     template<typename Alloc, typename T>                                    \
 998     void construct_from_tuple(Alloc&, T* ptr, namespace_ tuple<>)           \
 999     {                                                                       \
1000         new ((void*) ptr) T();                                              \
1001     }                                                                       \
1002                                                                             \
1003     BOOST_PP_REPEAT_FROM_TO(1, n,                                           \
1004         BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
1005
1006 #   define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_)      \
1007     template<typename Alloc, typename T,                                    \
1008         BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)>                           \
1009     void construct_from_tuple(Alloc&, T* ptr,                               \
1010             namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x)     \
1011     {                                                                       \
1012         new ((void*) ptr) T(                                                \
1013             BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
1014         );                                                                  \
1015     }
1016
1017 #   define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_)                  \
1018     namespace_ get<n>(x)
1019
1020 #else
1021
1022     template <int N> struct length {};
1023
1024 #   define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(n, namespace_)              \
1025     template<typename Alloc, typename T>                                    \
1026     void construct_from_tuple_impl(                                         \
1027             boost::unordered::detail::func::length<0>, Alloc&, T* ptr,      \
1028             namespace_ tuple<>)                                             \
1029     {                                                                       \
1030         new ((void*) ptr) T();                                              \
1031     }                                                                       \
1032                                                                             \
1033     BOOST_PP_REPEAT_FROM_TO(1, n,                                           \
1034         BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL, namespace_)
1035
1036 #   define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL(z, n, namespace_)      \
1037     template<typename Alloc, typename T,                                    \
1038         BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)>                           \
1039     void construct_from_tuple_impl(                                         \
1040             boost::unordered::detail::func::length<n>, Alloc&, T* ptr,      \
1041             namespace_ tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x)     \
1042     {                                                                       \
1043         new ((void*) ptr) T(                                                \
1044             BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_) \
1045         );                                                                  \
1046     }
1047
1048 #   define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_)                  \
1049     namespace_ get<n>(x)
1050
1051 #endif
1052
1053 BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, boost::)
1054
1055 #if !defined(__SUNPRO_CC) && !defined(BOOST_NO_CXX11_HDR_TUPLE)
1056    BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(10, std::)
1057 #endif
1058
1059 #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
1060 #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE_IMPL
1061 #undef BOOST_UNORDERED_GET_TUPLE_ARG
1062
1063 #if defined(__SUNPRO_CC)
1064
1065     template <typename Alloc, typename T, typename Tuple>
1066     void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
1067     {
1068         construct_from_tuple_impl(
1069             boost::unordered::detail::func::length<
1070                 boost::tuples::length<Tuple>::value>(),
1071             alloc, ptr, x);
1072     }
1073
1074 #endif
1075
1076     ////////////////////////////////////////////////////////////////////////////
1077     // Trait to check for piecewise construction.
1078
1079     template <typename A0>
1080     struct use_piecewise {
1081         static choice1::type test(choice1,
1082             boost::unordered::piecewise_construct_t);
1083
1084         static choice2::type test(choice2, ...);
1085
1086         enum { value = sizeof(choice1::type) ==
1087             sizeof(test(choose(), boost::unordered::detail::make<A0>())) };
1088     };
1089
1090 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1091
1092     ////////////////////////////////////////////////////////////////////////////
1093     // Construct from variadic parameters
1094
1095     // For the standard pair constructor.
1096
1097     template <typename Alloc, typename T, typename... Args>
1098     inline void construct_from_args(Alloc& alloc, T* address,
1099         BOOST_FWD_REF(Args)... args)
1100     {
1101         boost::unordered::detail::func::call_construct(alloc,
1102             address, boost::forward<Args>(args)...);
1103     }
1104
1105     // Special case for piece_construct
1106     //
1107     // TODO: When possible, it might be better to use std::pair's
1108     // constructor for std::piece_construct with std::tuple.
1109
1110     template <typename Alloc, typename A, typename B,
1111         typename A0, typename A1, typename A2>
1112     inline typename enable_if<use_piecewise<A0>, void>::type
1113         construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1114             BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1115     {
1116         boost::unordered::detail::func::construct_from_tuple(alloc,
1117             boost::unordered::detail::func::const_cast_pointer(
1118                 boost::addressof(address->first)),
1119             boost::forward<A1>(a1));
1120         boost::unordered::detail::func::construct_from_tuple(alloc,
1121             boost::unordered::detail::func::const_cast_pointer(
1122                 boost::addressof(address->second)),
1123             boost::forward<A2>(a2));
1124     }
1125
1126 #else // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1127
1128     ////////////////////////////////////////////////////////////////////////////
1129     // Construct from emplace_args
1130
1131     // Explicitly write out first three overloads for the sake of sane
1132     // error messages.
1133
1134     template <typename Alloc, typename T, typename A0>
1135     inline void construct_from_args(Alloc&, T* address,
1136             emplace_args1<A0> const& args)
1137     {
1138         new((void*) address) T(boost::forward<A0>(args.a0));
1139     }
1140
1141     template <typename Alloc, typename T, typename A0, typename A1>
1142     inline void construct_from_args(Alloc&, T* address,
1143             emplace_args2<A0, A1> const& args)
1144     {
1145         new((void*) address) T(
1146             boost::forward<A0>(args.a0),
1147             boost::forward<A1>(args.a1)
1148         );
1149     }
1150
1151     template <typename Alloc, typename T, typename A0, typename A1, typename A2>
1152     inline void construct_from_args(Alloc&, T* address,
1153             emplace_args3<A0, A1, A2> const& args)
1154     {
1155         new((void*) address) T(
1156             boost::forward<A0>(args.a0),
1157             boost::forward<A1>(args.a1),
1158             boost::forward<A2>(args.a2)
1159         );
1160     }
1161
1162     // Use a macro for the rest.
1163
1164 #define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _)                    \
1165     template <                                                              \
1166         typename Alloc, typename T,                                         \
1167         BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A)                   \
1168     >                                                                       \
1169     inline void construct_from_args(Alloc&, T* address,                     \
1170         boost::unordered::detail::BOOST_PP_CAT(emplace_args,num_params) <   \
1171             BOOST_PP_ENUM_PARAMS_Z(z, num_params, A)                        \
1172         > const& args)                                                      \
1173     {                                                                       \
1174         new((void*) address) T(                                             \
1175             BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD,     \
1176                 args.a));                                                   \
1177     }
1178
1179     BOOST_PP_REPEAT_FROM_TO(4, BOOST_UNORDERED_EMPLACE_LIMIT,
1180         BOOST_UNORDERED_CONSTRUCT_IMPL, _)
1181
1182 #undef BOOST_UNORDERED_CONSTRUCT_IMPL
1183
1184     // Construct with piece_construct
1185
1186     template <typename Alloc, typename A, typename B,
1187         typename A0, typename A1, typename A2>
1188     inline void construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1189             boost::unordered::detail::emplace_args3<A0, A1, A2> const& args,
1190             typename enable_if<use_piecewise<A0>, void*>::type = 0)
1191     {
1192         boost::unordered::detail::func::construct_from_tuple(alloc,
1193             boost::unordered::detail::func::const_cast_pointer(
1194                 boost::addressof(address->first)),
1195             args.a1);
1196         boost::unordered::detail::func::construct_from_tuple(alloc,
1197             boost::unordered::detail::func::const_cast_pointer(
1198                 boost::addressof(address->second)),
1199             args.a2);
1200     }
1201
1202 #endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1203
1204 }}}}
1205
1206 namespace boost { namespace unordered { namespace detail {
1207
1208     ///////////////////////////////////////////////////////////////////
1209     //
1210     // Node construction
1211
1212     template <typename NodeAlloc>
1213     struct node_constructor
1214     {
1215         typedef NodeAlloc node_allocator;
1216         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1217             node_allocator_traits;
1218         typedef typename node_allocator_traits::value_type node;
1219         typedef typename node_allocator_traits::pointer node_pointer;
1220         typedef typename node::value_type value_type;
1221
1222         node_allocator& alloc_;
1223         node_pointer node_;
1224         bool node_constructed_;
1225
1226         node_constructor(node_allocator& n) :
1227             alloc_(n),
1228             node_(),
1229             node_constructed_(false)
1230         {
1231         }
1232
1233         ~node_constructor();
1234
1235         void create_node();
1236
1237         // no throw
1238         node_pointer release()
1239         {
1240             BOOST_ASSERT(node_ && node_constructed_);
1241             node_pointer p = node_;
1242             node_ = node_pointer();
1243             return p;
1244         }
1245
1246         void reclaim(node_pointer p) {
1247             BOOST_ASSERT(!node_);
1248             node_ = p;
1249             node_constructed_ = true;
1250             boost::unordered::detail::func::call_destroy(alloc_,
1251                 node_->value_ptr());
1252         }
1253
1254     private:
1255         node_constructor(node_constructor const&);
1256         node_constructor& operator=(node_constructor const&);
1257     };
1258
1259     template <typename Alloc>
1260     node_constructor<Alloc>::~node_constructor()
1261     {
1262         if (node_) {
1263             if (node_constructed_) {
1264                 boost::unordered::detail::func::destroy(
1265                     boost::addressof(*node_));
1266             }
1267
1268             node_allocator_traits::deallocate(alloc_, node_, 1);
1269         }
1270     }
1271
1272     template <typename Alloc>
1273     void node_constructor<Alloc>::create_node()
1274     {
1275         BOOST_ASSERT(!node_);
1276         node_constructed_ = false;
1277
1278         node_ = node_allocator_traits::allocate(alloc_, 1);
1279
1280         new ((void*) boost::addressof(*node_)) node();
1281         node_->init(node_);
1282         node_constructed_ = true;
1283     }
1284
1285     template <typename NodeAlloc>
1286     struct node_tmp
1287     {
1288         typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1289             node_allocator_traits;
1290         typedef typename node_allocator_traits::pointer node_pointer;
1291
1292         NodeAlloc& alloc_;
1293         node_pointer node_;
1294
1295         explicit node_tmp(node_pointer n, NodeAlloc& a):
1296             alloc_(a),
1297             node_(n)
1298         {
1299         }
1300
1301         ~node_tmp();
1302
1303         // no throw
1304         node_pointer release()
1305         {
1306             node_pointer p = node_;
1307             node_ = node_pointer();
1308             return p;
1309         }
1310     };
1311
1312     template <typename Alloc>
1313     node_tmp<Alloc>::~node_tmp()
1314     {
1315         if (node_) {
1316             boost::unordered::detail::func::call_destroy(alloc_,
1317                 node_->value_ptr());
1318             boost::unordered::detail::func::destroy(
1319                 boost::addressof(*node_));
1320             node_allocator_traits::deallocate(alloc_, node_, 1);
1321         }
1322     }
1323 }}}
1324
1325 namespace boost { namespace unordered { namespace detail { namespace func {
1326
1327     // Some nicer construct_node functions, might try to
1328     // improve implementation later.
1329
1330     template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE>
1331     inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1332     construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS)
1333     {
1334         node_constructor<Alloc> a(alloc);
1335         a.create_node();
1336         construct_from_args(alloc, a.node_->value_ptr(),
1337                 BOOST_UNORDERED_EMPLACE_FORWARD);
1338         return a.release();
1339     }
1340
1341     template <typename Alloc, typename U>
1342     inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1343     construct_node(Alloc& alloc, BOOST_FWD_REF(U) x)
1344     {
1345         node_constructor<Alloc> a(alloc);
1346         a.create_node();
1347         boost::unordered::detail::func::call_construct(
1348                 alloc, a.node_->value_ptr(), boost::forward<U>(x));
1349         return a.release();
1350     }
1351
1352     // TODO: When possible, it might be better to use std::pair's
1353     // constructor for std::piece_construct with std::tuple.
1354     template <typename Alloc, typename Key>
1355     inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1356     construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
1357     {
1358         node_constructor<Alloc> a(alloc);
1359         a.create_node();
1360         boost::unordered::detail::func::call_construct(alloc,
1361                 boost::unordered::detail::func::const_cast_pointer(
1362                     boost::addressof(a.node_->value_ptr()->first)),
1363                 boost::forward<Key>(k));
1364         boost::unordered::detail::func::call_construct(alloc,
1365                 boost::unordered::detail::func::const_cast_pointer(
1366                     boost::addressof(a.node_->value_ptr()->second)));
1367         return a.release();
1368     }
1369
1370     template <typename Alloc, typename Key, typename Mapped>
1371     inline typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1372     construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
1373     {
1374         node_constructor<Alloc> a(alloc);
1375         a.create_node();
1376         boost::unordered::detail::func::call_construct(alloc,
1377                 boost::unordered::detail::func::const_cast_pointer(
1378                     boost::addressof(a.node_->value_ptr()->first)),
1379                 boost::forward<Key>(k));
1380         boost::unordered::detail::func::call_construct(alloc,
1381                 boost::unordered::detail::func::const_cast_pointer(
1382                     boost::addressof(a.node_->value_ptr()->second)),
1383                 boost::forward<Mapped>(m));
1384         return a.release();
1385     }
1386 }}}}
1387
1388 #if defined(BOOST_MSVC)
1389 #pragma warning(pop)
1390 #endif
1391
1392 #endif