summaryrefslogtreecommitdiff
path: root/boost/multi_index/hashed_index.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/multi_index/hashed_index.hpp')
-rw-r--r--boost/multi_index/hashed_index.hpp137
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_;