1 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP
10 #define BOOST_MULTI_INDEX_HASHED_INDEX_HPP
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
18 #include <boost/call_traits.hpp>
19 #include <boost/detail/allocator_utilities.hpp>
20 #include <boost/detail/no_exceptions_support.hpp>
21 #include <boost/detail/workaround.hpp>
22 #include <boost/foreach_fwd.hpp>
23 #include <boost/limits.hpp>
24 #include <boost/move/core.hpp>
25 #include <boost/mpl/bool.hpp>
26 #include <boost/mpl/if.hpp>
27 #include <boost/mpl/push_front.hpp>
28 #include <boost/multi_index/detail/access_specifier.hpp>
29 #include <boost/multi_index/detail/auto_space.hpp>
30 #include <boost/multi_index/detail/bucket_array.hpp>
31 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
32 #include <boost/multi_index/detail/hash_index_iterator.hpp>
33 #include <boost/multi_index/detail/index_node_base.hpp>
34 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
35 #include <boost/multi_index/detail/promotes_arg.hpp>
36 #include <boost/multi_index/detail/safe_mode.hpp>
37 #include <boost/multi_index/detail/scope_guard.hpp>
38 #include <boost/multi_index/detail/vartempl_support.hpp>
39 #include <boost/multi_index/hashed_index_fwd.hpp>
40 #include <boost/tuple/tuple.hpp>
41 #include <boost/type_traits/is_same.hpp>
48 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
49 #include <initializer_list>
52 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
53 #include <boost/serialization/nvp.hpp>
56 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
57 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) \
58 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
59 detail::make_obj_guard(x,&hashed_index::check_invariant_); \
60 BOOST_JOIN(check_invariant_,__LINE__).touch();
61 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \
62 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this)
64 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x)
65 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
70 namespace multi_index{
74 /* hashed_index adds a layer of hashed indexing to a given Super */
76 /* Most of the implementation of unique and non-unique indices is
77 * shared. We tell from one another on instantiation time by using
78 * Category tags defined in hash_index_node.hpp.
82 typename KeyFromValue,typename Hash,typename Pred,
83 typename SuperMeta,typename TagList,typename Category
86 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
88 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
89 ,public safe_mode::safe_container<
90 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
94 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
95 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
96 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
97 * lifetime of const references bound to temporaries --precisely what
101 #pragma parse_mfunc_templ off
104 typedef typename SuperMeta::type super;
107 typedef hashed_index_node<
108 typename super::node_type,Category> node_type;
111 typedef typename node_type::node_alg node_alg;
112 typedef typename node_type::impl_type node_impl_type;
113 typedef typename node_impl_type::pointer node_impl_pointer;
114 typedef typename node_impl_type::base_pointer node_impl_base_pointer;
115 typedef bucket_array<
116 typename super::final_allocator_type> bucket_array_type;
121 typedef typename KeyFromValue::result_type key_type;
122 typedef typename node_type::value_type value_type;
123 typedef KeyFromValue key_from_value;
125 typedef Pred key_equal;
126 typedef tuple<std::size_t,
127 key_from_value,hasher,key_equal> ctor_args;
128 typedef typename super::final_allocator_type allocator_type;
129 typedef typename allocator_type::pointer pointer;
130 typedef typename allocator_type::const_pointer const_pointer;
131 typedef typename allocator_type::reference reference;
132 typedef typename allocator_type::const_reference const_reference;
133 typedef std::size_t size_type;
134 typedef std::ptrdiff_t difference_type;
136 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
137 typedef safe_mode::safe_iterator<
138 hashed_index_iterator<
139 node_type,bucket_array_type,
140 hashed_index_global_iterator_tag>,
141 hashed_index> iterator;
143 typedef hashed_index_iterator<
144 node_type,bucket_array_type,
145 hashed_index_global_iterator_tag> iterator;
148 typedef iterator const_iterator;
150 typedef hashed_index_iterator<
151 node_type,bucket_array_type,
152 hashed_index_local_iterator_tag> local_iterator;
153 typedef local_iterator const_local_iterator;
155 typedef TagList tag_list;
158 typedef typename super::final_node_type final_node_type;
159 typedef tuples::cons<
161 typename super::ctor_args_list> ctor_args_list;
162 typedef typename mpl::push_front<
163 typename super::index_type_list,
164 hashed_index>::type index_type_list;
165 typedef typename mpl::push_front<
166 typename super::iterator_type_list,
167 iterator>::type iterator_type_list;
168 typedef typename mpl::push_front<
169 typename super::const_iterator_type_list,
170 const_iterator>::type const_iterator_type_list;
171 typedef typename super::copy_map_type copy_map_type;
173 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
174 typedef typename super::index_saver_type index_saver_type;
175 typedef typename super::index_loader_type index_loader_type;
179 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
180 typedef safe_mode::safe_container<
181 hashed_index> safe_super;
184 typedef typename call_traits<value_type>::param_type value_param_type;
185 typedef typename call_traits<
186 key_type>::param_type key_param_type;
188 /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
192 typedef std::pair<iterator,bool> emplace_return_type;
196 /* construct/destroy/copy
197 * Default and copy ctors are in the protected section as indices are
198 * not supposed to be created on their own. No range ctor either.
201 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
202 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
204 this->final()=x.final();
208 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
209 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
210 std::initializer_list<value_type> list)
217 allocator_type get_allocator()const BOOST_NOEXCEPT
219 return this->final().get_allocator();
222 /* size and capacity */
224 bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
225 size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
226 size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
230 iterator begin()BOOST_NOEXCEPT
231 {return make_iterator(node_type::from_impl(header()->next()->prior()));}
232 const_iterator begin()const BOOST_NOEXCEPT
233 {return make_iterator(node_type::from_impl(header()->next()->prior()));}
234 iterator end()BOOST_NOEXCEPT{return make_iterator(header());}
235 const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());}
236 const_iterator cbegin()const BOOST_NOEXCEPT{return begin();}
237 const_iterator cend()const BOOST_NOEXCEPT{return end();}
239 iterator iterator_to(const value_type& x)
241 return make_iterator(node_from_value<node_type>(&x));
244 const_iterator iterator_to(const value_type& x)const
246 return make_iterator(node_from_value<node_type>(&x));
251 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
252 emplace_return_type,emplace,emplace_impl)
254 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
255 iterator,emplace_hint,emplace_hint_impl,iterator,position)
257 std::pair<iterator,bool> insert(const value_type& x)
259 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
260 std::pair<final_node_type*,bool> p=this->final_insert_(x);
261 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
264 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
266 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
267 std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
268 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
271 iterator insert(iterator position,const value_type& x)
273 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
274 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
275 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
276 std::pair<final_node_type*,bool> p=this->final_insert_(
277 x,static_cast<final_node_type*>(position.get_node()));
278 return make_iterator(p.first);
281 iterator insert(iterator position,BOOST_RV_REF(value_type) x)
283 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
284 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
285 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
286 std::pair<final_node_type*,bool> p=this->final_insert_rv_(
287 x,static_cast<final_node_type*>(position.get_node()));
288 return make_iterator(p.first);
291 template<typename InputIterator>
292 void insert(InputIterator first,InputIterator last)
294 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
295 for(;first!=last;++first)this->final_insert_ref_(*first);
298 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
299 void insert(std::initializer_list<value_type> list)
301 insert(list.begin(),list.end());
305 iterator erase(iterator position)
307 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
308 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
309 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
310 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
311 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
315 size_type erase(key_param_type k)
317 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
319 std::size_t buc=buckets.position(hash_(k));
320 for(node_impl_pointer x=buckets.at(buc)->prior();
321 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
322 if(eq_(k,key(node_type::from_impl(x)->value()))){
323 node_impl_pointer y=end_of_range(x);
326 node_impl_pointer z=node_alg::after(x);
328 static_cast<final_node_type*>(node_type::from_impl(x)));
338 iterator erase(iterator first,iterator last)
340 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
341 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
342 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
343 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
344 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
345 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
352 bool replace(iterator position,const value_type& x)
354 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
355 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
356 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
357 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
358 return this->final_replace_(
359 x,static_cast<final_node_type*>(position.get_node()));
362 bool replace(iterator position,BOOST_RV_REF(value_type) x)
364 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
365 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
366 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
367 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
368 return this->final_replace_rv_(
369 x,static_cast<final_node_type*>(position.get_node()));
372 template<typename Modifier>
373 bool modify(iterator position,Modifier mod)
375 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
376 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
377 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
378 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
380 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
381 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
382 * this is not added. Left it for all compilers as it does no
389 return this->final_modify_(
390 mod,static_cast<final_node_type*>(position.get_node()));
393 template<typename Modifier,typename Rollback>
394 bool modify(iterator position,Modifier mod,Rollback back_)
396 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
397 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
398 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
399 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
401 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
402 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
403 * this is not added. Left it for all compilers as it does no
410 return this->final_modify_(
411 mod,back_,static_cast<final_node_type*>(position.get_node()));
414 template<typename Modifier>
415 bool modify_key(iterator position,Modifier mod)
417 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
418 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
419 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
420 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
422 position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
425 template<typename Modifier,typename Rollback>
426 bool modify_key(iterator position,Modifier mod,Rollback back_)
428 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
429 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
430 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
431 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
434 modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
435 modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
438 void clear()BOOST_NOEXCEPT
440 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
441 this->final_clear_();
444 void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
446 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
447 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x);
448 this->final_swap_(x.final());
453 key_from_value key_extractor()const{return key;}
454 hasher hash_function()const{return hash_;}
455 key_equal key_eq()const{return eq_;}
459 /* Internally, these ops rely on const_iterator being the same
463 /* Implementation note: When CompatibleKey is consistently promoted to
464 * KeyFromValue::result_type for equality comparison, the promotion is made
465 * once in advance to increase efficiency.
468 template<typename CompatibleKey>
469 iterator find(const CompatibleKey& k)const
471 return find(k,hash_,eq_);
475 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
478 const CompatibleKey& k,
479 const CompatibleHash& hash,const CompatiblePred& eq)const
482 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
485 template<typename CompatibleKey>
486 size_type count(const CompatibleKey& k)const
488 return count(k,hash_,eq_);
492 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
495 const CompatibleKey& k,
496 const CompatibleHash& hash,const CompatiblePred& eq)const
499 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
502 template<typename CompatibleKey>
503 std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
505 return equal_range(k,hash_,eq_);
509 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
511 std::pair<iterator,iterator> equal_range(
512 const CompatibleKey& k,
513 const CompatibleHash& hash,const CompatiblePred& eq)const
516 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
519 /* bucket interface */
521 size_type bucket_count()const BOOST_NOEXCEPT{return buckets.size();}
522 size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);}
524 size_type bucket_size(size_type n)const
527 for(node_impl_pointer x=buckets.at(n)->prior();
528 x!=node_impl_pointer(0);x=node_alg::after_local(x)){
534 size_type bucket(key_param_type k)const
536 return buckets.position(hash_(k));
539 local_iterator begin(size_type n)
541 return const_cast<const hashed_index*>(this)->begin(n);
544 const_local_iterator begin(size_type n)const
546 node_impl_pointer x=buckets.at(n)->prior();
547 if(x==node_impl_pointer(0))return end(n);
548 return make_local_iterator(node_type::from_impl(x));
551 local_iterator end(size_type n)
553 return const_cast<const hashed_index*>(this)->end(n);
556 const_local_iterator end(size_type)const
558 return make_local_iterator(0);
561 const_local_iterator cbegin(size_type n)const{return begin(n);}
562 const_local_iterator cend(size_type n)const{return end(n);}
564 local_iterator local_iterator_to(const value_type& x)
566 return make_local_iterator(node_from_value<node_type>(&x));
569 const_local_iterator local_iterator_to(const value_type& x)const
571 return make_local_iterator(node_from_value<node_type>(&x));
576 float load_factor()const BOOST_NOEXCEPT
577 {return static_cast<float>(size())/bucket_count();}
578 float max_load_factor()const BOOST_NOEXCEPT{return mlf;}
579 void max_load_factor(float z){mlf=z;calculate_max_load();}
581 void rehash(size_type n)
583 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
584 if(size()<=max_load&&n<=bucket_count())return;
586 size_type bc =(std::numeric_limits<size_type>::max)();
587 float fbc=static_cast<float>(1+size()/mlf);
589 bc=static_cast<size_type>(fbc);
592 unchecked_rehash(bc);
595 void reserve(size_type n)
597 rehash(static_cast<size_type>(std::ceil(static_cast<double>(n)/mlf)));
600 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
601 hashed_index(const ctor_args_list& args_list,const allocator_type& al):
602 super(args_list.get_tail(),al),
603 key(tuples::get<1>(args_list.get_head())),
604 hash_(tuples::get<2>(args_list.get_head())),
605 eq_(tuples::get<3>(args_list.get_head())),
606 buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
609 calculate_max_load();
613 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
616 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
623 buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
627 /* Copy ctor just takes the internal configuration objects from x. The rest
628 * is done in subsequent call to copy_().
633 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
634 do_not_copy_elements_tag):
635 super(x,do_not_copy_elements_tag()),
637 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
644 buckets(x.get_allocator(),header()->impl(),0),
647 calculate_max_load();
652 /* the container is guaranteed to be empty by now */
655 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
656 iterator make_iterator(node_type* node)
658 return iterator(node,this);
661 const_iterator make_iterator(node_type* node)const
663 return const_iterator(node,const_cast<hashed_index*>(this));
666 iterator make_iterator(node_type* node)
668 return iterator(node);
671 const_iterator make_iterator(node_type* node)const
673 return const_iterator(node);
677 local_iterator make_local_iterator(node_type* node)
679 return local_iterator(node);
682 const_local_iterator make_local_iterator(node_type* node)const
684 return const_local_iterator(node);
688 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
689 const copy_map_type& map)
691 copy_(x,map,Category());
695 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
696 const copy_map_type& map,hashed_unique_tag)
699 node_impl_pointer end_org=x.header()->impl(),
701 cpy=header()->impl();
703 node_impl_pointer prev_org=org->prior(),
705 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
706 node_type::from_impl(prev_org))))->impl();
707 cpy->prior()=prev_cpy;
708 if(node_alg::is_first_of_bucket(org)){
709 node_impl_base_pointer buc_org=prev_org->next(),
711 buckets.begin()+(buc_org-x.buckets.begin());
712 prev_cpy->next()=buc_cpy;
713 buc_cpy->prior()=cpy;
716 prev_cpy->next()=node_impl_type::base_pointer_from(cpy);
720 }while(org!=end_org);
727 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
728 const copy_map_type& map,hashed_non_unique_tag)
731 node_impl_pointer end_org=x.header()->impl(),
733 cpy=header()->impl();
735 node_impl_pointer next_org=node_alg::after(org),
737 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
738 node_type::from_impl(next_org))))->impl();
739 if(node_alg::is_first_of_bucket(next_org)){
740 node_impl_base_pointer buc_org=org->next(),
742 buckets.begin()+(buc_org-x.buckets.begin());
744 buc_cpy->prior()=next_cpy;
745 next_cpy->prior()=cpy;
748 if(org->next()==node_impl_type::base_pointer_from(next_org)){
749 cpy->next()=node_impl_type::base_pointer_from(next_cpy);
753 node_impl_type::base_pointer_from(
754 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
755 node_type::from_impl(
756 node_impl_type::pointer_from(org->next())))))->impl());
759 if(next_org->prior()!=org){
761 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
762 node_type::from_impl(next_org->prior()))))->impl();
765 next_cpy->prior()=cpy;
770 }while(org!=end_org);
776 template<typename Variant>
777 final_node_type* insert_(
778 value_param_type v,final_node_type*& x,Variant variant)
780 reserve_for_insert(size()+1);
782 std::size_t buc=find_bucket(v);
783 link_info pos(buckets.at(buc));
784 if(!link_point(v,pos)){
785 return static_cast<final_node_type*>(
786 node_type::from_impl(node_impl_type::pointer_from(pos)));
789 final_node_type* res=super::insert_(v,x,variant);
790 if(res==x)link(static_cast<node_type*>(x),pos);
794 template<typename Variant>
795 final_node_type* insert_(
796 value_param_type v,node_type* position,final_node_type*& x,Variant variant)
798 reserve_for_insert(size()+1);
800 std::size_t buc=find_bucket(v);
801 link_info pos(buckets.at(buc));
802 if(!link_point(v,pos)){
803 return static_cast<final_node_type*>(
804 node_type::from_impl(node_impl_type::pointer_from(pos)));
807 final_node_type* res=super::insert_(v,position,x,variant);
808 if(res==x)link(static_cast<node_type*>(x),pos);
812 void erase_(node_type* x)
817 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
822 void delete_all_nodes_()
824 delete_all_nodes_(Category());
827 void delete_all_nodes_(hashed_unique_tag)
829 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
830 node_impl_pointer y=x->prior();
831 this->final_delete_node_(
832 static_cast<final_node_type*>(node_type::from_impl(x)));
837 void delete_all_nodes_(hashed_non_unique_tag)
839 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
840 node_impl_pointer y=x->prior();
841 if(y->next()!=node_impl_type::base_pointer_from(x)&&
842 y->next()->prior()!=x){ /* n-1 of group */
843 /* Make the second node prior() pointer back-linked so that it won't
844 * refer to a deleted node when the time for its own destruction comes.
847 node_impl_pointer first=node_impl_type::pointer_from(y->next());
848 first->next()->prior()=first;
850 this->final_delete_node_(
851 static_cast<final_node_type*>(node_type::from_impl(x)));
859 buckets.clear(header()->impl());
861 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
862 safe_super::detach_dereferenceable_iterators();
867 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
869 std::swap(key,x.key);
870 std::swap(hash_,x.hash_);
871 std::swap(eq_,x.eq_);
872 buckets.swap(x.buckets);
873 std::swap(mlf,x.mlf);
874 std::swap(max_load,x.max_load);
876 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
884 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
886 buckets.swap(x.buckets);
887 std::swap(mlf,x.mlf);
888 std::swap(max_load,x.max_load);
890 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
894 super::swap_elements_(x);
897 template<typename Variant>
898 bool replace_(value_param_type v,node_type* x,Variant variant)
900 if(eq_(key(v),key(x->value()))){
901 return super::replace_(v,x,variant);
908 std::size_t buc=find_bucket(v);
909 link_info pos(buckets.at(buc));
910 if(link_point(v,pos)&&super::replace_(v,x,variant)){
924 bool modify_(node_type* x)
929 buc=find_bucket(x->value());
930 b=in_place(x->impl(),key(x->value()),buc);
940 link_info pos(buckets.at(buc));
941 if(!link_point(x->value(),pos)){
944 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
954 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
964 if(!super::modify_(x)){
967 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
977 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
986 bool modify_rollback_(node_type* x)
988 std::size_t buc=find_bucket(x->value());
989 if(in_place(x->impl(),key(x->value()),buc)){
990 return super::modify_rollback_(x);
997 link_info pos(buckets.at(buc));
998 if(link_point(x->value(),pos)&&super::modify_rollback_(x)){
1014 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
1015 /* defect macro refers to class, not function, templates, but anyway */
1017 template<typename K,typename H,typename P,typename S,typename T,typename C>
1018 friend bool operator==(
1019 const hashed_index<K,H,P,S,T,C>&,const hashed_index<K,H,P,S,T,C>& y);
1022 bool equals(const hashed_index& x)const{return equals(x,Category());}
1024 bool equals(const hashed_index& x,hashed_unique_tag)const
1026 if(size()!=x.size())return false;
1027 for(const_iterator it=begin(),it_end=end(),it2_end=x.end();
1029 const_iterator it2=x.find(key(*it));
1030 if(it2==it2_end||!(*it==*it2))return false;
1035 bool equals(const hashed_index& x,hashed_non_unique_tag)const
1037 if(size()!=x.size())return false;
1038 for(const_iterator it=begin(),it_end=end();it!=it_end;){
1039 const_iterator it2,it2_last;
1040 boost::tie(it2,it2_last)=x.equal_range(key(*it));
1041 if(it2==it2_last)return false;
1043 const_iterator it_last=make_iterator(
1044 node_type::from_impl(end_of_range(it.get_node()->impl())));
1045 if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false;
1047 /* From is_permutation code in
1048 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
1051 for(;it!=it_last;++it,++it2){
1052 if(!(*it==*it2))break;
1055 for(const_iterator scan=it;scan!=it_last;++scan){
1056 if(std::find(it,scan,*scan)!=scan)continue;
1057 std::ptrdiff_t matches=std::count(it2,it2_last,*scan);
1058 if(matches==0||matches!=std::count(scan,it_last,*scan))return false;
1066 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1069 template<typename Archive>
1071 Archive& ar,const unsigned int version,const index_saver_type& sm)const
1073 ar<<serialization::make_nvp("position",buckets);
1074 super::save_(ar,version,sm);
1077 template<typename Archive>
1078 void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1080 ar>>serialization::make_nvp("position",buckets);
1081 super::load_(ar,version,lm);
1085 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1086 /* invariant stuff */
1088 bool invariant_()const
1090 if(size()==0||begin()==end()){
1091 if(size()!=0||begin()!=end())return false;
1095 for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
1096 if(s0!=size())return false;
1099 for(size_type buc=0;buc<bucket_count();++buc){
1101 for(const_local_iterator it=begin(buc),it_end=end(buc);
1102 it!=it_end;++it,++ss1){
1103 if(find_bucket(*it)!=buc)return false;
1105 if(ss1!=bucket_size(buc))return false;
1108 if(s1!=size())return false;
1111 return super::invariant_();
1114 /* This forwarding function eases things for the boost::mem_fn construct
1115 * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
1116 * final_check_invariant is already an inherited member function of index.
1118 void check_invariant_()const{this->final_check_invariant_();}
1122 node_type* header()const{return this->final_header();}
1124 std::size_t find_bucket(value_param_type v)const
1126 return bucket(key(v));
1129 struct link_info_non_unique
1131 link_info_non_unique(node_impl_base_pointer pos):
1132 first(pos),last(node_impl_base_pointer(0)){}
1134 operator const node_impl_base_pointer&()const{return this->first;}
1136 node_impl_base_pointer first,last;
1139 typedef typename mpl::if_<
1140 is_same<Category,hashed_unique_tag>,
1141 node_impl_base_pointer,
1142 link_info_non_unique
1145 bool link_point(value_param_type v,link_info& pos)
1147 return link_point(v,pos,Category());
1151 value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
1153 for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0);
1154 x=node_alg::after_local(x)){
1155 if(eq_(key(v),key(node_type::from_impl(x)->value()))){
1156 pos=node_impl_type::base_pointer_from(x);
1164 value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag)
1166 for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0);
1167 x=node_alg::next_to_inspect(x)){
1168 if(eq_(key(v),key(node_type::from_impl(x)->value()))){
1169 pos.first=node_impl_type::base_pointer_from(x);
1170 pos.last=node_impl_type::base_pointer_from(last_of_range(x));
1177 node_impl_pointer last_of_range(node_impl_pointer x)const
1179 return last_of_range(x,Category());
1182 node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
1187 node_impl_pointer last_of_range(
1188 node_impl_pointer x,hashed_non_unique_tag)const
1190 node_impl_base_pointer y=x->next();
1191 node_impl_pointer z=y->prior();
1192 if(z==x){ /* range of size 1 or 2 */
1193 node_impl_pointer yy=node_impl_type::pointer_from(y);
1196 key(node_type::from_impl(x)->value()),
1197 key(node_type::from_impl(yy)->value()))?yy:x;
1199 else if(z->prior()==x) /* last of bucket */
1201 else /* group of size>2 */
1205 node_impl_pointer end_of_range(node_impl_pointer x)const
1207 return end_of_range(x,Category());
1210 node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const
1212 return node_alg::after(last_of_range(x));
1215 node_impl_pointer end_of_range(
1216 node_impl_pointer x,hashed_non_unique_tag)const
1218 node_impl_base_pointer y=x->next();
1219 node_impl_pointer z=y->prior();
1220 if(z==x){ /* range of size 1 or 2 */
1221 node_impl_pointer yy=node_impl_type::pointer_from(y);
1223 key(node_type::from_impl(x)->value()),
1224 key(node_type::from_impl(yy)->value())))yy=x;
1225 return yy->next()->prior()==yy?
1226 node_impl_type::pointer_from(yy->next()):
1227 yy->next()->prior();
1229 else if(z->prior()==x) /* last of bucket */
1231 else /* group of size>2 */
1232 return z->next()->prior()==z?
1233 node_impl_type::pointer_from(z->next()):
1237 void link(node_type* x,const link_info& pos)
1239 link(x,pos,Category());
1242 void link(node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
1244 node_alg::link(x->impl(),pos,header()->impl());
1247 void link(node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag)
1249 if(pos.last==node_impl_base_pointer(0)){
1250 node_alg::link(x->impl(),pos.first,header()->impl());
1255 node_impl_type::pointer_from(pos.first),
1256 node_impl_type::pointer_from(pos.last));
1260 void unlink(node_type* x)
1262 node_alg::unlink(x->impl());
1265 typedef typename node_alg::unlink_undo unlink_undo;
1267 void unlink(node_type* x,unlink_undo& undo)
1269 node_alg::unlink(x->impl(),undo);
1272 void calculate_max_load()
1274 float fml=static_cast<float>(mlf*static_cast<float>(bucket_count()));
1275 max_load=(std::numeric_limits<size_type>::max)();
1276 if(max_load>fml)max_load=static_cast<size_type>(fml);
1279 void reserve_for_insert(size_type n)
1282 size_type bc =(std::numeric_limits<size_type>::max)();
1283 float fbc=static_cast<float>(1+static_cast<double>(n)/mlf);
1284 if(bc>fbc)bc =static_cast<size_type>(fbc);
1285 unchecked_rehash(bc);
1289 void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
1291 void unchecked_rehash(size_type n,hashed_unique_tag)
1293 node_impl_type cpy_end_node;
1294 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1295 end_=header()->impl();
1296 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1300 std::size_t,allocator_type> hashes(get_allocator(),size());
1302 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1303 std::size_t i=0,size_=size();
1304 bool within_bucket=false;
1307 node_impl_pointer x=end_->prior();
1309 /* only this can possibly throw */
1310 std::size_t h=hash_(key(node_type::from_impl(x)->value()));
1313 node_ptrs.data()[i]=x;
1314 within_bucket=!node_alg::unlink_last(end_);
1315 node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1320 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1321 if(!within_bucket)prev_buc=~prev_buc;
1323 for(std::size_t j=i;j--;){
1324 std::size_t buc=buckets.position(hashes.data()[j]);
1325 node_impl_pointer x=node_ptrs.data()[j];
1326 if(buc==prev_buc)node_alg::append(x,end_);
1327 else node_alg::link(x,buckets.at(buc),end_);
1336 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1337 end_->next()=cpy_end->next();
1338 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1339 buckets.swap(buckets_cpy);
1340 calculate_max_load();
1343 void unchecked_rehash(size_type n,hashed_non_unique_tag)
1345 node_impl_type cpy_end_node;
1346 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1347 end_=header()->impl();
1348 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1352 std::size_t,allocator_type> hashes(get_allocator(),size());
1354 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1356 bool within_bucket=false;
1359 node_impl_pointer x=end_->prior();
1362 /* only this can possibly throw */
1363 std::size_t h=hash_(key(node_type::from_impl(x)->value()));
1366 node_ptrs.data()[i]=x;
1367 std::pair<node_impl_pointer,bool> p=
1368 node_alg::unlink_last_group(end_);
1369 node_alg::link_range(
1370 p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1371 within_bucket=!(p.second);
1376 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1377 if(!within_bucket)prev_buc=~prev_buc;
1379 for(std::size_t j=i;j--;){
1380 std::size_t buc=buckets.position(hashes.data()[j]);
1381 node_impl_pointer x=node_ptrs.data()[j],
1383 x->prior()->next()!=node_impl_type::base_pointer_from(x)&&
1384 x->prior()->next()->prior()!=x?
1385 node_impl_type::pointer_from(x->prior()->next()):x;
1386 node_alg::unlink_range(y,x);
1387 if(buc==prev_buc)node_alg::append_range(y,x,end_);
1388 else node_alg::link_range(y,x,buckets.at(buc),end_);
1397 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1398 end_->next()=cpy_end->next();
1399 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1400 buckets.swap(buckets_cpy);
1401 calculate_max_load();
1404 bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
1406 return in_place(x,k,buc,Category());
1410 node_impl_pointer x,key_param_type k,std::size_t buc,
1411 hashed_unique_tag)const
1414 for(node_impl_pointer y=buckets.at(buc)->prior();
1415 y!=node_impl_pointer(0);y=node_alg::after_local(y)){
1417 else if(eq_(k,key(node_type::from_impl(y)->value())))return false;
1423 node_impl_pointer x,key_param_type k,std::size_t buc,
1424 hashed_non_unique_tag)const
1428 for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){
1429 if(node_alg::is_first_of_group(y)){ /* group of 3 or more */
1431 /* in place <-> equal to some other member of the group */
1434 key(node_type::from_impl(
1435 node_impl_type::pointer_from(y->next()))->value()));
1438 node_impl_pointer z=
1439 node_alg::after_local(y->next()->prior()); /* end of range */
1440 if(eq_(k,key(node_type::from_impl(y)->value()))){
1441 if(found)return false; /* x lies outside */
1443 if(y==x)return true;
1444 y=node_alg::after_local(y);
1446 return false; /* x not found */
1449 if(range_size==1&&!found)return false;
1450 if(range_size==2)return found;
1452 y=z; /* skip range (and potentially x, too, which is fine) */
1456 else{ /* group of 1 or 2 */
1458 if(range_size==1)return true;
1462 else if(eq_(k,key(node_type::from_impl(y)->value()))){
1463 if(range_size==0&&found)return false;
1464 if(range_size==1&&!found)return false;
1465 if(range_size==2)return false;
1469 if(range_size==1&&!found)return false;
1470 if(range_size==2)return found;
1473 y=node_alg::after_local(y);
1479 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1480 void detach_iterators(node_type* x)
1482 iterator it=make_iterator(x);
1483 safe_mode::detach_equivalent_iterators(it);
1487 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1488 std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1490 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1491 std::pair<final_node_type*,bool>p=
1492 this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1493 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1496 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1497 iterator emplace_hint_impl(
1498 iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1500 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1501 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1502 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1503 std::pair<final_node_type*,bool>p=
1504 this->final_emplace_hint_(
1505 static_cast<final_node_type*>(position.get_node()),
1506 BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1507 return make_iterator(p.first);
1511 typename CompatibleHash,typename CompatiblePred
1515 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1517 return find(k,hash,eq,mpl::false_());
1521 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1524 const CompatibleKey& k,
1525 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1527 std::size_t buc=buckets.position(hash(k));
1528 for(node_impl_pointer x=buckets.at(buc)->prior();
1529 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1530 if(eq(k,key(node_type::from_impl(x)->value()))){
1531 return make_iterator(node_type::from_impl(x));
1538 typename CompatibleHash,typename CompatiblePred
1542 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1544 return count(k,hash,eq,mpl::false_());
1548 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1551 const CompatibleKey& k,
1552 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1554 std::size_t buc=buckets.position(hash(k));
1555 for(node_impl_pointer x=buckets.at(buc)->prior();
1556 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1557 if(eq(k,key(node_type::from_impl(x)->value()))){
1559 node_impl_pointer y=end_of_range(x);
1562 x=node_alg::after(x);
1571 typename CompatibleHash,typename CompatiblePred
1573 std::pair<iterator,iterator> equal_range(
1575 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1577 return equal_range(k,hash,eq,mpl::false_());
1581 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1583 std::pair<iterator,iterator> equal_range(
1584 const CompatibleKey& k,
1585 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1587 std::size_t buc=buckets.position(hash(k));
1588 for(node_impl_pointer x=buckets.at(buc)->prior();
1589 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1590 if(eq(k,key(node_type::from_impl(x)->value()))){
1591 return std::pair<iterator,iterator>(
1592 make_iterator(node_type::from_impl(x)),
1593 make_iterator(node_type::from_impl(end_of_range(x))));
1596 return std::pair<iterator,iterator>(end(),end());
1602 bucket_array_type buckets;
1606 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1607 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1608 #pragma parse_mfunc_templ reset
1615 typename KeyFromValue,typename Hash,typename Pred,
1616 typename SuperMeta,typename TagList,typename Category
1619 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1620 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1626 typename KeyFromValue,typename Hash,typename Pred,
1627 typename SuperMeta,typename TagList,typename Category
1630 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1631 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1636 /* specialized algorithms */
1639 typename KeyFromValue,typename Hash,typename Pred,
1640 typename SuperMeta,typename TagList,typename Category
1643 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1644 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1649 } /* namespace multi_index::detail */
1651 /* hashed index specifiers */
1653 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1654 struct hashed_unique
1656 typedef typename detail::hashed_index_args<
1657 Arg1,Arg2,Arg3,Arg4> index_args;
1658 typedef typename index_args::tag_list_type::type tag_list_type;
1659 typedef typename index_args::key_from_value_type key_from_value_type;
1660 typedef typename index_args::hash_type hash_type;
1661 typedef typename index_args::pred_type pred_type;
1663 template<typename Super>
1666 typedef detail::hashed_index_node<Super,detail::hashed_unique_tag> type;
1669 template<typename SuperMeta>
1672 typedef detail::hashed_index<
1673 key_from_value_type,hash_type,pred_type,
1674 SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1678 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1679 struct hashed_non_unique
1681 typedef typename detail::hashed_index_args<
1682 Arg1,Arg2,Arg3,Arg4> index_args;
1683 typedef typename index_args::tag_list_type::type tag_list_type;
1684 typedef typename index_args::key_from_value_type key_from_value_type;
1685 typedef typename index_args::hash_type hash_type;
1686 typedef typename index_args::pred_type pred_type;
1688 template<typename Super>
1691 typedef detail::hashed_index_node<
1692 Super,detail::hashed_non_unique_tag> type;
1695 template<typename SuperMeta>
1698 typedef detail::hashed_index<
1699 key_from_value_type,hash_type,pred_type,
1700 SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1704 } /* namespace multi_index */
1706 } /* namespace boost */
1708 /* Boost.Foreach compatibility */
1711 typename KeyFromValue,typename Hash,typename Pred,
1712 typename SuperMeta,typename TagList,typename Category
1714 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1715 boost::multi_index::detail::hashed_index<
1716 KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>*&,
1717 boost_foreach_argument_dependent_lookup_hack)
1722 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1723 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF