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