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_PTR_SEQUENCE_ADAPTER_HPP |
13 | #define BOOST_PTR_CONTAINER_PTR_SEQUENCE_ADAPTER_HPP |
14 | |
15 | #if defined(_MSC_VER) && (_MSC_VER >= 1200) |
16 | # pragma once |
17 | #endif |
18 | |
19 | |
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/type_traits/remove_pointer.hpp> |
24 | #include <boost/type_traits/is_same.hpp> |
25 | |
26 | |
27 | namespace boost |
28 | { |
29 | namespace ptr_container_detail |
30 | { |
31 | template |
32 | < |
33 | class T, |
34 | class VoidPtrSeq |
35 | > |
36 | struct sequence_config |
37 | { |
38 | typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type |
39 | U; |
40 | typedef VoidPtrSeq |
41 | void_container_type; |
42 | |
43 | typedef BOOST_DEDUCED_TYPENAME VoidPtrSeq::allocator_type |
44 | allocator_type; |
45 | |
46 | typedef U value_type; |
47 | |
48 | typedef void_ptr_iterator< |
49 | BOOST_DEDUCED_TYPENAME VoidPtrSeq::iterator, U > |
50 | iterator; |
51 | |
52 | typedef void_ptr_iterator< |
53 | BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_iterator, const U > |
54 | const_iterator; |
55 | |
56 | #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) |
57 | |
58 | template< class Iter > |
59 | static U* get_pointer( Iter i ) |
60 | { |
61 | return static_cast<U*>( *i.base() ); |
62 | } |
63 | |
64 | #else |
65 | template< class Iter > |
66 | static U* get_pointer( void_ptr_iterator<Iter,U> i ) |
67 | { |
68 | return static_cast<U*>( *i.base() ); |
69 | } |
70 | |
71 | template< class Iter > |
72 | static U* get_pointer( Iter i ) |
73 | { |
74 | return &*i; |
75 | } |
76 | #endif |
77 | |
78 | #if defined(BOOST_NO_SFINAE) && !BOOST_WORKAROUND(__MWERKS__, <= 0x3003) |
79 | |
80 | template< class Iter > |
81 | static const U* get_const_pointer( Iter i ) |
82 | { |
83 | return static_cast<const U*>( *i.base() ); |
84 | } |
85 | |
86 | #else // BOOST_NO_SFINAE |
87 | |
88 | #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) |
89 | template< class Iter > |
90 | static const U* get_const_pointer( void_ptr_iterator<Iter,U> i ) |
91 | { |
92 | return static_cast<const U*>( *i.base() ); |
93 | } |
94 | #else // BOOST_WORKAROUND |
95 | template< class Iter > |
96 | static const U* get_const_pointer( void_ptr_iterator<Iter,const U> i ) |
97 | { |
98 | return static_cast<const U*>( *i.base() ); |
99 | } |
100 | #endif // BOOST_WORKAROUND |
101 | |
102 | template< class Iter > |
103 | static const U* get_const_pointer( Iter i ) |
104 | { |
105 | return &*i; |
106 | } |
107 | #endif // BOOST_NO_SFINAE |
108 | |
109 | BOOST_STATIC_CONSTANT(bool, allow_null = boost::is_nullable<T>::value ); |
110 | }; |
111 | |
112 | } // ptr_container_detail |
113 | |
114 | |
115 | template< class Iterator, class T > |
116 | inline bool is_null( void_ptr_iterator<Iterator,T> i ) |
117 | { |
118 | return *i.base() == 0; |
119 | } |
120 | |
121 | |
122 | |
123 | template |
124 | < |
125 | class T, |
126 | class VoidPtrSeq, |
127 | class CloneAllocator = heap_clone_allocator |
128 | > |
129 | class ptr_sequence_adapter : public |
130 | ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>, |
131 | CloneAllocator > |
132 | { |
133 | typedef ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>, |
134 | CloneAllocator > |
135 | base_type; |
136 | |
137 | typedef ptr_sequence_adapter<T,VoidPtrSeq,CloneAllocator> |
138 | this_type; |
139 | |
140 | protected: |
141 | typedef BOOST_DEDUCED_TYPENAME base_type::scoped_deleter scoped_deleter; |
142 | |
143 | public: |
144 | typedef BOOST_DEDUCED_TYPENAME base_type::value_type value_type; |
145 | typedef BOOST_DEDUCED_TYPENAME base_type::reference reference; |
146 | typedef BOOST_DEDUCED_TYPENAME base_type::const_reference |
147 | const_reference; |
148 | typedef BOOST_DEDUCED_TYPENAME base_type::auto_type auto_type; |
149 | typedef BOOST_DEDUCED_TYPENAME base_type::clone_allocator_type |
150 | clone_allocator_type; |
151 | typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator; |
152 | typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type; |
153 | typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type |
154 | allocator_type; |
155 | |
156 | ptr_sequence_adapter() |
157 | { } |
158 | |
159 | template< class Allocator > |
160 | explicit ptr_sequence_adapter( const Allocator& a ) |
161 | : base_type( a ) |
162 | { } |
163 | |
164 | template< class SizeType > |
165 | ptr_sequence_adapter( SizeType n, |
166 | ptr_container_detail::fixed_length_sequence_tag tag ) |
167 | : base_type( n, tag ) |
168 | { } |
169 | |
170 | template< class SizeType, class Allocator > |
171 | ptr_sequence_adapter( SizeType n, const Allocator& a, |
172 | ptr_container_detail::fixed_length_sequence_tag tag ) |
173 | : base_type( n, a, tag ) |
174 | { } |
175 | |
176 | template< class InputIterator > |
177 | ptr_sequence_adapter( InputIterator first, InputIterator last ) |
178 | : base_type( first, last ) |
179 | { } |
180 | |
181 | template< class InputIterator, class Allocator > |
182 | ptr_sequence_adapter( InputIterator first, InputIterator last, |
183 | const Allocator& a ) |
184 | : base_type( first, last, a ) |
185 | { } |
186 | |
187 | template< class ForwardIterator > |
188 | ptr_sequence_adapter( ForwardIterator first, |
189 | ForwardIterator last, |
190 | ptr_container_detail::fixed_length_sequence_tag tag ) |
191 | : base_type( first, last, tag ) |
192 | { } |
193 | |
194 | template< class SizeType, class ForwardIterator > |
195 | ptr_sequence_adapter( SizeType n, |
196 | ForwardIterator first, |
197 | ForwardIterator last, |
198 | ptr_container_detail::fixed_length_sequence_tag tag ) |
199 | : base_type( n, first, last, tag ) |
200 | { } |
201 | |
202 | ptr_sequence_adapter( const ptr_sequence_adapter& r ) |
203 | : base_type( r ) |
204 | { } |
205 | |
206 | template< class U > |
207 | ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r ) |
208 | : base_type( r ) |
209 | { } |
210 | |
211 | ptr_sequence_adapter( const ptr_sequence_adapter& r, |
212 | ptr_container_detail::fixed_length_sequence_tag tag ) |
213 | : base_type( r, tag ) |
214 | { } |
215 | |
216 | template< class U > |
217 | ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r, |
218 | ptr_container_detail::fixed_length_sequence_tag tag ) |
219 | : base_type( r, tag ) |
220 | { } |
221 | |
222 | template< class PtrContainer > |
223 | explicit ptr_sequence_adapter( std::auto_ptr<PtrContainer> clone ) |
224 | : base_type( clone ) |
225 | { } |
226 | |
227 | ptr_sequence_adapter& operator=( const ptr_sequence_adapter r ) |
228 | { |
229 | this->swap( r ); |
230 | return *this; |
231 | } |
232 | |
233 | template< class PtrContainer > |
234 | ptr_sequence_adapter& operator=( std::auto_ptr<PtrContainer> clone ) |
235 | { |
236 | base_type::operator=( clone ); |
237 | return *this; |
238 | } |
239 | |
240 | ///////////////////////////////////////////////////////////// |
241 | // modifiers |
242 | ///////////////////////////////////////////////////////////// |
243 | |
244 | void push_back( value_type x ) // strong |
245 | { |
246 | this->enforce_null_policy( x, "Null pointer in 'push_back()'" ); |
247 | |
248 | auto_type ptr( x ); // notrow |
249 | this->base().push_back( x ); // strong, commit |
250 | ptr.release(); // nothrow |
251 | } |
252 | |
253 | template< class U > |
254 | void push_back( std::auto_ptr<U> x ) |
255 | { |
256 | push_back( x.release() ); |
257 | } |
258 | |
259 | void push_front( value_type x ) |
260 | { |
261 | this->enforce_null_policy( x, "Null pointer in 'push_front()'" ); |
262 | |
263 | auto_type ptr( x ); // nothrow |
264 | this->base().push_front( x ); // strong, commit |
265 | ptr.release(); // nothrow |
266 | } |
267 | |
268 | template< class U > |
269 | void push_front( std::auto_ptr<U> x ) |
270 | { |
271 | push_front( x.release() ); |
272 | } |
273 | |
274 | auto_type pop_back() |
275 | { |
276 | BOOST_ASSERT( !this->empty() && |
277 | "'pop_back()' on empty container" ); |
278 | auto_type ptr( static_cast<value_type>( this->base().back() ) ); |
279 | // nothrow |
280 | this->base().pop_back(); // nothrow |
281 | return ptr_container_detail::move( ptr ); // nothrow |
282 | } |
283 | |
284 | auto_type pop_front() |
285 | { |
286 | BOOST_ASSERT( !this->empty() && |
287 | "'pop_front()' on empty container" ); |
288 | auto_type ptr( static_cast<value_type>( this->base().front() ) ); |
289 | // nothrow |
290 | this->base().pop_front(); // nothrow |
291 | return ptr_container_detail::move( ptr ); |
292 | } |
293 | |
294 | reference front() |
295 | { |
296 | BOOST_ASSERT( !this->empty() && |
297 | "accessing 'front()' on empty container" ); |
298 | |
299 | BOOST_ASSERT( !::boost::is_null( this->begin() ) ); |
300 | return *this->begin(); |
301 | } |
302 | |
303 | const_reference front() const |
304 | { |
305 | return const_cast<ptr_sequence_adapter*>(this)->front(); |
306 | } |
307 | |
308 | reference back() |
309 | { |
310 | BOOST_ASSERT( !this->empty() && |
311 | "accessing 'back()' on empty container" ); |
312 | BOOST_ASSERT( !::boost::is_null( --this->end() ) ); |
313 | return *--this->end(); |
314 | } |
315 | |
316 | const_reference back() const |
317 | { |
318 | return const_cast<ptr_sequence_adapter*>(this)->back(); |
319 | } |
320 | |
321 | public: // deque/vector inerface |
322 | |
323 | reference operator[]( size_type n ) // nothrow |
324 | { |
325 | BOOST_ASSERT( n < this->size() ); |
326 | BOOST_ASSERT( !this->is_null( n ) ); |
327 | return *static_cast<value_type>( this->base()[n] ); |
328 | } |
329 | |
330 | const_reference operator[]( size_type n ) const // nothrow |
331 | { |
332 | BOOST_ASSERT( n < this->size() ); |
333 | BOOST_ASSERT( !this->is_null( n ) ); |
334 | return *static_cast<value_type>( this->base()[n] ); |
335 | } |
336 | |
337 | reference at( size_type n ) |
338 | { |
339 | BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, |
340 | "'at()' out of bounds" ); |
341 | BOOST_ASSERT( !this->is_null( n ) ); |
342 | return (*this)[n]; |
343 | } |
344 | |
345 | const_reference at( size_type n ) const |
346 | { |
347 | BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, |
348 | "'at()' out of bounds" ); |
349 | BOOST_ASSERT( !this->is_null( n ) ); |
350 | return (*this)[n]; |
351 | } |
352 | |
353 | public: // vector interface |
354 | |
355 | size_type capacity() const |
356 | { |
357 | return this->base().capacity(); |
358 | } |
359 | |
360 | void reserve( size_type n ) |
361 | { |
362 | this->base().reserve( n ); |
363 | } |
364 | |
365 | void reverse() |
366 | { |
367 | this->base().reverse(); |
368 | } |
369 | |
370 | public: // assign, insert, transfer |
371 | |
372 | // overhead: 1 heap allocation (very cheap compared to cloning) |
373 | template< class InputIterator > |
374 | void assign( InputIterator first, InputIterator last ) // strong |
375 | { |
376 | base_type temp( first, last ); |
377 | this->swap( temp ); |
378 | } |
379 | |
380 | template< class Range > |
381 | void assign( const Range& r ) // strong |
382 | { |
383 | assign( boost::begin(r), boost::end(r ) ); |
384 | } |
385 | |
386 | private: |
387 | template< class I > |
388 | void insert_impl( iterator before, I first, I last, std::input_iterator_tag ) // strong |
389 | { |
390 | ptr_sequence_adapter temp(first,last); // strong |
391 | transfer( before, temp ); // strong, commit |
392 | } |
393 | |
394 | template< class I > |
395 | void insert_impl( iterator before, I first, I last, std::forward_iterator_tag ) // strong |
396 | { |
397 | if( first == last ) |
398 | return; |
399 | scoped_deleter sd( first, last ); // strong |
400 | this->insert_clones_and_release( sd, before ); // strong, commit |
401 | } |
402 | |
403 | public: |
404 | |
405 | using base_type::insert; |
406 | |
407 | template< class InputIterator > |
408 | void insert( iterator before, InputIterator first, InputIterator last ) // strong |
409 | { |
410 | insert_impl( before, first, last, BOOST_DEDUCED_TYPENAME |
411 | iterator_category<InputIterator>::type() ); |
412 | } |
413 | |
414 | #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) |
415 | #else |
416 | template< class Range > |
417 | BOOST_DEDUCED_TYPENAME |
418 | boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type |
419 | insert( iterator before, const Range& r ) |
420 | { |
421 | insert( before, boost::begin(r), boost::end(r) ); |
422 | } |
423 | |
424 | #endif |
425 | |
426 | template< class PtrSeqAdapter > |
427 | void transfer( iterator before, |
428 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator first, |
429 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator last, |
430 | PtrSeqAdapter& from ) // strong |
431 | { |
432 | BOOST_ASSERT( (void*)&from != (void*)this ); |
433 | if( from.empty() ) |
434 | return; |
435 | this->base(). |
436 | insert( before.base(), first.base(), last.base() ); // strong |
437 | from.base().erase( first.base(), last.base() ); // nothrow |
438 | } |
439 | |
440 | template< class PtrSeqAdapter > |
441 | void transfer( iterator before, |
442 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator object, |
443 | PtrSeqAdapter& from ) // strong |
444 | { |
445 | BOOST_ASSERT( (void*)&from != (void*)this ); |
446 | if( from.empty() ) |
447 | return; |
448 | this->base().insert( before.base(), *object.base() ); // strong |
449 | from.base().erase( object.base() ); // nothrow |
450 | } |
451 | |
452 | #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) |
453 | #else |
454 | |
455 | template< class PtrSeqAdapter, class Range > |
456 | BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range, |
457 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator > >::type |
458 | transfer( iterator before, const Range& r, PtrSeqAdapter& from ) // strong |
459 | { |
460 | transfer( before, boost::begin(r), boost::end(r), from ); |
461 | } |
462 | |
463 | #endif |
464 | template< class PtrSeqAdapter > |
465 | void transfer( iterator before, PtrSeqAdapter& from ) // strong |
466 | { |
467 | BOOST_ASSERT( (void*)&from != (void*)this ); |
468 | if( from.empty() ) |
469 | return; |
470 | this->base(). |
471 | insert( before.base(), |
472 | from.begin().base(), from.end().base() ); // strong |
473 | from.base().clear(); // nothrow |
474 | } |
475 | |
476 | public: // C-array support |
477 | |
478 | void transfer( iterator before, value_type* from, |
479 | size_type size, bool delete_from = true ) // strong |
480 | { |
481 | BOOST_ASSERT( from != 0 ); |
482 | if( delete_from ) |
483 | { |
484 | BOOST_DEDUCED_TYPENAME base_type::scoped_deleter |
485 | deleter( from, size ); // nothrow |
486 | this->base().insert( before.base(), from, from + size ); // strong |
487 | deleter.release(); // nothrow |
488 | } |
489 | else |
490 | { |
491 | this->base().insert( before.base(), from, from + size ); // strong |
492 | } |
493 | } |
494 | |
495 | value_type* c_array() // nothrow |
496 | { |
497 | if( this->empty() ) |
498 | return 0; |
499 | T** res = reinterpret_cast<T**>( &this->begin().base()[0] ); |
500 | return res; |
501 | } |
502 | |
503 | public: // null functions |
504 | |
505 | bool is_null( size_type idx ) const |
506 | { |
507 | BOOST_ASSERT( idx < this->size() ); |
508 | return this->base()[idx] == 0; |
509 | } |
510 | |
511 | public: // resize |
512 | |
513 | void resize( size_type size ) // basic |
514 | { |
515 | size_type old_size = this->size(); |
516 | if( old_size > size ) |
517 | { |
518 | this->erase( boost::next( this->begin(), size ), this->end() ); |
519 | } |
520 | else if( size > old_size ) |
521 | { |
522 | for( ; old_size != size; ++old_size ) |
523 | this->push_back( new BOOST_DEDUCED_TYPENAME |
524 | boost::remove_pointer<value_type>::type() ); |
525 | } |
526 | |
527 | BOOST_ASSERT( this->size() == size ); |
528 | } |
529 | |
530 | void resize( size_type size, value_type to_clone ) // basic |
531 | { |
532 | size_type old_size = this->size(); |
533 | if( old_size > size ) |
534 | { |
535 | this->erase( boost::next( this->begin(), size ), this->end() ); |
536 | } |
537 | else if( size > old_size ) |
538 | { |
539 | for( ; old_size != size; ++old_size ) |
540 | this->push_back( this->null_policy_allocate_clone( to_clone ) ); |
541 | } |
542 | |
543 | BOOST_ASSERT( this->size() == size ); |
544 | } |
545 | |
546 | void rresize( size_type size ) // basic |
547 | { |
548 | size_type old_size = this->size(); |
549 | if( old_size > size ) |
550 | { |
551 | this->erase( this->begin(), |
552 | boost::next( this->begin(), old_size - size ) ); |
553 | } |
554 | else if( size > old_size ) |
555 | { |
556 | for( ; old_size != size; ++old_size ) |
557 | this->push_front( new BOOST_DEDUCED_TYPENAME |
558 | boost::remove_pointer<value_type>::type() ); |
559 | } |
560 | |
561 | BOOST_ASSERT( this->size() == size ); |
562 | } |
563 | |
564 | void rresize( size_type size, value_type to_clone ) // basic |
565 | { |
566 | size_type old_size = this->size(); |
567 | if( old_size > size ) |
568 | { |
569 | this->erase( this->begin(), |
570 | boost::next( this->begin(), old_size - size ) ); |
571 | } |
572 | else if( size > old_size ) |
573 | { |
574 | for( ; old_size != size; ++old_size ) |
575 | this->push_front( this->null_policy_allocate_clone( to_clone ) ); |
576 | } |
577 | |
578 | BOOST_ASSERT( this->size() == size ); |
579 | } |
580 | |
581 | public: // algorithms |
582 | |
583 | void sort( iterator first, iterator last ) |
584 | { |
585 | sort( first, last, std::less<T>() ); |
586 | } |
587 | |
588 | void sort() |
589 | { |
590 | sort( this->begin(), this->end() ); |
591 | } |
592 | |
593 | template< class Compare > |
594 | void sort( iterator first, iterator last, Compare comp ) |
595 | { |
596 | BOOST_ASSERT( first <= last && "out of range sort()" ); |
597 | BOOST_ASSERT( this->begin() <= first && "out of range sort()" ); |
598 | BOOST_ASSERT( last <= this->end() && "out of range sort()" ); |
599 | // some static assert on the arguments of the comparison |
600 | std::sort( first.base(), last.base(), |
601 | void_ptr_indirect_fun<Compare,T>(comp) ); |
602 | } |
603 | |
604 | template< class Compare > |
605 | void sort( Compare comp ) |
606 | { |
607 | sort( this->begin(), this->end(), comp ); |
608 | } |
609 | |
610 | void unique( iterator first, iterator last ) |
611 | { |
612 | unique( first, last, std::equal_to<T>() ); |
613 | } |
614 | |
615 | void unique() |
616 | { |
617 | unique( this->begin(), this->end() ); |
618 | } |
619 | |
620 | private: |
621 | struct is_not_zero_ptr |
622 | { |
623 | template< class U > |
624 | bool operator()( const U* r ) const |
625 | { |
626 | return r != 0; |
627 | } |
628 | }; |
629 | |
630 | protected: |
631 | template< class Fun, class Arg1 > |
632 | class void_ptr_delete_if |
633 | { |
634 | Fun fun; |
635 | public: |
636 | |
637 | void_ptr_delete_if() : fun(Fun()) |
638 | { } |
639 | |
640 | void_ptr_delete_if( Fun f ) : fun(f) |
641 | { } |
642 | |
643 | bool operator()( void* r ) const |
644 | { |
645 | BOOST_ASSERT( r != 0 ); |
646 | Arg1 arg1 = static_cast<Arg1>(r); |
647 | if( fun( *arg1 ) ) |
648 | { |
649 | clone_allocator_type::deallocate_clone( arg1 ); |
650 | return true; |
651 | } |
652 | return false; |
653 | } |
654 | }; |
655 | |
656 | private: |
657 | void compact_and_erase_nulls( iterator first, iterator last ) // nothrow |
658 | { |
659 | typename base_type::ptr_iterator p = std::stable_partition( |
660 | first.base(), |
661 | last.base(), |
662 | is_not_zero_ptr() ); |
663 | this->base().erase( p, this->end().base() ); |
664 | |
665 | } |
666 | |
667 | void range_check_impl( iterator first, iterator last, |
668 | std::bidirectional_iterator_tag ) |
669 | { /* do nothing */ } |
670 | |
671 | void range_check_impl( iterator first, iterator last, |
672 | std::random_access_iterator_tag ) |
673 | { |
674 | BOOST_ASSERT( first <= last && "out of range unique()/erase_if()" ); |
675 | BOOST_ASSERT( this->begin() <= first && "out of range unique()/erase_if()" ); |
676 | BOOST_ASSERT( last <= this->end() && "out of range unique()/erase_if)(" ); |
677 | } |
678 | |
679 | void range_check( iterator first, iterator last ) |
680 | { |
681 | range_check_impl( first, last, |
682 | BOOST_DEDUCED_TYPENAME iterator_category<iterator>::type() ); |
683 | } |
684 | |
685 | public: |
686 | |
687 | template< class Compare > |
688 | void unique( iterator first, iterator last, Compare comp ) |
689 | { |
690 | range_check(first,last); |
691 | |
692 | iterator prev = first; |
693 | iterator next = first; |
694 | ++next; |
695 | for( ; next != last; ++next ) |
696 | { |
697 | BOOST_ASSERT( !::boost::is_null(prev) ); |
698 | BOOST_ASSERT( !::boost::is_null(next) ); |
699 | if( comp( *prev, *next ) ) |
700 | { |
701 | this->remove( next ); // delete object |
702 | *next.base() = 0; // mark pointer as deleted |
703 | } |
704 | else |
705 | { |
706 | prev = next; |
707 | } |
708 | // ++next |
709 | } |
710 | |
711 | compact_and_erase_nulls( first, last ); |
712 | } |
713 | |
714 | template< class Compare > |
715 | void unique( Compare comp ) |
716 | { |
717 | unique( this->begin(), this->end(), comp ); |
718 | } |
719 | |
720 | template< class Pred > |
721 | void erase_if( iterator first, iterator last, Pred pred ) |
722 | { |
723 | range_check(first,last); |
724 | this->base().erase( std::remove_if( first.base(), last.base(), |
725 | void_ptr_delete_if<Pred,value_type>(pred) ), |
726 | last.base() ); |
727 | } |
728 | |
729 | template< class Pred > |
730 | void erase_if( Pred pred ) |
731 | { |
732 | erase_if( this->begin(), this->end(), pred ); |
733 | } |
734 | |
735 | |
736 | void merge( iterator first, iterator last, |
737 | ptr_sequence_adapter& from ) |
738 | { |
739 | merge( first, last, from, std::less<T>() ); |
740 | } |
741 | |
742 | template< class BinPred > |
743 | void merge( iterator first, iterator last, |
744 | ptr_sequence_adapter& from, BinPred pred ) |
745 | { |
746 | void_ptr_indirect_fun<BinPred,T> bin_pred(pred); |
747 | size_type current_size = this->size(); |
748 | this->transfer( this->end(), first, last, from ); |
749 | typename base_type::ptr_iterator middle = this->begin().base(); |
750 | std::advance(middle,current_size); |
751 | std::inplace_merge( this->begin().base(), |
752 | middle, |
753 | this->end().base(), |
754 | bin_pred ); |
755 | } |
756 | |
757 | void merge( ptr_sequence_adapter& r ) |
758 | { |
759 | merge( r, std::less<T>() ); |
760 | BOOST_ASSERT( r.empty() ); |
761 | } |
762 | |
763 | template< class BinPred > |
764 | void merge( ptr_sequence_adapter& r, BinPred pred ) |
765 | { |
766 | merge( r.begin(), r.end(), r, pred ); |
767 | BOOST_ASSERT( r.empty() ); |
768 | } |
769 | |
770 | }; |
771 | |
772 | |
773 | } // namespace 'boost' |
774 | |
775 | #endif |
776 | |