ceph/src/boost/boost/ptr_container/ptr_map_adapter.hpp

   1 //
   2 // Boost.Pointer Container
   3 //
   4 //  Copyright Thorsten Ottosen 2003-2005. Use, modification and
   5 //  distribution is subject to the Boost Software License, Version
   6 //  1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 //  http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // For more information, see http://www.boost.org/libs/ptr_container/
  10 //
  11
  12 #ifndef BOOST_PTR_CONTAINER_DETAIL_PTR_MAP_ADAPTER_HPP
  13 #define BOOST_PTR_CONTAINER_DETAIL_PTR_MAP_ADAPTER_HPP
  14
  15 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
  16 # pragma once
  17 #endif
  18
  19 #include <boost/ptr_container/detail/map_iterator.hpp>
  20 #include <boost/ptr_container/detail/associative_ptr_container.hpp>
  21 #include <boost/ptr_container/detail/meta_functions.hpp>
  22 #include <boost/static_assert.hpp>
  23 #include <boost/range/iterator_range.hpp>
  24
  25 namespace boost
  26 {
  27 namespace ptr_container_detail
  28 {
  29
  30     template
  31     <
  32         class T,
  33         class VoidPtrMap,
  34         bool  Ordered
  35     >
  36     struct map_config
  37     {
  38         typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type
  39                      U;
  40         typedef VoidPtrMap
  41                      void_container_type;
  42
  43         typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::allocator_type
  44                      allocator_type;
  45
  46        typedef BOOST_DEDUCED_TYPENAME
  47            mpl::eval_if_c<Ordered,
  48                           select_value_compare<VoidPtrMap>,
  49                           mpl::identity<void> >::type
  50                     value_compare;
  51
  52        typedef BOOST_DEDUCED_TYPENAME
  53            mpl::eval_if_c<Ordered,
  54                           select_key_compare<VoidPtrMap>,
  55                           mpl::identity<void> >::type
  56                     key_compare;
  57
  58        typedef BOOST_DEDUCED_TYPENAME
  59            mpl::eval_if_c<Ordered,
  60                           mpl::identity<void>,
  61                           select_hasher<VoidPtrMap> >::type
  62                     hasher;
  63
  64        typedef BOOST_DEDUCED_TYPENAME
  65            mpl::eval_if_c<Ordered,
  66                           mpl::identity<void>,
  67                           select_key_equal<VoidPtrMap> >::type
  68                     key_equal;
  69
  70        typedef BOOST_DEDUCED_TYPENAME
  71            mpl::if_c<Ordered,
  72                      ptr_container_detail::ordered_associative_container_tag,
  73                      ptr_container_detail::unordered_associative_container_tag>::type
  74                     container_type;
  75
  76         typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type
  77                      key_type;
  78
  79         typedef U    value_type;
  80
  81         typedef ptr_map_iterator< BOOST_DEDUCED_TYPENAME VoidPtrMap::iterator, key_type, U* const >
  82                      iterator;
  83
  84         typedef ptr_map_iterator< BOOST_DEDUCED_TYPENAME VoidPtrMap::const_iterator, key_type, const U* const>
  85                      const_iterator;
  86
  87         typedef ptr_map_iterator<
  88            BOOST_DEDUCED_TYPENAME
  89              mpl::eval_if_c<Ordered,
  90                             select_iterator<VoidPtrMap>,
  91                             select_local_iterator<VoidPtrMap> >::type,
  92              key_type, U* const >
  93                     local_iterator;
  94
  95        typedef ptr_map_iterator<
  96            BOOST_DEDUCED_TYPENAME
  97              mpl::eval_if_c<Ordered,
  98                             select_iterator<VoidPtrMap>,
  99                             select_const_local_iterator<VoidPtrMap> >::type,
 100              key_type, const U* const >
 101                     const_local_iterator;
 102
 103         template< class Iter >
 104         static U* get_pointer( Iter i )
 105         {
 106             return i->second;
 107         }
 108
 109         template< class Iter >
 110         static const U* get_const_pointer( Iter i )
 111         {
 112             return i->second;
 113         }
 114
 115         BOOST_STATIC_CONSTANT( bool, allow_null = boost::is_nullable<T>::value );
 116     };
 117
 118
 119
 120     template
 121     <
 122         class T,
 123         class VoidPtrMap,
 124         class CloneAllocator,
 125         bool  Ordered
 126     >
 127     class ptr_map_adapter_base :
 128         public ptr_container_detail::associative_ptr_container< map_config<T,VoidPtrMap,Ordered>,
 129                                                     CloneAllocator >
 130     {
 131         typedef ptr_container_detail::associative_ptr_container< map_config<T,VoidPtrMap,Ordered>,
 132                                                      CloneAllocator >
 133             base_type;
 134
 135         typedef map_config<T,VoidPtrMap,Ordered>                           config;
 136         typedef ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator,Ordered>  this_type;
 137
 138     public:
 139
 140         typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type
 141                     allocator_type;
 142         typedef BOOST_DEDUCED_TYPENAME base_type::iterator
 143                     iterator;
 144         typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
 145                     const_iterator;
 146         typedef BOOST_DEDUCED_TYPENAME base_type::size_type
 147                     size_type;
 148         typedef BOOST_DEDUCED_TYPENAME base_type::key_type
 149                     key_type;
 150         typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
 151                     auto_type;
 152         typedef BOOST_DEDUCED_TYPENAME base_type::value_type
 153                     mapped_type;
 154         typedef BOOST_DEDUCED_TYPENAME base_type::reference
 155                     mapped_reference;
 156         typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
 157                     const_mapped_reference;
 158         typedef BOOST_DEDUCED_TYPENAME iterator_value<iterator>::type
 159                     value_type;
 160         typedef value_type
 161                     reference;
 162         typedef BOOST_DEDUCED_TYPENAME iterator_value<const_iterator>::type
 163                     const_reference;
 164         typedef value_type
 165                     pointer;
 166         typedef const_reference
 167                     const_pointer;
 168
 169     private:
 170         const_mapped_reference lookup( const key_type& key ) const
 171         {
 172            const_iterator i = this->find( key );
 173            BOOST_PTR_CONTAINER_THROW_EXCEPTION( i == this->end(), bad_ptr_container_operation,
 174                                                 "'ptr_map/multimap::at()' could"
 175                                                 " not find key" );
 176            return *i->second;
 177         }
 178
 179         struct eraser // scope guard
 180         {
 181             bool            released_;
 182             VoidPtrMap*     m_;
 183             const key_type& key_;
 184
 185             eraser( VoidPtrMap* m, const key_type& key )
 186               : released_(false), m_(m), key_(key)
 187             {}
 188
 189             ~eraser()
 190             {
 191                 if( !released_ )
 192                     m_->erase(key_);
 193             }
 194
 195             void release() { released_ = true; }
 196
 197         private:
 198             eraser& operator=(const eraser&);
 199         };
 200
 201         mapped_reference insert_lookup( const key_type& key )
 202         {
 203             void*& ref = this->base()[key];
 204             if( ref )
 205             {
 206                 return *static_cast<mapped_type>(ref);
 207             }
 208             else
 209             {
 210                 eraser e(&this->base(),key);      // nothrow
 211                 mapped_type res = new T();        // strong
 212                 ref = res;                        // nothrow
 213                 e.release();                      // nothrow
 214                 return *res;
 215             }
 216           }
 217
 218     public:
 219
 220         ptr_map_adapter_base()
 221         { }
 222
 223         template< class SizeType >
 224         explicit ptr_map_adapter_base( SizeType n,
 225                                        ptr_container_detail::unordered_associative_container_tag tag )
 226         : base_type( n, tag )
 227         { }
 228
 229         template< class Compare, class Allocator >
 230         ptr_map_adapter_base( const Compare& comp,
 231                               const Allocator& a )
 232         : base_type( comp, a )
 233         { }
 234
 235         template< class Hash, class Pred, class Allocator >
 236         ptr_map_adapter_base( const Hash& hash,
 237                               const Pred& pred,
 238                               const Allocator& a )
 239          : base_type( hash, pred, a )
 240         { }
 241
 242         template< class InputIterator >
 243         ptr_map_adapter_base( InputIterator first, InputIterator last )
 244          : base_type( first, last )
 245         { }
 246
 247         template< class InputIterator, class Comp >
 248         ptr_map_adapter_base( InputIterator first, InputIterator last,
 249                               const Comp& comp,
 250                               const allocator_type& a = allocator_type() )
 251         : base_type( first, last, comp, a )
 252         { }
 253
 254         template< class InputIterator, class Hash, class Pred, class Allocator >
 255         ptr_map_adapter_base( InputIterator first, InputIterator last,
 256                               const Hash& hash,
 257                               const Pred& pred,
 258                               const Allocator& a )
 259          : base_type( first, last, hash, pred, a )
 260         { }
 261
 262         template< class PtrContainer >
 263         explicit ptr_map_adapter_base( std::auto_ptr<PtrContainer> clone )
 264         : base_type( clone )
 265         { }
 266
 267         template< typename PtrContainer >
 268         ptr_map_adapter_base& operator=( std::auto_ptr<PtrContainer> clone )
 269         {
 270             base_type::operator=( clone );
 271             return *this;
 272         }
 273
 274         iterator find( const key_type& x )
 275         {
 276             return iterator( this->base().find( x ) );
 277         }
 278
 279         const_iterator find( const key_type& x ) const
 280         {
 281             return const_iterator( this->base().find( x ) );
 282         }
 283
 284         size_type count( const key_type& x ) const
 285         {
 286             return this->base().count( x );
 287         }
 288
 289         iterator lower_bound( const key_type& x )
 290         {
 291             return iterator( this->base().lower_bound( x ) );
 292         }
 293
 294         const_iterator lower_bound( const key_type& x ) const
 295         {
 296             return const_iterator( this->base().lower_bound( x ) );
 297         }
 298
 299         iterator upper_bound( const key_type& x )
 300         {
 301             return iterator( this->base().upper_bound( x ) );
 302         }
 303
 304         const_iterator upper_bound( const key_type& x ) const
 305         {
 306             return const_iterator( this->base().upper_bound( x ) );
 307         }
 308
 309         iterator_range<iterator> equal_range( const key_type& x )
 310         {
 311             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,
 312                       BOOST_DEDUCED_TYPENAME base_type::ptr_iterator>
 313                  p = this->base().equal_range( x );
 314             return make_iterator_range( iterator( p.first ), iterator( p.second ) );
 315         }
 316
 317         iterator_range<const_iterator> equal_range( const key_type& x ) const
 318         {
 319             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator,
 320                       BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator>
 321                 p = this->base().equal_range( x );
 322             return make_iterator_range( const_iterator( p.first ),
 323                                         const_iterator( p.second ) );
 324         }
 325
 326         mapped_reference at( const key_type& key )
 327         {
 328             return const_cast<mapped_reference>( lookup( key ) );
 329         }
 330
 331         const_mapped_reference at( const key_type& key ) const
 332         {
 333             return lookup( key );
 334         }
 335
 336         mapped_reference operator[]( const key_type& key )
 337         {
 338             return insert_lookup( key );
 339         }
 340
 341         auto_type replace( iterator where, mapped_type x ) // strong
 342         {
 343             BOOST_ASSERT( where != this->end() );
 344             this->enforce_null_policy( x, "Null pointer in 'replace()'" );
 345
 346             auto_type ptr( x, *this );
 347             BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(),
 348                                                  bad_ptr_container_operation,
 349                                                  "'replace()' on empty container" );
 350
 351             auto_type old( where->second, *this ); // nothrow
 352             where.base()->second = ptr.release();  // nothrow, commit
 353             return boost::ptr_container::move( old );
 354         }
 355
 356         template< class U >
 357         auto_type replace( iterator where, std::auto_ptr<U> x )
 358         {
 359             return replace( where, x.release() );
 360         }
 361
 362     protected:
 363         size_type bucket( const key_type& key ) const
 364         {
 365             return this->base().bucket( key );
 366         }
 367     };
 368
 369 } // ptr_container_detail
 370
 371     /////////////////////////////////////////////////////////////////////////
 372     // ptr_map_adapter
 373     /////////////////////////////////////////////////////////////////////////
 374
 375     template
 376     <
 377         class T,
 378         class VoidPtrMap,
 379         class CloneAllocator = heap_clone_allocator,
 380         bool  Ordered        = true
 381     >
 382     class ptr_map_adapter :
 383         public ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator,Ordered>
 384     {
 385         typedef ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator,Ordered>
 386             base_type;
 387
 388     public:
 389         typedef BOOST_DEDUCED_TYPENAME base_type::iterator
 390                      iterator;
 391         typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
 392                      const_iterator;
 393         typedef BOOST_DEDUCED_TYPENAME base_type::size_type
 394                     size_type;
 395         typedef BOOST_DEDUCED_TYPENAME base_type::key_type
 396                     key_type;
 397         typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
 398                     const_reference;
 399         typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
 400                     auto_type;
 401         typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::allocator_type
 402                     allocator_type;
 403         typedef BOOST_DEDUCED_TYPENAME base_type::mapped_type
 404                     mapped_type;
 405     private:
 406
 407         void safe_insert( const key_type& key, auto_type ptr ) // strong
 408         {
 409             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool>
 410                 res =
 411                 this->base().insert( std::make_pair( key, ptr.get() ) ); // strong, commit
 412             if( res.second )                                             // nothrow
 413                 ptr.release();                                           // nothrow
 414         }
 415
 416         template< class II >
 417         void map_basic_clone_and_insert( II first, II last )
 418         {
 419             while( first != last )
 420             {
 421                 if( this->find( first->first ) == this->end() )
 422                 {
 423                     const_reference p = *first.base();     // nothrow
 424                     auto_type ptr( this->null_policy_allocate_clone(p.second), *this );
 425                                                            // strong
 426                     this->safe_insert( p.first,
 427                                        boost::ptr_container::move( ptr ) );
 428                                                            // strong, commit
 429                 }
 430                 ++first;
 431             }
 432         }
 433
 434     public:
 435         ptr_map_adapter( )
 436         { }
 437
 438         template< class Comp >
 439         explicit ptr_map_adapter( const Comp& comp,
 440                                   const allocator_type& a )
 441           : base_type( comp, a ) { }
 442
 443         template< class SizeType >
 444         explicit ptr_map_adapter( SizeType n,
 445             ptr_container_detail::unordered_associative_container_tag tag )
 446           : base_type( n, tag ) { }
 447
 448         template< class Hash, class Pred, class Allocator >
 449         ptr_map_adapter( const Hash& hash,
 450                          const Pred& pred,
 451                          const Allocator& a )
 452          : base_type( hash, pred, a )
 453         { }
 454
 455         template< class InputIterator >
 456         ptr_map_adapter( InputIterator first, InputIterator last )
 457         {
 458             map_basic_clone_and_insert( first, last );
 459         }
 460
 461         template< class InputIterator, class Comp >
 462         ptr_map_adapter( InputIterator first, InputIterator last,
 463                          const Comp& comp,
 464                          const allocator_type& a = allocator_type() )
 465           : base_type( comp, a )
 466         {
 467             map_basic_clone_and_insert( first, last );
 468         }
 469
 470         template< class InputIterator, class Hash, class Pred, class Allocator >
 471         ptr_map_adapter( InputIterator first, InputIterator last,
 472                          const Hash& hash,
 473                          const Pred& pred,
 474                          const Allocator& a )
 475           : base_type( hash, pred, a )
 476         {
 477             map_basic_clone_and_insert( first, last );
 478         }
 479
 480         ptr_map_adapter( const ptr_map_adapter& r )
 481         {
 482             map_basic_clone_and_insert( r.begin(), r.end() );
 483         }
 484
 485         template< class Key, class U, class CA, bool b >
 486         ptr_map_adapter( const ptr_map_adapter<Key,U,CA,b>& r )
 487         {
 488             map_basic_clone_and_insert( r.begin(), r.end() );
 489         }
 490
 491         template< class U >
 492         ptr_map_adapter( std::auto_ptr<U> r ) : base_type( r )
 493         { }
 494
 495         ptr_map_adapter& operator=( ptr_map_adapter r )
 496         {
 497             this->swap( r );
 498             return *this;
 499         }
 500
 501         template< class U >
 502         ptr_map_adapter& operator=( std::auto_ptr<U> r )
 503         {
 504             base_type::operator=( r );
 505             return *this;
 506         }
 507
 508         using base_type::release;
 509
 510         template< typename InputIterator >
 511         void insert( InputIterator first, InputIterator last ) // basic
 512         {
 513             map_basic_clone_and_insert( first, last );
 514         }
 515
 516         template< class Range >
 517         void insert( const Range& r )
 518         {
 519             insert( boost::begin(r), boost::end(r) );
 520         }
 521
 522     private:
 523         std::pair<iterator,bool> insert_impl( const key_type& key, mapped_type x ) // strong
 524         {
 525             this->enforce_null_policy( x, "Null pointer in ptr_map_adapter::insert()" );
 526
 527             auto_type ptr( x, *this );                                  // nothrow
 528             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool>
 529                  res = this->base().insert( std::make_pair( key, x ) ); // strong, commit
 530             if( res.second )                                            // nothrow
 531                 ptr.release();                                          // nothrow
 532             return std::make_pair( iterator( res.first ), res.second ); // nothrow
 533         }
 534
 535         iterator insert_impl( iterator before, const key_type& key, mapped_type x ) // strong
 536         {
 537             this->enforce_null_policy( x,
 538                   "Null pointer in 'ptr_map_adapter::insert()'" );
 539
 540             auto_type ptr( x, *this );  // nothrow
 541             BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
 542                 res = this->base().insert( before.base(), std::make_pair( key, x ) );
 543                                         // strong, commit
 544             ptr.release();              // notrow
 545             return iterator( res );
 546         }
 547
 548     public:
 549
 550         std::pair<iterator,bool> insert( key_type& key, mapped_type x )
 551         {
 552             return insert_impl( key, x );
 553         }
 554
 555         template< class U >
 556         std::pair<iterator,bool> insert( const key_type& key, std::auto_ptr<U> x )
 557         {
 558             return insert_impl( key, x.release() );
 559         }
 560
 561         template< class F, class S >
 562         iterator insert( iterator before, ptr_container_detail::ref_pair<F,S> p ) // strong
 563         {
 564             this->enforce_null_policy( p.second,
 565                   "Null pointer in 'ptr_map_adapter::insert()'" );
 566
 567             auto_type ptr( this->null_policy_allocate_clone(p.second), *this );
 568             BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
 569                 result = this->base().insert( before.base(),
 570                                      std::make_pair(p.first,ptr.get()) ); // strong
 571             if( ptr.get() == result->second )
 572                 ptr.release();
 573
 574             return iterator( result );
 575         }
 576
 577         iterator insert( iterator before, key_type& key, mapped_type x ) // strong
 578         {
 579             return insert_impl( before, key, x );
 580         }
 581
 582         template< class U >
 583         iterator insert( iterator before, const key_type& key, std::auto_ptr<U> x ) // strong
 584         {
 585             return insert_impl( before, key, x.release() );
 586         }
 587
 588         template< class PtrMapAdapter >
 589         bool transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator object,
 590                        PtrMapAdapter& from ) // strong
 591         {
 592             return this->single_transfer( object, from );
 593         }
 594
 595         template< class PtrMapAdapter >
 596         size_type transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator first,
 597                             BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator last,
 598                             PtrMapAdapter& from ) // basic
 599         {
 600             return this->single_transfer( first, last, from );
 601         }
 602
 603 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 604 #else
 605
 606         template< class PtrMapAdapter, class Range >
 607         BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
 608                             BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator >,
 609                                                             size_type >::type
 610         transfer( const Range& r, PtrMapAdapter& from ) // basic
 611         {
 612             return transfer( boost::begin(r), boost::end(r), from );
 613         }
 614
 615 #endif
 616
 617         template< class PtrMapAdapter >
 618         size_type transfer( PtrMapAdapter& from ) // basic
 619         {
 620             return transfer( from.begin(), from.end(), from );
 621         }
 622   };
 623
 624   /////////////////////////////////////////////////////////////////////////
 625   // ptr_multimap_adapter
 626   /////////////////////////////////////////////////////////////////////////
 627
 628     template
 629     <
 630         class T,
 631         class VoidPtrMultiMap,
 632         class CloneAllocator = heap_clone_allocator,
 633         bool  Ordered        = true
 634     >
 635     class ptr_multimap_adapter :
 636         public ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMultiMap,CloneAllocator,Ordered>
 637     {
 638         typedef ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMultiMap,CloneAllocator,Ordered>
 639              base_type;
 640
 641     public: // typedefs
 642         typedef BOOST_DEDUCED_TYPENAME base_type::iterator
 643                        iterator;
 644         typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
 645                        const_iterator;
 646         typedef BOOST_DEDUCED_TYPENAME base_type::size_type
 647                        size_type;
 648         typedef BOOST_DEDUCED_TYPENAME base_type::key_type
 649                        key_type;
 650         typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
 651                        const_reference;
 652         typedef BOOST_DEDUCED_TYPENAME base_type::mapped_type
 653                     mapped_type;
 654         typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
 655                     auto_type;
 656         typedef BOOST_DEDUCED_TYPENAME VoidPtrMultiMap::allocator_type
 657                     allocator_type;
 658     private:
 659
 660         void safe_insert( const key_type& key, auto_type ptr ) // strong
 661         {
 662             this->base().insert(
 663                            std::make_pair( key, ptr.get() ) ); // strong, commit
 664             ptr.release();                                     // nothrow
 665         }
 666
 667         template< typename II >
 668         void map_basic_clone_and_insert( II first, II last )
 669         {
 670             while( first != last )
 671             {
 672                 const_reference pair = *first.base();     // nothrow
 673                 auto_type ptr( this->null_policy_allocate_clone(pair.second), *this );
 674                                                           // strong
 675                 safe_insert( pair.first,
 676                              boost::ptr_container::move( ptr ) );
 677                                                           // strong, commit
 678                 ++first;
 679             }
 680         }
 681
 682     public:
 683
 684         ptr_multimap_adapter()
 685         { }
 686
 687         template< class SizeType >
 688         ptr_multimap_adapter( SizeType n,
 689                               ptr_container_detail::unordered_associative_container_tag tag )
 690           : base_type( n, tag )
 691         { }
 692
 693         template< class Comp >
 694         explicit ptr_multimap_adapter( const Comp& comp,
 695                                        const allocator_type& a )
 696           : base_type( comp, a ) { }
 697
 698         template< class Hash, class Pred, class Allocator >
 699         ptr_multimap_adapter( const Hash& hash,
 700                               const Pred& pred,
 701                               const Allocator& a )
 702          : base_type( hash, pred, a )
 703         { }
 704
 705         template< class InputIterator >
 706         ptr_multimap_adapter( InputIterator first, InputIterator last )
 707         {
 708             map_basic_clone_and_insert( first, last );
 709         }
 710
 711         template< class InputIterator, class Comp >
 712         ptr_multimap_adapter( InputIterator first, InputIterator last,
 713                               const Comp& comp,
 714                               const allocator_type& a )
 715           : base_type( comp, a )
 716         {
 717             map_basic_clone_and_insert( first, last );
 718         }
 719
 720         template< class InputIterator, class Hash, class Pred, class Allocator >
 721         ptr_multimap_adapter( InputIterator first, InputIterator last,
 722                               const Hash& hash,
 723                               const Pred& pred,
 724                               const Allocator& a )
 725          : base_type( hash, pred, a )
 726         {
 727             map_basic_clone_and_insert( first, last );
 728         }
 729
 730         ptr_multimap_adapter( const ptr_multimap_adapter& r )
 731         {
 732             map_basic_clone_and_insert( r.begin(), r.end() );
 733         }
 734
 735         template< class Key, class U, class CA, bool b >
 736         ptr_multimap_adapter( const ptr_multimap_adapter<Key,U,CA,b>& r )
 737         {
 738             map_basic_clone_and_insert( r.begin(), r.end() );
 739         }
 740
 741         template< class U >
 742         explicit ptr_multimap_adapter( std::auto_ptr<U> r ) : base_type( r )
 743         { }
 744
 745         ptr_multimap_adapter& operator=( ptr_multimap_adapter r )
 746         {
 747             this->swap( r );
 748             return *this;
 749         }
 750
 751         template< class U >
 752         ptr_multimap_adapter& operator=( std::auto_ptr<U> r )
 753         {
 754             base_type::operator=( r );
 755             return *this;
 756         }
 757
 758         using base_type::release;
 759
 760     private:
 761         iterator insert_impl( const key_type& key, mapped_type x ) // strong
 762         {
 763             this->enforce_null_policy( x,
 764                   "Null pointer in 'ptr_multimap_adapter::insert()'" );
 765
 766             auto_type ptr( x, *this );  // nothrow
 767             BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
 768                 res = this->base().insert( std::make_pair( key, x ) );
 769                                         // strong, commit
 770             ptr.release();              // notrow
 771             return iterator( res );
 772         }
 773
 774         iterator insert_impl( iterator before, const key_type& key, mapped_type x ) // strong
 775         {
 776             this->enforce_null_policy( x,
 777                   "Null pointer in 'ptr_multimap_adapter::insert()'" );
 778
 779             auto_type ptr( x, *this );  // nothrow
 780             BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
 781                 res = this->base().insert( before.base(),
 782                                            std::make_pair( key, x ) );
 783                                         // strong, commit
 784             ptr.release();              // notrow
 785             return iterator( res );
 786         }
 787
 788     public:
 789         template< typename InputIterator >
 790         void insert( InputIterator first, InputIterator last ) // basic
 791         {
 792             map_basic_clone_and_insert( first, last );
 793         }
 794
 795         template< class Range >
 796         void insert( const Range& r )
 797         {
 798             insert( boost::begin(r), boost::end(r) );
 799         }
 800
 801         iterator insert( key_type& key, mapped_type x ) // strong
 802         {
 803             return insert_impl( key, x );
 804         }
 805
 806         template< class U >
 807         iterator insert( const key_type& key, std::auto_ptr<U> x )
 808         {
 809             return insert_impl( key, x.release() );
 810         }
 811
 812         template< class F, class S >
 813         iterator insert( iterator before, ptr_container_detail::ref_pair<F,S> p ) // strong
 814         {
 815             this->enforce_null_policy( p.second,
 816                   "Null pointer in 'ptr_multimap_adapter::insert()'" );
 817             iterator res = insert_impl( before, p.first,
 818                                         this->null_policy_allocate_clone( p.second ) );
 819             return res;
 820         }
 821
 822         iterator insert( iterator before, key_type& key, mapped_type x ) // strong
 823         {
 824             return insert_impl( before, key, x );
 825         }
 826
 827         template< class U >
 828         iterator insert( iterator before, const key_type& key, std::auto_ptr<U> x ) // strong
 829         {
 830             return insert_impl( before, key, x.release() );
 831         }
 832
 833         template< class PtrMapAdapter >
 834         void transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator object,
 835                        PtrMapAdapter& from ) // strong
 836         {
 837             this->multi_transfer( object, from );
 838         }
 839
 840         template< class PtrMapAdapter >
 841         size_type transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator first,
 842                             BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator last,
 843                             PtrMapAdapter& from ) // basic
 844         {
 845             return this->multi_transfer( first, last, from );
 846         }
 847
 848 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 849 #else
 850
 851         template<  class PtrMapAdapter, class Range >
 852         BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
 853                             BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator >,
 854                                                             size_type >::type
 855         transfer( const Range& r, PtrMapAdapter& from ) // basic
 856         {
 857             return transfer( boost::begin(r), boost::end(r), from );
 858         }
 859
 860 #endif
 861         template< class PtrMapAdapter >
 862         void transfer( PtrMapAdapter& from ) // basic
 863         {
 864             transfer( from.begin(), from.end(), from );
 865             BOOST_ASSERT( from.empty() );
 866         }
 867
 868     };
 869
 870     template< class I, class F, class S >
 871     inline bool is_null( const ptr_map_iterator<I,F,S>& i )
 872     {
 873         return i->second == 0;
 874     }
 875
 876 } // namespace 'boost'
 877
 878 #endif