diff options
Diffstat (limited to 'boost/multi_index/hashed_index.hpp')
-rw-r--r-- | boost/multi_index/hashed_index.hpp | 137 |
1 files changed, 103 insertions, 34 deletions
diff --git a/boost/multi_index/hashed_index.hpp b/boost/multi_index/hashed_index.hpp index ebf55c9ef0..436fecf771 100644 --- a/boost/multi_index/hashed_index.hpp +++ b/boost/multi_index/hashed_index.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2014 Joaquin M Lopez Munoz. +/* Copyright 2003-2015 Joaquin M Lopez Munoz. * Distributed under the Boost Software License, Version 1.0. * (See accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) @@ -32,6 +32,7 @@ #include <boost/multi_index/detail/hash_index_iterator.hpp> #include <boost/multi_index/detail/index_node_base.hpp> #include <boost/multi_index/detail/modify_key_adaptor.hpp> +#include <boost/multi_index/detail/promotes_arg.hpp> #include <boost/multi_index/detail/safe_mode.hpp> #include <boost/multi_index/detail/scope_guard.hpp> #include <boost/multi_index/detail/vartempl_support.hpp> @@ -459,6 +460,11 @@ public: * type as iterator. */ + /* Implementation note: When CompatibleKey is consistently promoted to + * KeyFromValue::result_type for equality comparison, the promotion is made + * once in advance to increase efficiency. + */ + template<typename CompatibleKey> iterator find(const CompatibleKey& k)const { @@ -472,14 +478,8 @@ public: const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const { - std::size_t buc=buckets.position(hash(k)); - for(node_impl_pointer x=buckets.at(buc)->prior(); - x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq(k,key(node_type::from_impl(x)->value()))){ - return make_iterator(node_type::from_impl(x)); - } - } - return end(); + return find( + k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>()); } template<typename CompatibleKey> @@ -495,20 +495,8 @@ public: const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const { - std::size_t buc=buckets.position(hash(k)); - for(node_impl_pointer x=buckets.at(buc)->prior(); - x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq(k,key(node_type::from_impl(x)->value()))){ - size_type res=0; - node_impl_pointer y=end_of_range(x); - do{ - ++res; - x=node_alg::after(x); - }while(x!=y); - return res; - } - } - return 0; + return count( + k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>()); } template<typename CompatibleKey> @@ -524,16 +512,8 @@ public: const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const { - std::size_t buc=buckets.position(hash(k)); - for(node_impl_pointer x=buckets.at(buc)->prior(); - x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ - if(eq(k,key(node_type::from_impl(x)->value()))){ - return std::pair<iterator,iterator>( - make_iterator(node_type::from_impl(x)), - make_iterator(node_type::from_impl(end_of_range(x)))); - } - } - return std::pair<iterator,iterator>(end(),end()); + return equal_range( + k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>()); } /* bucket interface */ @@ -1291,7 +1271,7 @@ private: void calculate_max_load() { - float fml=static_cast<float>(mlf*bucket_count()); + float fml=static_cast<float>(mlf*static_cast<float>(bucket_count())); max_load=(std::numeric_limits<size_type>::max)(); if(max_load>fml)max_load=static_cast<size_type>(fml); } @@ -1527,6 +1507,95 @@ private: return make_iterator(p.first); } + template< + typename CompatibleHash,typename CompatiblePred + > + iterator find( + const key_type& k, + const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const + { + return find(k,hash,eq,mpl::false_()); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + iterator find( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const + { + std::size_t buc=buckets.position(hash(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq(k,key(node_type::from_impl(x)->value()))){ + return make_iterator(node_type::from_impl(x)); + } + } + return end(); + } + + template< + typename CompatibleHash,typename CompatiblePred + > + size_type count( + const key_type& k, + const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const + { + return count(k,hash,eq,mpl::false_()); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + size_type count( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const + { + std::size_t buc=buckets.position(hash(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq(k,key(node_type::from_impl(x)->value()))){ + size_type res=0; + node_impl_pointer y=end_of_range(x); + do{ + ++res; + x=node_alg::after(x); + }while(x!=y); + return res; + } + } + return 0; + } + + template< + typename CompatibleHash,typename CompatiblePred + > + std::pair<iterator,iterator> equal_range( + const key_type& k, + const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const + { + return equal_range(k,hash,eq,mpl::false_()); + } + + template< + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred + > + std::pair<iterator,iterator> equal_range( + const CompatibleKey& k, + const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const + { + std::size_t buc=buckets.position(hash(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq(k,key(node_type::from_impl(x)->value()))){ + return std::pair<iterator,iterator>( + make_iterator(node_type::from_impl(x)), + make_iterator(node_type::from_impl(end_of_range(x)))); + } + } + return std::pair<iterator,iterator>(end(),end()); + } + key_from_value key; hasher hash_; key_equal eq_; |