summaryrefslogtreecommitdiff
path: root/boost/multi_index
diff options
context:
space:
mode:
Diffstat (limited to 'boost/multi_index')
-rw-r--r--boost/multi_index/detail/bidir_node_iterator.hpp3
-rw-r--r--boost/multi_index/detail/hash_index_iterator.hpp1
-rw-r--r--boost/multi_index/detail/is_transparent.hpp135
-rw-r--r--boost/multi_index/detail/ord_index_ops.hpp125
-rw-r--r--boost/multi_index/detail/promotes_arg.hpp83
-rw-r--r--boost/multi_index/detail/rnd_index_node.hpp6
-rw-r--r--boost/multi_index/detail/rnd_index_ops.hpp3
-rw-r--r--boost/multi_index/detail/rnd_node_iterator.hpp3
-rw-r--r--boost/multi_index/hashed_index.hpp137
-rw-r--r--boost/multi_index/ordered_index.hpp1
10 files changed, 453 insertions, 44 deletions
diff --git a/boost/multi_index/detail/bidir_node_iterator.hpp b/boost/multi_index/detail/bidir_node_iterator.hpp
index 9bb0470..9be5ec8 100644
--- a/boost/multi_index/detail/bidir_node_iterator.hpp
+++ b/boost/multi_index/detail/bidir_node_iterator.hpp
@@ -1,4 +1,4 @@
-/* Copyright 2003-2013 Joaquin M Lopez Munoz.
+/* Copyright 2003-2014 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)
@@ -41,6 +41,7 @@ class bidir_node_iterator:
const typename Node::value_type&>
{
public:
+ /* coverity[uninit_ctor]: suppress warning */
bidir_node_iterator(){}
explicit bidir_node_iterator(Node* node_):node(node_){}
diff --git a/boost/multi_index/detail/hash_index_iterator.hpp b/boost/multi_index/detail/hash_index_iterator.hpp
index f8e983d..8d06300 100644
--- a/boost/multi_index/detail/hash_index_iterator.hpp
+++ b/boost/multi_index/detail/hash_index_iterator.hpp
@@ -44,6 +44,7 @@ class hashed_index_iterator:
const typename Node::value_type&>
{
public:
+ /* coverity[uninit_ctor]: suppress warning */
hashed_index_iterator(){}
hashed_index_iterator(Node* node_):node(node_){}
diff --git a/boost/multi_index/detail/is_transparent.hpp b/boost/multi_index/detail/is_transparent.hpp
new file mode 100644
index 0000000..72036d2
--- /dev/null
+++ b/boost/multi_index/detail/is_transparent.hpp
@@ -0,0 +1,135 @@
+/* Copyright 2003-2014 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)
+ *
+ * See http://www.boost.org/libs/multi_index for library home page.
+ */
+
+#ifndef BOOST_MULTI_INDEX_DETAIL_IS_TRANSPARENT_HPP
+#define BOOST_MULTI_INDEX_DETAIL_IS_TRANSPARENT_HPP
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <boost/mpl/bool.hpp>
+#include <boost/type_traits/intrinsics.hpp>
+
+namespace boost{
+
+namespace multi_index{
+
+namespace detail{
+
+/* Metafunction that checks if f(arg,arg2) executes without argument type
+ * conversion. By default (i.e. when it cannot be determined) it evaluates to
+ * true.
+ */
+
+template<typename F,typename Arg1,typename Arg2,typename=void>
+struct is_transparent:mpl::true_{};
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#if !defined(BOOST_NO_SFINAE)&&!defined(BOOST_NO_SFINAE_EXPR)&& \
+ !defined(BOOST_NO_CXX11_DECLTYPE)&& \
+ (defined(BOOST_NO_CXX11_FINAL)||defined(BOOST_IS_FINAL))
+
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/mpl/or.hpp>
+#include <boost/type_traits/function_traits.hpp>
+#include <boost/type_traits/is_class.hpp>
+#include <boost/type_traits/is_final.hpp>
+#include <boost/type_traits/is_function.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/type_traits/remove_pointer.hpp>
+#include <boost/utility/declval.hpp>
+#include <boost/utility/enable_if.hpp>
+
+namespace boost{
+
+namespace multi_index{
+
+namespace detail{
+
+struct not_is_transparent_result_type{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct is_transparent_class_helper:F
+{
+ using F::operator();
+ template<typename T,typename Q>
+ not_is_transparent_result_type operator()(const T&,const Q&)const;
+};
+
+template<typename F,typename Arg1,typename Arg2,typename=void>
+struct is_transparent_class:mpl::true_{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct is_transparent_class<
+ F,Arg1,Arg2,
+ typename enable_if<
+ is_same<
+ decltype(
+ declval<const is_transparent_class_helper<F,Arg1,Arg2> >()(
+ declval<const Arg1&>(),declval<const Arg2&>())
+ ),
+ not_is_transparent_result_type
+ >
+ >::type
+>:mpl::false_{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct is_transparent<
+ F,Arg1,Arg2,
+ typename enable_if<
+ mpl::and_<
+ is_class<F>,
+ mpl::not_<is_final<F> > /* is_transparent_class_helper derives from F */
+ >
+ >::type
+>:is_transparent_class<F,Arg1,Arg2>{};
+
+template<typename F,typename Arg1,typename Arg2,typename=void>
+struct is_transparent_function:mpl::true_{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct is_transparent_function<
+ F,Arg1,Arg2,
+ typename enable_if<
+ mpl::or_<
+ mpl::not_<mpl::or_<
+ is_same<typename function_traits<F>::arg1_type,const Arg1&>,
+ is_same<typename function_traits<F>::arg1_type,Arg1>
+ > >,
+ mpl::not_<mpl::or_<
+ is_same<typename function_traits<F>::arg2_type,const Arg2&>,
+ is_same<typename function_traits<F>::arg2_type,Arg2>
+ > >
+ >
+ >::type
+>:mpl::false_{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct is_transparent<
+ F,Arg1,Arg2,
+ typename enable_if<
+ is_function<typename remove_pointer<F>::type>
+ >::type
+>:is_transparent_function<typename remove_pointer<F>::type,Arg1,Arg2>{};
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#endif
+#endif
diff --git a/boost/multi_index/detail/ord_index_ops.hpp b/boost/multi_index/detail/ord_index_ops.hpp
index d42f5f1..84d5cac 100644
--- a/boost/multi_index/detail/ord_index_ops.hpp
+++ b/boost/multi_index/detail/ord_index_ops.hpp
@@ -1,4 +1,4 @@
-/* Copyright 2003-2013 Joaquin M Lopez Munoz.
+/* Copyright 2003-2014 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)
@@ -41,6 +41,8 @@
#endif
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <boost/mpl/and.hpp>
+#include <boost/multi_index/detail/promotes_arg.hpp>
#include <utility>
namespace boost{
@@ -51,6 +53,9 @@ namespace detail{
/* Common code for index memfuns having templatized and
* non-templatized versions.
+ * Implementation note: When CompatibleKey is consistently promoted to
+ * KeyFromValue::result_type for comparison, the promotion is made once in
+ * advance to increase efficiency.
*/
template<
@@ -61,6 +66,35 @@ inline Node* ordered_index_find(
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
const CompatibleCompare& comp)
{
+ typedef typename KeyFromValue::result_type key_type;
+
+ return ordered_index_find(
+ top,y,key,x,comp,
+ mpl::and_<
+ promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
+ promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleCompare
+>
+inline Node* ordered_index_find(
+ Node* top,Node* y,const KeyFromValue& key,
+ const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
+ const CompatibleCompare& comp,mpl::true_)
+{
+ return ordered_index_find(top,y,key,x,comp,mpl::false_());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleKey,typename CompatibleCompare
+>
+inline Node* ordered_index_find(
+ Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
+ const CompatibleCompare& comp,mpl::false_)
+{
Node* y0=y;
while (top){
@@ -82,6 +116,33 @@ inline Node* ordered_index_lower_bound(
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
const CompatibleCompare& comp)
{
+ typedef typename KeyFromValue::result_type key_type;
+
+ return ordered_index_lower_bound(
+ top,y,key,x,comp,
+ promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleCompare
+>
+inline Node* ordered_index_lower_bound(
+ Node* top,Node* y,const KeyFromValue& key,
+ const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
+ const CompatibleCompare& comp,mpl::true_)
+{
+ return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleKey,typename CompatibleCompare
+>
+inline Node* ordered_index_lower_bound(
+ Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
+ const CompatibleCompare& comp,mpl::false_)
+{
while(top){
if(!comp(key(top->value()),x)){
y=top;
@@ -101,6 +162,33 @@ inline Node* ordered_index_upper_bound(
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
const CompatibleCompare& comp)
{
+ typedef typename KeyFromValue::result_type key_type;
+
+ return ordered_index_upper_bound(
+ top,y,key,x,comp,
+ promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleCompare
+>
+inline Node* ordered_index_upper_bound(
+ Node* top,Node* y,const KeyFromValue& key,
+ const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
+ const CompatibleCompare& comp,mpl::true_)
+{
+ return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleKey,typename CompatibleCompare
+>
+inline Node* ordered_index_upper_bound(
+ Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
+ const CompatibleCompare& comp,mpl::false_)
+{
while(top){
if(comp(x,key(top->value()))){
y=top;
@@ -120,6 +208,35 @@ inline std::pair<Node*,Node*> ordered_index_equal_range(
Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
const CompatibleCompare& comp)
{
+ typedef typename KeyFromValue::result_type key_type;
+
+ return ordered_index_equal_range(
+ top,y,key,x,comp,
+ mpl::and_<
+ promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>,
+ promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleCompare
+>
+inline std::pair<Node*,Node*> ordered_index_equal_range(
+ Node* top,Node* y,const KeyFromValue& key,
+ const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x,
+ const CompatibleCompare& comp,mpl::true_)
+{
+ return ordered_index_equal_range(top,y,key,x,comp,mpl::false_());
+}
+
+template<
+ typename Node,typename KeyFromValue,
+ typename CompatibleKey,typename CompatibleCompare
+>
+inline std::pair<Node*,Node*> ordered_index_equal_range(
+ Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x,
+ const CompatibleCompare& comp,mpl::false_)
+{
while(top){
if(comp(key(top->value()),x)){
top=Node::from_impl(top->right());
@@ -130,8 +247,10 @@ inline std::pair<Node*,Node*> ordered_index_equal_range(
}
else{
return std::pair<Node*,Node*>(
- ordered_index_lower_bound(Node::from_impl(top->left()),top,key,x,comp),
- ordered_index_upper_bound(Node::from_impl(top->right()),y,key,x,comp));
+ ordered_index_lower_bound(
+ Node::from_impl(top->left()),top,key,x,comp,mpl::false_()),
+ ordered_index_upper_bound(
+ Node::from_impl(top->right()),y,key,x,comp,mpl::false_()));
}
}
diff --git a/boost/multi_index/detail/promotes_arg.hpp b/boost/multi_index/detail/promotes_arg.hpp
new file mode 100644
index 0000000..75cf436
--- /dev/null
+++ b/boost/multi_index/detail/promotes_arg.hpp
@@ -0,0 +1,83 @@
+/* Copyright 2003-2014 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)
+ *
+ * See http://www.boost.org/libs/multi_index for library home page.
+ */
+
+#ifndef BOOST_MULTI_INDEX_DETAIL_PROMOTES_ARG_HPP
+#define BOOST_MULTI_INDEX_DETAIL_PROMOTES_ARG_HPP
+
+#if defined(_MSC_VER)
+#pragma once
+#endif
+
+#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
+#include <boost/mpl/bool.hpp>
+#include <boost/type_traits/intrinsics.hpp>
+
+/* Metafunctions to check if f(arg1,arg2) promotes either arg1 to the type of
+ * arg2 or viceversa. By default, (i.e. if it cannot be determined), no
+ * promotion is assumed.
+ */
+
+#if !defined(BOOST_IS_CONVERTIBLE)
+
+namespace boost{
+
+namespace multi_index{
+
+namespace detail{
+
+template<typename F,typename Arg1,typename Arg2>
+struct promotes_1st_arg:mpl::false_{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct promotes_2nd_arg:mpl::false_{};
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#else
+
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/multi_index/detail/is_transparent.hpp>
+#include <boost/type_traits/is_convertible.hpp>
+
+namespace boost{
+
+namespace multi_index{
+
+namespace detail{
+
+template<typename F,typename Arg1,typename Arg2>
+struct promotes_1st_arg:
+ mpl::and_<
+ mpl::not_<is_transparent<F,Arg1,Arg2> >,
+ is_convertible<const Arg1,Arg2>,
+ is_transparent<F,Arg2,Arg2>
+ >
+{};
+
+template<typename F,typename Arg1,typename Arg2>
+struct promotes_2nd_arg:
+ mpl::and_<
+ mpl::not_<is_transparent<F,Arg1,Arg2> >,
+ is_convertible<const Arg2,Arg1>,
+ is_transparent<F,Arg1,Arg1>
+ >
+{};
+
+} /* namespace multi_index::detail */
+
+} /* namespace multi_index */
+
+} /* namespace boost */
+
+#endif /* defined(BOOST_IS_CONVERTIBLE) */
+#endif
diff --git a/boost/multi_index/detail/rnd_index_node.hpp b/boost/multi_index/detail/rnd_index_node.hpp
index 991f6da..def0575 100644
--- a/boost/multi_index/detail/rnd_index_node.hpp
+++ b/boost/multi_index/detail/rnd_index_node.hpp
@@ -1,4 +1,4 @@
-/* Copyright 2003-2013 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)
@@ -16,7 +16,7 @@
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/detail/allocator_utilities.hpp>
-#include <boost/math/common_factor_rt.hpp>
+#include <boost/integer/common_factor_rt.hpp>
#include <cstddef>
#include <functional>
@@ -105,7 +105,7 @@ struct random_access_index_node_impl
std::ptrdiff_t n=end-begin;
std::ptrdiff_t m=middle-begin;
std::ptrdiff_t n_m=n-m;
- std::ptrdiff_t p=math::gcd(n,m);
+ std::ptrdiff_t p=integer::gcd(n,m);
for(std::ptrdiff_t i=0;i<p;++i){
pointer tmp=begin[i];
diff --git a/boost/multi_index/detail/rnd_index_ops.hpp b/boost/multi_index/detail/rnd_index_ops.hpp
index 6cb030f..d05386d 100644
--- a/boost/multi_index/detail/rnd_index_ops.hpp
+++ b/boost/multi_index/detail/rnd_index_ops.hpp
@@ -1,4 +1,4 @@
-/* Copyright 2003-2013 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)
@@ -172,7 +172,6 @@ void random_access_index_sort(
if(ptrs.size()<=1)return;
- typedef typename Node::value_type value_type;
typedef typename Node::impl_pointer impl_pointer;
typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
typedef random_access_index_sort_compare<
diff --git a/boost/multi_index/detail/rnd_node_iterator.hpp b/boost/multi_index/detail/rnd_node_iterator.hpp
index 65bf5e8..4802613 100644
--- a/boost/multi_index/detail/rnd_node_iterator.hpp
+++ b/boost/multi_index/detail/rnd_node_iterator.hpp
@@ -1,4 +1,4 @@
-/* Copyright 2003-2013 Joaquin M Lopez Munoz.
+/* Copyright 2003-2014 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)
@@ -39,6 +39,7 @@ class rnd_node_iterator:
const typename Node::value_type&>
{
public:
+ /* coverity[uninit_ctor]: suppress warning */
rnd_node_iterator(){}
explicit rnd_node_iterator(Node* node_):node(node_){}
diff --git a/boost/multi_index/hashed_index.hpp b/boost/multi_index/hashed_index.hpp
index ebf55c9..436fecf 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_;
diff --git a/boost/multi_index/ordered_index.hpp b/boost/multi_index/ordered_index.hpp
index 3f0ae5d..267f153 100644
--- a/boost/multi_index/ordered_index.hpp
+++ b/boost/multi_index/ordered_index.hpp
@@ -987,6 +987,7 @@ private:
struct link_info
{
+ /* coverity[uninit_ctor]: suppress warning */
link_info():side(to_left){}
ordered_index_side side;