Line data Source code
1 : /* Multiply indexed container.
2 : *
3 : * Copyright 2003-2023 Joaquin M Lopez Munoz.
4 : * Distributed under the Boost Software License, Version 1.0.
5 : * (See accompanying file LICENSE_1_0.txt or copy at
6 : * http://www.boost.org/LICENSE_1_0.txt)
7 : *
8 : * See http://www.boost.org/libs/multi_index for library home page.
9 : */
10 :
11 : #ifndef BOOST_MULTI_INDEX_HPP
12 : #define BOOST_MULTI_INDEX_HPP
13 :
14 : #if defined(_MSC_VER)
15 : #pragma once
16 : #endif
17 :
18 : #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
19 : #include <algorithm>
20 : #include <boost/core/addressof.hpp>
21 : #include <boost/core/no_exceptions_support.hpp>
22 : #include <boost/detail/workaround.hpp>
23 : #include <boost/move/core.hpp>
24 : #include <boost/move/utility_core.hpp>
25 : #include <boost/mpl/at.hpp>
26 : #include <boost/mpl/contains.hpp>
27 : #include <boost/mpl/find_if.hpp>
28 : #include <boost/mpl/identity.hpp>
29 : #include <boost/mpl/int.hpp>
30 : #include <boost/mpl/size.hpp>
31 : #include <boost/mpl/deref.hpp>
32 : #include <boost/multi_index_container_fwd.hpp>
33 : #include <boost/multi_index/detail/access_specifier.hpp>
34 : #include <boost/multi_index/detail/adl_swap.hpp>
35 : #include <boost/multi_index/detail/allocator_traits.hpp>
36 : #include <boost/multi_index/detail/base_type.hpp>
37 : #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
38 : #include <boost/multi_index/detail/converter.hpp>
39 : #include <boost/multi_index/detail/header_holder.hpp>
40 : #include <boost/multi_index/detail/has_tag.hpp>
41 : #include <boost/multi_index/detail/invalidate_iterators.hpp>
42 : #include <boost/multi_index/detail/no_duplicate_tags.hpp>
43 : #include <boost/multi_index/detail/safe_mode.hpp>
44 : #include <boost/multi_index/detail/scope_guard.hpp>
45 : #include <boost/multi_index/detail/vartempl_support.hpp>
46 : #include <boost/static_assert.hpp>
47 : #include <boost/type_traits/integral_constant.hpp>
48 : #include <boost/type_traits/is_same.hpp>
49 : #include <boost/utility/base_from_member.hpp>
50 :
51 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
52 : #include <initializer_list>
53 : #endif
54 :
55 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
56 : #include <boost/core/serialization.hpp>
57 : #include <boost/multi_index/detail/archive_constructed.hpp>
58 : #include <boost/multi_index/detail/bad_archive_exception.hpp>
59 : #include <boost/multi_index/detail/serialization_version.hpp>
60 : #include <boost/throw_exception.hpp>
61 :
62 : #if defined(BOOST_MULTI_INDEX_ENABLE_SERIALIZATION_COMPATIBILITY_V2)
63 : #define BOOST_MULTI_INDEX_BLOCK_BOOSTDEP_HEADER \
64 : <boost/serialization/collection_size_type.hpp>
65 : #include BOOST_MULTI_INDEX_BLOCK_BOOSTDEP_HEADER
66 : #undef BOOST_MULTI_INDEX_BLOCK_BOOSTDEP_HEADER
67 : #endif
68 : #endif
69 :
70 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
71 : #include <boost/multi_index/detail/invariant_assert.hpp>
72 : #define BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x) \
73 : detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
74 : detail::make_obj_guard(x,&multi_index_container::check_invariant_); \
75 : BOOST_JOIN(check_invariant_,__LINE__).touch();
76 : #define BOOST_MULTI_INDEX_CHECK_INVARIANT \
77 : BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(*this)
78 : #else
79 : #define BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x)
80 : #define BOOST_MULTI_INDEX_CHECK_INVARIANT
81 : #endif
82 :
83 : namespace boost{
84 :
85 : namespace multi_index{
86 :
87 : namespace detail{
88 :
89 : struct unequal_alloc_move_ctor_tag{};
90 :
91 : } /* namespace multi_index::detail */
92 :
93 : #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
94 : #pragma warning(push)
95 : #pragma warning(disable:4522) /* spurious warning on multiple operator=()'s */
96 : #endif
97 :
98 : template<typename Value,typename IndexSpecifierList,typename Allocator>
99 : class multi_index_container:
100 : private ::boost::base_from_member<
101 : typename detail::rebind_alloc_for<
102 : Allocator,
103 : typename detail::multi_index_node_type<
104 : Value,IndexSpecifierList,Allocator>::type
105 : >::type
106 : >,
107 : BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS detail::header_holder<
108 : typename detail::allocator_traits<
109 : typename detail::rebind_alloc_for<
110 : Allocator,
111 : typename detail::multi_index_node_type<
112 : Value,IndexSpecifierList,Allocator>::type
113 : >::type
114 : >::pointer,
115 : multi_index_container<Value,IndexSpecifierList,Allocator> >,
116 : public detail::multi_index_base_type<
117 : Value,IndexSpecifierList,Allocator>::type
118 : {
119 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
120 : BOOST_WORKAROUND(__MWERKS__,<=0x3003)
121 : /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
122 : * lifetime of const references bound to temporaries --precisely what
123 : * scopeguards are.
124 : */
125 :
126 : #pragma parse_mfunc_templ off
127 : #endif
128 :
129 : private:
130 : BOOST_COPYABLE_AND_MOVABLE(multi_index_container)
131 :
132 : #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
133 : template <typename,typename,typename> friend class detail::index_base;
134 : template <typename,typename> friend struct detail::header_holder;
135 : template <typename,typename> friend struct detail::converter;
136 : #endif
137 :
138 : typedef typename detail::multi_index_base_type<
139 : Value,IndexSpecifierList,Allocator>::type super;
140 : typedef typename detail::rebind_alloc_for<
141 : Allocator,
142 : typename super::index_node_type
143 : >::type node_allocator;
144 : typedef detail::allocator_traits<node_allocator> node_alloc_traits;
145 : typedef typename node_alloc_traits::pointer node_pointer;
146 : typedef ::boost::base_from_member<
147 : node_allocator> bfm_allocator;
148 : typedef detail::header_holder<
149 : node_pointer,
150 : multi_index_container> bfm_header;
151 :
152 : public:
153 : /* All types are inherited from super, a few are explicitly
154 : * brought forward here to save us some typename's.
155 : */
156 :
157 : typedef typename super::ctor_args_list ctor_args_list;
158 : typedef IndexSpecifierList index_specifier_type_list;
159 :
160 : typedef typename super::index_type_list index_type_list;
161 :
162 : typedef typename super::iterator_type_list iterator_type_list;
163 : typedef typename super::const_iterator_type_list const_iterator_type_list;
164 : typedef typename super::value_type value_type;
165 : typedef typename super::final_allocator_type allocator_type;
166 : typedef typename super::size_type size_type;
167 : typedef typename super::iterator iterator;
168 : typedef typename super::const_iterator const_iterator;
169 :
170 : BOOST_STATIC_ASSERT(
171 : detail::no_duplicate_tags_in_index_list<index_type_list>::value);
172 :
173 : /* global project() needs to see this publicly */
174 :
175 : typedef typename super::final_node_type final_node_type;
176 :
177 : /* construct/copy/destroy */
178 :
179 1097595 : multi_index_container():
180 365865 : bfm_allocator(allocator_type()),
181 365865 : super(ctor_args_list(),bfm_allocator::member),
182 365865 : node_count(0)
183 1097595 : {
184 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
185 731730 : }
186 :
187 : explicit multi_index_container(
188 : const ctor_args_list& args_list,
189 :
190 : #if BOOST_WORKAROUND(__IBMCPP__,<=600)
191 : /* VisualAge seems to have an ETI issue with the default value for
192 : * argument al.
193 : */
194 :
195 : const allocator_type& al=
196 : typename mpl::identity<multi_index_container>::type::
197 : allocator_type()):
198 : #else
199 : const allocator_type& al=allocator_type()):
200 : #endif
201 :
202 : bfm_allocator(al),
203 : super(args_list,bfm_allocator::member),
204 : node_count(0)
205 : {
206 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
207 : }
208 :
209 : explicit multi_index_container(const allocator_type& al):
210 : bfm_allocator(al),
211 : super(ctor_args_list(),bfm_allocator::member),
212 : node_count(0)
213 : {
214 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
215 : }
216 :
217 : template<typename InputIterator>
218 : multi_index_container(
219 : InputIterator first,InputIterator last,
220 :
221 : #if BOOST_WORKAROUND(__IBMCPP__,<=600)
222 : /* VisualAge seems to have an ETI issue with the default values
223 : * for arguments args_list and al.
224 : */
225 :
226 : const ctor_args_list& args_list=
227 : typename mpl::identity<multi_index_container>::type::
228 : ctor_args_list(),
229 : const allocator_type& al=
230 : typename mpl::identity<multi_index_container>::type::
231 : allocator_type()):
232 : #else
233 : const ctor_args_list& args_list=ctor_args_list(),
234 : const allocator_type& al=allocator_type()):
235 : #endif
236 :
237 : bfm_allocator(al),
238 : super(args_list,bfm_allocator::member),
239 : node_count(0)
240 : {
241 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
242 : BOOST_TRY{
243 : iterator hint=super::end();
244 : for(;first!=last;++first){
245 : hint=super::make_iterator(
246 : insert_ref_(*first,hint.get_node()).first);
247 : ++hint;
248 : }
249 : }
250 : BOOST_CATCH(...){
251 : clear_();
252 : BOOST_RETHROW;
253 : }
254 : BOOST_CATCH_END
255 : }
256 :
257 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
258 : multi_index_container(
259 : std::initializer_list<Value> list,
260 : const ctor_args_list& args_list=ctor_args_list(),
261 : const allocator_type& al=allocator_type()):
262 : bfm_allocator(al),
263 : super(args_list,bfm_allocator::member),
264 : node_count(0)
265 : {
266 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
267 : BOOST_TRY{
268 : typedef const Value* init_iterator;
269 :
270 : iterator hint=super::end();
271 : for(init_iterator first=list.begin(),last=list.end();
272 : first!=last;++first){
273 : hint=super::make_iterator(insert_(*first,hint.get_node()).first);
274 : ++hint;
275 : }
276 : }
277 : BOOST_CATCH(...){
278 : clear_();
279 : BOOST_RETHROW;
280 : }
281 : BOOST_CATCH_END
282 : }
283 : #endif
284 :
285 : multi_index_container(
286 : const multi_index_container<Value,IndexSpecifierList,Allocator>& x):
287 : bfm_allocator(
288 : node_alloc_traits::select_on_container_copy_construction(
289 : x.bfm_allocator::member)),
290 : bfm_header(),
291 : super(x),
292 : node_count(0)
293 : {
294 : copy_construct_from(x);
295 : }
296 :
297 : multi_index_container(BOOST_RV_REF(multi_index_container) x):
298 : bfm_allocator(boost::move(x.bfm_allocator::member)),
299 : bfm_header(),
300 : super(x,detail::do_not_copy_elements_tag()),
301 : node_count(0)
302 : {
303 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
304 : BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x);
305 : swap_elements_(x);
306 : }
307 :
308 : multi_index_container(
309 : const multi_index_container<Value,IndexSpecifierList,Allocator>& x,
310 : const allocator_type& al):
311 : bfm_allocator(al),
312 : bfm_header(),
313 : super(x),
314 : node_count(0)
315 : {
316 : copy_construct_from(x);
317 : }
318 :
319 : multi_index_container(
320 : BOOST_RV_REF(multi_index_container) x,const allocator_type& al):
321 : bfm_allocator(al),
322 : bfm_header(),
323 : super(x,detail::do_not_copy_elements_tag()),
324 : node_count(0)
325 : {
326 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
327 : BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x);
328 :
329 : if(al==x.get_allocator()){
330 : swap_elements_(x);
331 : }
332 : else{
333 : multi_index_container y(x,al,detail::unequal_alloc_move_ctor_tag());
334 : swap_elements_(y);
335 : }
336 : }
337 :
338 731730 : ~multi_index_container()
339 365865 : {
340 365865 : delete_all_nodes_();
341 731730 : }
342 :
343 : #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
344 : /* As per http://www.boost.org/doc/html/move/emulation_limitations.html
345 : * #move.emulation_limitations.assignment_operator
346 : */
347 :
348 : multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
349 : const multi_index_container<Value,IndexSpecifierList,Allocator>& x)
350 : {
351 : multi_index_container y(
352 : x,
353 : node_alloc_traits::propagate_on_container_copy_assignment::value?
354 : x.get_allocator():this->get_allocator());
355 : swap_(y,boost::true_type() /* swap_allocators */);
356 : return *this;
357 : }
358 : #endif
359 :
360 : multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
361 : BOOST_COPY_ASSIGN_REF(multi_index_container) x)
362 : {
363 : multi_index_container y(
364 : x,
365 : node_alloc_traits::propagate_on_container_copy_assignment::value?
366 : x.get_allocator():this->get_allocator());
367 : swap_(y,boost::true_type() /* swap_allocators */);
368 : return *this;
369 : }
370 :
371 : multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
372 : BOOST_RV_REF(multi_index_container) x)
373 : {
374 : #include <boost/multi_index/detail/define_if_constexpr_macro.hpp>
375 :
376 : BOOST_MULTI_INDEX_IF_CONSTEXPR(
377 : node_alloc_traits::propagate_on_container_move_assignment::value){
378 : swap_(x,boost::true_type() /* swap_allocators */);
379 : }
380 : else if(this->get_allocator()==x.get_allocator()){
381 : swap_(x,boost::false_type() /* swap_allocators */);
382 : }
383 : else{
384 : multi_index_container y(boost::move(x),this->get_allocator());
385 : swap_(y,boost::false_type() /* swap_allocators */);
386 : }
387 : return *this;
388 :
389 : #include <boost/multi_index/detail/undef_if_constexpr_macro.hpp>
390 : }
391 :
392 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
393 : multi_index_container<Value,IndexSpecifierList,Allocator>& operator=(
394 : std::initializer_list<Value> list)
395 : {
396 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
397 : typedef const Value* init_iterator;
398 :
399 : multi_index_container x(*this,detail::do_not_copy_elements_tag());
400 : iterator hint=x.end();
401 : for(init_iterator first=list.begin(),last=list.end();
402 : first!=last;++first){
403 : hint=x.make_iterator(x.insert_(*first,hint.get_node()).first);
404 : ++hint;
405 : }
406 : x.swap_elements_(*this);
407 : return*this;
408 : }
409 : #endif
410 :
411 444 : allocator_type get_allocator()const BOOST_NOEXCEPT
412 : {
413 444 : return allocator_type(bfm_allocator::member);
414 : }
415 :
416 : /* retrieval of indices by number */
417 :
418 : #if !defined(BOOST_NO_MEMBER_TEMPLATES)
419 : template<int N>
420 : struct nth_index
421 : {
422 : BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
423 : typedef typename mpl::at_c<index_type_list,N>::type type;
424 : };
425 :
426 : template<int N>
427 : typename nth_index<N>::type& get()BOOST_NOEXCEPT
428 : {
429 : BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
430 : return *this;
431 : }
432 :
433 : template<int N>
434 : const typename nth_index<N>::type& get()const BOOST_NOEXCEPT
435 : {
436 : BOOST_STATIC_ASSERT(N>=0&&N<mpl::size<index_type_list>::type::value);
437 : return *this;
438 : }
439 : #endif
440 :
441 : /* retrieval of indices by tag */
442 :
443 : #if !defined(BOOST_NO_MEMBER_TEMPLATES)
444 : template<typename Tag>
445 : struct index
446 : {
447 : typedef typename mpl::find_if<
448 : index_type_list,
449 : detail::has_tag<Tag>
450 : >::type iter;
451 :
452 : BOOST_STATIC_CONSTANT(
453 : bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
454 : BOOST_STATIC_ASSERT(index_found);
455 :
456 : typedef typename mpl::deref<iter>::type type;
457 : };
458 :
459 : template<typename Tag>
460 224257 : typename index<Tag>::type& get()BOOST_NOEXCEPT
461 : {
462 224257 : return *this;
463 : }
464 :
465 : template<typename Tag>
466 303538 : const typename index<Tag>::type& get()const BOOST_NOEXCEPT
467 : {
468 303538 : return *this;
469 : }
470 : #endif
471 :
472 : /* projection of iterators by number */
473 :
474 : #if !defined(BOOST_NO_MEMBER_TEMPLATES)
475 : template<int N>
476 : struct nth_index_iterator
477 : {
478 : typedef typename nth_index<N>::type::iterator type;
479 : };
480 :
481 : template<int N>
482 : struct nth_index_const_iterator
483 : {
484 : typedef typename nth_index<N>::type::const_iterator type;
485 : };
486 :
487 : template<int N,typename IteratorType>
488 18 : typename nth_index_iterator<N>::type project(IteratorType it)
489 : {
490 : typedef typename nth_index<N>::type index_type;
491 :
492 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
493 : BOOST_STATIC_ASSERT(
494 : (mpl::contains<iterator_type_list,IteratorType>::value));
495 : #endif
496 :
497 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
498 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this);
499 36 : return index_type::make_iterator(
500 18 : static_cast<final_node_type*>(it.get_node()));
501 : }
502 :
503 : template<int N,typename IteratorType>
504 83150 : typename nth_index_const_iterator<N>::type project(IteratorType it)const
505 : {
506 : typedef typename nth_index<N>::type index_type;
507 :
508 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
509 : BOOST_STATIC_ASSERT((
510 : mpl::contains<iterator_type_list,IteratorType>::value||
511 : mpl::contains<const_iterator_type_list,IteratorType>::value));
512 : #endif
513 :
514 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
515 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this);
516 166300 : return index_type::make_iterator(
517 83150 : static_cast<final_node_type*>(it.get_node()));
518 : }
519 : #endif
520 :
521 : /* projection of iterators by tag */
522 :
523 : #if !defined(BOOST_NO_MEMBER_TEMPLATES)
524 : template<typename Tag>
525 : struct index_iterator
526 : {
527 : typedef typename index<Tag>::type::iterator type;
528 : };
529 :
530 : template<typename Tag>
531 : struct index_const_iterator
532 : {
533 : typedef typename index<Tag>::type::const_iterator type;
534 : };
535 :
536 : template<typename Tag,typename IteratorType>
537 : typename index_iterator<Tag>::type project(IteratorType it)
538 : {
539 : typedef typename index<Tag>::type index_type;
540 :
541 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
542 : BOOST_STATIC_ASSERT(
543 : (mpl::contains<iterator_type_list,IteratorType>::value));
544 : #endif
545 :
546 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
547 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this);
548 : return index_type::make_iterator(
549 : static_cast<final_node_type*>(it.get_node()));
550 : }
551 :
552 : template<typename Tag,typename IteratorType>
553 : typename index_const_iterator<Tag>::type project(IteratorType it)const
554 : {
555 : typedef typename index<Tag>::type index_type;
556 :
557 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* fails in Sun C++ 5.7 */
558 : BOOST_STATIC_ASSERT((
559 : mpl::contains<iterator_type_list,IteratorType>::value||
560 : mpl::contains<const_iterator_type_list,IteratorType>::value));
561 : #endif
562 :
563 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
564 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,*this);
565 : return index_type::make_iterator(
566 : static_cast<final_node_type*>(it.get_node()));
567 : }
568 : #endif
569 :
570 : BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
571 : typedef typename super::final_node_handle_type final_node_handle_type;
572 : typedef typename super::copy_map_type copy_map_type;
573 :
574 : multi_index_container(
575 : multi_index_container<Value,IndexSpecifierList,Allocator>& x,
576 : const allocator_type& al,
577 : detail::unequal_alloc_move_ctor_tag):
578 : bfm_allocator(al),
579 : bfm_header(),
580 : super(x),
581 : node_count(0)
582 : {
583 : BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x);
584 : BOOST_TRY{
585 : copy_map_type map(bfm_allocator::member,x.size(),x.header(),header());
586 : for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){
587 : map.move_clone(it.get_node());
588 : }
589 : super::copy_(x,map);
590 : map.release();
591 : node_count=x.size();
592 : x.clear();
593 : }
594 : BOOST_CATCH(...){
595 : x.clear();
596 : BOOST_RETHROW;
597 : }
598 : BOOST_CATCH_END
599 :
600 : /* Not until this point are the indices required to be consistent,
601 : * hence the position of the invariant checker.
602 : */
603 :
604 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
605 : }
606 :
607 : #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
608 : multi_index_container(
609 : const multi_index_container<Value,IndexSpecifierList,Allocator>& x,
610 : detail::do_not_copy_elements_tag):
611 : bfm_allocator(x.bfm_allocator::member),
612 : bfm_header(),
613 : super(x,detail::do_not_copy_elements_tag()),
614 : node_count(0)
615 : {
616 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
617 : }
618 : #endif
619 :
620 : void copy_construct_from(
621 : const multi_index_container<Value,IndexSpecifierList,Allocator>& x)
622 : {
623 : copy_map_type map(bfm_allocator::member,x.size(),x.header(),header());
624 : for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){
625 : map.copy_clone(it.get_node());
626 : }
627 : super::copy_(x,map);
628 : map.release();
629 : node_count=x.size();
630 :
631 : /* Not until this point are the indices required to be consistent,
632 : * hence the position of the invariant checker.
633 : */
634 :
635 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
636 : }
637 :
638 94668728 : final_node_type* header()const
639 : {
640 94668728 : return &*bfm_header::member;
641 : }
642 :
643 470088 : final_node_type* allocate_node()
644 : {
645 470088 : return &*node_alloc_traits::allocate(bfm_allocator::member,1);
646 : }
647 :
648 470088 : void deallocate_node(final_node_type* x)
649 : {
650 470088 : node_alloc_traits::deallocate(
651 470088 : bfm_allocator::member,static_cast<node_pointer>(x),1);
652 470088 : }
653 :
654 40507 : void construct_value(final_node_type* x,const Value& v)
655 : {
656 40507 : node_alloc_traits::construct(
657 40507 : bfm_allocator::member,boost::addressof(x->value()),v);
658 40507 : }
659 :
660 : void construct_value(final_node_type* x,BOOST_RV_REF(Value) v)
661 : {
662 : node_alloc_traits::construct(
663 : bfm_allocator::member,boost::addressof(x->value()),boost::move(v));
664 : }
665 :
666 63716 : BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
667 : void,construct_value,vartempl_construct_value_impl,final_node_type*,x)
668 :
669 104223 : void destroy_value(final_node_type* x)
670 : {
671 104223 : node_alloc_traits::destroy(
672 104223 : bfm_allocator::member,boost::addressof(x->value()));
673 104223 : }
674 :
675 635142 : bool empty_()const
676 : {
677 635142 : return node_count==0;
678 : }
679 :
680 16656327 : size_type size_()const
681 : {
682 16656327 : return node_count;
683 : }
684 :
685 : size_type max_size_()const
686 : {
687 : return static_cast<size_type>(-1);
688 : }
689 :
690 : template<typename Variant>
691 40507 : std::pair<final_node_type*,bool> insert_(const Value& v,Variant variant)
692 : {
693 40507 : final_node_type* x=0;
694 40507 : final_node_type* res=super::insert_(v,x,variant);
695 40507 : if(res==x){
696 40507 : ++node_count;
697 40507 : return std::pair<final_node_type*,bool>(res,true);
698 : }
699 : else{
700 0 : return std::pair<final_node_type*,bool>(res,false);
701 : }
702 40507 : }
703 :
704 40507 : std::pair<final_node_type*,bool> insert_(const Value& v)
705 : {
706 40507 : return insert_(v,detail::lvalue_tag());
707 : }
708 :
709 : std::pair<final_node_type*,bool> insert_rv_(const Value& v)
710 : {
711 : return insert_(v,detail::rvalue_tag());
712 : }
713 :
714 : template<typename T>
715 : std::pair<final_node_type*,bool> insert_ref_(T& t)
716 : {
717 : final_node_type* x=allocate_node();
718 : BOOST_TRY{
719 : construct_value(x,t);
720 : BOOST_TRY{
721 : final_node_type* res=super::insert_(
722 : x->value(),x,detail::emplaced_tag());
723 : if(res==x){
724 : ++node_count;
725 : return std::pair<final_node_type*,bool>(res,true);
726 : }
727 : else{
728 : delete_node_(x);
729 : return std::pair<final_node_type*,bool>(res,false);
730 : }
731 : }
732 : BOOST_CATCH(...){
733 : destroy_value(x);
734 : BOOST_RETHROW;
735 : }
736 : BOOST_CATCH_END
737 : }
738 : BOOST_CATCH(...){
739 : deallocate_node(x);
740 : BOOST_RETHROW;
741 : }
742 : BOOST_CATCH_END
743 : }
744 :
745 : std::pair<final_node_type*,bool> insert_ref_(const value_type& x)
746 : {
747 : return insert_(x);
748 : }
749 :
750 : std::pair<final_node_type*,bool> insert_ref_(value_type& x)
751 : {
752 : return insert_(x);
753 : }
754 :
755 : std::pair<final_node_type*,bool> insert_nh_(final_node_handle_type& nh)
756 : {
757 : if(!nh)return std::pair<final_node_type*,bool>(header(),false);
758 : else{
759 : final_node_type* x=nh.node;
760 : final_node_type* res=super::insert_(
761 : x->value(),x,detail::emplaced_tag());
762 : if(res==x){
763 : nh.release_node();
764 : ++node_count;
765 : return std::pair<final_node_type*,bool>(res,true);
766 : }
767 : else return std::pair<final_node_type*,bool>(res,false);
768 : }
769 : }
770 :
771 : template<typename Index>
772 : std::pair<final_node_type*,bool> transfer_(Index& x,final_node_type* n)
773 : {
774 : final_node_type* res=super::insert_(n->value(),n,&super::final(x));
775 : if(res==n){
776 : ++node_count;
777 : return std::pair<final_node_type*,bool>(res,true);
778 : }
779 : else{
780 : return std::pair<final_node_type*,bool>(res,false);
781 : }
782 : }
783 :
784 : template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
785 63716 : std::pair<final_node_type*,bool> emplace_(
786 : BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
787 : {
788 63716 : final_node_type* x=allocate_node();
789 : BOOST_TRY{
790 63716 : construct_value(x,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
791 : BOOST_TRY{
792 127432 : final_node_type* res=super::insert_(
793 63716 : x->value(),x,detail::emplaced_tag());
794 63716 : if(res==x){
795 63716 : ++node_count;
796 63716 : return std::pair<final_node_type*,bool>(res,true);
797 : }
798 : else{
799 0 : delete_node_(x);
800 0 : return std::pair<final_node_type*,bool>(res,false);
801 : }
802 0 : }
803 : BOOST_CATCH(...){
804 0 : destroy_value(x);
805 0 : BOOST_RETHROW;
806 0 : }
807 : BOOST_CATCH_END
808 0 : }
809 : BOOST_CATCH(...){
810 0 : deallocate_node(x);
811 0 : BOOST_RETHROW;
812 0 : }
813 : BOOST_CATCH_END
814 63716 : }
815 :
816 : template<typename Variant>
817 : std::pair<final_node_type*,bool> insert_(
818 : const Value& v,final_node_type* position,Variant variant)
819 : {
820 : final_node_type* x=0;
821 : final_node_type* res=super::insert_(v,position,x,variant);
822 : if(res==x){
823 : ++node_count;
824 : return std::pair<final_node_type*,bool>(res,true);
825 : }
826 : else{
827 : return std::pair<final_node_type*,bool>(res,false);
828 : }
829 : }
830 :
831 : std::pair<final_node_type*,bool> insert_(
832 : const Value& v,final_node_type* position)
833 : {
834 : return insert_(v,position,detail::lvalue_tag());
835 : }
836 :
837 : std::pair<final_node_type*,bool> insert_rv_(
838 : const Value& v,final_node_type* position)
839 : {
840 : return insert_(v,position,detail::rvalue_tag());
841 : }
842 :
843 : template<typename T>
844 : std::pair<final_node_type*,bool> insert_ref_(
845 : T& t,final_node_type* position)
846 : {
847 : final_node_type* x=allocate_node();
848 : BOOST_TRY{
849 : construct_value(x,t);
850 : BOOST_TRY{
851 : final_node_type* res=super::insert_(
852 : x->value(),position,x,detail::emplaced_tag());
853 : if(res==x){
854 : ++node_count;
855 : return std::pair<final_node_type*,bool>(res,true);
856 : }
857 : else{
858 : delete_node_(x);
859 : return std::pair<final_node_type*,bool>(res,false);
860 : }
861 : }
862 : BOOST_CATCH(...){
863 : destroy_value(x);
864 : BOOST_RETHROW;
865 : }
866 : BOOST_CATCH_END
867 : }
868 : BOOST_CATCH(...){
869 : deallocate_node(x);
870 : BOOST_RETHROW;
871 : }
872 : BOOST_CATCH_END
873 : }
874 :
875 : std::pair<final_node_type*,bool> insert_ref_(
876 : const value_type& x,final_node_type* position)
877 : {
878 : return insert_(x,position);
879 : }
880 :
881 : std::pair<final_node_type*,bool> insert_ref_(
882 : value_type& x,final_node_type* position)
883 : {
884 : return insert_(x,position);
885 : }
886 :
887 : std::pair<final_node_type*,bool> insert_nh_(
888 : final_node_handle_type& nh,final_node_type* position)
889 : {
890 : if(!nh)return std::pair<final_node_type*,bool>(header(),false);
891 : else{
892 : final_node_type* x=nh.node;
893 : final_node_type* res=super::insert_(
894 : x->value(),position,x,detail::emplaced_tag());
895 : if(res==x){
896 : nh.release_node();
897 : ++node_count;
898 : return std::pair<final_node_type*,bool>(res,true);
899 : }
900 : else return std::pair<final_node_type*,bool>(res,false);
901 : }
902 : }
903 :
904 : template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
905 : std::pair<final_node_type*,bool> emplace_hint_(
906 : final_node_type* position,
907 : BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
908 : {
909 : final_node_type* x=allocate_node();
910 : BOOST_TRY{
911 : construct_value(x,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
912 : BOOST_TRY{
913 : final_node_type* res=super::insert_(
914 : x->value(),position,x,detail::emplaced_tag());
915 : if(res==x){
916 : ++node_count;
917 : return std::pair<final_node_type*,bool>(res,true);
918 : }
919 : else{
920 : delete_node_(x);
921 : return std::pair<final_node_type*,bool>(res,false);
922 : }
923 : }
924 : BOOST_CATCH(...){
925 : destroy_value(x);
926 : BOOST_RETHROW;
927 : }
928 : BOOST_CATCH_END
929 : }
930 : BOOST_CATCH(...){
931 : deallocate_node(x);
932 : BOOST_RETHROW;
933 : }
934 : BOOST_CATCH_END
935 : }
936 :
937 : final_node_handle_type extract_(final_node_type* x)
938 : {
939 : --node_count;
940 : super::extract_(x,detail::invalidate_iterators());
941 : return final_node_handle_type(x,get_allocator());
942 : }
943 :
944 : template<typename Dst>
945 : void extract_for_transfer_(final_node_type* x,Dst dst)
946 : {
947 : --node_count;
948 : super::extract_(x,dst);
949 : }
950 :
951 72132 : void erase_(final_node_type* x)
952 : {
953 72132 : --node_count;
954 72132 : super::extract_(x,detail::invalidate_iterators());
955 72132 : delete_node_(x);
956 72132 : }
957 :
958 104223 : void delete_node_(final_node_type* x)
959 : {
960 104223 : destroy_value(x);
961 104223 : deallocate_node(x);
962 104223 : }
963 :
964 399022 : void delete_all_nodes_()
965 : {
966 399022 : super::delete_all_nodes_();
967 399022 : }
968 :
969 33157 : void clear_()
970 : {
971 33157 : delete_all_nodes_();
972 33157 : super::clear_();
973 33157 : node_count=0;
974 33157 : }
975 :
976 : template<typename Index>
977 : void transfer_range_(
978 : Index& x,
979 : BOOST_DEDUCED_TYPENAME Index::iterator first,
980 : BOOST_DEDUCED_TYPENAME Index::iterator last)
981 : {
982 : while(first!=last){
983 : transfer_(x,static_cast<final_node_type*>((first++).get_node()));
984 : }
985 : }
986 :
987 : void swap_(multi_index_container<Value,IndexSpecifierList,Allocator>& x)
988 : {
989 : swap_(
990 : x,
991 : boost::integral_constant<
992 : bool,node_alloc_traits::propagate_on_container_swap::value>());
993 : }
994 :
995 : void swap_(
996 : multi_index_container<Value,IndexSpecifierList,Allocator>& x,
997 : boost::true_type swap_allocators)
998 : {
999 : detail::adl_swap(bfm_allocator::member,x.bfm_allocator::member);
1000 : std::swap(bfm_header::member,x.bfm_header::member);
1001 : super::swap_(x,swap_allocators);
1002 : std::swap(node_count,x.node_count);
1003 : }
1004 :
1005 : void swap_(
1006 : multi_index_container<Value,IndexSpecifierList,Allocator>& x,
1007 : boost::false_type swap_allocators)
1008 : {
1009 : std::swap(bfm_header::member,x.bfm_header::member);
1010 : super::swap_(x,swap_allocators);
1011 : std::swap(node_count,x.node_count);
1012 : }
1013 :
1014 : void swap_elements_(
1015 : multi_index_container<Value,IndexSpecifierList,Allocator>& x)
1016 : {
1017 : std::swap(bfm_header::member,x.bfm_header::member);
1018 : super::swap_elements_(x);
1019 : std::swap(node_count,x.node_count);
1020 : }
1021 :
1022 : bool replace_(const Value& k,final_node_type* x)
1023 : {
1024 : return super::replace_(k,x,detail::lvalue_tag());
1025 : }
1026 :
1027 : bool replace_rv_(const Value& k,final_node_type* x)
1028 : {
1029 : return super::replace_(k,x,detail::rvalue_tag());
1030 : }
1031 :
1032 : template<typename Modifier>
1033 1848485 : bool modify_(Modifier& mod,final_node_type* x)
1034 : {
1035 : BOOST_TRY{
1036 1848485 : mod(const_cast<value_type&>(x->value()));
1037 1848485 : }
1038 : BOOST_CATCH(...){
1039 0 : this->erase_(x);
1040 0 : BOOST_RETHROW;
1041 0 : }
1042 : BOOST_CATCH_END
1043 :
1044 : BOOST_TRY{
1045 1848485 : if(!super::modify_(x)){
1046 0 : delete_node_(x);
1047 0 : --node_count;
1048 0 : return false;
1049 : }
1050 1848485 : else return true;
1051 0 : }
1052 : BOOST_CATCH(...){
1053 0 : delete_node_(x);
1054 0 : --node_count;
1055 0 : BOOST_RETHROW;
1056 0 : }
1057 : BOOST_CATCH_END
1058 1848485 : }
1059 :
1060 : template<typename Modifier,typename Rollback>
1061 : bool modify_(Modifier& mod,Rollback& back_,final_node_type* x)
1062 : {
1063 : BOOST_TRY{
1064 : mod(const_cast<value_type&>(x->value()));
1065 : }
1066 : BOOST_CATCH(...){
1067 : this->erase_(x);
1068 : BOOST_RETHROW;
1069 : }
1070 : BOOST_CATCH_END
1071 :
1072 : bool b;
1073 : BOOST_TRY{
1074 : b=super::modify_rollback_(x);
1075 : }
1076 : BOOST_CATCH(...){
1077 : BOOST_TRY{
1078 : back_(const_cast<value_type&>(x->value()));
1079 : if(!super::check_rollback_(x))this->erase_(x);
1080 : BOOST_RETHROW;
1081 : }
1082 : BOOST_CATCH(...){
1083 : this->erase_(x);
1084 : BOOST_RETHROW;
1085 : }
1086 : BOOST_CATCH_END
1087 : }
1088 : BOOST_CATCH_END
1089 :
1090 : BOOST_TRY{
1091 : if(!b){
1092 : back_(const_cast<value_type&>(x->value()));
1093 : if(!super::check_rollback_(x))this->erase_(x);
1094 : return false;
1095 : }
1096 : else return true;
1097 : }
1098 : BOOST_CATCH(...){
1099 : this->erase_(x);
1100 : BOOST_RETHROW;
1101 : }
1102 : BOOST_CATCH_END
1103 : }
1104 :
1105 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1106 : /* serialization */
1107 :
1108 : friend class boost::serialization::access;
1109 :
1110 : template<class Archive>
1111 : void serialize(Archive& ar,const unsigned int version)
1112 : {
1113 : core::split_member(ar,*this,version);
1114 : }
1115 :
1116 : typedef typename super::index_saver_type index_saver_type;
1117 : typedef typename super::index_loader_type index_loader_type;
1118 :
1119 : template<class Archive>
1120 : void save(Archive& ar,const unsigned int version)const
1121 : {
1122 : const std::size_t s(size_());
1123 : const detail::serialization_version<value_type> value_version;
1124 : ar<<core::make_nvp("count",s);
1125 : ar<<core::make_nvp("value_version",value_version);
1126 :
1127 : index_saver_type sm(bfm_allocator::member,s);
1128 :
1129 : for(iterator it=super::begin(),it_end=super::end();it!=it_end;++it){
1130 : core::save_construct_data_adl(
1131 : ar,boost::addressof(*it),value_version);
1132 : ar<<serialization::make_nvp("item",*it);
1133 : sm.add(it.get_node(),ar,version);
1134 : }
1135 : sm.add_track(header(),ar,version);
1136 :
1137 : super::save_(ar,version,sm);
1138 : }
1139 :
1140 : template<class Archive>
1141 : void load(Archive& ar,const unsigned int version)
1142 : {
1143 : BOOST_MULTI_INDEX_CHECK_INVARIANT;
1144 :
1145 : clear_();
1146 : std::size_t s;
1147 : detail::serialization_version<value_type> value_version;
1148 : if(version<1){
1149 : std::size_t sz;
1150 : ar>>core::make_nvp("count",sz);
1151 : s=static_cast<std::size_t>(sz);
1152 : }
1153 : else if(version<3){
1154 : #if defined(BOOST_MULTI_INDEX_ENABLE_SERIALIZATION_COMPATIBILITY_V2)
1155 : serialization::collection_size_type csz;
1156 : ar>>core::make_nvp("count",csz);
1157 : s=static_cast<std::size_t>(csz);
1158 : #else
1159 : ar>>core::make_nvp("count",s);
1160 : #endif
1161 : }
1162 : else if(version<4){
1163 : unsigned long ul;
1164 : ar>>core::make_nvp("count",ul);
1165 : s=static_cast<std::size_t>(ul);
1166 : }
1167 : else{
1168 : ar>>core::make_nvp("count",s);
1169 : }
1170 :
1171 : if(version<2){
1172 : value_version=0;
1173 : }
1174 : else{
1175 : ar>>core::make_nvp("value_version",value_version);
1176 : }
1177 :
1178 : index_loader_type lm(bfm_allocator::member,s);
1179 :
1180 : for(std::size_t n=0;n<s;++n){
1181 : detail::archive_constructed<Value> value("item",ar,value_version);
1182 : std::pair<final_node_type*,bool> p=insert_rv_(
1183 : value.get(),super::end().get_node());
1184 : if(!p.second)throw_exception(detail::bad_archive_exception());
1185 : ar.reset_object_address(
1186 : boost::addressof(p.first->value()),boost::addressof(value.get()));
1187 : lm.add(p.first,ar,version);
1188 : }
1189 : lm.add_track(header(),ar,version);
1190 :
1191 : super::load_(ar,version,lm);
1192 : }
1193 : #endif
1194 :
1195 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1196 : /* invariant stuff */
1197 :
1198 : bool invariant_()const
1199 : {
1200 : return super::invariant_();
1201 : }
1202 :
1203 : void check_invariant_()const
1204 : {
1205 : BOOST_MULTI_INDEX_INVARIANT_ASSERT(invariant_());
1206 : }
1207 : #endif
1208 :
1209 : private:
1210 : template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1211 63716 : void vartempl_construct_value_impl(
1212 : final_node_type* x,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1213 : {
1214 63716 : node_alloc_traits::construct(
1215 63716 : bfm_allocator::member,boost::addressof(x->value()),
1216 63716 : BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1217 63716 : }
1218 :
1219 : size_type node_count;
1220 :
1221 : #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1222 : BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1223 : #pragma parse_mfunc_templ reset
1224 : #endif
1225 : };
1226 :
1227 : #if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500))
1228 : #pragma warning(pop) /* C4522 */
1229 : #endif
1230 :
1231 : /* retrieval of indices by number */
1232 :
1233 : template<typename MultiIndexContainer,int N>
1234 : struct nth_index
1235 : {
1236 : BOOST_STATIC_CONSTANT(
1237 : int,
1238 : M=mpl::size<typename MultiIndexContainer::index_type_list>::type::value);
1239 : BOOST_STATIC_ASSERT(N>=0&&N<M);
1240 : typedef typename mpl::at_c<
1241 : typename MultiIndexContainer::index_type_list,N>::type type;
1242 : };
1243 :
1244 : template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
1245 : typename nth_index<
1246 : multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
1247 : get(
1248 : multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
1249 : {
1250 : typedef multi_index_container<
1251 : Value,IndexSpecifierList,Allocator> multi_index_type;
1252 : typedef typename nth_index<
1253 : multi_index_container<
1254 : Value,IndexSpecifierList,Allocator>,
1255 : N
1256 : >::type index_type;
1257 :
1258 : BOOST_STATIC_ASSERT(N>=0&&
1259 : N<
1260 : mpl::size<
1261 : BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1262 : >::type::value);
1263 :
1264 : return detail::converter<multi_index_type,index_type>::index(m);
1265 : }
1266 :
1267 : template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
1268 : const typename nth_index<
1269 : multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type&
1270 : get(
1271 : const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1272 : )BOOST_NOEXCEPT
1273 : {
1274 : typedef multi_index_container<
1275 : Value,IndexSpecifierList,Allocator> multi_index_type;
1276 : typedef typename nth_index<
1277 : multi_index_container<
1278 : Value,IndexSpecifierList,Allocator>,
1279 : N
1280 : >::type index_type;
1281 :
1282 : BOOST_STATIC_ASSERT(N>=0&&
1283 : N<
1284 : mpl::size<
1285 : BOOST_DEDUCED_TYPENAME multi_index_type::index_type_list
1286 : >::type::value);
1287 :
1288 : return detail::converter<multi_index_type,index_type>::index(m);
1289 : }
1290 :
1291 : /* retrieval of indices by tag */
1292 :
1293 : template<typename MultiIndexContainer,typename Tag>
1294 : struct index
1295 : {
1296 : typedef typename MultiIndexContainer::index_type_list index_type_list;
1297 :
1298 : typedef typename mpl::find_if<
1299 : index_type_list,
1300 : detail::has_tag<Tag>
1301 : >::type iter;
1302 :
1303 : BOOST_STATIC_CONSTANT(
1304 : bool,index_found=!(is_same<iter,typename mpl::end<index_type_list>::type >::value));
1305 : BOOST_STATIC_ASSERT(index_found);
1306 :
1307 : typedef typename mpl::deref<iter>::type type;
1308 : };
1309 :
1310 : template<
1311 : typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1312 : >
1313 : typename ::boost::multi_index::index<
1314 : multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
1315 : get(
1316 : multi_index_container<Value,IndexSpecifierList,Allocator>& m)BOOST_NOEXCEPT
1317 : {
1318 : typedef multi_index_container<
1319 : Value,IndexSpecifierList,Allocator> multi_index_type;
1320 : typedef typename ::boost::multi_index::index<
1321 : multi_index_container<
1322 : Value,IndexSpecifierList,Allocator>,
1323 : Tag
1324 : >::type index_type;
1325 :
1326 : return detail::converter<multi_index_type,index_type>::index(m);
1327 : }
1328 :
1329 : template<
1330 : typename Tag,typename Value,typename IndexSpecifierList,typename Allocator
1331 : >
1332 : const typename ::boost::multi_index::index<
1333 : multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type&
1334 : get(
1335 : const multi_index_container<Value,IndexSpecifierList,Allocator>& m
1336 : )BOOST_NOEXCEPT
1337 : {
1338 : typedef multi_index_container<
1339 : Value,IndexSpecifierList,Allocator> multi_index_type;
1340 : typedef typename ::boost::multi_index::index<
1341 : multi_index_container<
1342 : Value,IndexSpecifierList,Allocator>,
1343 : Tag
1344 : >::type index_type;
1345 :
1346 : return detail::converter<multi_index_type,index_type>::index(m);
1347 : }
1348 :
1349 : /* projection of iterators by number */
1350 :
1351 : template<typename MultiIndexContainer,int N>
1352 : struct nth_index_iterator
1353 : {
1354 : typedef typename nth_index<MultiIndexContainer,N>::type::iterator type;
1355 : };
1356 :
1357 : template<typename MultiIndexContainer,int N>
1358 : struct nth_index_const_iterator
1359 : {
1360 : typedef typename nth_index<MultiIndexContainer,N>::type::const_iterator type;
1361 : };
1362 :
1363 : template<
1364 : int N,typename IteratorType,
1365 : typename Value,typename IndexSpecifierList,typename Allocator>
1366 : typename nth_index_iterator<
1367 : multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
1368 : project(
1369 : multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1370 : IteratorType it)
1371 : {
1372 : typedef multi_index_container<
1373 : Value,IndexSpecifierList,Allocator> multi_index_type;
1374 : typedef typename nth_index<multi_index_type,N>::type index_type;
1375 :
1376 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1377 : BOOST_STATIC_ASSERT((
1378 : mpl::contains<
1379 : BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1380 : IteratorType>::value));
1381 : #endif
1382 :
1383 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1384 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m);
1385 : return detail::converter<multi_index_type,index_type>::iterator(
1386 : m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1387 : }
1388 :
1389 : template<
1390 : int N,typename IteratorType,
1391 : typename Value,typename IndexSpecifierList,typename Allocator>
1392 : typename nth_index_const_iterator<
1393 : multi_index_container<Value,IndexSpecifierList,Allocator>,N>::type
1394 : project(
1395 : const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1396 : IteratorType it)
1397 : {
1398 : typedef multi_index_container<
1399 : Value,IndexSpecifierList,Allocator> multi_index_type;
1400 : typedef typename nth_index<multi_index_type,N>::type index_type;
1401 :
1402 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1403 : BOOST_STATIC_ASSERT((
1404 : mpl::contains<
1405 : BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1406 : IteratorType>::value||
1407 : mpl::contains<
1408 : BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1409 : IteratorType>::value));
1410 : #endif
1411 :
1412 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1413 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m);
1414 : return detail::converter<multi_index_type,index_type>::const_iterator(
1415 : m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1416 : }
1417 :
1418 : /* projection of iterators by tag */
1419 :
1420 : template<typename MultiIndexContainer,typename Tag>
1421 : struct index_iterator
1422 : {
1423 : typedef typename ::boost::multi_index::index<
1424 : MultiIndexContainer,Tag>::type::iterator type;
1425 : };
1426 :
1427 : template<typename MultiIndexContainer,typename Tag>
1428 : struct index_const_iterator
1429 : {
1430 : typedef typename ::boost::multi_index::index<
1431 : MultiIndexContainer,Tag>::type::const_iterator type;
1432 : };
1433 :
1434 : template<
1435 : typename Tag,typename IteratorType,
1436 : typename Value,typename IndexSpecifierList,typename Allocator>
1437 : typename index_iterator<
1438 : multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1439 : project(
1440 : multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1441 : IteratorType it)
1442 : {
1443 : typedef multi_index_container<
1444 : Value,IndexSpecifierList,Allocator> multi_index_type;
1445 : typedef typename ::boost::multi_index::index<
1446 : multi_index_type,Tag>::type index_type;
1447 :
1448 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1449 : BOOST_STATIC_ASSERT((
1450 : mpl::contains<
1451 : BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1452 : IteratorType>::value));
1453 : #endif
1454 :
1455 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1456 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m);
1457 : return detail::converter<multi_index_type,index_type>::iterator(
1458 : m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1459 : }
1460 :
1461 : template<
1462 : typename Tag,typename IteratorType,
1463 : typename Value,typename IndexSpecifierList,typename Allocator>
1464 : typename index_const_iterator<
1465 : multi_index_container<Value,IndexSpecifierList,Allocator>,Tag>::type
1466 : project(
1467 : const multi_index_container<Value,IndexSpecifierList,Allocator>& m,
1468 : IteratorType it)
1469 : {
1470 : typedef multi_index_container<
1471 : Value,IndexSpecifierList,Allocator> multi_index_type;
1472 : typedef typename ::boost::multi_index::index<
1473 : multi_index_type,Tag>::type index_type;
1474 :
1475 : #if !defined(__SUNPRO_CC)||!(__SUNPRO_CC<0x580) /* Sun C++ 5.7 fails */
1476 : BOOST_STATIC_ASSERT((
1477 : mpl::contains<
1478 : BOOST_DEDUCED_TYPENAME multi_index_type::iterator_type_list,
1479 : IteratorType>::value||
1480 : mpl::contains<
1481 : BOOST_DEDUCED_TYPENAME multi_index_type::const_iterator_type_list,
1482 : IteratorType>::value));
1483 : #endif
1484 :
1485 : BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it);
1486 : BOOST_MULTI_INDEX_CHECK_BELONGS_IN_SOME_INDEX(it,m);
1487 : return detail::converter<multi_index_type,index_type>::const_iterator(
1488 : m,static_cast<typename multi_index_type::final_node_type*>(it.get_node()));
1489 : }
1490 :
1491 : /* Comparison. Simple forward to first index. */
1492 :
1493 : template<
1494 : typename Value1,typename IndexSpecifierList1,typename Allocator1,
1495 : typename Value2,typename IndexSpecifierList2,typename Allocator2
1496 : >
1497 : bool operator==(
1498 : const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1499 : const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1500 : {
1501 : return get<0>(x)==get<0>(y);
1502 : }
1503 :
1504 : template<
1505 : typename Value1,typename IndexSpecifierList1,typename Allocator1,
1506 : typename Value2,typename IndexSpecifierList2,typename Allocator2
1507 : >
1508 : bool operator<(
1509 : const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1510 : const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1511 : {
1512 : return get<0>(x)<get<0>(y);
1513 : }
1514 :
1515 : template<
1516 : typename Value1,typename IndexSpecifierList1,typename Allocator1,
1517 : typename Value2,typename IndexSpecifierList2,typename Allocator2
1518 : >
1519 : bool operator!=(
1520 : const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1521 : const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1522 : {
1523 : return get<0>(x)!=get<0>(y);
1524 : }
1525 :
1526 : template<
1527 : typename Value1,typename IndexSpecifierList1,typename Allocator1,
1528 : typename Value2,typename IndexSpecifierList2,typename Allocator2
1529 : >
1530 : bool operator>(
1531 : const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1532 : const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1533 : {
1534 : return get<0>(x)>get<0>(y);
1535 : }
1536 :
1537 : template<
1538 : typename Value1,typename IndexSpecifierList1,typename Allocator1,
1539 : typename Value2,typename IndexSpecifierList2,typename Allocator2
1540 : >
1541 : bool operator>=(
1542 : const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1543 : const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1544 : {
1545 : return get<0>(x)>=get<0>(y);
1546 : }
1547 :
1548 : template<
1549 : typename Value1,typename IndexSpecifierList1,typename Allocator1,
1550 : typename Value2,typename IndexSpecifierList2,typename Allocator2
1551 : >
1552 : bool operator<=(
1553 : const multi_index_container<Value1,IndexSpecifierList1,Allocator1>& x,
1554 : const multi_index_container<Value2,IndexSpecifierList2,Allocator2>& y)
1555 : {
1556 : return get<0>(x)<=get<0>(y);
1557 : }
1558 :
1559 : /* specialized algorithms */
1560 :
1561 : template<typename Value,typename IndexSpecifierList,typename Allocator>
1562 : void swap(
1563 : multi_index_container<Value,IndexSpecifierList,Allocator>& x,
1564 : multi_index_container<Value,IndexSpecifierList,Allocator>& y)
1565 : {
1566 : x.swap(y);
1567 : }
1568 :
1569 : } /* namespace multi_index */
1570 :
1571 : #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1572 : /* class version = 1 : we now serialize the size through
1573 : * boost::serialization::collection_size_type.
1574 : * class version = 2 : proper use of {save|load}_construct_data.
1575 : * class version = 3 : dropped boost::serialization::collection_size_type
1576 : * in favor of unsigned long --this allows us to provide serialization
1577 : * support without including any header from Boost.Serialization.
1578 : * class version = 4 : uses std::size_t rather than unsigned long (which
1579 : * is smaller in LLP64 data models).
1580 : */
1581 :
1582 : namespace serialization {
1583 : template<typename Value,typename IndexSpecifierList,typename Allocator>
1584 : struct version<
1585 : boost::multi_index_container<Value,IndexSpecifierList,Allocator>
1586 : >
1587 : {
1588 : BOOST_STATIC_CONSTANT(int,value=4);
1589 : };
1590 : } /* namespace serialization */
1591 : #endif
1592 :
1593 : /* Associated global functions are promoted to namespace boost, except
1594 : * comparison operators and swap, which are meant to be Koenig looked-up.
1595 : */
1596 :
1597 : using multi_index::get;
1598 : using multi_index::project;
1599 :
1600 : } /* namespace boost */
1601 :
1602 : #undef BOOST_MULTI_INDEX_CHECK_INVARIANT
1603 : #undef BOOST_MULTI_INDEX_CHECK_INVARIANT_OF
1604 :
1605 : #endif
|
