2 // Boost.Pointer Container
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)
9 // For more information, see http://www.boost.org/libs/ptr_container/
12 #ifndef BOOST_PTR_CONTAINER_DETAIL_PTR_MAP_ADAPTER_HPP
13 #define BOOST_PTR_CONTAINER_DETAIL_PTR_MAP_ADAPTER_HPP
15 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
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>
27 namespace ptr_container_detail
38 typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type
43 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::allocator_type
46 typedef BOOST_DEDUCED_TYPENAME
47 mpl::eval_if_c<Ordered,
48 select_value_compare<VoidPtrMap>,
49 mpl::identity<void> >::type
52 typedef BOOST_DEDUCED_TYPENAME
53 mpl::eval_if_c<Ordered,
54 select_key_compare<VoidPtrMap>,
55 mpl::identity<void> >::type
58 typedef BOOST_DEDUCED_TYPENAME
59 mpl::eval_if_c<Ordered,
61 select_hasher<VoidPtrMap> >::type
64 typedef BOOST_DEDUCED_TYPENAME
65 mpl::eval_if_c<Ordered,
67 select_key_equal<VoidPtrMap> >::type
70 typedef BOOST_DEDUCED_TYPENAME
72 ptr_container_detail::ordered_associative_container_tag,
73 ptr_container_detail::unordered_associative_container_tag>::type
76 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::key_type
81 typedef ptr_map_iterator< BOOST_DEDUCED_TYPENAME VoidPtrMap::iterator, key_type, U* const >
84 typedef ptr_map_iterator< BOOST_DEDUCED_TYPENAME VoidPtrMap::const_iterator, key_type, const U* const>
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,
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;
103 template< class Iter >
104 static U* get_pointer( Iter i )
109 template< class Iter >
110 static const U* get_const_pointer( Iter i )
115 BOOST_STATIC_CONSTANT( bool, allow_null = boost::is_nullable<T>::value );
124 class CloneAllocator,
127 class ptr_map_adapter_base :
128 public ptr_container_detail::associative_ptr_container< map_config<T,VoidPtrMap,Ordered>,
131 typedef ptr_container_detail::associative_ptr_container< map_config<T,VoidPtrMap,Ordered>,
135 typedef map_config<T,VoidPtrMap,Ordered> config;
136 typedef ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator,Ordered> this_type;
140 typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type
142 typedef BOOST_DEDUCED_TYPENAME base_type::iterator
144 typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
146 typedef BOOST_DEDUCED_TYPENAME base_type::size_type
148 typedef BOOST_DEDUCED_TYPENAME base_type::key_type
150 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
152 typedef BOOST_DEDUCED_TYPENAME base_type::value_type
154 typedef BOOST_DEDUCED_TYPENAME base_type::reference
156 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
157 const_mapped_reference;
158 typedef BOOST_DEDUCED_TYPENAME iterator_value<iterator>::type
162 typedef BOOST_DEDUCED_TYPENAME iterator_value<const_iterator>::type
166 typedef const_reference
170 const_mapped_reference lookup( const key_type& key ) const
172 const_iterator i = this->find( key );
173 if( i != this->end() )
176 BOOST_PTR_CONTAINER_THROW_EXCEPTION( true, bad_ptr_container_operation,
177 "'ptr_map/multimap::at()' could"
181 struct eraser // scope guard
185 const key_type& key_;
187 eraser( VoidPtrMap* m, const key_type& key )
188 : released_(false), m_(m), key_(key)
197 void release() { released_ = true; }
200 eraser& operator=(const eraser&);
203 mapped_reference insert_lookup( const key_type& key )
205 void*& ref = this->base()[key];
208 return *static_cast<mapped_type>(ref);
212 eraser e(&this->base(),key); // nothrow
213 mapped_type res = new T(); // strong
214 ref = res; // nothrow
215 e.release(); // nothrow
222 ptr_map_adapter_base()
225 template< class SizeType >
226 explicit ptr_map_adapter_base( SizeType n,
227 ptr_container_detail::unordered_associative_container_tag tag )
228 : base_type( n, tag )
231 template< class Compare, class Allocator >
232 ptr_map_adapter_base( const Compare& comp,
234 : base_type( comp, a )
237 template< class Hash, class Pred, class Allocator >
238 ptr_map_adapter_base( const Hash& hash,
241 : base_type( hash, pred, a )
244 template< class InputIterator >
245 ptr_map_adapter_base( InputIterator first, InputIterator last )
246 : base_type( first, last )
249 template< class InputIterator, class Comp >
250 ptr_map_adapter_base( InputIterator first, InputIterator last,
252 const allocator_type& a = allocator_type() )
253 : base_type( first, last, comp, a )
256 template< class InputIterator, class Hash, class Pred, class Allocator >
257 ptr_map_adapter_base( InputIterator first, InputIterator last,
261 : base_type( first, last, hash, pred, a )
264 template< class PtrContainer >
265 explicit ptr_map_adapter_base( std::auto_ptr<PtrContainer> clone )
269 template< typename PtrContainer >
270 ptr_map_adapter_base& operator=( std::auto_ptr<PtrContainer> clone )
272 base_type::operator=( clone );
276 iterator find( const key_type& x )
278 return iterator( this->base().find( x ) );
281 const_iterator find( const key_type& x ) const
283 return const_iterator( this->base().find( x ) );
286 size_type count( const key_type& x ) const
288 return this->base().count( x );
291 iterator lower_bound( const key_type& x )
293 return iterator( this->base().lower_bound( x ) );
296 const_iterator lower_bound( const key_type& x ) const
298 return const_iterator( this->base().lower_bound( x ) );
301 iterator upper_bound( const key_type& x )
303 return iterator( this->base().upper_bound( x ) );
306 const_iterator upper_bound( const key_type& x ) const
308 return const_iterator( this->base().upper_bound( x ) );
311 iterator_range<iterator> equal_range( const key_type& x )
313 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,
314 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator>
315 p = this->base().equal_range( x );
316 return make_iterator_range( iterator( p.first ), iterator( p.second ) );
319 iterator_range<const_iterator> equal_range( const key_type& x ) const
321 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator,
322 BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator>
323 p = this->base().equal_range( x );
324 return make_iterator_range( const_iterator( p.first ),
325 const_iterator( p.second ) );
328 mapped_reference at( const key_type& key )
330 return const_cast<mapped_reference>( lookup( key ) );
333 const_mapped_reference at( const key_type& key ) const
335 return lookup( key );
338 mapped_reference operator[]( const key_type& key )
340 return insert_lookup( key );
343 auto_type replace( iterator where, mapped_type x ) // strong
345 BOOST_ASSERT( where != this->end() );
347 this->enforce_null_policy( x, "Null pointer in 'replace()'" );
351 BOOST_PTR_CONTAINER_THROW_EXCEPTION( this->empty(),
352 bad_ptr_container_operation,
353 "'replace()' on empty container" );
355 auto_type old( where->second ); // nothrow
356 where.base()->second = ptr.release(); // nothrow, commit
357 return boost::ptr_container::move( old );
361 auto_type replace( iterator where, std::auto_ptr<U> x )
363 return replace( where, x.release() );
367 size_type bucket( const key_type& key ) const
369 return this->base().bucket( key );
373 } // ptr_container_detail
375 /////////////////////////////////////////////////////////////////////////
377 /////////////////////////////////////////////////////////////////////////
383 class CloneAllocator = heap_clone_allocator,
386 class ptr_map_adapter :
387 public ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator,Ordered>
389 typedef ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMap,CloneAllocator,Ordered>
393 typedef BOOST_DEDUCED_TYPENAME base_type::iterator
395 typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
397 typedef BOOST_DEDUCED_TYPENAME base_type::size_type
399 typedef BOOST_DEDUCED_TYPENAME base_type::key_type
401 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
403 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
405 typedef BOOST_DEDUCED_TYPENAME VoidPtrMap::allocator_type
407 typedef BOOST_DEDUCED_TYPENAME base_type::mapped_type
411 void safe_insert( const key_type& key, auto_type ptr ) // strong
413 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool>
415 this->base().insert( std::make_pair( key, ptr.get() ) ); // strong, commit
416 if( res.second ) // nothrow
417 ptr.release(); // nothrow
421 void map_basic_clone_and_insert( II first, II last )
423 while( first != last )
425 if( this->find( first->first ) == this->end() )
427 const_reference p = *first.base(); // nothrow
428 auto_type ptr( this->null_policy_allocate_clone( p.second ) );
430 this->safe_insert( p.first,
431 boost::ptr_container::move( ptr ) );
442 template< class Comp >
443 explicit ptr_map_adapter( const Comp& comp,
444 const allocator_type& a )
445 : base_type( comp, a ) { }
447 template< class Hash, class Pred, class Allocator >
448 ptr_map_adapter( const Hash& hash,
451 : base_type( hash, pred, a )
454 template< class InputIterator >
455 ptr_map_adapter( InputIterator first, InputIterator last )
457 map_basic_clone_and_insert( first, last );
460 template< class InputIterator, class Comp >
461 ptr_map_adapter( InputIterator first, InputIterator last,
463 const allocator_type& a = allocator_type() )
464 : base_type( comp, a )
466 map_basic_clone_and_insert( first, last );
469 template< class InputIterator, class Hash, class Pred, class Allocator >
470 ptr_map_adapter( InputIterator first, InputIterator last,
474 : base_type( hash, pred, a )
476 map_basic_clone_and_insert( first, last );
479 ptr_map_adapter( const ptr_map_adapter& r )
481 map_basic_clone_and_insert( r.begin(), r.end() );
484 template< class Key, class U, class CA, bool b >
485 ptr_map_adapter( const ptr_map_adapter<Key,U,CA,b>& r )
487 map_basic_clone_and_insert( r.begin(), r.end() );
491 ptr_map_adapter( std::auto_ptr<U> r ) : base_type( r )
494 ptr_map_adapter& operator=( ptr_map_adapter r )
501 ptr_map_adapter& operator=( std::auto_ptr<U> r )
503 base_type::operator=( r );
507 using base_type::release;
509 template< typename InputIterator >
510 void insert( InputIterator first, InputIterator last ) // basic
512 map_basic_clone_and_insert( first, last );
515 template< class Range >
516 void insert( const Range& r )
518 insert( boost::begin(r), boost::end(r) );
522 std::pair<iterator,bool> insert_impl( const key_type& key, mapped_type x ) // strong
524 this->enforce_null_policy( x, "Null pointer in ptr_map_adapter::insert()" );
525 auto_type ptr( x ); // nothrow
527 std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool>
528 res = this->base().insert( std::make_pair( key, x ) ); // strong, commit
529 if( res.second ) // nothrow
530 ptr.release(); // nothrow
531 return std::make_pair( iterator( res.first ), res.second ); // nothrow
534 iterator insert_impl( iterator before, const key_type& key, mapped_type x ) // strong
536 this->enforce_null_policy( x,
537 "Null pointer in 'ptr_map_adapter::insert()'" );
538 auto_type ptr( x ); // nothrow
539 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
540 res = this->base().insert( before.base(), std::make_pair( key, x ) );
542 ptr.release(); // notrow
543 return iterator( res );
548 std::pair<iterator,bool> insert( key_type& key, mapped_type x )
550 return insert_impl( key, x );
554 std::pair<iterator,bool> insert( const key_type& key, std::auto_ptr<U> x )
556 return insert_impl( key, x.release() );
559 template< class F, class S >
560 iterator insert( iterator before, ptr_container_detail::ref_pair<F,S> p ) // strong
562 this->enforce_null_policy( p.second,
563 "Null pointer in 'ptr_map_adapter::insert()'" );
565 auto_type ptr( this->null_policy_allocate_clone( p.second ) );
566 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
567 result = this->base().insert( before.base(),
568 std::make_pair(p.first,ptr.get()) ); // strong
569 if( ptr.get() == result->second )
572 return iterator( result );
575 iterator insert( iterator before, key_type& key, mapped_type x ) // strong
577 return insert_impl( before, key, x );
581 iterator insert( iterator before, const key_type& key, std::auto_ptr<U> x ) // strong
583 return insert_impl( before, key, x.release() );
586 template< class PtrMapAdapter >
587 bool transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator object,
588 PtrMapAdapter& from ) // strong
590 return this->single_transfer( object, from );
593 template< class PtrMapAdapter >
594 size_type transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator first,
595 BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator last,
596 PtrMapAdapter& from ) // basic
598 return this->single_transfer( first, last, from );
601 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
604 template< class PtrMapAdapter, class Range >
605 BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
606 BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator >,
608 transfer( const Range& r, PtrMapAdapter& from ) // basic
610 return transfer( boost::begin(r), boost::end(r), from );
615 template< class PtrMapAdapter >
616 size_type transfer( PtrMapAdapter& from ) // basic
618 return transfer( from.begin(), from.end(), from );
622 /////////////////////////////////////////////////////////////////////////
623 // ptr_multimap_adapter
624 /////////////////////////////////////////////////////////////////////////
629 class VoidPtrMultiMap,
630 class CloneAllocator = heap_clone_allocator,
633 class ptr_multimap_adapter :
634 public ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMultiMap,CloneAllocator,Ordered>
636 typedef ptr_container_detail::ptr_map_adapter_base<T,VoidPtrMultiMap,CloneAllocator,Ordered>
640 typedef BOOST_DEDUCED_TYPENAME base_type::iterator
642 typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
644 typedef BOOST_DEDUCED_TYPENAME base_type::size_type
646 typedef BOOST_DEDUCED_TYPENAME base_type::key_type
648 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
650 typedef BOOST_DEDUCED_TYPENAME base_type::mapped_type
652 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
654 typedef BOOST_DEDUCED_TYPENAME VoidPtrMultiMap::allocator_type
658 void safe_insert( const key_type& key, auto_type ptr ) // strong
661 std::make_pair( key, ptr.get() ) ); // strong, commit
662 ptr.release(); // nothrow
665 template< typename II >
666 void map_basic_clone_and_insert( II first, II last )
668 while( first != last )
670 const_reference pair = *first.base(); // nothrow
671 auto_type ptr( this->null_policy_allocate_clone( pair.second ) );
673 safe_insert( pair.first,
674 boost::ptr_container::move( ptr ) );
682 ptr_multimap_adapter()
685 template< class SizeType >
686 ptr_multimap_adapter( SizeType n,
687 ptr_container_detail::unordered_associative_container_tag tag )
688 : base_type( n, tag )
691 template< class Comp >
692 explicit ptr_multimap_adapter( const Comp& comp,
693 const allocator_type& a )
694 : base_type( comp, a ) { }
696 template< class Hash, class Pred, class Allocator >
697 ptr_multimap_adapter( const Hash& hash,
700 : base_type( hash, pred, a )
703 template< class InputIterator >
704 ptr_multimap_adapter( InputIterator first, InputIterator last )
706 map_basic_clone_and_insert( first, last );
709 template< class InputIterator, class Comp >
710 ptr_multimap_adapter( InputIterator first, InputIterator last,
712 const allocator_type& a )
713 : base_type( comp, a )
715 map_basic_clone_and_insert( first, last );
718 template< class InputIterator, class Hash, class Pred, class Allocator >
719 ptr_multimap_adapter( InputIterator first, InputIterator last,
723 : base_type( hash, pred, a )
725 map_basic_clone_and_insert( first, last );
728 ptr_multimap_adapter( const ptr_multimap_adapter& r )
730 map_basic_clone_and_insert( r.begin(), r.end() );
733 template< class Key, class U, class CA, bool b >
734 ptr_multimap_adapter( const ptr_multimap_adapter<Key,U,CA,b>& r )
736 map_basic_clone_and_insert( r.begin(), r.end() );
740 explicit ptr_multimap_adapter( std::auto_ptr<U> r ) : base_type( r )
743 ptr_multimap_adapter& operator=( ptr_multimap_adapter r )
750 ptr_multimap_adapter& operator=( std::auto_ptr<U> r )
752 base_type::operator=( r );
756 using base_type::release;
759 iterator insert_impl( const key_type& key, mapped_type x ) // strong
761 this->enforce_null_policy( x,
762 "Null pointer in 'ptr_multimap_adapter::insert()'" );
763 auto_type ptr( x ); // nothrow
764 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
765 res = this->base().insert( std::make_pair( key, x ) );
767 ptr.release(); // notrow
768 return iterator( res );
771 iterator insert_impl( iterator before, const key_type& key, mapped_type x ) // strong
773 this->enforce_null_policy( x,
774 "Null pointer in 'ptr_multimap_adapter::insert()'" );
775 auto_type ptr( x ); // nothrow
776 BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
777 res = this->base().insert( before.base(),
778 std::make_pair( key, x ) );
780 ptr.release(); // notrow
781 return iterator( res );
785 template< typename InputIterator >
786 void insert( InputIterator first, InputIterator last ) // basic
788 map_basic_clone_and_insert( first, last );
791 template< class Range >
792 void insert( const Range& r )
794 insert( boost::begin(r), boost::end(r) );
797 iterator insert( key_type& key, mapped_type x ) // strong
799 return insert_impl( key, x );
803 iterator insert( const key_type& key, std::auto_ptr<U> x )
805 return insert_impl( key, x.release() );
808 template< class F, class S >
809 iterator insert( iterator before, ptr_container_detail::ref_pair<F,S> p ) // strong
811 this->enforce_null_policy( p.second,
812 "Null pointer in 'ptr_multimap_adapter::insert()'" );
813 iterator res = insert_impl( before, p.first,
814 this->null_policy_allocate_clone( p.second ) );
818 iterator insert( iterator before, key_type& key, mapped_type x ) // strong
820 return insert_impl( before, key, x );
824 iterator insert( iterator before, const key_type& key, std::auto_ptr<U> x ) // strong
826 return insert_impl( before, key, x.release() );
829 template< class PtrMapAdapter >
830 void transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator object,
831 PtrMapAdapter& from ) // strong
833 this->multi_transfer( object, from );
836 template< class PtrMapAdapter >
837 size_type transfer( BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator first,
838 BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator last,
839 PtrMapAdapter& from ) // basic
841 return this->multi_transfer( first, last, from );
844 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
847 template< class PtrMapAdapter, class Range >
848 BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
849 BOOST_DEDUCED_TYPENAME PtrMapAdapter::iterator >,
851 transfer( const Range& r, PtrMapAdapter& from ) // basic
853 return transfer( boost::begin(r), boost::end(r), from );
857 template< class PtrMapAdapter >
858 void transfer( PtrMapAdapter& from ) // basic
860 transfer( from.begin(), from.end(), from );
861 BOOST_ASSERT( from.empty() );
866 template< class I, class F, class S >
867 inline bool is_null( const ptr_map_iterator<I,F,S>& i )
869 return i->second == 0;
872 } // namespace 'boost'