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_PTR_SEQUENCE_ADAPTER_HPP
13 #define BOOST_PTR_CONTAINER_PTR_SEQUENCE_ADAPTER_HPP
15 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
20 #include <boost/ptr_container/detail/reversible_ptr_container.hpp>
21 #include <boost/ptr_container/indirect_fun.hpp>
22 #include <boost/ptr_container/detail/void_ptr_iterator.hpp>
23 #include <boost/ptr_container/detail/ptr_container_disable_deprecated.hpp>
24 #include <boost/type_traits/remove_pointer.hpp>
25 #include <boost/type_traits/is_same.hpp>
26 #include <boost/next_prior.hpp>
28 #if defined(BOOST_PTR_CONTAINER_DISABLE_DEPRECATED)
29 #pragma GCC diagnostic push
30 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
35 namespace ptr_container_detail
42 struct sequence_config
44 typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type
49 typedef BOOST_DEDUCED_TYPENAME VoidPtrSeq::allocator_type
54 typedef void_ptr_iterator<
55 BOOST_DEDUCED_TYPENAME VoidPtrSeq::iterator, U >
58 typedef void_ptr_iterator<
59 BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_iterator, const U >
62 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
64 template< class Iter >
65 static U* get_pointer( Iter i )
67 return static_cast<U*>( *i.base() );
71 template< class Iter >
72 static U* get_pointer( void_ptr_iterator<Iter,U> i )
74 return static_cast<U*>( *i.base() );
77 template< class Iter >
78 static U* get_pointer( Iter i )
84 #if defined(BOOST_NO_SFINAE) && !BOOST_WORKAROUND(__MWERKS__, <= 0x3003)
86 template< class Iter >
87 static const U* get_const_pointer( Iter i )
89 return static_cast<const U*>( *i.base() );
92 #else // BOOST_NO_SFINAE
94 #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003)
95 template< class Iter >
96 static const U* get_const_pointer( void_ptr_iterator<Iter,U> i )
98 return static_cast<const U*>( *i.base() );
100 #else // BOOST_WORKAROUND
101 template< class Iter >
102 static const U* get_const_pointer( void_ptr_iterator<Iter,const U> i )
104 return static_cast<const U*>( *i.base() );
106 #endif // BOOST_WORKAROUND
108 template< class Iter >
109 static const U* get_const_pointer( Iter i )
113 #endif // BOOST_NO_SFINAE
115 BOOST_STATIC_CONSTANT(bool, allow_null = boost::is_nullable<T>::value );
118 } // ptr_container_detail
121 template< class Iterator, class T >
122 inline bool is_null( void_ptr_iterator<Iterator,T> i )
124 return *i.base() == 0;
133 class CloneAllocator = heap_clone_allocator
135 class ptr_sequence_adapter : public
136 ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>,
139 typedef ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>,
143 typedef ptr_sequence_adapter<T,VoidPtrSeq,CloneAllocator>
147 typedef BOOST_DEDUCED_TYPENAME base_type::scoped_deleter scoped_deleter;
150 typedef BOOST_DEDUCED_TYPENAME base_type::value_type value_type;
151 typedef BOOST_DEDUCED_TYPENAME base_type::reference reference;
152 typedef BOOST_DEDUCED_TYPENAME base_type::const_reference
154 typedef BOOST_DEDUCED_TYPENAME base_type::auto_type auto_type;
155 typedef BOOST_DEDUCED_TYPENAME base_type::clone_allocator_type
156 clone_allocator_type;
157 typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator;
158 typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type;
159 typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type
162 ptr_sequence_adapter()
165 template< class Allocator >
166 explicit ptr_sequence_adapter( const Allocator& a )
170 template< class SizeType >
171 ptr_sequence_adapter( SizeType n,
172 ptr_container_detail::fixed_length_sequence_tag tag )
173 : base_type( n, tag )
176 template< class SizeType, class Allocator >
177 ptr_sequence_adapter( SizeType n, const Allocator& a,
178 ptr_container_detail::fixed_length_sequence_tag tag )
179 : base_type( n, a, tag )
182 template< class InputIterator >
183 ptr_sequence_adapter( InputIterator first, InputIterator last )
184 : base_type( first, last )
187 template< class InputIterator, class Allocator >
188 ptr_sequence_adapter( InputIterator first, InputIterator last,
190 : base_type( first, last, a )
193 template< class ForwardIterator >
194 ptr_sequence_adapter( ForwardIterator first,
195 ForwardIterator last,
196 ptr_container_detail::fixed_length_sequence_tag tag )
197 : base_type( first, last, tag )
200 template< class SizeType, class ForwardIterator >
201 ptr_sequence_adapter( SizeType n,
202 ForwardIterator first,
203 ForwardIterator last,
204 ptr_container_detail::fixed_length_sequence_tag tag )
205 : base_type( n, first, last, tag )
208 ptr_sequence_adapter( const ptr_sequence_adapter& r )
213 ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r )
217 ptr_sequence_adapter( const ptr_sequence_adapter& r,
218 ptr_container_detail::fixed_length_sequence_tag tag )
219 : base_type( r, tag )
223 ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r,
224 ptr_container_detail::fixed_length_sequence_tag tag )
225 : base_type( r, tag )
228 #ifndef BOOST_NO_AUTO_PTR
229 template< class PtrContainer >
230 explicit ptr_sequence_adapter( std::auto_ptr<PtrContainer> clone )
234 #ifndef BOOST_NO_CXX11_SMART_PTR
235 template< class PtrContainer >
236 explicit ptr_sequence_adapter( std::unique_ptr<PtrContainer> clone )
237 : base_type( std::move( clone ) )
241 ptr_sequence_adapter& operator=( const ptr_sequence_adapter r )
247 #ifndef BOOST_NO_AUTO_PTR
248 template< class PtrContainer >
249 ptr_sequence_adapter& operator=( std::auto_ptr<PtrContainer> clone )
251 base_type::operator=( clone );
255 #ifndef BOOST_NO_CXX11_SMART_PTR
256 template< class PtrContainer >
257 ptr_sequence_adapter& operator=( std::unique_ptr<PtrContainer> clone )
259 base_type::operator=( std::move( clone ) );
264 /////////////////////////////////////////////////////////////
266 /////////////////////////////////////////////////////////////
268 void push_back( value_type x ) // strong
270 this->enforce_null_policy( x, "Null pointer in 'push_back()'" );
271 auto_type ptr( x, *this ); // notrow
272 this->base().push_back( x ); // strong, commit
273 ptr.release(); // nothrow
276 #ifndef BOOST_NO_AUTO_PTR
278 void push_back( std::auto_ptr<U> x )
280 push_back( x.release() );
283 #ifndef BOOST_NO_CXX11_SMART_PTR
285 void push_back( std::unique_ptr<U> x )
287 push_back( x.release() );
291 void push_front( value_type x )
293 this->enforce_null_policy( x, "Null pointer in 'push_front()'" );
294 auto_type ptr( x, *this ); // nothrow
295 this->base().push_front( x ); // strong, commit
296 ptr.release(); // nothrow
299 #ifndef BOOST_NO_AUTO_PTR
301 void push_front( std::auto_ptr<U> x )
303 push_front( x.release() );
306 #ifndef BOOST_NO_CXX11_SMART_PTR
308 void push_front( std::unique_ptr<U> x )
310 push_front( x.release() );
316 BOOST_ASSERT( !this->empty() &&
317 "'pop_back()' on empty container" );
318 auto_type ptr( static_cast<value_type>(this->base().back()), *this );
320 this->base().pop_back(); // nothrow
321 return ptr_container_detail::move( ptr ); // nothrow
324 auto_type pop_front()
326 BOOST_ASSERT( !this->empty() &&
327 "'pop_front()' on empty container" );
328 auto_type ptr( static_cast<value_type>(this->base().front()), *this );
330 this->base().pop_front(); // nothrow
331 return ptr_container_detail::move( ptr );
336 BOOST_ASSERT( !this->empty() &&
337 "accessing 'front()' on empty container" );
339 BOOST_ASSERT( !::boost::is_null( this->begin() ) );
340 return *this->begin();
343 const_reference front() const
345 return const_cast<ptr_sequence_adapter*>(this)->front();
350 BOOST_ASSERT( !this->empty() &&
351 "accessing 'back()' on empty container" );
352 BOOST_ASSERT( !::boost::is_null( --this->end() ) );
353 return *--this->end();
356 const_reference back() const
358 return const_cast<ptr_sequence_adapter*>(this)->back();
361 public: // deque/vector inerface
363 reference operator[]( size_type n ) // nothrow
365 BOOST_ASSERT( n < this->size() );
366 BOOST_ASSERT( !this->is_null( n ) );
367 return *static_cast<value_type>( this->base()[n] );
370 const_reference operator[]( size_type n ) const // nothrow
372 BOOST_ASSERT( n < this->size() );
373 BOOST_ASSERT( !this->is_null( n ) );
374 return *static_cast<value_type>( this->base()[n] );
377 reference at( size_type n )
379 BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index,
380 "'at()' out of bounds" );
381 BOOST_ASSERT( !this->is_null( n ) );
385 const_reference at( size_type n ) const
387 BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index,
388 "'at()' out of bounds" );
389 BOOST_ASSERT( !this->is_null( n ) );
393 public: // vector interface
395 size_type capacity() const
397 return this->base().capacity();
400 void reserve( size_type n )
402 this->base().reserve( n );
407 this->base().reverse();
410 public: // assign, insert, transfer
412 // overhead: 1 heap allocation (very cheap compared to cloning)
413 template< class InputIterator >
414 void assign( InputIterator first, InputIterator last ) // strong
416 base_type temp( first, last );
420 template< class Range >
421 void assign( const Range& r ) // strong
423 assign( boost::begin(r), boost::end(r ) );
428 void insert_impl( iterator before, I first, I last, std::input_iterator_tag ) // strong
430 ptr_sequence_adapter temp(first,last); // strong
431 transfer( before, temp ); // strong, commit
435 void insert_impl( iterator before, I first, I last, std::forward_iterator_tag ) // strong
439 scoped_deleter sd( *this, first, last ); // strong
440 this->insert_clones_and_release( sd, before ); // strong, commit
445 using base_type::insert;
447 template< class InputIterator >
448 void insert( iterator before, InputIterator first, InputIterator last ) // strong
450 insert_impl( before, first, last, BOOST_DEDUCED_TYPENAME
451 iterator_category<InputIterator>::type() );
454 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
456 template< class Range >
457 BOOST_DEDUCED_TYPENAME
458 boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type
459 insert( iterator before, const Range& r )
461 insert( before, boost::begin(r), boost::end(r) );
466 template< class PtrSeqAdapter >
467 void transfer( iterator before,
468 BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator first,
469 BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator last,
470 PtrSeqAdapter& from ) // strong
472 BOOST_ASSERT( (void*)&from != (void*)this );
476 insert( before.base(), first.base(), last.base() ); // strong
477 from.base().erase( first.base(), last.base() ); // nothrow
480 template< class PtrSeqAdapter >
481 void transfer( iterator before,
482 BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator object,
483 PtrSeqAdapter& from ) // strong
485 BOOST_ASSERT( (void*)&from != (void*)this );
488 this->base().insert( before.base(), *object.base() ); // strong
489 from.base().erase( object.base() ); // nothrow
492 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
495 template< class PtrSeqAdapter, class Range >
496 BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
497 BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator > >::type
498 transfer( iterator before, const Range& r, PtrSeqAdapter& from ) // strong
500 transfer( before, boost::begin(r), boost::end(r), from );
504 template< class PtrSeqAdapter >
505 void transfer( iterator before, PtrSeqAdapter& from ) // strong
507 BOOST_ASSERT( (void*)&from != (void*)this );
511 insert( before.base(),
512 from.begin().base(), from.end().base() ); // strong
513 from.base().clear(); // nothrow
516 public: // C-array support
518 void transfer( iterator before, value_type* from,
519 size_type size, bool delete_from = true ) // strong
521 BOOST_ASSERT( from != 0 );
524 BOOST_DEDUCED_TYPENAME base_type::scoped_deleter
525 deleter( *this, from, size ); // nothrow
526 this->base().insert( before.base(), from, from + size ); // strong
527 deleter.release(); // nothrow
531 this->base().insert( before.base(), from, from + size ); // strong
535 value_type* c_array() // nothrow
539 T** res = reinterpret_cast<T**>( &this->begin().base()[0] );
543 public: // null functions
545 bool is_null( size_type idx ) const
547 BOOST_ASSERT( idx < this->size() );
548 return this->base()[idx] == 0;
553 void resize( size_type size ) // basic
555 size_type old_size = this->size();
556 if( old_size > size )
558 this->erase( boost::next( this->begin(), size ), this->end() );
560 else if( size > old_size )
562 for( ; old_size != size; ++old_size )
563 this->push_back( new BOOST_DEDUCED_TYPENAME
564 boost::remove_pointer<value_type>::type() );
567 BOOST_ASSERT( this->size() == size );
570 void resize( size_type size, value_type to_clone ) // basic
572 size_type old_size = this->size();
573 if( old_size > size )
575 this->erase( boost::next( this->begin(), size ), this->end() );
577 else if( size > old_size )
579 for( ; old_size != size; ++old_size )
580 this->push_back( this->null_policy_allocate_clone( to_clone ) );
583 BOOST_ASSERT( this->size() == size );
586 void rresize( size_type size ) // basic
588 size_type old_size = this->size();
589 if( old_size > size )
591 this->erase( this->begin(),
592 boost::next( this->begin(), old_size - size ) );
594 else if( size > old_size )
596 for( ; old_size != size; ++old_size )
597 this->push_front( new BOOST_DEDUCED_TYPENAME
598 boost::remove_pointer<value_type>::type() );
601 BOOST_ASSERT( this->size() == size );
604 void rresize( size_type size, value_type to_clone ) // basic
606 size_type old_size = this->size();
607 if( old_size > size )
609 this->erase( this->begin(),
610 boost::next( this->begin(), old_size - size ) );
612 else if( size > old_size )
614 for( ; old_size != size; ++old_size )
615 this->push_front( this->null_policy_allocate_clone( to_clone ) );
618 BOOST_ASSERT( this->size() == size );
621 public: // algorithms
623 void sort( iterator first, iterator last )
625 sort( first, last, std::less<T>() );
630 sort( this->begin(), this->end() );
633 template< class Compare >
634 void sort( iterator first, iterator last, Compare comp )
636 BOOST_ASSERT( first <= last && "out of range sort()" );
637 BOOST_ASSERT( this->begin() <= first && "out of range sort()" );
638 BOOST_ASSERT( last <= this->end() && "out of range sort()" );
639 // some static assert on the arguments of the comparison
640 std::sort( first.base(), last.base(),
641 void_ptr_indirect_fun<Compare,T>(comp) );
644 template< class Compare >
645 void sort( Compare comp )
647 sort( this->begin(), this->end(), comp );
650 void unique( iterator first, iterator last )
652 unique( first, last, std::equal_to<T>() );
657 unique( this->begin(), this->end() );
661 struct is_not_zero_ptr
664 bool operator()( const U* r ) const
671 template< class Fun, class Arg1 >
672 class void_ptr_delete_if
677 void_ptr_delete_if() : fun(Fun())
680 void_ptr_delete_if( Fun f ) : fun(f)
683 bool operator()( void* r ) const
685 BOOST_ASSERT( r != 0 );
686 Arg1 arg1 = static_cast<Arg1>(r);
689 clone_allocator_type::deallocate_clone( arg1 );
697 void compact_and_erase_nulls( iterator first, iterator last ) // nothrow
699 typename base_type::ptr_iterator p = std::stable_partition(
703 this->base().erase( p, this->end().base() );
707 void range_check_impl( iterator, iterator,
708 std::bidirectional_iterator_tag )
711 void range_check_impl( iterator first, iterator last,
712 std::random_access_iterator_tag )
714 BOOST_ASSERT( first <= last && "out of range unique()/erase_if()" );
715 BOOST_ASSERT( this->begin() <= first && "out of range unique()/erase_if()" );
716 BOOST_ASSERT( last <= this->end() && "out of range unique()/erase_if)(" );
719 void range_check( iterator first, iterator last )
721 range_check_impl( first, last,
722 BOOST_DEDUCED_TYPENAME iterator_category<iterator>::type() );
727 template< class Compare >
728 void unique( iterator first, iterator last, Compare comp )
730 range_check(first,last);
732 iterator prev = first;
733 iterator next = first;
735 for( ; next != last; ++next )
737 BOOST_ASSERT( !::boost::is_null(prev) );
738 BOOST_ASSERT( !::boost::is_null(next) );
739 if( comp( *prev, *next ) )
741 this->remove( next ); // delete object
742 *next.base() = 0; // mark pointer as deleted
751 compact_and_erase_nulls( first, last );
754 template< class Compare >
755 void unique( Compare comp )
757 unique( this->begin(), this->end(), comp );
760 template< class Pred >
761 void erase_if( iterator first, iterator last, Pred pred )
763 range_check(first,last);
764 this->base().erase( std::remove_if( first.base(), last.base(),
765 void_ptr_delete_if<Pred,value_type>(pred) ),
769 template< class Pred >
770 void erase_if( Pred pred )
772 erase_if( this->begin(), this->end(), pred );
776 void merge( iterator first, iterator last,
777 ptr_sequence_adapter& from )
779 merge( first, last, from, std::less<T>() );
782 template< class BinPred >
783 void merge( iterator first, iterator last,
784 ptr_sequence_adapter& from, BinPred pred )
786 void_ptr_indirect_fun<BinPred,T> bin_pred(pred);
787 size_type current_size = this->size();
788 this->transfer( this->end(), first, last, from );
789 typename base_type::ptr_iterator middle = this->begin().base();
790 std::advance(middle,current_size);
791 std::inplace_merge( this->begin().base(),
797 void merge( ptr_sequence_adapter& r )
799 merge( r, std::less<T>() );
800 BOOST_ASSERT( r.empty() );
803 template< class BinPred >
804 void merge( ptr_sequence_adapter& r, BinPred pred )
806 merge( r.begin(), r.end(), r, pred );
807 BOOST_ASSERT( r.empty() );
813 } // namespace 'boost'
815 #if defined(BOOST_PTR_CONTAINER_DISABLE_DEPRECATED)
816 #pragma GCC diagnostic pop