| // |
| // Boost.Pointer Container |
| // |
| // Copyright Thorsten Ottosen 2003-2005. Use, modification and |
| // distribution is subject to the Boost Software License, Version |
| // 1.0. (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // For more information, see http://www.boost.org/libs/ptr_container/ |
| // |
| |
| |
| #ifndef BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP |
| #define BOOST_PTR_CONTAINER_DETAIL_REVERSIBLE_PTR_CONTAINER_HPP |
| |
| #if defined(_MSC_VER) && (_MSC_VER >= 1200) |
| # pragma once |
| #endif |
| |
| #include <boost/ptr_container/detail/throw_exception.hpp> |
| #include <boost/ptr_container/detail/scoped_deleter.hpp> |
| #include <boost/ptr_container/detail/static_move_ptr.hpp> |
| #include <boost/ptr_container/exception.hpp> |
| #include <boost/ptr_container/clone_allocator.hpp> |
| #include <boost/ptr_container/nullable.hpp> |
| |
| #ifdef BOOST_NO_SFINAE |
| #else |
| #include <boost/range/functions.hpp> |
| #endif |
| |
| #include <boost/config.hpp> |
| #include <boost/iterator/reverse_iterator.hpp> |
| #include <boost/range/iterator.hpp> |
| #include <boost/utility/enable_if.hpp> |
| #include <boost/type_traits/is_pointer.hpp> |
| #include <boost/type_traits/is_integral.hpp> |
| #include <typeinfo> |
| #include <memory> |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) |
| #pragma warning(push) |
| #pragma warning(disable:4127) |
| #endif |
| |
| namespace boost |
| { |
| |
| namespace ptr_container_detail |
| { |
| template< class CloneAllocator > |
| struct clone_deleter |
| { |
| template< class T > |
| void operator()( const T* p ) const |
| { |
| CloneAllocator::deallocate_clone( p ); |
| } |
| }; |
| |
| template< class T > |
| struct is_pointer_or_integral |
| { |
| BOOST_STATIC_CONSTANT(bool, value = is_pointer<T>::value || is_integral<T>::value ); |
| }; |
| |
| struct is_pointer_or_integral_tag {}; |
| struct is_range_tag {}; |
| struct sequence_tag {}; |
| struct fixed_length_sequence_tag : sequence_tag {}; |
| struct associative_container_tag {}; |
| struct ordered_associative_container_tag : associative_container_tag {}; |
| struct unordered_associative_container_tag : associative_container_tag {}; |
| |
| |
| |
| template |
| < |
| class Config, |
| class CloneAllocator |
| > |
| class reversible_ptr_container |
| { |
| private: |
| BOOST_STATIC_CONSTANT( bool, allow_null = Config::allow_null ); |
| |
| typedef BOOST_DEDUCED_TYPENAME Config::value_type Ty_; |
| |
| template< bool allow_null_values > |
| struct null_clone_allocator |
| { |
| template< class Iter > |
| static Ty_* allocate_clone_from_iterator( Iter i ) |
| { |
| return allocate_clone( Config::get_const_pointer( i ) ); |
| } |
| |
| static Ty_* allocate_clone( const Ty_* x ) |
| { |
| if( allow_null_values ) |
| { |
| if( x == 0 ) |
| return 0; |
| } |
| else |
| { |
| BOOST_ASSERT( x != 0 && "Cannot insert clone of null!" ); |
| } |
| |
| Ty_* res = CloneAllocator::allocate_clone( *x ); |
| BOOST_ASSERT( typeid(*res) == typeid(*x) && |
| "CloneAllocator::allocate_clone() does not clone the " |
| "object properly. Check that new_clone() is implemented" |
| " correctly" ); |
| return res; |
| } |
| |
| static void deallocate_clone( const Ty_* x ) |
| { |
| if( allow_null_values ) |
| { |
| if( x == 0 ) |
| return; |
| } |
| |
| CloneAllocator::deallocate_clone( x ); |
| } |
| }; |
| |
| typedef BOOST_DEDUCED_TYPENAME Config::void_container_type Cont; |
| #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) |
| typedef null_clone_allocator<reversible_ptr_container::allow_null> |
| null_cloner_type; |
| #else |
| typedef null_clone_allocator<allow_null> null_cloner_type; |
| #endif |
| typedef clone_deleter<null_cloner_type> Deleter; |
| |
| Cont c_; |
| |
| public: |
| Cont& base() { return c_; } |
| protected: // having this public could break encapsulation |
| const Cont& base() const { return c_; } |
| |
| public: // typedefs |
| typedef Ty_* value_type; |
| typedef Ty_* pointer; |
| typedef Ty_& reference; |
| typedef const Ty_& const_reference; |
| |
| typedef BOOST_DEDUCED_TYPENAME Config::iterator |
| iterator; |
| typedef BOOST_DEDUCED_TYPENAME Config::const_iterator |
| const_iterator; |
| typedef boost::reverse_iterator< iterator > |
| reverse_iterator; |
| typedef boost::reverse_iterator< const_iterator > |
| const_reverse_iterator; |
| typedef BOOST_DEDUCED_TYPENAME Cont::difference_type |
| difference_type; |
| typedef BOOST_DEDUCED_TYPENAME Cont::size_type |
| size_type; |
| typedef BOOST_DEDUCED_TYPENAME Config::allocator_type |
| allocator_type; |
| typedef CloneAllocator clone_allocator_type; |
| typedef ptr_container_detail::static_move_ptr<Ty_,Deleter> |
| auto_type; |
| |
| protected: |
| |
| typedef ptr_container_detail::scoped_deleter<Ty_,null_cloner_type> |
| scoped_deleter; |
| typedef BOOST_DEDUCED_TYPENAME Cont::iterator |
| ptr_iterator; |
| typedef BOOST_DEDUCED_TYPENAME Cont::const_iterator |
| ptr_const_iterator; |
| private: |
| |
| template< class InputIterator > |
| void copy( InputIterator first, InputIterator last ) |
| { |
| std::copy( first, last, begin() ); |
| } |
| |
| void copy( const reversible_ptr_container& r ) |
| { |
| copy( r.begin(), r.end() ); |
| } |
| |
| void copy_clones_and_release( scoped_deleter& sd ) // nothrow |
| { |
| BOOST_ASSERT( size_type( std::distance( sd.begin(), sd.end() ) ) == c_.size() ); |
| std::copy( sd.begin(), sd.end(), c_.begin() ); |
| sd.release(); |
| } |
| |
| template< class ForwardIterator > |
| void clone_assign( ForwardIterator first, |
| ForwardIterator last ) // strong |
| { |
| BOOST_ASSERT( first != last ); |
| scoped_deleter sd( first, last ); // strong |
| copy_clones_and_release( sd ); // nothrow |
| } |
| |
| template< class ForwardIterator > |
| void clone_back_insert( ForwardIterator first, |
| ForwardIterator last ) |
| { |
| BOOST_ASSERT( first != last ); |
| scoped_deleter sd( first, last ); |
| insert_clones_and_release( sd, end() ); |
| } |
| |
| void remove_all() |
| { |
| remove( begin(), end() ); |
| } |
| |
| protected: |
| |
| void insert_clones_and_release( scoped_deleter& sd, |
| iterator where ) // strong |
| { |
| // |
| // 'c_.insert' always provides the strong guarantee for T* elements |
| // since a copy constructor of a pointer cannot throw |
| // |
| c_.insert( where.base(), |
| sd.begin(), sd.end() ); |
| sd.release(); |
| } |
| |
| void insert_clones_and_release( scoped_deleter& sd ) // strong |
| { |
| c_.insert( sd.begin(), sd.end() ); |
| sd.release(); |
| } |
| |
| template< class U > |
| void remove( U* ptr ) |
| { |
| null_policy_deallocate_clone( ptr ); |
| } |
| |
| template< class I > |
| void remove( I i ) |
| { |
| null_policy_deallocate_clone( Config::get_const_pointer(i) ); |
| } |
| |
| template< class I > |
| void remove( I first, I last ) |
| { |
| for( ; first != last; ++first ) |
| remove( first ); |
| } |
| |
| static void enforce_null_policy( const Ty_* x, const char* msg ) |
| { |
| if( !allow_null ) |
| { |
| BOOST_PTR_CONTAINER_THROW_EXCEPTION( 0 == x && "null not allowed", |
| bad_pointer, msg ); |
| } |
| } |
| |
| static Ty_* null_policy_allocate_clone( const Ty_* x ) |
| { |
| return null_cloner_type::allocate_clone( x ); |
| } |
| |
| static void null_policy_deallocate_clone( const Ty_* x ) |
| { |
| null_cloner_type::deallocate_clone( x ); |
| } |
| |
| private: |
| template< class ForwardIterator > |
| ForwardIterator advance( ForwardIterator beginArg, size_type n ) |
| { |
| ForwardIterator iter = beginArg; |
| std::advance( iter, n ); |
| return iter; |
| } |
| |
| template< class I > |
| void constructor_impl( I first, I last, std::input_iterator_tag ) // basic |
| { |
| while( first != last ) |
| { |
| insert( end(), null_cloner_type::allocate_clone_from_iterator(first) ); |
| ++first; |
| } |
| } |
| |
| template< class I > |
| void constructor_impl( I first, I last, std::forward_iterator_tag ) // strong |
| { |
| if( first == last ) |
| return; |
| clone_back_insert( first, last ); |
| } |
| |
| template< class I > |
| void associative_constructor_impl( I first, I last ) // strong |
| { |
| if( first == last ) |
| return; |
| |
| scoped_deleter sd( first, last ); |
| insert_clones_and_release( sd ); |
| } |
| |
| public: // foundation! should be protected! |
| reversible_ptr_container() |
| { } |
| |
| template< class SizeType > |
| reversible_ptr_container( SizeType n, unordered_associative_container_tag ) |
| : c_( n ) |
| { } |
| |
| template< class SizeType > |
| reversible_ptr_container( SizeType n, fixed_length_sequence_tag ) |
| : c_( n ) |
| { } |
| |
| template< class SizeType > |
| reversible_ptr_container( SizeType n, const allocator_type& a, |
| fixed_length_sequence_tag ) |
| : c_( n, a ) |
| { } |
| |
| explicit reversible_ptr_container( const allocator_type& a ) |
| : c_( a ) |
| { } |
| |
| template< class PtrContainer > |
| explicit reversible_ptr_container( std::auto_ptr<PtrContainer> clone ) |
| { |
| swap( *clone ); |
| } |
| |
| reversible_ptr_container( const reversible_ptr_container& r ) |
| { |
| constructor_impl( r.begin(), r.end(), std::forward_iterator_tag() ); |
| } |
| |
| template< class C, class V > |
| reversible_ptr_container( const reversible_ptr_container<C,V>& r ) |
| { |
| constructor_impl( r.begin(), r.end(), std::forward_iterator_tag() ); |
| } |
| |
| template< class PtrContainer > |
| reversible_ptr_container& operator=( std::auto_ptr<PtrContainer> clone ) // nothrow |
| { |
| swap( *clone ); |
| return *this; |
| } |
| |
| reversible_ptr_container& operator=( reversible_ptr_container r ) // strong |
| { |
| swap( r ); |
| return *this; |
| } |
| |
| // overhead: null-initilization of container pointer (very cheap compared to cloning) |
| // overhead: 1 heap allocation (very cheap compared to cloning) |
| template< class InputIterator > |
| reversible_ptr_container( InputIterator first, |
| InputIterator last, |
| const allocator_type& a = allocator_type() ) // basic, strong |
| : c_( a ) |
| { |
| constructor_impl( first, last, |
| #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) |
| #else |
| BOOST_DEDUCED_TYPENAME |
| #endif |
| iterator_category<InputIterator>::type() ); |
| } |
| |
| template< class Compare > |
| reversible_ptr_container( const Compare& comp, |
| const allocator_type& a ) |
| : c_( comp, a ) {} |
| |
| template< class ForwardIterator > |
| reversible_ptr_container( ForwardIterator first, |
| ForwardIterator last, |
| fixed_length_sequence_tag ) |
| : c_( std::distance(first,last) ) |
| { |
| constructor_impl( first, last, |
| std::forward_iterator_tag() ); |
| } |
| |
| template< class SizeType, class InputIterator > |
| reversible_ptr_container( SizeType n, |
| InputIterator first, |
| InputIterator last, |
| fixed_length_sequence_tag ) |
| : c_( n ) |
| { |
| constructor_impl( first, last, |
| #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) |
| #else |
| BOOST_DEDUCED_TYPENAME |
| #endif |
| iterator_category<InputIterator>::type() ); |
| } |
| |
| template< class Compare > |
| reversible_ptr_container( const Compare& comp, |
| const allocator_type& a, |
| associative_container_tag ) |
| : c_( comp, a ) |
| { } |
| |
| template< class InputIterator > |
| reversible_ptr_container( InputIterator first, |
| InputIterator last, |
| associative_container_tag ) |
| { |
| associative_constructor_impl( first, last ); |
| } |
| |
| template< class InputIterator, class Compare > |
| reversible_ptr_container( InputIterator first, |
| InputIterator last, |
| const Compare& comp, |
| const allocator_type& a, |
| associative_container_tag ) |
| : c_( comp, a ) |
| { |
| associative_constructor_impl( first, last ); |
| } |
| |
| explicit reversible_ptr_container( size_type n ) |
| : c_( n ) {} |
| |
| template< class Hash, class Pred > |
| reversible_ptr_container( const Hash& h, |
| const Pred& pred, |
| const allocator_type& a ) |
| : c_( h, pred, a ) {} |
| |
| template< class InputIterator, class Hash, class Pred > |
| reversible_ptr_container( InputIterator first, |
| InputIterator last, |
| const Hash& h, |
| const Pred& pred, |
| const allocator_type& a ) |
| : c_( h, pred, a ) |
| { |
| associative_constructor_impl( first, last ); |
| } |
| |
| public: |
| ~reversible_ptr_container() |
| { |
| remove_all(); |
| } |
| |
| public: |
| |
| allocator_type get_allocator() const |
| { |
| return c_.get_allocator(); |
| } |
| |
| public: // container requirements |
| iterator begin() |
| { return iterator( c_.begin() ); } |
| const_iterator begin() const |
| { return const_iterator( c_.begin() ); } |
| iterator end() |
| { return iterator( c_.end() ); } |
| const_iterator end() const |
| { return const_iterator( c_.end() ); } |
| |
| reverse_iterator rbegin() |
| { return reverse_iterator( this->end() ); } |
| const_reverse_iterator rbegin() const |
| { return const_reverse_iterator( this->end() ); } |
| reverse_iterator rend() |
| { return reverse_iterator( this->begin() ); } |
| const_reverse_iterator rend() const |
| { return const_reverse_iterator( this->begin() ); } |
| |
| const_iterator cbegin() const |
| { return const_iterator( c_.begin() ); } |
| const_iterator cend() const |
| { return const_iterator( c_.end() ); } |
| |
| const_reverse_iterator crbegin() const |
| { return const_reverse_iterator( this->end() ); } |
| const_reverse_iterator crend() const |
| { return const_reverse_iterator( this->begin() ); } |
| |
| void swap( reversible_ptr_container& r ) // nothrow |
| { |
| c_.swap( r.c_ ); |
| } |
| |
| size_type size() const // nothrow |
| { |
| return c_.size(); |
| } |
| |
| size_type max_size() const // nothrow |
| { |
| return c_.max_size(); |
| } |
| |
| bool empty() const // nothrow |
| { |
| return c_.empty(); |
| } |
| |
| public: // optional container requirements |
| |
| bool operator==( const reversible_ptr_container& r ) const // nothrow |
| { |
| if( size() != r.size() ) |
| return false; |
| else |
| return std::equal( begin(), end(), r.begin() ); |
| } |
| |
| bool operator!=( const reversible_ptr_container& r ) const // nothrow |
| { |
| return !(*this == r); |
| } |
| |
| bool operator<( const reversible_ptr_container& r ) const // nothrow |
| { |
| return std::lexicographical_compare( begin(), end(), r.begin(), r.end() ); |
| } |
| |
| bool operator<=( const reversible_ptr_container& r ) const // nothrow |
| { |
| return !(r < *this); |
| } |
| |
| bool operator>( const reversible_ptr_container& r ) const // nothrow |
| { |
| return r < *this; |
| } |
| |
| bool operator>=( const reversible_ptr_container& r ) const // nothrow |
| { |
| return !(*this < r); |
| } |
| |
| public: // modifiers |
| |
| iterator insert( iterator before, Ty_* x ) |
| { |
| enforce_null_policy( x, "Null pointer in 'insert()'" ); |
| |
| auto_type ptr( x ); // nothrow |
| iterator res( c_.insert( before.base(), x ) ); // strong, commit |
| ptr.release(); // nothrow |
| return res; |
| } |
| |
| template< class U > |
| iterator insert( iterator before, std::auto_ptr<U> x ) |
| { |
| return insert( before, x.release() ); |
| } |
| |
| iterator erase( iterator x ) // nothrow |
| { |
| BOOST_ASSERT( !empty() ); |
| BOOST_ASSERT( x != end() ); |
| |
| remove( x ); |
| return iterator( c_.erase( x.base() ) ); |
| } |
| |
| iterator erase( iterator first, iterator last ) // nothrow |
| { |
| remove( first, last ); |
| return iterator( c_.erase( first.base(), |
| last.base() ) ); |
| } |
| |
| template< class Range > |
| iterator erase( const Range& r ) |
| { |
| return erase( boost::begin(r), boost::end(r) ); |
| } |
| |
| void clear() |
| { |
| remove_all(); |
| c_.clear(); |
| } |
| |
| public: // access interface |
| |
| auto_type release( iterator where ) |
| { |
| BOOST_ASSERT( where != end() ); |
| |
| BOOST_PTR_CONTAINER_THROW_EXCEPTION( empty(), bad_ptr_container_operation, |
| "'release()' on empty container" ); |
| |
| auto_type ptr( Config::get_pointer( where ) ); // nothrow |
| c_.erase( where.base() ); // nothrow |
| return boost::ptr_container_detail::move( ptr ); |
| } |
| |
| auto_type replace( iterator where, Ty_* x ) // strong |
| { |
| BOOST_ASSERT( where != end() ); |
| |
| enforce_null_policy( x, "Null pointer in 'replace()'" ); |
| |
| auto_type ptr( x ); |
| |
| BOOST_PTR_CONTAINER_THROW_EXCEPTION( empty(), bad_ptr_container_operation, |
| "'replace()' on empty container" ); |
| |
| auto_type old( Config::get_pointer( where ) ); // nothrow |
| const_cast<void*&>(*where.base()) = ptr.release(); |
| return boost::ptr_container_detail::move( old ); |
| } |
| |
| template< class U > |
| auto_type replace( iterator where, std::auto_ptr<U> x ) |
| { |
| return replace( where, x.release() ); |
| } |
| |
| auto_type replace( size_type idx, Ty_* x ) // strong |
| { |
| enforce_null_policy( x, "Null pointer in 'replace()'" ); |
| |
| auto_type ptr( x ); |
| |
| BOOST_PTR_CONTAINER_THROW_EXCEPTION( idx >= size(), bad_index, |
| "'replace()' out of bounds" ); |
| |
| auto_type old( static_cast<Ty_*>( c_[idx] ) ); // nothrow |
| c_[idx] = ptr.release(); // nothrow, commit |
| return boost::ptr_container_detail::move( old ); |
| } |
| |
| template< class U > |
| auto_type replace( size_type idx, std::auto_ptr<U> x ) |
| { |
| return replace( idx, x.release() ); |
| } |
| |
| }; // 'reversible_ptr_container' |
| |
| |
| #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) |
| #define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \ |
| typename base_type::auto_type \ |
| release( typename base_type::iterator i ) \ |
| { \ |
| return boost::ptr_container_detail::move(base_type::release(i)); \ |
| } |
| #else |
| #define BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \ |
| using base_type::release; |
| #endif |
| |
| // |
| // two-phase lookup of template functions |
| // is buggy on most compilers, so we use a macro instead |
| // |
| #define BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type ) \ |
| explicit PC( std::auto_ptr<this_type> r ) \ |
| : base_type ( r ) { } \ |
| \ |
| PC& operator=( std::auto_ptr<this_type> r ) \ |
| { \ |
| base_type::operator=( r ); \ |
| return *this; \ |
| } \ |
| \ |
| std::auto_ptr<this_type> release() \ |
| { \ |
| std::auto_ptr<this_type> ptr( new this_type );\ |
| this->swap( *ptr ); \ |
| return ptr; \ |
| } \ |
| BOOST_PTR_CONTAINER_DEFINE_RELEASE( base_type ) \ |
| \ |
| std::auto_ptr<this_type> clone() const \ |
| { \ |
| return std::auto_ptr<this_type>( new this_type( this->begin(), this->end() ) ); \ |
| } |
| |
| #define BOOST_PTR_CONTAINER_DEFINE_COPY_CONSTRUCTORS( PC, base_type ) \ |
| \ |
| template< class U > \ |
| PC( const PC<U>& r ) : base_type( r ) { } \ |
| \ |
| PC& operator=( PC r ) \ |
| { \ |
| this->swap( r ); \ |
| return *this; \ |
| } \ |
| |
| |
| #define BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type ) \ |
| typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator; \ |
| typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type; \ |
| typedef BOOST_DEDUCED_TYPENAME base_type::const_reference const_reference; \ |
| typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type allocator_type; \ |
| PC() {} \ |
| explicit PC( const allocator_type& a ) : base_type(a) {} \ |
| template< class InputIterator > \ |
| PC( InputIterator first, InputIterator last ) : base_type( first, last ) {} \ |
| template< class InputIterator > \ |
| PC( InputIterator first, InputIterator last, \ |
| const allocator_type& a ) : base_type( first, last, a ) {} |
| |
| #define BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type ) \ |
| BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( PC, base_type ) \ |
| BOOST_PTR_CONTAINER_DEFINE_RELEASE_AND_CLONE( PC, base_type, this_type ) |
| |
| #define BOOST_PTR_CONTAINER_DEFINE_SEQEUENCE_MEMBERS( PC, base_type, this_type ) \ |
| BOOST_PTR_CONTAINER_DEFINE_NON_INHERITED_MEMBERS( PC, base_type, this_type ) \ |
| BOOST_PTR_CONTAINER_DEFINE_COPY_CONSTRUCTORS( PC, base_type ) |
| |
| } // namespace 'ptr_container_detail' |
| |
| // |
| // @remark: expose movability of internal move-pointer |
| // |
| namespace ptr_container |
| { |
| using ptr_container_detail::move; |
| } |
| |
| } // namespace 'boost' |
| |
| #if BOOST_WORKAROUND(BOOST_MSVC, >= 1400) |
| #pragma warning(pop) |
| #endif |
| |
| #endif |