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