1 /* Copyright 2003-2020 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/adl_swap.hpp>
30 #include <boost/multi_index/detail/allocator_traits.hpp>
31 #include <boost/multi_index/detail/auto_space.hpp>
32 #include <boost/multi_index/detail/bucket_array.hpp>
33 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
34 #include <boost/multi_index/detail/hash_index_iterator.hpp>
35 #include <boost/multi_index/detail/index_node_base.hpp>
36 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
37 #include <boost/multi_index/detail/promotes_arg.hpp>
38 #include <boost/multi_index/detail/safe_mode.hpp>
39 #include <boost/multi_index/detail/scope_guard.hpp>
40 #include <boost/multi_index/detail/vartempl_support.hpp>
41 #include <boost/multi_index/hashed_index_fwd.hpp>
42 #include <boost/tuple/tuple.hpp>
43 #include <boost/type_traits/is_same.hpp>
50 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
51 #include <initializer_list>
54 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
55 #include <boost/serialization/nvp.hpp>
58 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
59 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) \
60 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
61 detail::make_obj_guard(x,&hashed_index::check_invariant_); \
62 BOOST_JOIN(check_invariant_,__LINE__).touch();
63 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \
64 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this)
66 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x)
67 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
72 namespace multi_index{
76 /* hashed_index adds a layer of hashed indexing to a given Super */
78 /* Most of the implementation of unique and non-unique indices is
79 * shared. We tell from one another on instantiation time by using
80 * Category tags defined in hash_index_node.hpp.
84 typename KeyFromValue,typename Hash,typename Pred,
85 typename SuperMeta,typename TagList,typename Category
88 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
90 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
91 ,public safe_mode::safe_container<
92 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
96 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
97 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
98 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
99 * lifetime of const references bound to temporaries --precisely what
103 #pragma parse_mfunc_templ off
106 typedef typename SuperMeta::type super;
109 typedef hashed_index_node<
110 typename super::node_type,Category> node_type;
113 typedef typename node_type::node_alg node_alg;
114 typedef typename node_type::impl_type node_impl_type;
115 typedef typename node_impl_type::pointer node_impl_pointer;
116 typedef typename node_impl_type::base_pointer node_impl_base_pointer;
117 typedef bucket_array<
118 typename super::final_allocator_type> bucket_array_type;
123 typedef typename KeyFromValue::result_type key_type;
124 typedef typename node_type::value_type value_type;
125 typedef KeyFromValue key_from_value;
127 typedef Pred key_equal;
128 typedef typename super::final_allocator_type allocator_type;
131 typedef allocator_traits<allocator_type> alloc_traits;
134 typedef typename alloc_traits::pointer pointer;
135 typedef typename alloc_traits::const_pointer const_pointer;
136 typedef value_type& reference;
137 typedef const value_type& const_reference;
138 typedef typename alloc_traits::size_type size_type;
139 typedef typename alloc_traits::difference_type difference_type;
140 typedef tuple<size_type,
141 key_from_value,hasher,key_equal> ctor_args;
143 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
144 typedef safe_mode::safe_iterator<
145 hashed_index_iterator<
146 node_type,bucket_array_type,
147 hashed_index_global_iterator_tag>,
148 hashed_index> iterator;
150 typedef hashed_index_iterator<
151 node_type,bucket_array_type,
152 hashed_index_global_iterator_tag> iterator;
155 typedef iterator const_iterator;
157 typedef hashed_index_iterator<
158 node_type,bucket_array_type,
159 hashed_index_local_iterator_tag> local_iterator;
160 typedef local_iterator const_local_iterator;
162 typedef TagList tag_list;
165 typedef typename super::final_node_type final_node_type;
166 typedef tuples::cons<
168 typename super::ctor_args_list> ctor_args_list;
169 typedef typename mpl::push_front<
170 typename super::index_type_list,
171 hashed_index>::type index_type_list;
172 typedef typename mpl::push_front<
173 typename super::iterator_type_list,
174 iterator>::type iterator_type_list;
175 typedef typename mpl::push_front<
176 typename super::const_iterator_type_list,
177 const_iterator>::type const_iterator_type_list;
178 typedef typename super::copy_map_type copy_map_type;
180 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
181 typedef typename super::index_saver_type index_saver_type;
182 typedef typename super::index_loader_type index_loader_type;
186 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
187 typedef safe_mode::safe_container<
188 hashed_index> safe_super;
191 typedef typename call_traits<value_type>::param_type value_param_type;
192 typedef typename call_traits<
193 key_type>::param_type key_param_type;
195 /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
199 typedef std::pair<iterator,bool> emplace_return_type;
203 /* construct/destroy/copy
204 * Default and copy ctors are in the protected section as indices are
205 * not supposed to be created on their own. No range ctor either.
208 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
209 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
211 this->final()=x.final();
215 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
216 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
217 std::initializer_list<value_type> list)
224 allocator_type get_allocator()const BOOST_NOEXCEPT
226 return this->final().get_allocator();
229 /* size and capacity */
231 bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
232 size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
233 size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
237 iterator begin()BOOST_NOEXCEPT
238 {return make_iterator(node_type::from_impl(header()->next()->prior()));}
239 const_iterator begin()const BOOST_NOEXCEPT
240 {return make_iterator(node_type::from_impl(header()->next()->prior()));}
241 iterator end()BOOST_NOEXCEPT{return make_iterator(header());}
242 const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());}
243 const_iterator cbegin()const BOOST_NOEXCEPT{return begin();}
244 const_iterator cend()const BOOST_NOEXCEPT{return end();}
246 iterator iterator_to(const value_type& x)
248 return make_iterator(node_from_value<node_type>(boost::addressof(x)));
251 const_iterator iterator_to(const value_type& x)const
253 return make_iterator(node_from_value<node_type>(boost::addressof(x)));
258 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
259 emplace_return_type,emplace,emplace_impl)
261 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
262 iterator,emplace_hint,emplace_hint_impl,iterator,position)
264 std::pair<iterator,bool> insert(const value_type& x)
266 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
267 std::pair<final_node_type*,bool> p=this->final_insert_(x);
268 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
271 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
273 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
274 std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
275 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
278 iterator insert(iterator position,const value_type& x)
280 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
281 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
282 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
283 std::pair<final_node_type*,bool> p=this->final_insert_(
284 x,static_cast<final_node_type*>(position.get_node()));
285 return make_iterator(p.first);
288 iterator insert(iterator position,BOOST_RV_REF(value_type) x)
290 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
291 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
292 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
293 std::pair<final_node_type*,bool> p=this->final_insert_rv_(
294 x,static_cast<final_node_type*>(position.get_node()));
295 return make_iterator(p.first);
298 template<typename InputIterator>
299 void insert(InputIterator first,InputIterator last)
301 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
302 for(;first!=last;++first)this->final_insert_ref_(*first);
305 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
306 void insert(std::initializer_list<value_type> list)
308 insert(list.begin(),list.end());
312 iterator erase(iterator position)
314 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
315 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
316 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
317 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
318 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
322 size_type erase(key_param_type k)
324 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
326 std::size_t buc=buckets.position(hash_(k));
327 for(node_impl_pointer x=buckets.at(buc)->prior();
328 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
329 if(eq_(k,key(node_type::from_impl(x)->value()))){
330 node_impl_pointer y=end_of_range(x);
333 node_impl_pointer z=node_alg::after(x);
335 static_cast<final_node_type*>(node_type::from_impl(x)));
345 iterator erase(iterator first,iterator last)
347 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
348 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
349 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
350 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
351 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
352 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
359 bool replace(iterator position,const value_type& x)
361 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
362 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
363 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
364 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
365 return this->final_replace_(
366 x,static_cast<final_node_type*>(position.get_node()));
369 bool replace(iterator position,BOOST_RV_REF(value_type) x)
371 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
372 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
373 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
374 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
375 return this->final_replace_rv_(
376 x,static_cast<final_node_type*>(position.get_node()));
379 template<typename Modifier>
380 bool modify(iterator position,Modifier mod)
382 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
383 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
384 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
385 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
387 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
388 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
389 * this is not added. Left it for all compilers as it does no
396 return this->final_modify_(
397 mod,static_cast<final_node_type*>(position.get_node()));
400 template<typename Modifier,typename Rollback>
401 bool modify(iterator position,Modifier mod,Rollback back_)
403 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
404 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
405 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
406 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
408 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
409 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
410 * this is not added. Left it for all compilers as it does no
417 return this->final_modify_(
418 mod,back_,static_cast<final_node_type*>(position.get_node()));
421 template<typename Modifier>
422 bool modify_key(iterator position,Modifier mod)
424 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
425 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
426 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
427 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
429 position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
432 template<typename Modifier,typename Rollback>
433 bool modify_key(iterator position,Modifier mod,Rollback back_)
435 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
436 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
437 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
438 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
441 modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
442 modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
445 void clear()BOOST_NOEXCEPT
447 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
448 this->final_clear_();
451 void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
453 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
454 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x);
455 this->final_swap_(x.final());
460 key_from_value key_extractor()const{return key;}
461 hasher hash_function()const{return hash_;}
462 key_equal key_eq()const{return eq_;}
466 /* Internally, these ops rely on const_iterator being the same
470 /* Implementation note: When CompatibleKey is consistently promoted to
471 * KeyFromValue::result_type for equality comparison, the promotion is made
472 * once in advance to increase efficiency.
475 template<typename CompatibleKey>
476 iterator find(const CompatibleKey& k)const
478 return find(k,hash_,eq_);
482 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
485 const CompatibleKey& k,
486 const CompatibleHash& hash,const CompatiblePred& eq)const
489 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
492 template<typename CompatibleKey>
493 size_type count(const CompatibleKey& k)const
495 return count(k,hash_,eq_);
499 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
502 const CompatibleKey& k,
503 const CompatibleHash& hash,const CompatiblePred& eq)const
506 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
509 template<typename CompatibleKey>
510 std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
512 return equal_range(k,hash_,eq_);
516 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
518 std::pair<iterator,iterator> equal_range(
519 const CompatibleKey& k,
520 const CompatibleHash& hash,const CompatiblePred& eq)const
523 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
526 /* bucket interface */
528 size_type bucket_count()const BOOST_NOEXCEPT
530 return static_cast<size_type>(buckets.size());
533 size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);}
535 size_type bucket_size(size_type n)const
538 for(node_impl_pointer x=buckets.at(n)->prior();
539 x!=node_impl_pointer(0);x=node_alg::after_local(x)){
545 size_type bucket(key_param_type k)const
547 return static_cast<size_type>(buckets.position(hash_(k)));
550 local_iterator begin(size_type n)
552 return const_cast<const hashed_index*>(this)->begin(n);
555 const_local_iterator begin(size_type n)const
557 node_impl_pointer x=buckets.at(n)->prior();
558 if(x==node_impl_pointer(0))return end(n);
559 return make_local_iterator(node_type::from_impl(x));
562 local_iterator end(size_type n)
564 return const_cast<const hashed_index*>(this)->end(n);
567 const_local_iterator end(size_type)const
569 return make_local_iterator(0);
572 const_local_iterator cbegin(size_type n)const{return begin(n);}
573 const_local_iterator cend(size_type n)const{return end(n);}
575 local_iterator local_iterator_to(const value_type& x)
577 return make_local_iterator(
578 node_from_value<node_type>(boost::addressof(x)));
581 const_local_iterator local_iterator_to(const value_type& x)const
583 return make_local_iterator(
584 node_from_value<node_type>(boost::addressof(x)));
589 float load_factor()const BOOST_NOEXCEPT
590 {return static_cast<float>(size())/bucket_count();}
591 float max_load_factor()const BOOST_NOEXCEPT{return mlf;}
592 void max_load_factor(float z){mlf=z;calculate_max_load();}
594 void rehash(size_type n)
596 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
597 if(size()<=max_load&&n<=bucket_count())return;
599 size_type bc =(std::numeric_limits<size_type>::max)();
600 float fbc=1.0f+static_cast<float>(size())/mlf;
602 bc=static_cast<size_type>(fbc);
605 unchecked_rehash(bc);
608 void reserve(size_type n)
610 rehash(static_cast<size_type>(std::ceil(static_cast<float>(n)/mlf)));
613 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
614 hashed_index(const ctor_args_list& args_list,const allocator_type& al):
615 super(args_list.get_tail(),al),
616 key(tuples::get<1>(args_list.get_head())),
617 hash_(tuples::get<2>(args_list.get_head())),
618 eq_(tuples::get<3>(args_list.get_head())),
619 buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
622 calculate_max_load();
626 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
629 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
636 buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
640 /* Copy ctor just takes the internal configuration objects from x. The rest
641 * is done in subsequent call to copy_().
646 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
647 do_not_copy_elements_tag):
648 super(x,do_not_copy_elements_tag()),
650 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
657 buckets(x.get_allocator(),header()->impl(),0),
660 calculate_max_load();
665 /* the container is guaranteed to be empty by now */
668 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
669 iterator make_iterator(node_type* node)
671 return iterator(node,this);
674 const_iterator make_iterator(node_type* node)const
676 return const_iterator(node,const_cast<hashed_index*>(this));
679 iterator make_iterator(node_type* node)
681 return iterator(node);
684 const_iterator make_iterator(node_type* node)const
686 return const_iterator(node);
690 local_iterator make_local_iterator(node_type* node)
692 return local_iterator(node);
695 const_local_iterator make_local_iterator(node_type* node)const
697 return const_local_iterator(node);
701 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
702 const copy_map_type& map)
704 copy_(x,map,Category());
708 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
709 const copy_map_type& map,hashed_unique_tag)
712 node_impl_pointer end_org=x.header()->impl(),
714 cpy=header()->impl();
716 node_impl_pointer prev_org=org->prior(),
718 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
719 node_type::from_impl(prev_org))))->impl();
720 cpy->prior()=prev_cpy;
721 if(node_alg::is_first_of_bucket(org)){
722 node_impl_base_pointer buc_org=prev_org->next(),
724 buckets.begin()+(buc_org-x.buckets.begin());
725 prev_cpy->next()=buc_cpy;
726 buc_cpy->prior()=cpy;
729 prev_cpy->next()=node_impl_type::base_pointer_from(cpy);
733 }while(org!=end_org);
740 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
741 const copy_map_type& map,hashed_non_unique_tag)
744 node_impl_pointer end_org=x.header()->impl(),
746 cpy=header()->impl();
748 node_impl_pointer next_org=node_alg::after(org),
750 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
751 node_type::from_impl(next_org))))->impl();
752 if(node_alg::is_first_of_bucket(next_org)){
753 node_impl_base_pointer buc_org=org->next(),
755 buckets.begin()+(buc_org-x.buckets.begin());
757 buc_cpy->prior()=next_cpy;
758 next_cpy->prior()=cpy;
761 if(org->next()==node_impl_type::base_pointer_from(next_org)){
762 cpy->next()=node_impl_type::base_pointer_from(next_cpy);
766 node_impl_type::base_pointer_from(
767 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
768 node_type::from_impl(
769 node_impl_type::pointer_from(org->next())))))->impl());
772 if(next_org->prior()!=org){
774 static_cast<node_type*>(map.find(static_cast<final_node_type*>(
775 node_type::from_impl(next_org->prior()))))->impl();
778 next_cpy->prior()=cpy;
783 }while(org!=end_org);
789 template<typename Variant>
790 final_node_type* insert_(
791 value_param_type v,final_node_type*& x,Variant variant)
793 reserve_for_insert(size()+1);
795 std::size_t buc=find_bucket(v);
796 link_info pos(buckets.at(buc));
797 if(!link_point(v,pos)){
798 return static_cast<final_node_type*>(
799 node_type::from_impl(node_impl_type::pointer_from(pos)));
802 final_node_type* res=super::insert_(v,x,variant);
803 if(res==x)link(static_cast<node_type*>(x),pos);
807 template<typename Variant>
808 final_node_type* insert_(
809 value_param_type v,node_type* position,final_node_type*& x,Variant variant)
811 reserve_for_insert(size()+1);
813 std::size_t buc=find_bucket(v);
814 link_info pos(buckets.at(buc));
815 if(!link_point(v,pos)){
816 return static_cast<final_node_type*>(
817 node_type::from_impl(node_impl_type::pointer_from(pos)));
820 final_node_type* res=super::insert_(v,position,x,variant);
821 if(res==x)link(static_cast<node_type*>(x),pos);
825 void erase_(node_type* x)
830 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
835 void delete_all_nodes_()
837 delete_all_nodes_(Category());
840 void delete_all_nodes_(hashed_unique_tag)
842 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
843 node_impl_pointer y=x->prior();
844 this->final_delete_node_(
845 static_cast<final_node_type*>(node_type::from_impl(x)));
850 void delete_all_nodes_(hashed_non_unique_tag)
852 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
853 node_impl_pointer y=x->prior();
854 if(y->next()!=node_impl_type::base_pointer_from(x)&&
855 y->next()->prior()!=x){ /* n-1 of group */
856 /* Make the second node prior() pointer back-linked so that it won't
857 * refer to a deleted node when the time for its own destruction comes.
860 node_impl_pointer first=node_impl_type::pointer_from(y->next());
861 first->next()->prior()=first;
863 this->final_delete_node_(
864 static_cast<final_node_type*>(node_type::from_impl(x)));
872 buckets.clear(header()->impl());
874 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
875 safe_super::detach_dereferenceable_iterators();
879 template<typename BoolConstant>
881 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
882 BoolConstant swap_allocators)
885 adl_swap(hash_,x.hash_);
887 buckets.swap(x.buckets,swap_allocators);
888 std::swap(mlf,x.mlf);
889 std::swap(max_load,x.max_load);
891 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
895 super::swap_(x,swap_allocators);
899 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
901 buckets.swap(x.buckets);
902 std::swap(mlf,x.mlf);
903 std::swap(max_load,x.max_load);
905 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
909 super::swap_elements_(x);
912 template<typename Variant>
913 bool replace_(value_param_type v,node_type* x,Variant variant)
915 if(eq_(key(v),key(x->value()))){
916 return super::replace_(v,x,variant);
923 std::size_t buc=find_bucket(v);
924 link_info pos(buckets.at(buc));
925 if(link_point(v,pos)&&super::replace_(v,x,variant)){
939 bool modify_(node_type* x)
944 buc=find_bucket(x->value());
945 b=in_place(x->impl(),key(x->value()),buc);
955 link_info pos(buckets.at(buc));
956 if(!link_point(x->value(),pos)){
959 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
969 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
979 if(!super::modify_(x)){
982 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
992 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1001 bool modify_rollback_(node_type* x)
1003 std::size_t buc=find_bucket(x->value());
1004 if(in_place(x->impl(),key(x->value()),buc)){
1005 return super::modify_rollback_(x);
1012 link_info pos(buckets.at(buc));
1013 if(link_point(x->value(),pos)&&super::modify_rollback_(x)){
1027 bool check_rollback_(node_type* x)const
1029 std::size_t buc=find_bucket(x->value());
1030 return in_place(x->impl(),key(x->value()),buc)&&super::check_rollback_(x);
1035 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
1036 /* defect macro refers to class, not function, templates, but anyway */
1038 template<typename K,typename H,typename P,typename S,typename T,typename C>
1039 friend bool operator==(
1040 const hashed_index<K,H,P,S,T,C>&,const hashed_index<K,H,P,S,T,C>& y);
1043 bool equals(const hashed_index& x)const{return equals(x,Category());}
1045 bool equals(const hashed_index& x,hashed_unique_tag)const
1047 if(size()!=x.size())return false;
1048 for(const_iterator it=begin(),it_end=end(),it2_end=x.end();
1050 const_iterator it2=x.find(key(*it));
1051 if(it2==it2_end||!(*it==*it2))return false;
1056 bool equals(const hashed_index& x,hashed_non_unique_tag)const
1058 if(size()!=x.size())return false;
1059 for(const_iterator it=begin(),it_end=end();it!=it_end;){
1060 const_iterator it2,it2_last;
1061 boost::tie(it2,it2_last)=x.equal_range(key(*it));
1062 if(it2==it2_last)return false;
1064 const_iterator it_last=make_iterator(
1065 node_type::from_impl(end_of_range(it.get_node()->impl())));
1066 if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false;
1068 /* From is_permutation code in
1069 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
1072 for(;it!=it_last;++it,++it2){
1073 if(!(*it==*it2))break;
1076 for(const_iterator scan=it;scan!=it_last;++scan){
1077 if(std::find(it,scan,*scan)!=scan)continue;
1078 difference_type matches=std::count(it2,it2_last,*scan);
1079 if(matches==0||matches!=std::count(scan,it_last,*scan))return false;
1087 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1090 template<typename Archive>
1092 Archive& ar,const unsigned int version,const index_saver_type& sm)const
1094 ar<<serialization::make_nvp("position",buckets);
1095 super::save_(ar,version,sm);
1098 template<typename Archive>
1099 void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1101 ar>>serialization::make_nvp("position",buckets);
1102 super::load_(ar,version,lm);
1106 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1107 /* invariant stuff */
1109 bool invariant_()const
1111 if(size()==0||begin()==end()){
1112 if(size()!=0||begin()!=end())return false;
1116 for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
1117 if(s0!=size())return false;
1120 for(size_type buc=0;buc<bucket_count();++buc){
1122 for(const_local_iterator it=begin(buc),it_end=end(buc);
1123 it!=it_end;++it,++ss1){
1124 if(find_bucket(*it)!=buc)return false;
1126 if(ss1!=bucket_size(buc))return false;
1129 if(s1!=size())return false;
1132 return super::invariant_();
1135 /* This forwarding function eases things for the boost::mem_fn construct
1136 * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
1137 * final_check_invariant is already an inherited member function of index.
1139 void check_invariant_()const{this->final_check_invariant_();}
1143 node_type* header()const{return this->final_header();}
1145 std::size_t find_bucket(value_param_type v)const
1147 return bucket(key(v));
1150 struct link_info_non_unique
1152 link_info_non_unique(node_impl_base_pointer pos):
1153 first(pos),last(node_impl_base_pointer(0)){}
1155 operator const node_impl_base_pointer&()const{return this->first;}
1157 node_impl_base_pointer first,last;
1160 typedef typename mpl::if_<
1161 is_same<Category,hashed_unique_tag>,
1162 node_impl_base_pointer,
1163 link_info_non_unique
1166 bool link_point(value_param_type v,link_info& pos)
1168 return link_point(v,pos,Category());
1172 value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
1174 for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0);
1175 x=node_alg::after_local(x)){
1176 if(eq_(key(v),key(node_type::from_impl(x)->value()))){
1177 pos=node_impl_type::base_pointer_from(x);
1185 value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag)
1187 for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0);
1188 x=node_alg::next_to_inspect(x)){
1189 if(eq_(key(v),key(node_type::from_impl(x)->value()))){
1190 pos.first=node_impl_type::base_pointer_from(x);
1191 pos.last=node_impl_type::base_pointer_from(last_of_range(x));
1198 node_impl_pointer last_of_range(node_impl_pointer x)const
1200 return last_of_range(x,Category());
1203 node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
1208 node_impl_pointer last_of_range(
1209 node_impl_pointer x,hashed_non_unique_tag)const
1211 node_impl_base_pointer y=x->next();
1212 node_impl_pointer z=y->prior();
1213 if(z==x){ /* range of size 1 or 2 */
1214 node_impl_pointer yy=node_impl_type::pointer_from(y);
1217 key(node_type::from_impl(x)->value()),
1218 key(node_type::from_impl(yy)->value()))?yy:x;
1220 else if(z->prior()==x) /* last of bucket */
1222 else /* group of size>2 */
1226 node_impl_pointer end_of_range(node_impl_pointer x)const
1228 return end_of_range(x,Category());
1231 node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const
1233 return node_alg::after(last_of_range(x));
1236 node_impl_pointer end_of_range(
1237 node_impl_pointer x,hashed_non_unique_tag)const
1239 node_impl_base_pointer y=x->next();
1240 node_impl_pointer z=y->prior();
1241 if(z==x){ /* range of size 1 or 2 */
1242 node_impl_pointer yy=node_impl_type::pointer_from(y);
1244 key(node_type::from_impl(x)->value()),
1245 key(node_type::from_impl(yy)->value())))yy=x;
1246 return yy->next()->prior()==yy?
1247 node_impl_type::pointer_from(yy->next()):
1248 yy->next()->prior();
1250 else if(z->prior()==x) /* last of bucket */
1252 else /* group of size>2 */
1253 return z->next()->prior()==z?
1254 node_impl_type::pointer_from(z->next()):
1258 void link(node_type* x,const link_info& pos)
1260 link(x,pos,Category());
1263 void link(node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
1265 node_alg::link(x->impl(),pos,header()->impl());
1268 void link(node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag)
1270 if(pos.last==node_impl_base_pointer(0)){
1271 node_alg::link(x->impl(),pos.first,header()->impl());
1276 node_impl_type::pointer_from(pos.first),
1277 node_impl_type::pointer_from(pos.last));
1281 void unlink(node_type* x)
1283 node_alg::unlink(x->impl());
1286 typedef typename node_alg::unlink_undo unlink_undo;
1288 void unlink(node_type* x,unlink_undo& undo)
1290 node_alg::unlink(x->impl(),undo);
1293 void calculate_max_load()
1295 float fml=mlf*static_cast<float>(bucket_count());
1296 max_load=(std::numeric_limits<size_type>::max)();
1297 if(max_load>fml)max_load=static_cast<size_type>(fml);
1300 void reserve_for_insert(size_type n)
1303 size_type bc =(std::numeric_limits<size_type>::max)();
1304 float fbc=1.0f+static_cast<float>(n)/mlf;
1305 if(bc>fbc)bc =static_cast<size_type>(fbc);
1306 unchecked_rehash(bc);
1310 void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
1312 void unchecked_rehash(size_type n,hashed_unique_tag)
1314 node_impl_type cpy_end_node;
1315 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1316 end_=header()->impl();
1317 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1321 std::size_t,allocator_type> hashes(get_allocator(),size());
1323 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1324 std::size_t i=0,size_=size();
1325 bool within_bucket=false;
1328 node_impl_pointer x=end_->prior();
1330 /* only this can possibly throw */
1331 std::size_t h=hash_(key(node_type::from_impl(x)->value()));
1334 node_ptrs.data()[i]=x;
1335 within_bucket=!node_alg::unlink_last(end_);
1336 node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1341 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1342 if(!within_bucket)prev_buc=~prev_buc;
1344 for(std::size_t j=i;j--;){
1345 std::size_t buc=buckets.position(hashes.data()[j]);
1346 node_impl_pointer x=node_ptrs.data()[j];
1347 if(buc==prev_buc)node_alg::append(x,end_);
1348 else node_alg::link(x,buckets.at(buc),end_);
1357 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1358 end_->next()=cpy_end->next();
1359 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1360 buckets.swap(buckets_cpy);
1361 calculate_max_load();
1364 void unchecked_rehash(size_type n,hashed_non_unique_tag)
1366 node_impl_type cpy_end_node;
1367 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1368 end_=header()->impl();
1369 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1373 std::size_t,allocator_type> hashes(get_allocator(),size());
1375 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1377 bool within_bucket=false;
1380 node_impl_pointer x=end_->prior();
1383 /* only this can possibly throw */
1384 std::size_t h=hash_(key(node_type::from_impl(x)->value()));
1387 node_ptrs.data()[i]=x;
1388 std::pair<node_impl_pointer,bool> p=
1389 node_alg::unlink_last_group(end_);
1390 node_alg::link_range(
1391 p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1392 within_bucket=!(p.second);
1397 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1398 if(!within_bucket)prev_buc=~prev_buc;
1400 for(std::size_t j=i;j--;){
1401 std::size_t buc=buckets.position(hashes.data()[j]);
1402 node_impl_pointer x=node_ptrs.data()[j],
1404 x->prior()->next()!=node_impl_type::base_pointer_from(x)&&
1405 x->prior()->next()->prior()!=x?
1406 node_impl_type::pointer_from(x->prior()->next()):x;
1407 node_alg::unlink_range(y,x);
1408 if(buc==prev_buc)node_alg::append_range(y,x,end_);
1409 else node_alg::link_range(y,x,buckets.at(buc),end_);
1418 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1419 end_->next()=cpy_end->next();
1420 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1421 buckets.swap(buckets_cpy);
1422 calculate_max_load();
1425 bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
1427 return in_place(x,k,buc,Category());
1431 node_impl_pointer x,key_param_type k,std::size_t buc,
1432 hashed_unique_tag)const
1435 for(node_impl_pointer y=buckets.at(buc)->prior();
1436 y!=node_impl_pointer(0);y=node_alg::after_local(y)){
1438 else if(eq_(k,key(node_type::from_impl(y)->value())))return false;
1444 node_impl_pointer x,key_param_type k,std::size_t buc,
1445 hashed_non_unique_tag)const
1449 for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){
1450 if(node_alg::is_first_of_group(y)){ /* group of 3 or more */
1452 /* in place <-> equal to some other member of the group */
1455 key(node_type::from_impl(
1456 node_impl_type::pointer_from(y->next()))->value()));
1459 node_impl_pointer z=
1460 node_alg::after_local(y->next()->prior()); /* end of range */
1461 if(eq_(k,key(node_type::from_impl(y)->value()))){
1462 if(found)return false; /* x lies outside */
1464 if(y==x)return true;
1465 y=node_alg::after_local(y);
1467 return false; /* x not found */
1470 if(range_size==1&&!found)return false;
1471 if(range_size==2)return found;
1473 y=z; /* skip range (and potentially x, too, which is fine) */
1477 else{ /* group of 1 or 2 */
1479 if(range_size==1)return true;
1483 else if(eq_(k,key(node_type::from_impl(y)->value()))){
1484 if(range_size==0&&found)return false;
1485 if(range_size==1&&!found)return false;
1486 if(range_size==2)return false;
1490 if(range_size==1&&!found)return false;
1491 if(range_size==2)return found;
1494 y=node_alg::after_local(y);
1500 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1501 void detach_iterators(node_type* x)
1503 iterator it=make_iterator(x);
1504 safe_mode::detach_equivalent_iterators(it);
1508 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1509 std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1511 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1512 std::pair<final_node_type*,bool>p=
1513 this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1514 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1517 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1518 iterator emplace_hint_impl(
1519 iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1521 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1522 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1523 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1524 std::pair<final_node_type*,bool>p=
1525 this->final_emplace_hint_(
1526 static_cast<final_node_type*>(position.get_node()),
1527 BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1528 return make_iterator(p.first);
1532 typename CompatibleHash,typename CompatiblePred
1536 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1538 return find(k,hash,eq,mpl::false_());
1542 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1545 const CompatibleKey& k,
1546 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1548 std::size_t buc=buckets.position(hash(k));
1549 for(node_impl_pointer x=buckets.at(buc)->prior();
1550 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1551 if(eq(k,key(node_type::from_impl(x)->value()))){
1552 return make_iterator(node_type::from_impl(x));
1559 typename CompatibleHash,typename CompatiblePred
1563 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1565 return count(k,hash,eq,mpl::false_());
1569 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1572 const CompatibleKey& k,
1573 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1575 std::size_t buc=buckets.position(hash(k));
1576 for(node_impl_pointer x=buckets.at(buc)->prior();
1577 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1578 if(eq(k,key(node_type::from_impl(x)->value()))){
1580 node_impl_pointer y=end_of_range(x);
1583 x=node_alg::after(x);
1592 typename CompatibleHash,typename CompatiblePred
1594 std::pair<iterator,iterator> equal_range(
1596 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1598 return equal_range(k,hash,eq,mpl::false_());
1602 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1604 std::pair<iterator,iterator> equal_range(
1605 const CompatibleKey& k,
1606 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1608 std::size_t buc=buckets.position(hash(k));
1609 for(node_impl_pointer x=buckets.at(buc)->prior();
1610 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1611 if(eq(k,key(node_type::from_impl(x)->value()))){
1612 return std::pair<iterator,iterator>(
1613 make_iterator(node_type::from_impl(x)),
1614 make_iterator(node_type::from_impl(end_of_range(x))));
1617 return std::pair<iterator,iterator>(end(),end());
1623 bucket_array_type buckets;
1627 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1628 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1629 #pragma parse_mfunc_templ reset
1636 typename KeyFromValue,typename Hash,typename Pred,
1637 typename SuperMeta,typename TagList,typename Category
1640 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1641 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1647 typename KeyFromValue,typename Hash,typename Pred,
1648 typename SuperMeta,typename TagList,typename Category
1651 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1652 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1657 /* specialized algorithms */
1660 typename KeyFromValue,typename Hash,typename Pred,
1661 typename SuperMeta,typename TagList,typename Category
1664 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1665 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1670 } /* namespace multi_index::detail */
1672 /* hashed index specifiers */
1674 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1675 struct hashed_unique
1677 typedef typename detail::hashed_index_args<
1678 Arg1,Arg2,Arg3,Arg4> index_args;
1679 typedef typename index_args::tag_list_type::type tag_list_type;
1680 typedef typename index_args::key_from_value_type key_from_value_type;
1681 typedef typename index_args::hash_type hash_type;
1682 typedef typename index_args::pred_type pred_type;
1684 template<typename Super>
1687 typedef detail::hashed_index_node<Super,detail::hashed_unique_tag> type;
1690 template<typename SuperMeta>
1693 typedef detail::hashed_index<
1694 key_from_value_type,hash_type,pred_type,
1695 SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1699 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1700 struct hashed_non_unique
1702 typedef typename detail::hashed_index_args<
1703 Arg1,Arg2,Arg3,Arg4> index_args;
1704 typedef typename index_args::tag_list_type::type tag_list_type;
1705 typedef typename index_args::key_from_value_type key_from_value_type;
1706 typedef typename index_args::hash_type hash_type;
1707 typedef typename index_args::pred_type pred_type;
1709 template<typename Super>
1712 typedef detail::hashed_index_node<
1713 Super,detail::hashed_non_unique_tag> type;
1716 template<typename SuperMeta>
1719 typedef detail::hashed_index<
1720 key_from_value_type,hash_type,pred_type,
1721 SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1725 } /* namespace multi_index */
1727 } /* namespace boost */
1729 /* Boost.Foreach compatibility */
1732 typename KeyFromValue,typename Hash,typename Pred,
1733 typename SuperMeta,typename TagList,typename Category
1735 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1736 boost::multi_index::detail::hashed_index<
1737 KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>*&,
1738 boost_foreach_argument_dependent_lookup_hack)
1743 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1744 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF