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/static_assert.hpp> 22 #include <boost/range/iterator_range.hpp> 23 24 namespace boost 25 { 26 namespace ptr_container_detail 27 { 28 29 template 30 < 31 class T, 32 class VoidPtrMap 33 > 34 struct map_config 35 { 36 typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type 37 U; 38 typedef VoidPtrMap 39 void_container_type; 40 41 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::allocator_type 42 allocator_type; 43 44 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::key_compare 45 key_compare; 46 47 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::value_compare 48 value_compare; 49 50 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type 51 key_type; 52 53 typedef U value_type; 54 55 typedef ptr_map_iterator< 56 BOOST_DEDUCED_TYPENAME VoidPtrMap::iterator, 57 BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type, value_type> 58 iterator; 59 60 typedef 61 ptr_map_iterator< 62 BOOST_DEDUCED_TYPENAME VoidPtrMap::const_iterator, 63 BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type, 64 const value_type> 65 const_iterator; 66 67 typedef 68 ptr_map_iterator< 69 BOOST_DEDUCED_TYPENAME VoidPtrMap::reverse_iterator, 70 BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type, value_type> 71 reverse_iterator; 72 73 typedef 74 ptr_map_iterator< 75 BOOST_DEDUCED_TYPENAME VoidPtrMap::const_reverse_iterator, 76 BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type, 77 const value_type> 78 const_reverse_iterator; 79 80 typedef std::pair<const key_type, void*> 81 object_type; 82 83 template< class Iter > get_pointerboost::ptr_container_detail::map_config84 static U* get_pointer( Iter i ) 85 { 86 return static_cast<U*>( i.base()->second ); 87 } 88 89 template< class Iter > get_const_pointerboost::ptr_container_detail::map_config90 static const U* get_const_pointer( Iter i ) 91 { 92 return static_cast<const U*>( i.base()->second ); 93 } 94 95 BOOST_STATIC_CONSTANT( bool, allow_null = boost::is_nullable<T>::value ); 96 }; 97 98 99 100 template 101 < 102 class T, 103 class VoidPtrMap, 104 class CloneAllocator 105 > 106 class ptr_map_adapter_base : 107 public ptr_container_detail::associative_ptr_container< map_config<T,VoidPtrMap>, 108 CloneAllocator > 109 { 110 typedef ptr_container_detail::associative_ptr_container< map_config<T,VoidPtrMap>, 111 CloneAllocator > 112 base_type; 113 114 typedef ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator> this_type; 115 116 public: 117 118 typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator 119 const_iterator; 120 typedef BOOST_DEDUCED_TYPENAME base_type::key_type 121 key_type; 122 typedef BOOST_DEDUCED_TYPENAME base_type::reference 123 reference; 124 typedef BOOST_DEDUCED_TYPENAME base_type::value_type 125 value_type; 126 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type 127 auto_type; 128 129 private: lookup(const key_type & key) const130 reference lookup( const key_type& key ) const 131 { 132 iterator i = const_cast<ptr_map_adapter_base*>(this) 133 ->find( key ); 134 if( i != const_cast<ptr_map_adapter_base*>(this)->end() ) 135 return *i; 136 else 137 throw bad_ptr_container_operation( "'ptr_map/multimap::at()' could" 138 " not find key" ); 139 } 140 141 struct eraser // scope guard 142 { 143 bool released_; 144 VoidPtrMap* m_; 145 const key_type& key_; 146 eraserboost::ptr_container_detail::ptr_map_adapter_base::eraser147 eraser( VoidPtrMap* m, const key_type& key ) 148 : released_(false), m_(m), key_(key) 149 {} 150 ~eraserboost::ptr_container_detail::ptr_map_adapter_base::eraser151 ~eraser() 152 { 153 if( !released_ ) 154 m_->erase(key_); 155 } 156 releaseboost::ptr_container_detail::ptr_map_adapter_base::eraser157 void release() { released_ = true; } 158 }; 159 insert_lookup(const key_type & key)160 reference insert_lookup( const key_type& key ) 161 { 162 void*& ref = this->c_private()[key]; 163 if( ref ) 164 { 165 value_type v = static_cast<value_type>( ref ); 166 return *v; 167 } 168 else 169 { 170 eraser e(&this->c_private(),key); // nothrow 171 value_type res = new T(); // strong 172 ref = res; // nothrow 173 e.release(); // nothrow 174 return *res; 175 } 176 } 177 178 public: 179 180 BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( ptr_map_adapter_base, 181 base_type ); 182 183 template< class Compare, class Allocator > ptr_map_adapter_base(const Compare & comp,const Allocator & a)184 explicit ptr_map_adapter_base( const Compare& comp, 185 const Allocator& a ) 186 : base_type( comp, a ) 187 { } 188 189 template< class PtrContainer > ptr_map_adapter_base(std::auto_ptr<PtrContainer> clone)190 ptr_map_adapter_base( std::auto_ptr<PtrContainer> clone ) 191 : base_type( clone ) 192 { } 193 194 template< typename PtrContainer > operator =(std::auto_ptr<PtrContainer> clone)195 void operator=( std::auto_ptr<PtrContainer> clone ) 196 { 197 base_type::operator=( clone ); 198 } 199 find(const key_type & x)200 iterator find( const key_type& x ) 201 { 202 return iterator( this->c_private().find( x ) ); 203 } 204 find(const key_type & x) const205 const_iterator find( const key_type& x ) const 206 { 207 return const_iterator( this->c_private().find( x ) ); 208 } 209 count(const key_type & x) const210 size_type count( const key_type& x ) const 211 { 212 return this->c_private().count( x ); 213 } 214 lower_bound(const key_type & x)215 iterator lower_bound( const key_type& x ) 216 { 217 return iterator( this->c_private().lower_bound( x ) ); 218 } 219 lower_bound(const key_type & x) const220 const_iterator lower_bound( const key_type& x ) const 221 { 222 return const_iterator( this->c_private().lower_bound( x ) ); 223 } 224 upper_bound(const key_type & x)225 iterator upper_bound( const key_type& x ) 226 { 227 return iterator( this->c_private().upper_bound( x ) ); 228 } 229 upper_bound(const key_type & x) const230 const_iterator upper_bound( const key_type& x ) const 231 { 232 return const_iterator( this->c_private().upper_bound( x ) ); 233 } 234 equal_range(const key_type & x)235 iterator_range<iterator> equal_range( const key_type& x ) 236 { 237 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator, 238 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator> 239 p = this->c_private().equal_range( x ); 240 return make_iterator_range( iterator( p.first ), iterator( p.second ) ); 241 } 242 equal_range(const key_type & x) const243 iterator_range<const_iterator> equal_range( const key_type& x ) const 244 { 245 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator, 246 BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator> 247 p = this->c_private().equal_range( x ); 248 return make_iterator_range( const_iterator( p.first ), const_iterator( p.second ) ); 249 } 250 at(const key_type & key)251 reference at( const key_type& key ) 252 { 253 return lookup( key ); 254 } 255 at(const key_type & key) const256 const_reference at( const key_type& key ) const 257 { 258 return lookup( key ); 259 } 260 operator [](const key_type & key)261 reference operator[]( const key_type& key ) 262 { 263 return insert_lookup( key ); 264 } 265 replace(iterator where,value_type x)266 auto_type replace( iterator where, value_type x ) // strong 267 { 268 BOOST_ASSERT( where != this->end() ); 269 270 this->enforce_null_policy( x, "Null pointer in 'replace()'" ); 271 272 auto_type ptr( x ); 273 274 if( this->empty() ) 275 throw bad_ptr_container_operation( "'replace()' on empty container" ); 276 277 auto_type old( &*where ); // nothrow 278 where.base()->second = ptr.release(); // nothrow, commit 279 return move( old ); 280 } 281 282 }; 283 284 } // ptr_container_detail 285 286 ///////////////////////////////////////////////////////////////////////// 287 // ptr_map_adapter 288 ///////////////////////////////////////////////////////////////////////// 289 290 template 291 < 292 class T, 293 class VoidPtrMap, 294 class CloneAllocator = heap_clone_allocator 295 > 296 class ptr_map_adapter : 297 public ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator> 298 { 299 typedef ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator> 300 base_type; 301 302 public: 303 typedef BOOST_DEDUCED_TYPENAME base_type::iterator 304 iterator; 305 typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator 306 const_iterator; 307 typedef BOOST_DEDUCED_TYPENAME base_type::object_type 308 object_type; 309 typedef BOOST_DEDUCED_TYPENAME base_type::size_type 310 size_type; 311 typedef BOOST_DEDUCED_TYPENAME base_type::key_type 312 key_type; 313 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference 314 const_reference; 315 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type 316 auto_type; 317 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::key_compare 318 key_compare; 319 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::allocator_type 320 allocator_type; 321 typedef BOOST_DEDUCED_TYPENAME base_type::value_type 322 value_type; 323 private: 324 safe_insert(const key_type & key,auto_type ptr)325 void safe_insert( const key_type& key, auto_type ptr ) // strong 326 { 327 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool> 328 res = 329 this->c_private().insert( std::make_pair( key, ptr.get() ) ); // strong, commit 330 if( res.second ) // nothrow 331 ptr.release(); // nothrow 332 } 333 334 template< class II > map_basic_clone_and_insert(II first,II last)335 void map_basic_clone_and_insert( II first, II last ) 336 { 337 while( first != last ) 338 { 339 if( this->find( first.key() ) == this->end() ) 340 { 341 const object_type& p = *first.base(); // nothrow 342 auto_type ptr( this->null_policy_allocate_clone( 343 static_cast<value_type>(p.second) ) ); 344 // strong 345 this->safe_insert( p.first, ptr_container_detail:: 346 move( ptr ) );// strong, commit 347 } 348 ++first; 349 } 350 } 351 352 public: 353 ptr_map_adapter(const key_compare & comp=key_compare (),const allocator_type & a=allocator_type ())354 explicit ptr_map_adapter( const key_compare& comp = key_compare(), 355 const allocator_type& a = allocator_type() ) 356 : base_type( comp, a ) { } 357 358 template< class InputIterator > ptr_map_adapter(InputIterator first,InputIterator last,const key_compare & comp=key_compare (),const allocator_type & a=allocator_type ())359 ptr_map_adapter( InputIterator first, InputIterator last, 360 const key_compare& comp = key_compare(), 361 const allocator_type& a = allocator_type() ) 362 : base_type( comp, a ) 363 { 364 map_basic_clone_and_insert( first, last ); 365 } 366 367 template< class U > ptr_map_adapter(std::auto_ptr<U> r)368 ptr_map_adapter( std::auto_ptr<U> r ) : base_type( r ) 369 { } 370 371 template< class U > operator =(std::auto_ptr<U> r)372 void operator=( std::auto_ptr<U> r ) 373 { 374 base_type::operator=( r ); 375 } 376 377 using base_type::release; 378 379 template< typename InputIterator > insert(InputIterator first,InputIterator last)380 void insert( InputIterator first, InputIterator last ) // basic 381 { 382 map_basic_clone_and_insert( first, last ); 383 } 384 385 template< class Range > insert(const Range & r)386 void insert( const Range& r ) 387 { 388 insert( this->adl_begin(r), this->adl_end(r) ); 389 } 390 insert(key_type & key,value_type x)391 std::pair<iterator,bool> insert( key_type& key, value_type x ) // strong 392 { 393 this->enforce_null_policy( x, "Null pointer in ptr_map_adapter::insert()" ); 394 auto_type ptr( x ); // nothrow 395 396 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool> 397 res = this->c_private().insert( std::make_pair( key, x ) ); // strong, commit 398 if( res.second ) // nothrow 399 ptr.release(); // nothrow 400 return std::make_pair( iterator( res.first ), res.second ); // nothrow 401 } 402 transfer(iterator object,ptr_map_adapter & from)403 bool transfer( iterator object, 404 ptr_map_adapter& from ) // strong 405 { 406 return this->single_transfer( object, from ); 407 } 408 transfer(iterator first,iterator last,ptr_map_adapter & from)409 size_type transfer( iterator first, 410 iterator last, 411 ptr_map_adapter& from ) // basic 412 { 413 return this->single_transfer( first, last, from ); 414 } 415 416 #ifdef BOOST_NO_SFINAE 417 #else 418 419 template< class Range > 420 BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range, 421 iterator >, 422 size_type >::type transfer(const Range & r,ptr_map_adapter & from)423 transfer( const Range& r, ptr_map_adapter& from ) // basic 424 { 425 return transfer( this->adl_begin(r), this->adl_end(r), from ); 426 } 427 428 #endif 429 transfer(ptr_map_adapter & from)430 size_type transfer( ptr_map_adapter& from ) // basic 431 { 432 return transfer( from.begin(), from.end(), from ); 433 } 434 435 }; 436 437 ///////////////////////////////////////////////////////////////////////// 438 // ptr_multimap_adapter 439 ///////////////////////////////////////////////////////////////////////// 440 441 template 442 < 443 class T, 444 class VoidPtrMultiMap, 445 class CloneAllocator = heap_clone_allocator 446 > 447 class ptr_multimap_adapter : 448 public ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMultiMap,CloneAllocator> 449 { 450 typedef ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMultiMap,CloneAllocator> 451 base_type; 452 453 public: // typedefs 454 typedef BOOST_DEDUCED_TYPENAME base_type::iterator 455 iterator; 456 typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator 457 const_iterator; 458 typedef BOOST_DEDUCED_TYPENAME base_type::object_type 459 object_type; 460 typedef BOOST_DEDUCED_TYPENAME base_type::size_type 461 size_type; 462 typedef BOOST_DEDUCED_TYPENAME base_type::key_type 463 key_type; 464 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference 465 const_reference; 466 typedef BOOST_DEDUCED_TYPENAME base_type::value_type 467 value_type; 468 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type 469 auto_type; 470 typedef BOOST_DEDUCED_TYPENAME VoidPtrMultiMap::key_compare 471 key_compare; 472 typedef BOOST_DEDUCED_TYPENAME VoidPtrMultiMap::allocator_type 473 allocator_type; 474 private: 475 safe_insert(const key_type & key,auto_type ptr)476 void safe_insert( const key_type& key, auto_type ptr ) // strong 477 { 478 this->c_private().insert( 479 std::make_pair( key, ptr.get() ) ); // strong, commit 480 ptr.release(); // nothrow 481 } 482 483 template< typename II > map_basic_clone_and_insert(II first,II last)484 void map_basic_clone_and_insert( II first, II last ) 485 { 486 while( first != last ) 487 { 488 const object_type& pair = *first.base(); // nothrow 489 auto_type ptr( this->null_policy_allocate_clone( 490 static_cast<value_type>( pair.second ) ) ); 491 // strong 492 safe_insert( pair.first, ptr_container_detail:: 493 move( ptr ) ); // strong, commit 494 ++first; 495 } 496 } 497 498 public: 499 ptr_multimap_adapter(const key_compare & comp=key_compare (),const allocator_type & a=allocator_type ())500 explicit ptr_multimap_adapter( const key_compare& comp = key_compare(), 501 const allocator_type& a = allocator_type() ) 502 : base_type( comp, a ) { } 503 504 template< class InputIterator > ptr_multimap_adapter(InputIterator first,InputIterator last,const key_compare & comp=key_compare (),const allocator_type & a=allocator_type ())505 ptr_multimap_adapter( InputIterator first, InputIterator last, 506 const key_compare& comp = key_compare(), 507 const allocator_type& a = allocator_type() ) 508 : base_type( comp, a ) 509 { 510 map_basic_clone_and_insert( first, last ); 511 } 512 513 template< class U > ptr_multimap_adapter(std::auto_ptr<U> r)514 ptr_multimap_adapter( std::auto_ptr<U> r ) : base_type( r ) 515 { } 516 517 template< class U > operator =(std::auto_ptr<U> r)518 void operator=( std::auto_ptr<U> r ) 519 { 520 base_type::operator=( r ); 521 } 522 523 using base_type::release; 524 525 template< typename InputIterator > insert(InputIterator first,InputIterator last)526 void insert( InputIterator first, InputIterator last ) // basic 527 { 528 map_basic_clone_and_insert( first, last ); 529 } 530 531 template< class Range > insert(const Range & r)532 void insert( const Range& r ) 533 { 534 insert( this->adl_begin(r), this->adl_end(r) ); 535 } 536 insert(key_type & key,value_type x)537 iterator insert( key_type& key, value_type x ) // strong 538 { 539 this->enforce_null_policy( x, "Null pointer in 'ptr_multimap_adapter::insert()'" ); 540 541 auto_type ptr( x ); // nothrow 542 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator 543 res = this->c_private().insert( std::make_pair( key, x ) ); 544 // strong, commit 545 ptr.release(); // notrow 546 return iterator( res ); 547 } 548 549 transfer(iterator object,ptr_multimap_adapter & from)550 void transfer( iterator object, 551 ptr_multimap_adapter& from ) // strong 552 { 553 this->multi_transfer( object, from ); 554 } 555 transfer(iterator first,iterator last,ptr_multimap_adapter & from)556 size_type transfer( iterator first, 557 iterator last, 558 ptr_multimap_adapter& from ) // basic 559 { 560 return this->multi_transfer( first, last, from ); 561 } 562 563 #ifdef BOOST_NO_SFINAE 564 #else 565 566 template< class Range > 567 BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range, 568 iterator >, 569 size_type >::type transfer(const Range & r,ptr_multimap_adapter & from)570 transfer( const Range& r, ptr_multimap_adapter& from ) // basic 571 { 572 return transfer( this->adl_begin(r), this->adl_end(r), from ); 573 } 574 575 #endif 576 transfer(ptr_multimap_adapter & from)577 void transfer( ptr_multimap_adapter& from ) // basic 578 { 579 transfer( from.begin(), from.end(), from ); 580 BOOST_ASSERT( from.empty() ); 581 } 582 }; 583 584 template< class I, class K, class V > is_null(ptr_map_iterator<I,K,V> i)585 inline bool is_null( ptr_map_iterator<I,K,V> i ) 586 { 587 return i.base()->second == 0; 588 } 589 590 } // namespace 'boost' 591 592 #endif 593