1 /* Copyright 2003-2018 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/core/addressof.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/allocator_traits.hpp>
30 #include <boost/multi_index/detail/auto_space.hpp>
31 #include <boost/multi_index/detail/bucket_array.hpp>
32 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
33 #include <boost/multi_index/detail/hash_index_iterator.hpp>
34 #include <boost/multi_index/detail/index_node_base.hpp>
35 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
36 #include <boost/multi_index/detail/promotes_arg.hpp>
37 #include <boost/multi_index/detail/safe_mode.hpp>
38 #include <boost/multi_index/detail/scope_guard.hpp>
39 #include <boost/multi_index/detail/vartempl_support.hpp>
40 #include <boost/multi_index/hashed_index_fwd.hpp>
41 #include <boost/tuple/tuple.hpp>
42 #include <boost/type_traits/is_same.hpp>
49 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
50 #include <initializer_list>
53 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
54 #include <boost/serialization/nvp.hpp>
57 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
58 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) \
59 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
60 detail::make_obj_guard(x,&hashed_index::check_invariant_); \
61 BOOST_JOIN(check_invariant_,__LINE__).touch();
62 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \
63 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this)
65 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x)
66 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
71 namespace multi_index{
75 /* hashed_index adds a layer of hashed indexing to a given Super */
77 /* Most of the implementation of unique and non-unique indices is
78 * shared. We tell from one another on instantiation time by using
79 * Category tags defined in hash_index_node.hpp.
83 typename KeyFromValue,typename Hash,typename Pred,
84 typename SuperMeta,typename TagList,typename Category
87 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
89 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
90 ,public safe_mode::safe_container<
91 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
95 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
96 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
97 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
98 * lifetime of const references bound to temporaries --precisely what
102 #pragma parse_mfunc_templ off
105 typedef typename SuperMeta::type super;
108 typedef hashed_index_node<
109 typename super::node_type,Category> node_type;
112 typedef typename node_type::node_alg node_alg;
113 typedef typename node_type::impl_type node_impl_type;
114 typedef typename node_impl_type::pointer node_impl_pointer;
115 typedef typename node_impl_type::base_pointer node_impl_base_pointer;
116 typedef bucket_array<
117 typename super::final_allocator_type> bucket_array_type;
122 typedef typename KeyFromValue::result_type key_type;
123 typedef typename node_type::value_type value_type;
124 typedef KeyFromValue key_from_value;
126 typedef Pred key_equal;
127 typedef typename super::final_allocator_type allocator_type;
130 typedef allocator_traits<allocator_type> alloc_traits;
133 typedef typename alloc_traits::pointer pointer;
134 typedef typename alloc_traits::const_pointer const_pointer;
135 typedef value_type& reference;
136 typedef const value_type& const_reference;
137 typedef typename alloc_traits::size_type size_type;
138 typedef typename alloc_traits::difference_type difference_type;
139 typedef tuple<size_type,
140 key_from_value,hasher,key_equal> ctor_args;
142 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
143 typedef safe_mode::safe_iterator<
144 hashed_index_iterator<
145 node_type,bucket_array_type,
146 hashed_index_global_iterator_tag>,
147 hashed_index> iterator;
149 typedef hashed_index_iterator<
150 node_type,bucket_array_type,
151 hashed_index_global_iterator_tag> iterator;
154 typedef iterator const_iterator;
156 typedef hashed_index_iterator<
157 node_type,bucket_array_type,
158 hashed_index_local_iterator_tag> local_iterator;
159 typedef local_iterator const_local_iterator;
161 typedef TagList tag_list;
164 typedef typename super::final_node_type final_node_type;
165 typedef tuples::cons<
167 typename super::ctor_args_list> ctor_args_list;
168 typedef typename mpl::push_front<
169 typename super::index_type_list,
170 hashed_index>::type index_type_list;
171 typedef typename mpl::push_front<
172 typename super::iterator_type_list,
173 iterator>::type iterator_type_list;
174 typedef typename mpl::push_front<
175 typename super::const_iterator_type_list,
176 const_iterator>::type const_iterator_type_list;
177 typedef typename super::copy_map_type copy_map_type;
179 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
180 typedef typename super::index_saver_type index_saver_type;
181 typedef typename super::index_loader_type index_loader_type;
185 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
186 typedef safe_mode::safe_container<
187 hashed_index> safe_super;
190 typedef typename call_traits<value_type>::param_type value_param_type;
191 typedef typename call_traits<
192 key_type>::param_type key_param_type;
194 /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
198 typedef std::pair<iterator,bool> emplace_return_type;
202 /* construct/destroy/copy
203 * Default and copy ctors are in the protected section as indices are
204 * not supposed to be created on their own. No range ctor either.
207 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
208 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
210 this->final()=x.final();
214 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
215 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
216 std::initializer_list<value_type> list)
223 allocator_type get_allocator()const BOOST_NOEXCEPT
225 return this->final().get_allocator();
228 /* size and capacity */
230 bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
231 size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
232 size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
236 iterator begin()BOOST_NOEXCEPT
237 {return make_iterator(node_type::from_impl(header()->next()->prior()));}
238 const_iterator begin()const BOOST_NOEXCEPT
239 {return make_iterator(node_type::from_impl(header()->next()->prior()));}
240 iterator end()BOOST_NOEXCEPT{return make_iterator(header());}
241 const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());}
242 const_iterator cbegin()const BOOST_NOEXCEPT{return begin();}
243 const_iterator cend()const BOOST_NOEXCEPT{return end();}
245 iterator iterator_to(const value_type& x)
247 return make_iterator(node_from_value<node_type>(boost::addressof(x)));
250 const_iterator iterator_to(const value_type& x)const
252 return make_iterator(node_from_value<node_type>(boost::addressof(x)));
257 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
258 emplace_return_type,emplace,emplace_impl)
260 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
261 iterator,emplace_hint,emplace_hint_impl,iterator,position)
263 std::pair<iterator,bool> insert(const value_type& x)
265 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
266 std::pair<final_node_type*,bool> p=this->final_insert_(x);
267 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
270 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
272 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
273 std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
274 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
277 iterator insert(iterator position,const value_type& x)
279 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
280 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
281 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
282 std::pair<final_node_type*,bool> p=this->final_insert_(
283 x,static_cast<final_node_type*>(position.get_node()));
284 return make_iterator(p.first);
287 iterator insert(iterator position,BOOST_RV_REF(value_type) x)
289 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
290 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
291 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
292 std::pair<final_node_type*,bool> p=this->final_insert_rv_(
293 x,static_cast<final_node_type*>(position.get_node()));
294 return make_iterator(p.first);
297 template<typename InputIterator>
298 void insert(InputIterator first,InputIterator last)
300 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
301 for(;first!=last;++first)this->final_insert_ref_(*first);
304 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
305 void insert(std::initializer_list<value_type> list)
307 insert(list.begin(),list.end());
311 iterator erase(iterator position)
313 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
314 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
315 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
316 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
317 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
321 size_type erase(key_param_type k)
323 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
325 std::size_t buc=buckets.position(hash_(k));
326 for(node_impl_pointer x=buckets.at(buc)->prior();
327 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
328 if(eq_(k,key(node_type::from_impl(x)->value()))){
329 node_impl_pointer y=end_of_range(x);
332 node_impl_pointer z=node_alg::after(x);
334 static_cast<final_node_type*>(node_type::from_impl(x)));
344 iterator erase(iterator first,iterator last)
346 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
347 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
348 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
349 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
350 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
351 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
358 bool replace(iterator position,const value_type& x)
360 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
361 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
362 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
363 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
364 return this->final_replace_(
365 x,static_cast<final_node_type*>(position.get_node()));
368 bool replace(iterator position,BOOST_RV_REF(value_type) x)
370 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
371 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
372 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
373 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
374 return this->final_replace_rv_(
375 x,static_cast<final_node_type*>(position.get_node()));
378 template<typename Modifier>
379 bool modify(iterator position,Modifier mod)
381 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
382 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
383 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
384 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
386 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
387 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
388 * this is not added. Left it for all compilers as it does no
395 return this->final_modify_(
396 mod,static_cast<final_node_type*>(position.get_node()));
399 template<typename Modifier,typename Rollback>
400 bool modify(iterator position,Modifier mod,Rollback back_)
402 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
403 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
404 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
405 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
407 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
408 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
409 * this is not added. Left it for all compilers as it does no
416 return this->final_modify_(
417 mod,back_,static_cast<final_node_type*>(position.get_node()));
420 template<typename Modifier>
421 bool modify_key(iterator position,Modifier mod)
423 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
424 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
425 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
426 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
428 position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
431 template<typename Modifier,typename Rollback>
432 bool modify_key(iterator position,Modifier mod,Rollback back_)
434 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
435 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
436 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
437 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
440 modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
441 modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
444 void clear()BOOST_NOEXCEPT
446 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
447 this->final_clear_();
450 void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
452 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
453 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x);
454 this->final_swap_(x.final());
459 key_from_value key_extractor()const{return key;}
460 hasher hash_function()const{return hash_;}
461 key_equal key_eq()const{return eq_;}
465 /* Internally, these ops rely on const_iterator being the same
469 /* Implementation note: When CompatibleKey is consistently promoted to
470 * KeyFromValue::result_type for equality comparison, the promotion is made
471 * once in advance to increase efficiency.
474 template<typename CompatibleKey>
475 iterator find(const CompatibleKey& k)const
477 return find(k,hash_,eq_);
481 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
484 const CompatibleKey& k,
485 const CompatibleHash& hash,const CompatiblePred& eq)const
488 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
491 template<typename CompatibleKey>
492 size_type count(const CompatibleKey& k)const
494 return count(k,hash_,eq_);
498 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
501 const CompatibleKey& k,
502 const CompatibleHash& hash,const CompatiblePred& eq)const
505 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
508 template<typename CompatibleKey>
509 std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
511 return equal_range(k,hash_,eq_);
515 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
517 std::pair<iterator,iterator> equal_range(
518 const CompatibleKey& k,
519 const CompatibleHash& hash,const CompatiblePred& eq)const
522 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
525 /* bucket interface */
527 size_type bucket_count()const BOOST_NOEXCEPT
529 return static_cast<size_type>(buckets.size());
532 size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);}
534 size_type bucket_size(size_type n)const
537 for(node_impl_pointer x=buckets.at(n)->prior();
538 x!=node_impl_pointer(0);x=node_alg::after_local(x)){
544 size_type bucket(key_param_type k)const
546 return static_cast<size_type>(buckets.position(hash_(k)));
549 local_iterator begin(size_type n)
551 return const_cast<const hashed_index*>(this)->begin(n);
554 const_local_iterator begin(size_type n)const
556 node_impl_pointer x=buckets.at(n)->prior();
557 if(x==node_impl_pointer(0))return end(n);
558 return make_local_iterator(node_type::from_impl(x));
561 local_iterator end(size_type n)
563 return const_cast<const hashed_index*>(this)->end(n);
566 const_local_iterator end(size_type)const
568 return make_local_iterator(0);
571 const_local_iterator cbegin(size_type n)const{return begin(n);}
572 const_local_iterator cend(size_type n)const{return end(n);}
574 local_iterator local_iterator_to(const value_type& x)
576 return make_local_iterator(
577 node_from_value<node_type>(boost::addressof(x)));
580 const_local_iterator local_iterator_to(const value_type& x)const
582 return make_local_iterator(
583 node_from_value<node_type>(boost::addressof(x)));
588 float load_factor()const BOOST_NOEXCEPT
589 {return static_cast<float>(size())/bucket_count();}
590 float max_load_factor()const BOOST_NOEXCEPT{return mlf;}
591 void max_load_factor(float z){mlf=z;calculate_max_load();}
593 void rehash(size_type n)
595 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
596 if(size()<=max_load&&n<=bucket_count())return;
598 size_type bc =(std::numeric_limits<size_type>::max)();
599 float fbc=1.0f+static_cast<float>(size())/mlf;
601 bc=static_cast<size_type>(fbc);
604 unchecked_rehash(bc);
607 void reserve(size_type n)
609 rehash(static_cast<size_type>(std::ceil(static_cast<float>(n)/mlf)));
612 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
613 hashed_index(const ctor_args_list& args_list,const allocator_type& al):
614 super(args_list.get_tail(),al),
615 key(tuples::get<1>(args_list.get_head())),
616 hash_(tuples::get<2>(args_list.get_head())),
617 eq_(tuples::get<3>(args_list.get_head())),
618 buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
621 calculate_max_load();
625 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
628 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
635 buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
639 /* Copy ctor just takes the internal configuration objects from x. The rest
640 * is done in subsequent call to copy_().
645 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
646 do_not_copy_elements_tag):
647 super(x,do_not_copy_elements_tag()),
649 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
656 buckets(x.get_allocator(),header()->impl(),0),
659 calculate_max_load();
664 /* the container is guaranteed to be empty by now */
667 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
668 iterator make_iterator(node_type* node)
670 return iterator(node,this);
673 const_iterator make_iterator(node_type* node)const
675 return const_iterator(node,const_cast<hashed_index*>(this));
678 iterator make_iterator(node_type* node)
680 return iterator(node);
683 const_iterator make_iterator(node_type* node)const
685 return const_iterator(node);
689 local_iterator make_local_iterator(node_type* node)
691 return local_iterator(node);
694 const_local_iterator make_local_iterator(node_type* node)const
696 return const_local_iterator(node);
700 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
701 const copy_map_type& map)
703 copy_(x,map,Category());
707 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
708 const copy_map_type& map,hashed_unique_tag)
711 node_impl_pointer end_org=x.header()->impl(),
713 cpy=header()->impl();
715 node_impl_pointer prev_org=org->prior(),
717 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
718 node_type::from_impl(prev_org))))->impl();
719 cpy->prior()=prev_cpy;
720 if(node_alg::is_first_of_bucket(org)){
721 node_impl_base_pointer buc_org=prev_org->next(),
723 buckets.begin()+(buc_org-x.buckets.begin());
724 prev_cpy->next()=buc_cpy;
725 buc_cpy->prior()=cpy;
728 prev_cpy->next()=node_impl_type::base_pointer_from(cpy);
732 }while(org!=end_org);
739 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
740 const copy_map_type& map,hashed_non_unique_tag)
743 node_impl_pointer end_org=x.header()->impl(),
745 cpy=header()->impl();
747 node_impl_pointer next_org=node_alg::after(org),
749 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
750 node_type::from_impl(next_org))))->impl();
751 if(node_alg::is_first_of_bucket(next_org)){
752 node_impl_base_pointer buc_org=org->next(),
754 buckets.begin()+(buc_org-x.buckets.begin());
756 buc_cpy->prior()=next_cpy;
757 next_cpy->prior()=cpy;
760 if(org->next()==node_impl_type::base_pointer_from(next_org)){
761 cpy->next()=node_impl_type::base_pointer_from(next_cpy);
765 node_impl_type::base_pointer_from(
766 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
767 node_type::from_impl(
768 node_impl_type::pointer_from(org->next())))))->impl());
771 if(next_org->prior()!=org){
773 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
774 node_type::from_impl(next_org->prior()))))->impl();
777 next_cpy->prior()=cpy;
782 }while(org!=end_org);
788 template<typename Variant>
789 final_node_type* insert_(
790 value_param_type v,final_node_type*& x,Variant variant)
792 reserve_for_insert(size()+1);
794 std::size_t buc=find_bucket(v);
795 link_info pos(buckets.at(buc));
796 if(!link_point(v,pos)){
797 return static_cast<final_node_type*>(
798 node_type::from_impl(node_impl_type::pointer_from(pos)));
801 final_node_type* res=super::insert_(v,x,variant);
802 if(res==x)link(static_cast<node_type*>(x),pos);
806 template<typename Variant>
807 final_node_type* insert_(
808 value_param_type v,node_type* position,final_node_type*& x,Variant variant)
810 reserve_for_insert(size()+1);
812 std::size_t buc=find_bucket(v);
813 link_info pos(buckets.at(buc));
814 if(!link_point(v,pos)){
815 return static_cast<final_node_type*>(
816 node_type::from_impl(node_impl_type::pointer_from(pos)));
819 final_node_type* res=super::insert_(v,position,x,variant);
820 if(res==x)link(static_cast<node_type*>(x),pos);
824 void erase_(node_type* x)
829 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
834 void delete_all_nodes_()
836 delete_all_nodes_(Category());
839 void delete_all_nodes_(hashed_unique_tag)
841 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
842 node_impl_pointer y=x->prior();
843 this->final_delete_node_(
844 static_cast<final_node_type*>(node_type::from_impl(x)));
849 void delete_all_nodes_(hashed_non_unique_tag)
851 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
852 node_impl_pointer y=x->prior();
853 if(y->next()!=node_impl_type::base_pointer_from(x)&&
854 y->next()->prior()!=x){ /* n-1 of group */
855 /* Make the second node prior() pointer back-linked so that it won't
856 * refer to a deleted node when the time for its own destruction comes.
859 node_impl_pointer first=node_impl_type::pointer_from(y->next());
860 first->next()->prior()=first;
862 this->final_delete_node_(
863 static_cast<final_node_type*>(node_type::from_impl(x)));
871 buckets.clear(header()->impl());
873 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
874 safe_super::detach_dereferenceable_iterators();
879 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
881 std::swap(key,x.key);
882 std::swap(hash_,x.hash_);
883 std::swap(eq_,x.eq_);
884 buckets.swap(x.buckets);
885 std::swap(mlf,x.mlf);
886 std::swap(max_load,x.max_load);
888 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
896 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
898 buckets.swap(x.buckets);
899 std::swap(mlf,x.mlf);
900 std::swap(max_load,x.max_load);
902 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
906 super::swap_elements_(x);
909 template<typename Variant>
910 bool replace_(value_param_type v,node_type* x,Variant variant)
912 if(eq_(key(v),key(x->value()))){
913 return super::replace_(v,x,variant);
920 std::size_t buc=find_bucket(v);
921 link_info pos(buckets.at(buc));
922 if(link_point(v,pos)&&super::replace_(v,x,variant)){
936 bool modify_(node_type* x)
941 buc=find_bucket(x->value());
942 b=in_place(x->impl(),key(x->value()),buc);
952 link_info pos(buckets.at(buc));
953 if(!link_point(x->value(),pos)){
956 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
966 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
976 if(!super::modify_(x)){
979 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
989 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
998 bool modify_rollback_(node_type* x)
1000 std::size_t buc=find_bucket(x->value());
1001 if(in_place(x->impl(),key(x->value()),buc)){
1002 return super::modify_rollback_(x);
1009 link_info pos(buckets.at(buc));
1010 if(link_point(x->value(),pos)&&super::modify_rollback_(x)){
1024 bool check_rollback_(node_type* x)const
1026 std::size_t buc=find_bucket(x->value());
1027 return in_place(x->impl(),key(x->value()),buc)&&super::check_rollback_(x);
1032 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
1033 /* defect macro refers to class, not function, templates, but anyway */
1035 template<typename K,typename H,typename P,typename S,typename T,typename C>
1036 friend bool operator==(
1037 const hashed_index<K,H,P,S,T,C>&,const hashed_index<K,H,P,S,T,C>& y);
1040 bool equals(const hashed_index& x)const{return equals(x,Category());}
1042 bool equals(const hashed_index& x,hashed_unique_tag)const
1044 if(size()!=x.size())return false;
1045 for(const_iterator it=begin(),it_end=end(),it2_end=x.end();
1047 const_iterator it2=x.find(key(*it));
1048 if(it2==it2_end||!(*it==*it2))return false;
1053 bool equals(const hashed_index& x,hashed_non_unique_tag)const
1055 if(size()!=x.size())return false;
1056 for(const_iterator it=begin(),it_end=end();it!=it_end;){
1057 const_iterator it2,it2_last;
1058 boost::tie(it2,it2_last)=x.equal_range(key(*it));
1059 if(it2==it2_last)return false;
1061 const_iterator it_last=make_iterator(
1062 node_type::from_impl(end_of_range(it.get_node()->impl())));
1063 if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false;
1065 /* From is_permutation code in
1066 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
1069 for(;it!=it_last;++it,++it2){
1070 if(!(*it==*it2))break;
1073 for(const_iterator scan=it;scan!=it_last;++scan){
1074 if(std::find(it,scan,*scan)!=scan)continue;
1075 difference_type matches=std::count(it2,it2_last,*scan);
1076 if(matches==0||matches!=std::count(scan,it_last,*scan))return false;
1084 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1087 template<typename Archive>
1089 Archive& ar,const unsigned int version,const index_saver_type& sm)const
1091 ar<<serialization::make_nvp("position",buckets);
1092 super::save_(ar,version,sm);
1095 template<typename Archive>
1096 void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1098 ar>>serialization::make_nvp("position",buckets);
1099 super::load_(ar,version,lm);
1103 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1104 /* invariant stuff */
1106 bool invariant_()const
1108 if(size()==0||begin()==end()){
1109 if(size()!=0||begin()!=end())return false;
1113 for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
1114 if(s0!=size())return false;
1117 for(size_type buc=0;buc<bucket_count();++buc){
1119 for(const_local_iterator it=begin(buc),it_end=end(buc);
1120 it!=it_end;++it,++ss1){
1121 if(find_bucket(*it)!=buc)return false;
1123 if(ss1!=bucket_size(buc))return false;
1126 if(s1!=size())return false;
1129 return super::invariant_();
1132 /* This forwarding function eases things for the boost::mem_fn construct
1133 * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
1134 * final_check_invariant is already an inherited member function of index.
1136 void check_invariant_()const{this->final_check_invariant_();}
1140 node_type* header()const{return this->final_header();}
1142 std::size_t find_bucket(value_param_type v)const
1144 return bucket(key(v));
1147 struct link_info_non_unique
1149 link_info_non_unique(node_impl_base_pointer pos):
1150 first(pos),last(node_impl_base_pointer(0)){}
1152 operator const node_impl_base_pointer&()const{return this->first;}
1154 node_impl_base_pointer first,last;
1157 typedef typename mpl::if_<
1158 is_same<Category,hashed_unique_tag>,
1159 node_impl_base_pointer,
1160 link_info_non_unique
1163 bool link_point(value_param_type v,link_info& pos)
1165 return link_point(v,pos,Category());
1169 value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
1171 for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0);
1172 x=node_alg::after_local(x)){
1173 if(eq_(key(v),key(node_type::from_impl(x)->value()))){
1174 pos=node_impl_type::base_pointer_from(x);
1182 value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag)
1184 for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0);
1185 x=node_alg::next_to_inspect(x)){
1186 if(eq_(key(v),key(node_type::from_impl(x)->value()))){
1187 pos.first=node_impl_type::base_pointer_from(x);
1188 pos.last=node_impl_type::base_pointer_from(last_of_range(x));
1195 node_impl_pointer last_of_range(node_impl_pointer x)const
1197 return last_of_range(x,Category());
1200 node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
1205 node_impl_pointer last_of_range(
1206 node_impl_pointer x,hashed_non_unique_tag)const
1208 node_impl_base_pointer y=x->next();
1209 node_impl_pointer z=y->prior();
1210 if(z==x){ /* range of size 1 or 2 */
1211 node_impl_pointer yy=node_impl_type::pointer_from(y);
1214 key(node_type::from_impl(x)->value()),
1215 key(node_type::from_impl(yy)->value()))?yy:x;
1217 else if(z->prior()==x) /* last of bucket */
1219 else /* group of size>2 */
1223 node_impl_pointer end_of_range(node_impl_pointer x)const
1225 return end_of_range(x,Category());
1228 node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const
1230 return node_alg::after(last_of_range(x));
1233 node_impl_pointer end_of_range(
1234 node_impl_pointer x,hashed_non_unique_tag)const
1236 node_impl_base_pointer y=x->next();
1237 node_impl_pointer z=y->prior();
1238 if(z==x){ /* range of size 1 or 2 */
1239 node_impl_pointer yy=node_impl_type::pointer_from(y);
1241 key(node_type::from_impl(x)->value()),
1242 key(node_type::from_impl(yy)->value())))yy=x;
1243 return yy->next()->prior()==yy?
1244 node_impl_type::pointer_from(yy->next()):
1245 yy->next()->prior();
1247 else if(z->prior()==x) /* last of bucket */
1249 else /* group of size>2 */
1250 return z->next()->prior()==z?
1251 node_impl_type::pointer_from(z->next()):
1255 void link(node_type* x,const link_info& pos)
1257 link(x,pos,Category());
1260 void link(node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
1262 node_alg::link(x->impl(),pos,header()->impl());
1265 void link(node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag)
1267 if(pos.last==node_impl_base_pointer(0)){
1268 node_alg::link(x->impl(),pos.first,header()->impl());
1273 node_impl_type::pointer_from(pos.first),
1274 node_impl_type::pointer_from(pos.last));
1278 void unlink(node_type* x)
1280 node_alg::unlink(x->impl());
1283 typedef typename node_alg::unlink_undo unlink_undo;
1285 void unlink(node_type* x,unlink_undo& undo)
1287 node_alg::unlink(x->impl(),undo);
1290 void calculate_max_load()
1292 float fml=mlf*static_cast<float>(bucket_count());
1293 max_load=(std::numeric_limits<size_type>::max)();
1294 if(max_load>fml)max_load=static_cast<size_type>(fml);
1297 void reserve_for_insert(size_type n)
1300 size_type bc =(std::numeric_limits<size_type>::max)();
1301 float fbc=1.0f+static_cast<float>(n)/mlf;
1302 if(bc>fbc)bc =static_cast<size_type>(fbc);
1303 unchecked_rehash(bc);
1307 void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
1309 void unchecked_rehash(size_type n,hashed_unique_tag)
1311 node_impl_type cpy_end_node;
1312 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1313 end_=header()->impl();
1314 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1318 std::size_t,allocator_type> hashes(get_allocator(),size());
1320 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1321 std::size_t i=0,size_=size();
1322 bool within_bucket=false;
1325 node_impl_pointer x=end_->prior();
1327 /* only this can possibly throw */
1328 std::size_t h=hash_(key(node_type::from_impl(x)->value()));
1331 node_ptrs.data()[i]=x;
1332 within_bucket=!node_alg::unlink_last(end_);
1333 node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1338 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1339 if(!within_bucket)prev_buc=~prev_buc;
1341 for(std::size_t j=i;j--;){
1342 std::size_t buc=buckets.position(hashes.data()[j]);
1343 node_impl_pointer x=node_ptrs.data()[j];
1344 if(buc==prev_buc)node_alg::append(x,end_);
1345 else node_alg::link(x,buckets.at(buc),end_);
1354 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1355 end_->next()=cpy_end->next();
1356 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1357 buckets.swap(buckets_cpy);
1358 calculate_max_load();
1361 void unchecked_rehash(size_type n,hashed_non_unique_tag)
1363 node_impl_type cpy_end_node;
1364 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1365 end_=header()->impl();
1366 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1370 std::size_t,allocator_type> hashes(get_allocator(),size());
1372 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1374 bool within_bucket=false;
1377 node_impl_pointer x=end_->prior();
1380 /* only this can possibly throw */
1381 std::size_t h=hash_(key(node_type::from_impl(x)->value()));
1384 node_ptrs.data()[i]=x;
1385 std::pair<node_impl_pointer,bool> p=
1386 node_alg::unlink_last_group(end_);
1387 node_alg::link_range(
1388 p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1389 within_bucket=!(p.second);
1394 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1395 if(!within_bucket)prev_buc=~prev_buc;
1397 for(std::size_t j=i;j--;){
1398 std::size_t buc=buckets.position(hashes.data()[j]);
1399 node_impl_pointer x=node_ptrs.data()[j],
1401 x->prior()->next()!=node_impl_type::base_pointer_from(x)&&
1402 x->prior()->next()->prior()!=x?
1403 node_impl_type::pointer_from(x->prior()->next()):x;
1404 node_alg::unlink_range(y,x);
1405 if(buc==prev_buc)node_alg::append_range(y,x,end_);
1406 else node_alg::link_range(y,x,buckets.at(buc),end_);
1415 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1416 end_->next()=cpy_end->next();
1417 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1418 buckets.swap(buckets_cpy);
1419 calculate_max_load();
1422 bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
1424 return in_place(x,k,buc,Category());
1428 node_impl_pointer x,key_param_type k,std::size_t buc,
1429 hashed_unique_tag)const
1432 for(node_impl_pointer y=buckets.at(buc)->prior();
1433 y!=node_impl_pointer(0);y=node_alg::after_local(y)){
1435 else if(eq_(k,key(node_type::from_impl(y)->value())))return false;
1441 node_impl_pointer x,key_param_type k,std::size_t buc,
1442 hashed_non_unique_tag)const
1446 for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){
1447 if(node_alg::is_first_of_group(y)){ /* group of 3 or more */
1449 /* in place <-> equal to some other member of the group */
1452 key(node_type::from_impl(
1453 node_impl_type::pointer_from(y->next()))->value()));
1456 node_impl_pointer z=
1457 node_alg::after_local(y->next()->prior()); /* end of range */
1458 if(eq_(k,key(node_type::from_impl(y)->value()))){
1459 if(found)return false; /* x lies outside */
1461 if(y==x)return true;
1462 y=node_alg::after_local(y);
1464 return false; /* x not found */
1467 if(range_size==1&&!found)return false;
1468 if(range_size==2)return found;
1470 y=z; /* skip range (and potentially x, too, which is fine) */
1474 else{ /* group of 1 or 2 */
1476 if(range_size==1)return true;
1480 else if(eq_(k,key(node_type::from_impl(y)->value()))){
1481 if(range_size==0&&found)return false;
1482 if(range_size==1&&!found)return false;
1483 if(range_size==2)return false;
1487 if(range_size==1&&!found)return false;
1488 if(range_size==2)return found;
1491 y=node_alg::after_local(y);
1497 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1498 void detach_iterators(node_type* x)
1500 iterator it=make_iterator(x);
1501 safe_mode::detach_equivalent_iterators(it);
1505 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1506 std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1508 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1509 std::pair<final_node_type*,bool>p=
1510 this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1511 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1514 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1515 iterator emplace_hint_impl(
1516 iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1518 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1519 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1520 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1521 std::pair<final_node_type*,bool>p=
1522 this->final_emplace_hint_(
1523 static_cast<final_node_type*>(position.get_node()),
1524 BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1525 return make_iterator(p.first);
1529 typename CompatibleHash,typename CompatiblePred
1533 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1535 return find(k,hash,eq,mpl::false_());
1539 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1542 const CompatibleKey& k,
1543 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1545 std::size_t buc=buckets.position(hash(k));
1546 for(node_impl_pointer x=buckets.at(buc)->prior();
1547 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1548 if(eq(k,key(node_type::from_impl(x)->value()))){
1549 return make_iterator(node_type::from_impl(x));
1556 typename CompatibleHash,typename CompatiblePred
1560 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1562 return count(k,hash,eq,mpl::false_());
1566 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1569 const CompatibleKey& k,
1570 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1572 std::size_t buc=buckets.position(hash(k));
1573 for(node_impl_pointer x=buckets.at(buc)->prior();
1574 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1575 if(eq(k,key(node_type::from_impl(x)->value()))){
1577 node_impl_pointer y=end_of_range(x);
1580 x=node_alg::after(x);
1589 typename CompatibleHash,typename CompatiblePred
1591 std::pair<iterator,iterator> equal_range(
1593 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1595 return equal_range(k,hash,eq,mpl::false_());
1599 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1601 std::pair<iterator,iterator> equal_range(
1602 const CompatibleKey& k,
1603 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1605 std::size_t buc=buckets.position(hash(k));
1606 for(node_impl_pointer x=buckets.at(buc)->prior();
1607 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1608 if(eq(k,key(node_type::from_impl(x)->value()))){
1609 return std::pair<iterator,iterator>(
1610 make_iterator(node_type::from_impl(x)),
1611 make_iterator(node_type::from_impl(end_of_range(x))));
1614 return std::pair<iterator,iterator>(end(),end());
1620 bucket_array_type buckets;
1624 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1625 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1626 #pragma parse_mfunc_templ reset
1633 typename KeyFromValue,typename Hash,typename Pred,
1634 typename SuperMeta,typename TagList,typename Category
1637 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1638 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1644 typename KeyFromValue,typename Hash,typename Pred,
1645 typename SuperMeta,typename TagList,typename Category
1648 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1649 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1654 /* specialized algorithms */
1657 typename KeyFromValue,typename Hash,typename Pred,
1658 typename SuperMeta,typename TagList,typename Category
1661 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1662 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1667 } /* namespace multi_index::detail */
1669 /* hashed index specifiers */
1671 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1672 struct hashed_unique
1674 typedef typename detail::hashed_index_args<
1675 Arg1,Arg2,Arg3,Arg4> index_args;
1676 typedef typename index_args::tag_list_type::type tag_list_type;
1677 typedef typename index_args::key_from_value_type key_from_value_type;
1678 typedef typename index_args::hash_type hash_type;
1679 typedef typename index_args::pred_type pred_type;
1681 template<typename Super>
1684 typedef detail::hashed_index_node<Super,detail::hashed_unique_tag> type;
1687 template<typename SuperMeta>
1690 typedef detail::hashed_index<
1691 key_from_value_type,hash_type,pred_type,
1692 SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1696 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1697 struct hashed_non_unique
1699 typedef typename detail::hashed_index_args<
1700 Arg1,Arg2,Arg3,Arg4> index_args;
1701 typedef typename index_args::tag_list_type::type tag_list_type;
1702 typedef typename index_args::key_from_value_type key_from_value_type;
1703 typedef typename index_args::hash_type hash_type;
1704 typedef typename index_args::pred_type pred_type;
1706 template<typename Super>
1709 typedef detail::hashed_index_node<
1710 Super,detail::hashed_non_unique_tag> type;
1713 template<typename SuperMeta>
1716 typedef detail::hashed_index<
1717 key_from_value_type,hash_type,pred_type,
1718 SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1722 } /* namespace multi_index */
1724 } /* namespace boost */
1726 /* Boost.Foreach compatibility */
1729 typename KeyFromValue,typename Hash,typename Pred,
1730 typename SuperMeta,typename TagList,typename Category
1732 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1733 boost::multi_index::detail::hashed_index<
1734 KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>*&,
1735 boost_foreach_argument_dependent_lookup_hack)
1740 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1741 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF