summaryrefslogtreecommitdiff
path: root/boost/unordered/unordered_map.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/unordered/unordered_map.hpp')
-rw-r--r--boost/unordered/unordered_map.hpp1469
1 files changed, 873 insertions, 596 deletions
diff --git a/boost/unordered/unordered_map.hpp b/boost/unordered/unordered_map.hpp
index 64e5b1fdf8..a0b4d53292 100644
--- a/boost/unordered/unordered_map.hpp
+++ b/boost/unordered/unordered_map.hpp
@@ -17,6 +17,7 @@
#include <boost/core/explicit_operator_bool.hpp>
#include <boost/functional/hash.hpp>
#include <boost/move/move.hpp>
+#include <boost/type_traits/is_constructible.hpp>
#include <boost/unordered/detail/map.hpp>
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
@@ -44,8 +45,8 @@ template <class K, class T, class H, class P, class A> class unordered_map
public:
typedef K key_type;
- typedef std::pair<const K, T> value_type;
typedef T mapped_type;
+ typedef std::pair<const K, T> value_type;
typedef H hasher;
typedef P key_equal;
typedef A allocator_type;
@@ -54,6 +55,8 @@ template <class K, class T, class H, class P, class A> class unordered_map
typedef boost::unordered::detail::map<A, K, T, H, P> types;
typedef typename types::value_allocator_traits value_allocator_traits;
typedef typename types::table table;
+ typedef typename table::node_pointer node_pointer;
+ typedef typename table::link_pointer link_pointer;
public:
typedef typename value_allocator_traits::pointer pointer;
@@ -65,10 +68,10 @@ template <class K, class T, class H, class P, class A> class unordered_map
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef typename table::cl_iterator const_local_iterator;
- typedef typename table::l_iterator local_iterator;
- typedef typename table::c_iterator const_iterator;
typedef typename table::iterator iterator;
+ typedef typename table::c_iterator const_iterator;
+ typedef typename table::l_iterator local_iterator;
+ typedef typename table::cl_iterator const_local_iterator;
typedef typename types::node_type node_type;
typedef typename types::insert_return_type insert_return_type;
@@ -84,59 +87,54 @@ template <class K, class T, class H, class P, class A> class unordered_map
const key_equal& = key_equal(),
const allocator_type& = allocator_type());
- explicit unordered_map(size_type, const allocator_type&);
-
- explicit unordered_map(size_type, const hasher&, const allocator_type&);
-
- explicit unordered_map(allocator_type const&);
-
- template <class InputIt> unordered_map(InputIt, InputIt);
-
- template <class InputIt>
- unordered_map(InputIt, InputIt, size_type, const hasher& = hasher(),
- const key_equal& = key_equal());
-
template <class InputIt>
- unordered_map(InputIt, InputIt, size_type, const hasher&, const key_equal&,
- const allocator_type&);
-
- template <class InputIt>
- unordered_map(
- InputIt, InputIt, size_type, const hasher&, const allocator_type&);
-
- template <class InputIt>
- unordered_map(InputIt, InputIt, size_type, const allocator_type&);
-
- // copy/move constructors
+ unordered_map(InputIt, InputIt,
+ size_type = boost::unordered::detail::default_bucket_count,
+ const hasher& = hasher(), const key_equal& = key_equal(),
+ const allocator_type& = allocator_type());
unordered_map(unordered_map const&);
- unordered_map(unordered_map const&, allocator_type const&);
- unordered_map(BOOST_RV_REF(unordered_map), allocator_type const&);
-
-#if defined(BOOST_UNORDERED_USE_MOVE)
+#if defined(BOOST_UNORDERED_USE_MOVE) || \
+ !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_map(BOOST_RV_REF(unordered_map) other)
BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
: table_(other.table_, boost::unordered::detail::move_tag())
{
- }
-#elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
- unordered_map(unordered_map&& other)
- BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
- : table_(other.table_, boost::unordered::detail::move_tag())
- {
+ // The move is done in table_
}
#endif
+ explicit unordered_map(allocator_type const&);
+
+ unordered_map(unordered_map const&, allocator_type const&);
+
+ unordered_map(BOOST_RV_REF(unordered_map), allocator_type const&);
+
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
unordered_map(std::initializer_list<value_type>,
size_type = boost::unordered::detail::default_bucket_count,
const hasher& = hasher(), const key_equal& l = key_equal(),
const allocator_type& = allocator_type());
- unordered_map(std::initializer_list<value_type>, size_type, const hasher&,
- const allocator_type&);
+#endif
+
+ explicit unordered_map(size_type, const allocator_type&);
+
+ explicit unordered_map(size_type, const hasher&, const allocator_type&);
+
+ template <class InputIt>
+ unordered_map(InputIt, InputIt, size_type, const allocator_type&);
+
+ template <class InputIt>
+ unordered_map(
+ InputIt, InputIt, size_type, const hasher&, const allocator_type&);
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
unordered_map(
std::initializer_list<value_type>, size_type, const allocator_type&);
+
+ unordered_map(std::initializer_list<value_type>, size_type, const hasher&,
+ const allocator_type&);
#endif
// Destructor
@@ -148,26 +146,34 @@ template <class K, class T, class H, class P, class A> class unordered_map
#if defined(BOOST_UNORDERED_USE_MOVE)
unordered_map& operator=(BOOST_COPY_ASSIGN_REF(unordered_map) x)
{
- table_.assign(x.table_);
+ table_.assign(x.table_, boost::unordered::detail::true_type());
return *this;
}
unordered_map& operator=(BOOST_RV_REF(unordered_map) x)
+ // C++17 support: BOOST_NOEXCEPT_IF(
+ // value_allocator_traits::is_always_equal::value &&
+ // is_nothrow_move_assignable_v<H> &&
+ // is_nothrow_move_assignable_v<P>)
{
- table_.move_assign(x.table_);
+ table_.move_assign(x.table_, boost::unordered::detail::true_type());
return *this;
}
#else
unordered_map& operator=(unordered_map const& x)
{
- table_.assign(x.table_);
+ table_.assign(x.table_, boost::unordered::detail::true_type());
return *this;
}
#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_map& operator=(unordered_map&& x)
+ // C++17 support: BOOST_NOEXCEPT_IF(
+ // value_allocator_traits::is_always_equal::value &&
+ // is_nothrow_move_assignable_v<H> &&
+ // is_nothrow_move_assignable_v<P>)
{
- table_.move_assign(x.table_);
+ table_.move_assign(x.table_, boost::unordered::detail::true_type());
return *this;
}
#endif
@@ -182,14 +188,6 @@ template <class K, class T, class H, class P, class A> class unordered_map
return table_.node_alloc();
}
- // size and capacity
-
- bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
-
- size_type size() const BOOST_NOEXCEPT { return table_.size_; }
-
- size_type max_size() const BOOST_NOEXCEPT;
-
// iterators
iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
@@ -210,311 +208,456 @@ template <class K, class T, class H, class P, class A> class unordered_map
const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
- // extract
+ // size and capacity
- node_type extract(const_iterator position)
- {
- return node_type(
- table_.extract_by_iterator(position), table_.node_alloc());
- }
+ bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
- node_type extract(const key_type& k)
- {
- return node_type(table_.extract_by_key(k), table_.node_alloc());
- }
+ size_type size() const BOOST_NOEXCEPT { return table_.size_; }
+
+ size_type max_size() const BOOST_NOEXCEPT;
// emplace
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
template <class... Args>
std::pair<iterator, bool> emplace(BOOST_FWD_REF(Args)... args)
{
- return table_.emplace(boost::forward<Args>(args)...);
+ return table_.emplace_unique(
+ table::extractor::extract(boost::forward<Args>(args)...),
+ boost::forward<Args>(args)...);
}
- template <class... Args>
- iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
+#else
+
+#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
+
+ // 0 argument emplace requires special treatment in case
+ // the container is instantiated with a value type that
+ // doesn't have a default constructor.
+
+ std::pair<iterator, bool> emplace(
+ boost::unordered::detail::empty_emplace =
+ boost::unordered::detail::empty_emplace(),
+ value_type v = value_type())
{
- return table_.emplace_hint(hint, boost::forward<Args>(args)...);
+ return this->emplace(boost::move(v));
}
- template <class... Args>
- std::pair<iterator, bool> try_emplace(
- key_type const& k, BOOST_FWD_REF(Args)... args)
+#endif
+
+ template <typename A0>
+ std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0)
{
- return table_.try_emplace_impl(k, boost::forward<Args>(args)...);
+ return table_.emplace_unique(
+ table::extractor::extract(boost::forward<A0>(a0)),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
}
- template <class... Args>
- iterator try_emplace(
- const_iterator hint, key_type const& k, BOOST_FWD_REF(Args)... args)
+ template <typename A0, typename A1>
+ std::pair<iterator, bool> emplace(
+ BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
{
- return table_.try_emplace_hint_impl(
- hint, k, boost::forward<Args>(args)...);
+ return table_.emplace_unique(
+ table::extractor::extract(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)));
}
- template <class... Args>
- std::pair<iterator, bool> try_emplace(
- BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
+ template <typename A0, typename A1, typename A2>
+ std::pair<iterator, bool> emplace(
+ BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
- return table_.try_emplace_impl(
- boost::move(k), boost::forward<Args>(args)...);
+ return table_.emplace_unique(
+ table::extractor::extract(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)));
}
+#endif
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
template <class... Args>
- iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
- BOOST_FWD_REF(Args)... args)
+ iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
{
- return table_.try_emplace_hint_impl(
- hint, boost::move(k), boost::forward<Args>(args)...);
+ return table_.emplace_hint_unique(hint,
+ table::extractor::extract(boost::forward<Args>(args)...),
+ boost::forward<Args>(args)...);
}
-#else
-#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
+#else
- // 0 argument emplace requires special treatment in case
- // the container is instantiated with a value type that
- // doesn't have a default constructor.
+#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
- std::pair<iterator, bool> emplace(
+ iterator emplace_hint(const_iterator hint,
boost::unordered::detail::empty_emplace =
boost::unordered::detail::empty_emplace(),
value_type v = value_type())
{
- return this->emplace(boost::move(v));
+ return this->emplace_hint(hint, boost::move(v));
}
- iterator emplace_hint(const_iterator hint,
- boost::unordered::detail::empty_emplace =
- boost::unordered::detail::empty_emplace(),
- value_type v = value_type())
+#endif
+
+ template <typename A0>
+ iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
{
- return this->emplace_hint(hint, boost::move(v));
+ return table_.emplace_hint_unique(hint,
+ table::extractor::extract(boost::forward<A0>(a0)),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
+ }
+
+ template <typename A0, typename A1>
+ iterator emplace_hint(
+ const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ {
+ return table_.emplace_hint_unique(
+ hint, table::extractor::extract(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)));
+ }
+
+ template <typename A0, typename A1, typename A2>
+ iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
+ BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
+ {
+ return table_.emplace_hint_unique(
+ hint, table::extractor::extract(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)));
}
#endif
- template <typename Key>
- std::pair<iterator, bool> try_emplace(BOOST_FWD_REF(Key) k)
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ std::pair<iterator, bool> emplace( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
+ { \
+ return table_.emplace_unique( \
+ table::extractor::extract( \
+ boost::forward<A0>(a0), boost::forward<A1>(a1)), \
+ boost::unordered::detail::create_emplace_args( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
+ } \
+ \
+ template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
+ iterator emplace_hint(const_iterator hint, \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
+ { \
+ return table_.emplace_hint_unique( \
+ hint, table::extractor::extract( \
+ boost::forward<A0>(a0), boost::forward<A1>(a1)), \
+ boost::unordered::detail::create_emplace_args( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
+ }
+
+ BOOST_UNORDERED_EMPLACE(1, 4, _)
+ BOOST_UNORDERED_EMPLACE(1, 5, _)
+ BOOST_UNORDERED_EMPLACE(1, 6, _)
+ BOOST_UNORDERED_EMPLACE(1, 7, _)
+ BOOST_UNORDERED_EMPLACE(1, 8, _)
+ BOOST_UNORDERED_EMPLACE(1, 9, _)
+ BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ std::pair<iterator, bool> insert(value_type const& x)
{
- return table_.try_emplace_impl(boost::forward<Key>(k));
+ return this->emplace(x);
}
- template <typename Key>
- iterator try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k)
+ std::pair<iterator, bool> insert(BOOST_RV_REF(value_type) x)
{
- return table_.try_emplace_hint_impl(hint, boost::forward<Key>(k));
+ return this->emplace(boost::move(x));
}
- template <typename A0>
- std::pair<iterator, bool> emplace(BOOST_FWD_REF(A0) a0)
+ template <class P2>
+ std::pair<iterator, bool> insert(BOOST_RV_REF(P2) obj,
+ typename boost::enable_if_c<
+ boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value,
+ void*>::type = 0)
{
- return table_.emplace(boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
+ return this->emplace(boost::forward<P2>(obj));
}
- template <typename A0>
- iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
+ iterator insert(const_iterator hint, value_type const& x)
{
- return table_.emplace_hint(
- hint, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
+ return this->emplace_hint(hint, x);
}
- template <typename A0>
- std::pair<iterator, bool> try_emplace(
- key_type const& k, BOOST_FWD_REF(A0) a0)
+ iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x)
{
- return table_.try_emplace_impl(
- k, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
+ return this->emplace_hint(hint, boost::move(x));
}
- template <typename A0>
- iterator try_emplace(
- const_iterator hint, key_type const& k, BOOST_FWD_REF(A0) a0)
+ template <class P2>
+ iterator insert(const_iterator hint, BOOST_RV_REF(P2) obj,
+ typename boost::enable_if_c<
+ boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value,
+ void*>::type = 0)
{
- return table_.try_emplace_hint_impl(
- hint, k, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
+ return this->emplace_hint(hint, boost::forward<P2>(obj));
}
- template <typename A0>
+ template <class InputIt> void insert(InputIt, InputIt);
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+ void insert(std::initializer_list<value_type>);
+#endif
+
+ // extract
+
+ node_type extract(const_iterator position)
+ {
+ return node_type(
+ table_.extract_by_iterator_unique(position), table_.node_alloc());
+ }
+
+ node_type extract(const key_type& k)
+ {
+ return node_type(table_.extract_by_key(k), table_.node_alloc());
+ }
+
+ insert_return_type insert(BOOST_RV_REF(node_type) np)
+ {
+ insert_return_type result;
+ table_.move_insert_node_type_unique(np, result);
+ return boost::move(result);
+ }
+
+ iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
+ {
+ return table_.move_insert_node_type_with_hint_unique(hint, np);
+ }
+
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \
+ (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0))
+ private:
+ // Note: Use r-value node_type to insert.
+ insert_return_type insert(node_type&);
+ iterator insert(const_iterator, node_type& np);
+
+ public:
+#endif
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template <class... Args>
std::pair<iterator, bool> try_emplace(
- BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
+ key_type const& k, BOOST_FWD_REF(Args)... args)
{
- return table_.try_emplace_impl(
- boost::move(k), boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
+ return table_.try_emplace_unique(k, boost::forward<Args>(args)...);
}
- template <typename A0>
+ template <class... Args>
+ std::pair<iterator, bool> try_emplace(
+ BOOST_RV_REF(key_type) k, BOOST_FWD_REF(Args)... args)
+ {
+ return table_.try_emplace_unique(
+ boost::move(k), boost::forward<Args>(args)...);
+ }
+
+ template <class... Args>
iterator try_emplace(
- const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
+ const_iterator hint, key_type const& k, BOOST_FWD_REF(Args)... args)
{
- return table_.try_emplace_hint_impl(
- hint, boost::move(k), boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
+ return table_.try_emplace_hint_unique(
+ hint, k, boost::forward<Args>(args)...);
}
- template <typename A0, typename A1>
- std::pair<iterator, bool> emplace(
- BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ template <class... Args>
+ iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
+ BOOST_FWD_REF(Args)... args)
{
- return table_.emplace(boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1)));
+ return table_.try_emplace_hint_unique(
+ hint, boost::move(k), boost::forward<Args>(args)...);
}
- template <typename A0, typename A1>
- iterator emplace_hint(
- const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+#else
+
+ // In order to make this a template, this handles both:
+ // try_emplace(key const&)
+ // try_emplace(key&&)
+
+ template <typename Key>
+ std::pair<iterator, bool> try_emplace(BOOST_FWD_REF(Key) k)
{
- return table_.emplace_hint(
- hint, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1)));
+ return table_.try_emplace_unique(boost::forward<Key>(k));
+ }
+
+ // In order to make this a template, this handles both:
+ // try_emplace(const_iterator hint, key const&)
+ // try_emplace(const_iterator hint, key&&)
+
+ template <typename Key>
+ iterator try_emplace(const_iterator hint, BOOST_FWD_REF(Key) k)
+ {
+ return table_.try_emplace_hint_unique(hint, boost::forward<Key>(k));
+ }
+
+ // try_emplace(key const&, Args&&...)
+
+ template <typename A0>
+ std::pair<iterator, bool> try_emplace(
+ key_type const& k, BOOST_FWD_REF(A0) a0)
+ {
+ return table_.try_emplace_unique(
+ k, boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
}
template <typename A0, typename A1>
std::pair<iterator, bool> try_emplace(
key_type const& k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
{
- return table_.try_emplace_impl(
+ return table_.try_emplace_unique(
k, boost::unordered::detail::create_emplace_args(
boost::forward<A0>(a0), boost::forward<A1>(a1)));
}
- template <typename A0, typename A1>
- iterator try_emplace(const_iterator hint, key_type const& k,
- BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ template <typename A0, typename A1, typename A2>
+ std::pair<iterator, bool> try_emplace(key_type const& k,
+ BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
- return table_.try_emplace_hint_impl(
- hint, k, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1)));
+ return table_.try_emplace_unique(
+ k, boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)));
}
- template <typename A0, typename A1>
+ // try_emplace(key&&, Args&&...)
+
+ template <typename A0>
std::pair<iterator, bool> try_emplace(
- BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
{
- return table_.try_emplace_impl(
- boost::move(k),
- boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1)));
+ return table_.try_emplace_unique(
+ boost::move(k), boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
}
template <typename A0, typename A1>
- iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
- BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ std::pair<iterator, bool> try_emplace(
+ BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
{
- return table_.try_emplace_hint_impl(
- hint, boost::move(k),
+ return table_.try_emplace_unique(
+ boost::move(k),
boost::unordered::detail::create_emplace_args(
boost::forward<A0>(a0), boost::forward<A1>(a1)));
}
template <typename A0, typename A1, typename A2>
- std::pair<iterator, bool> emplace(
+ std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k,
BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
- return table_.emplace(boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)));
+ return table_.try_emplace_unique(
+ boost::move(k), boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)));
}
- template <typename A0, typename A1, typename A2>
- iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
- BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
+ // try_emplace(const_iterator hint, key const&, Args&&...)
+
+ template <typename A0>
+ iterator try_emplace(
+ const_iterator hint, key_type const& k, BOOST_FWD_REF(A0) a0)
{
- return table_.emplace_hint(
- hint, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)));
+ return table_.try_emplace_hint_unique(
+ hint, k, boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
}
- template <typename A0, typename A1, typename A2>
- std::pair<iterator, bool> try_emplace(key_type const& k,
- BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
+ template <typename A0, typename A1>
+ iterator try_emplace(const_iterator hint, key_type const& k,
+ BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
{
- return table_.try_emplace_impl(
- k, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)));
+ return table_.try_emplace_hint_unique(
+ hint, k, boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)));
}
template <typename A0, typename A1, typename A2>
iterator try_emplace(const_iterator hint, key_type const& k,
BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
- return table_
- .try_emplace_impl_(
- hint, k, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)))
- .first;
+ return table_.try_emplace_hint_unique(
+ hint, k, boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)));
}
- template <typename A0, typename A1, typename A2>
- std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k,
- BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
+ // try_emplace(const_iterator hint, key&&, Args&&...)
+
+ template <typename A0>
+ iterator try_emplace(
+ const_iterator hint, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(A0) a0)
{
- return table_.try_emplace_impl(
- boost::move(k), boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)));
+ return table_.try_emplace_hint_unique(
+ hint, boost::move(k), boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)));
+ }
+
+ template <typename A0, typename A1>
+ iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
+ BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ {
+ return table_.try_emplace_hint_unique(
+ hint, boost::move(k),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)));
}
template <typename A0, typename A1, typename A2>
iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k,
BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
- return table_.try_emplace_hint_impl(
+ return table_.try_emplace_hint_unique(
hint, boost::move(k),
boost::unordered::detail::create_emplace_args(
boost::forward<A0>(a0), boost::forward<A1>(a1),
boost::forward<A2>(a2)));
}
-#define BOOST_UNORDERED_EMPLACE(z, n, _) \
- template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
- std::pair<iterator, bool> emplace( \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
- { \
- return table_.emplace(boost::unordered::detail::create_emplace_args( \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
- } \
- \
- template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
- iterator emplace_hint(const_iterator hint, \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
- { \
- return table_.emplace_hint( \
- hint, boost::unordered::detail::create_emplace_args( \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
- } \
+#define BOOST_UNORDERED_TRY_EMPLACE(z, n, _) \
\
template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
std::pair<iterator, bool> try_emplace( \
key_type const& k, BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
{ \
- return table_.try_emplace_impl( \
+ return table_.try_emplace_unique( \
k, boost::unordered::detail::create_emplace_args( \
BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
} \
\
template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
- iterator try_emplace(const_iterator hint, key_type const& k, \
+ std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, \
BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
{ \
- return table_.try_emplace_hint_impl(hint, k, \
+ return table_.try_emplace_unique(boost::move(k), \
boost::unordered::detail::create_emplace_args(BOOST_PP_ENUM_##z( \
n, BOOST_UNORDERED_CALL_FORWARD, a))); \
} \
\
template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
- std::pair<iterator, bool> try_emplace(BOOST_RV_REF(key_type) k, \
+ iterator try_emplace(const_iterator hint, key_type const& k, \
BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
{ \
- return table_.try_emplace_impl(boost::move(k), \
+ return table_.try_emplace_hint_unique(hint, k, \
boost::unordered::detail::create_emplace_args(BOOST_PP_ENUM_##z( \
n, BOOST_UNORDERED_CALL_FORWARD, a))); \
} \
@@ -523,58 +666,44 @@ template <class K, class T, class H, class P, class A> class unordered_map
iterator try_emplace(const_iterator hint, BOOST_RV_REF(key_type) k, \
BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
{ \
- return table_.try_emplace_hint_impl(hint, boost::move(k), \
+ return table_.try_emplace_hint_unique(hint, boost::move(k), \
boost::unordered::detail::create_emplace_args(BOOST_PP_ENUM_##z( \
n, BOOST_UNORDERED_CALL_FORWARD, a))); \
}
- BOOST_PP_REPEAT_FROM_TO(
- 4, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EMPLACE, _)
+ BOOST_UNORDERED_TRY_EMPLACE(1, 4, _)
+ BOOST_UNORDERED_TRY_EMPLACE(1, 5, _)
+ BOOST_UNORDERED_TRY_EMPLACE(1, 6, _)
+ BOOST_UNORDERED_TRY_EMPLACE(1, 7, _)
+ BOOST_UNORDERED_TRY_EMPLACE(1, 8, _)
+ BOOST_UNORDERED_TRY_EMPLACE(1, 9, _)
+ BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
+ BOOST_UNORDERED_TRY_EMPLACE, _)
-#undef BOOST_UNORDERED_EMPLACE
+#undef BOOST_UNORDERED_TRY_EMPLACE
#endif
- std::pair<iterator, bool> insert(value_type const& x)
- {
- return this->emplace(x);
- }
-
- std::pair<iterator, bool> insert(BOOST_RV_REF(value_type) x)
- {
- return this->emplace(boost::move(x));
- }
-
- iterator insert(const_iterator hint, value_type const& x)
- {
- return this->emplace_hint(hint, x);
- }
-
- iterator insert(const_iterator hint, BOOST_RV_REF(value_type) x)
- {
- return this->emplace_hint(hint, boost::move(x));
- }
-
template <class M>
std::pair<iterator, bool> insert_or_assign(
key_type const& k, BOOST_FWD_REF(M) obj)
{
- return table_.insert_or_assign_impl(k, boost::forward<M>(obj));
+ return table_.insert_or_assign_unique(k, boost::forward<M>(obj));
}
template <class M>
- iterator insert_or_assign(
- const_iterator, key_type const& k, BOOST_FWD_REF(M) obj)
+ std::pair<iterator, bool> insert_or_assign(
+ BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
{
- return table_.insert_or_assign_impl(k, boost::forward<M>(obj)).first;
+ return table_.insert_or_assign_unique(
+ boost::move(k), boost::forward<M>(obj));
}
template <class M>
- std::pair<iterator, bool> insert_or_assign(
- BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
+ iterator insert_or_assign(
+ const_iterator, key_type const& k, BOOST_FWD_REF(M) obj)
{
- return table_.insert_or_assign_impl(
- boost::move(k), boost::forward<M>(obj));
+ return table_.insert_or_assign_unique(k, boost::forward<M>(obj)).first;
}
template <class M>
@@ -582,45 +711,25 @@ template <class K, class T, class H, class P, class A> class unordered_map
const_iterator, BOOST_RV_REF(key_type) k, BOOST_FWD_REF(M) obj)
{
return table_
- .insert_or_assign_impl(boost::move(k), boost::forward<M>(obj))
+ .insert_or_assign_unique(boost::move(k), boost::forward<M>(obj))
.first;
}
- template <class InputIt> void insert(InputIt, InputIt);
-
-#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
- void insert(std::initializer_list<value_type>);
-#endif
-
- insert_return_type insert(BOOST_RV_REF(node_type) np)
- {
- insert_return_type result;
- table_.move_insert_node_type(np, result);
- return boost::move(result);
- }
-
- iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
- {
- return table_.move_insert_node_type_with_hint(hint, np);
- }
-
-#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
- private:
- // Note: Use r-value node_type to insert.
- insert_return_type insert(node_type&);
- iterator insert(const_iterator, node_type& np);
-
- public:
-#endif
-
+ iterator erase(iterator);
iterator erase(const_iterator);
size_type erase(const key_type&);
iterator erase(const_iterator, const_iterator);
+ BOOST_UNORDERED_DEPRECATED("Use erase instead")
void quick_erase(const_iterator it) { erase(it); }
+ BOOST_UNORDERED_DEPRECATED("Use erase instead")
void erase_return_void(const_iterator it) { erase(it); }
- void clear();
void swap(unordered_map&);
+ // C++17 support: BOOST_NOEXCEPT_IF(
+ // value_allocator_traits::is_always_equal::value &&
+ // is_nothrow_move_assignable_v<H> &&
+ // is_nothrow_move_assignable_v<P>)
+ void clear() BOOST_NOEXCEPT { table_.clear_impl(); }
template <typename H2, typename P2>
void merge(boost::unordered_map<K, T, H2, P2, A>& source);
@@ -630,7 +739,6 @@ template <class K, class T, class H, class P, class A> class unordered_map
void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
#endif
-#if BOOST_UNORDERED_INTEROPERABLE_NODES
template <typename H2, typename P2>
void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
@@ -638,17 +746,12 @@ template <class K, class T, class H, class P, class A> class unordered_map
template <typename H2, typename P2>
void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
#endif
-#endif
// observers
hasher hash_function() const;
key_equal key_eq() const;
- mapped_type& operator[](const key_type&);
- mapped_type& at(const key_type&);
- mapped_type const& at(const key_type&) const;
-
// lookup
iterator find(const key_type&);
@@ -670,6 +773,11 @@ template <class K, class T, class H, class P, class A> class unordered_map
std::pair<const_iterator, const_iterator> equal_range(
const key_type&) const;
+ mapped_type& operator[](const key_type&);
+ mapped_type& operator[](BOOST_RV_REF(key_type));
+ mapped_type& at(const key_type&);
+ mapped_type const& at(const key_type&) const;
+
// bucket interface
size_type bucket_count() const BOOST_NOEXCEPT
@@ -715,9 +823,8 @@ template <class K, class T, class H, class P, class A> class unordered_map
// hash policy
- float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
-
float load_factor() const BOOST_NOEXCEPT;
+ float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
void max_load_factor(float) BOOST_NOEXCEPT;
void rehash(size_type);
void reserve(size_type);
@@ -740,16 +847,18 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
public:
typedef K key_type;
- typedef std::pair<const K, T> value_type;
typedef T mapped_type;
+ typedef std::pair<const K, T> value_type;
typedef H hasher;
typedef P key_equal;
typedef A allocator_type;
private:
- typedef boost::unordered::detail::multimap<A, K, T, H, P> types;
+ typedef boost::unordered::detail::map<A, K, T, H, P> types;
typedef typename types::value_allocator_traits value_allocator_traits;
typedef typename types::table table;
+ typedef typename table::node_pointer node_pointer;
+ typedef typename table::link_pointer link_pointer;
public:
typedef typename value_allocator_traits::pointer pointer;
@@ -761,10 +870,10 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef typename table::cl_iterator const_local_iterator;
- typedef typename table::l_iterator local_iterator;
- typedef typename table::c_iterator const_iterator;
typedef typename table::iterator iterator;
+ typedef typename table::c_iterator const_iterator;
+ typedef typename table::l_iterator local_iterator;
+ typedef typename table::cl_iterator const_local_iterator;
typedef typename types::node_type node_type;
private:
@@ -779,60 +888,55 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
const key_equal& = key_equal(),
const allocator_type& = allocator_type());
- explicit unordered_multimap(size_type, const allocator_type&);
-
- explicit unordered_multimap(
- size_type, const hasher&, const allocator_type&);
-
- explicit unordered_multimap(allocator_type const&);
-
- template <class InputIt> unordered_multimap(InputIt, InputIt);
-
template <class InputIt>
- unordered_multimap(InputIt, InputIt, size_type, const hasher& = hasher(),
- const key_equal& = key_equal());
-
- template <class InputIt>
- unordered_multimap(InputIt, InputIt, size_type, const hasher&,
- const key_equal&, const allocator_type&);
-
- template <class InputIt>
- unordered_multimap(
- InputIt, InputIt, size_type, const hasher&, const allocator_type&);
-
- template <class InputIt>
- unordered_multimap(InputIt, InputIt, size_type, const allocator_type&);
-
- // copy/move constructors
+ unordered_multimap(InputIt, InputIt,
+ size_type = boost::unordered::detail::default_bucket_count,
+ const hasher& = hasher(), const key_equal& = key_equal(),
+ const allocator_type& = allocator_type());
unordered_multimap(unordered_multimap const&);
- unordered_multimap(unordered_multimap const&, allocator_type const&);
- unordered_multimap(BOOST_RV_REF(unordered_multimap), allocator_type const&);
-
-#if defined(BOOST_UNORDERED_USE_MOVE)
+#if defined(BOOST_UNORDERED_USE_MOVE) || \
+ !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_multimap(BOOST_RV_REF(unordered_multimap) other)
BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
: table_(other.table_, boost::unordered::detail::move_tag())
{
- }
-#elif !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
- unordered_multimap(unordered_multimap&& other)
- BOOST_NOEXCEPT_IF(table::nothrow_move_constructible)
- : table_(other.table_, boost::unordered::detail::move_tag())
- {
+ // The move is done in table_
}
#endif
+ explicit unordered_multimap(allocator_type const&);
+
+ unordered_multimap(unordered_multimap const&, allocator_type const&);
+
+ unordered_multimap(BOOST_RV_REF(unordered_multimap), allocator_type const&);
+
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
unordered_multimap(std::initializer_list<value_type>,
size_type = boost::unordered::detail::default_bucket_count,
const hasher& = hasher(), const key_equal& l = key_equal(),
const allocator_type& = allocator_type());
- unordered_multimap(std::initializer_list<value_type>, size_type,
- const hasher&, const allocator_type&);
+#endif
+
+ explicit unordered_multimap(size_type, const allocator_type&);
+
+ explicit unordered_multimap(
+ size_type, const hasher&, const allocator_type&);
+
+ template <class InputIt>
+ unordered_multimap(InputIt, InputIt, size_type, const allocator_type&);
+
+ template <class InputIt>
+ unordered_multimap(
+ InputIt, InputIt, size_type, const hasher&, const allocator_type&);
+
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
unordered_multimap(
std::initializer_list<value_type>, size_type, const allocator_type&);
+
+ unordered_multimap(std::initializer_list<value_type>, size_type,
+ const hasher&, const allocator_type&);
#endif
// Destructor
@@ -844,26 +948,34 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
#if defined(BOOST_UNORDERED_USE_MOVE)
unordered_multimap& operator=(BOOST_COPY_ASSIGN_REF(unordered_multimap) x)
{
- table_.assign(x.table_);
+ table_.assign(x.table_, boost::unordered::detail::false_type());
return *this;
}
unordered_multimap& operator=(BOOST_RV_REF(unordered_multimap) x)
+ // C++17 support: BOOST_NOEXCEPT_IF(
+ // value_allocator_traits::is_always_equal::value &&
+ // is_nothrow_move_assignable_v<H> &&
+ // is_nothrow_move_assignable_v<P>)
{
- table_.move_assign(x.table_);
+ table_.move_assign(x.table_, boost::unordered::detail::false_type());
return *this;
}
#else
unordered_multimap& operator=(unordered_multimap const& x)
{
- table_.assign(x.table_);
+ table_.assign(x.table_, boost::unordered::detail::false_type());
return *this;
}
#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
unordered_multimap& operator=(unordered_multimap&& x)
+ // C++17 support: BOOST_NOEXCEPT_IF(
+ // value_allocator_traits::is_always_equal::value &&
+ // is_nothrow_move_assignable_v<H> &&
+ // is_nothrow_move_assignable_v<P>)
{
- table_.move_assign(x.table_);
+ table_.move_assign(x.table_, boost::unordered::detail::false_type());
return *this;
}
#endif
@@ -878,14 +990,6 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
return table_.node_alloc();
}
- // size and capacity
-
- bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
-
- size_type size() const BOOST_NOEXCEPT { return table_.size_; }
-
- size_type max_size() const BOOST_NOEXCEPT;
-
// iterators
iterator begin() BOOST_NOEXCEPT { return iterator(table_.begin()); }
@@ -906,35 +1010,28 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
const_iterator cend() const BOOST_NOEXCEPT { return const_iterator(); }
- // extract
+ // size and capacity
- node_type extract(const_iterator position)
- {
- return node_type(
- table_.extract_by_iterator(position), table_.node_alloc());
- }
+ bool empty() const BOOST_NOEXCEPT { return table_.size_ == 0; }
- node_type extract(const key_type& k)
- {
- return node_type(table_.extract_by_key(k), table_.node_alloc());
- }
+ size_type size() const BOOST_NOEXCEPT { return table_.size_; }
+
+ size_type max_size() const BOOST_NOEXCEPT;
// emplace
#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
template <class... Args> iterator emplace(BOOST_FWD_REF(Args)... args)
{
- return table_.emplace(boost::forward<Args>(args)...);
+ return iterator(table_.emplace_equiv(
+ boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(), boost::forward<Args>(args)...)));
}
- template <class... Args>
- iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
- {
- return table_.emplace_hint(hint, boost::forward<Args>(args)...);
- }
#else
-#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
+#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
// 0 argument emplace requires special treatment in case
// the container is instantiated with a value type that
@@ -947,6 +1044,55 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
return this->emplace(boost::move(v));
}
+#endif
+
+ template <typename A0> iterator emplace(BOOST_FWD_REF(A0) a0)
+ {
+ return iterator(table_.emplace_equiv(
+ boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)))));
+ }
+
+ template <typename A0, typename A1>
+ iterator emplace(BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
+ {
+ return iterator(table_.emplace_equiv(
+ boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)))));
+ }
+
+ template <typename A0, typename A1, typename A2>
+ iterator emplace(
+ BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
+ {
+ return iterator(table_.emplace_equiv(
+ boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)))));
+ }
+
+#endif
+
+#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
+ template <class... Args>
+ iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(Args)... args)
+ {
+ return iterator(table_.emplace_hint_equiv(
+ hint, boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(), boost::forward<Args>(args)...)));
+ }
+
+#else
+
+#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
+
iterator emplace_hint(const_iterator hint,
boost::unordered::detail::empty_emplace =
boost::unordered::detail::empty_emplace(),
@@ -957,74 +1103,74 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
#endif
- template <typename A0> iterator emplace(BOOST_FWD_REF(A0) a0)
- {
- return table_.emplace(boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
- }
-
template <typename A0>
iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0)
{
- return table_.emplace_hint(
- hint, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0)));
- }
-
- template <typename A0, typename A1>
- iterator emplace(BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
- {
- return table_.emplace(boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1)));
+ return iterator(table_.emplace_hint_equiv(
+ hint, boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0)))));
}
template <typename A0, typename A1>
iterator emplace_hint(
const_iterator hint, BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1)
{
- return table_.emplace_hint(
- hint, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1)));
- }
-
- template <typename A0, typename A1, typename A2>
- iterator emplace(
- BOOST_FWD_REF(A0) a0, BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
- {
- return table_.emplace(boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)));
+ return iterator(table_.emplace_hint_equiv(
+ hint, boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1)))));
}
template <typename A0, typename A1, typename A2>
iterator emplace_hint(const_iterator hint, BOOST_FWD_REF(A0) a0,
BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
{
- return table_.emplace_hint(
- hint, boost::unordered::detail::create_emplace_args(
- boost::forward<A0>(a0), boost::forward<A1>(a1),
- boost::forward<A2>(a2)));
+ return iterator(table_.emplace_hint_equiv(
+ hint, boost::unordered::detail::func::construct_node_from_args(
+ table_.node_alloc(),
+ boost::unordered::detail::create_emplace_args(
+ boost::forward<A0>(a0), boost::forward<A1>(a1),
+ boost::forward<A2>(a2)))));
}
+#endif
+
+#if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
+
#define BOOST_UNORDERED_EMPLACE(z, n, _) \
template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
iterator emplace(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
{ \
- return table_.emplace(boost::unordered::detail::create_emplace_args( \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
+ return iterator(table_.emplace_equiv( \
+ boost::unordered::detail::func::construct_node_from_args( \
+ table_.node_alloc(), \
+ boost::unordered::detail::create_emplace_args( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \
} \
\
template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
iterator emplace_hint(const_iterator hint, \
BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, a)) \
{ \
- return table_.emplace_hint( \
- hint, boost::unordered::detail::create_emplace_args( \
- BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(
- 4, BOOST_UNORDERED_EMPLACE_LIMIT, BOOST_UNORDERED_EMPLACE, _)
+ return iterator(table_.emplace_hint_equiv( \
+ hint, \
+ boost::unordered::detail::func::construct_node_from_args( \
+ table_.node_alloc(), \
+ boost::unordered::detail::create_emplace_args( \
+ BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_CALL_FORWARD, a))))); \
+ }
+
+ BOOST_UNORDERED_EMPLACE(1, 4, _)
+ BOOST_UNORDERED_EMPLACE(1, 5, _)
+ BOOST_UNORDERED_EMPLACE(1, 6, _)
+ BOOST_UNORDERED_EMPLACE(1, 7, _)
+ BOOST_UNORDERED_EMPLACE(1, 8, _)
+ BOOST_UNORDERED_EMPLACE(1, 9, _)
+ BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
+ BOOST_UNORDERED_EMPLACE, _)
#undef BOOST_UNORDERED_EMPLACE
@@ -1037,6 +1183,15 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
return this->emplace(boost::move(x));
}
+ template <class P2>
+ iterator insert(BOOST_RV_REF(P2) obj,
+ typename boost::enable_if_c<
+ boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value,
+ void*>::type = 0)
+ {
+ return this->emplace(boost::forward<P2>(obj));
+ }
+
iterator insert(const_iterator hint, value_type const& x)
{
return this->emplace_hint(hint, x);
@@ -1047,23 +1202,46 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
return this->emplace_hint(hint, boost::move(x));
}
+ template <class P2>
+ iterator insert(const_iterator hint, BOOST_RV_REF(P2) obj,
+ typename boost::enable_if_c<
+ boost::is_constructible<value_type, BOOST_RV_REF(P2)>::value,
+ void*>::type = 0)
+ {
+ return this->emplace_hint(hint, boost::forward<P2>(obj));
+ }
+
template <class InputIt> void insert(InputIt, InputIt);
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
void insert(std::initializer_list<value_type>);
#endif
+ // extract
+
+ node_type extract(const_iterator position)
+ {
+ return node_type(
+ table_.extract_by_iterator_equiv(position), table_.node_alloc());
+ }
+
+ node_type extract(const key_type& k)
+ {
+ return node_type(table_.extract_by_key(k), table_.node_alloc());
+ }
+
iterator insert(BOOST_RV_REF(node_type) np)
{
- return table_.move_insert_node_type(np);
+ return table_.move_insert_node_type_equiv(np);
}
iterator insert(const_iterator hint, BOOST_RV_REF(node_type) np)
{
- return table_.move_insert_node_type_with_hint(hint, np);
+ return table_.move_insert_node_type_with_hint_equiv(hint, np);
}
-#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
+#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES) || \
+ (BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 6, 0))
private:
// Note: Use r-value node_type to insert.
iterator insert(node_type&);
@@ -1072,14 +1250,21 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
public:
#endif
+ iterator erase(iterator);
iterator erase(const_iterator);
size_type erase(const key_type&);
iterator erase(const_iterator, const_iterator);
+ BOOST_UNORDERED_DEPRECATED("Use erase instead")
void quick_erase(const_iterator it) { erase(it); }
+ BOOST_UNORDERED_DEPRECATED("Use erase instead")
void erase_return_void(const_iterator it) { erase(it); }
- void clear();
void swap(unordered_multimap&);
+ // C++17 support: BOOST_NOEXCEPT_IF(
+ // value_allocator_traits::is_always_equal::value &&
+ // is_nothrow_move_assignable_v<H> &&
+ // is_nothrow_move_assignable_v<P>)
+ void clear() BOOST_NOEXCEPT { table_.clear_impl(); }
template <typename H2, typename P2>
void merge(boost::unordered_multimap<K, T, H2, P2, A>& source);
@@ -1089,7 +1274,6 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
void merge(boost::unordered_multimap<K, T, H2, P2, A>&& source);
#endif
-#if BOOST_UNORDERED_INTEROPERABLE_NODES
template <typename H2, typename P2>
void merge(boost::unordered_map<K, T, H2, P2, A>& source);
@@ -1097,7 +1281,6 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
template <typename H2, typename P2>
void merge(boost::unordered_map<K, T, H2, P2, A>&& source);
#endif
-#endif
// observers
@@ -1170,9 +1353,8 @@ template <class K, class T, class H, class P, class A> class unordered_multimap
// hash policy
- float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
-
float load_factor() const BOOST_NOEXCEPT;
+ float max_load_factor() const BOOST_NOEXCEPT { return table_.mlf_; }
void max_load_factor(float) BOOST_NOEXCEPT;
void rehash(size_type);
void reserve(size_type);
@@ -1202,17 +1384,24 @@ unordered_map<K, T, H, P, A>::unordered_map(size_type n, const hasher& hf,
}
template <class K, class T, class H, class P, class A>
-unordered_map<K, T, H, P, A>::unordered_map(
- size_type n, const allocator_type& a)
- : table_(n, hasher(), key_equal(), a)
+template <class InputIt>
+unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l, size_type n,
+ const hasher& hf, const key_equal& eql, const allocator_type& a)
+ : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
{
+ this->insert(f, l);
}
template <class K, class T, class H, class P, class A>
-unordered_map<K, T, H, P, A>::unordered_map(
- size_type n, const hasher& hf, const allocator_type& a)
- : table_(n, hf, key_equal(), a)
+unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other)
+ : table_(other.table_,
+ unordered_map::value_allocator_traits::
+ select_on_container_copy_construction(other.get_allocator()))
{
+ if (other.table_.size_) {
+ table_.copy_buckets(
+ other.table_, boost::unordered::detail::true_type());
+ }
}
template <class K, class T, class H, class P, class A>
@@ -1227,44 +1416,52 @@ unordered_map<K, T, H, P, A>::unordered_map(
unordered_map const& other, allocator_type const& a)
: table_(other.table_, a)
{
+ if (other.table_.size_) {
+ table_.copy_buckets(
+ other.table_, boost::unordered::detail::true_type());
+ }
}
template <class K, class T, class H, class P, class A>
-template <class InputIt>
-unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l)
- : table_(boost::unordered::detail::initial_size(f, l), hasher(),
- key_equal(), allocator_type())
+unordered_map<K, T, H, P, A>::unordered_map(
+ BOOST_RV_REF(unordered_map) other, allocator_type const& a)
+ : table_(other.table_, a, boost::unordered::detail::move_tag())
{
- table_.insert_range(f, l);
+ if (table_.node_alloc() == other.table_.node_alloc()) {
+ table_.move_buckets_from(other.table_);
+ } else if (other.table_.size_) {
+ // TODO: Could pick new bucket size?
+ table_.move_buckets(other.table_);
+ }
}
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+
template <class K, class T, class H, class P, class A>
-template <class InputIt>
unordered_map<K, T, H, P, A>::unordered_map(
- InputIt f, InputIt l, size_type n, const hasher& hf, const key_equal& eql)
- : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql,
- allocator_type())
+ std::initializer_list<value_type> list, size_type n, const hasher& hf,
+ const key_equal& eql, const allocator_type& a)
+ : table_(
+ boost::unordered::detail::initial_size(list.begin(), list.end(), n),
+ hf, eql, a)
{
- table_.insert_range(f, l);
+ this->insert(list.begin(), list.end());
}
+#endif
+
template <class K, class T, class H, class P, class A>
-template <class InputIt>
-unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l, size_type n,
- const hasher& hf, const key_equal& eql, const allocator_type& a)
- : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
+unordered_map<K, T, H, P, A>::unordered_map(
+ size_type n, const allocator_type& a)
+ : table_(n, hasher(), key_equal(), a)
{
- table_.insert_range(f, l);
}
template <class K, class T, class H, class P, class A>
-template <class InputIt>
-unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l, size_type n,
- const hasher& hf, const allocator_type& a)
- : table_(
- boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
+unordered_map<K, T, H, P, A>::unordered_map(
+ size_type n, const hasher& hf, const allocator_type& a)
+ : table_(n, hf, key_equal(), a)
{
- table_.insert_range(f, l);
}
template <class K, class T, class H, class P, class A>
@@ -1274,38 +1471,30 @@ unordered_map<K, T, H, P, A>::unordered_map(
: table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
key_equal(), a)
{
- table_.insert_range(f, l);
-}
-
-template <class K, class T, class H, class P, class A>
-unordered_map<K, T, H, P, A>::~unordered_map() BOOST_NOEXCEPT
-{
+ this->insert(f, l);
}
template <class K, class T, class H, class P, class A>
-unordered_map<K, T, H, P, A>::unordered_map(unordered_map const& other)
- : table_(other.table_)
-{
-}
-
-template <class K, class T, class H, class P, class A>
-unordered_map<K, T, H, P, A>::unordered_map(
- BOOST_RV_REF(unordered_map) other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered::detail::move_tag())
+template <class InputIt>
+unordered_map<K, T, H, P, A>::unordered_map(InputIt f, InputIt l, size_type n,
+ const hasher& hf, const allocator_type& a)
+ : table_(
+ boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
{
+ this->insert(f, l);
}
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
template <class K, class T, class H, class P, class A>
unordered_map<K, T, H, P, A>::unordered_map(
- std::initializer_list<value_type> list, size_type n, const hasher& hf,
- const key_equal& eql, const allocator_type& a)
+ std::initializer_list<value_type> list, size_type n,
+ const allocator_type& a)
: table_(
boost::unordered::detail::initial_size(list.begin(), list.end(), n),
- hf, eql, a)
+ hasher(), key_equal(), a)
{
- table_.insert_range(list.begin(), list.end());
+ this->insert(list.begin(), list.end());
}
template <class K, class T, class H, class P, class A>
@@ -1316,26 +1505,24 @@ unordered_map<K, T, H, P, A>::unordered_map(
boost::unordered::detail::initial_size(list.begin(), list.end(), n),
hf, key_equal(), a)
{
- table_.insert_range(list.begin(), list.end());
+ this->insert(list.begin(), list.end());
}
+#endif
+
template <class K, class T, class H, class P, class A>
-unordered_map<K, T, H, P, A>::unordered_map(
- std::initializer_list<value_type> list, size_type n,
- const allocator_type& a)
- : table_(
- boost::unordered::detail::initial_size(list.begin(), list.end(), n),
- hasher(), key_equal(), a)
+unordered_map<K, T, H, P, A>::~unordered_map() BOOST_NOEXCEPT
{
- table_.insert_range(list.begin(), list.end());
}
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+
template <class K, class T, class H, class P, class A>
unordered_map<K, T, H, P, A>& unordered_map<K, T, H, P, A>::operator=(
std::initializer_list<value_type> list)
{
- table_.clear();
- table_.insert_range(list.begin(), list.end());
+ this->clear();
+ this->insert(list.begin(), list.end());
return *this;
}
@@ -1346,7 +1533,13 @@ unordered_map<K, T, H, P, A>& unordered_map<K, T, H, P, A>::operator=(
template <class K, class T, class H, class P, class A>
std::size_t unordered_map<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT
{
- return table_.max_size();
+ using namespace std;
+
+ // size <= mlf_ * count
+ return boost::unordered::detail::double_to_size(
+ ceil(static_cast<double>(table_.mlf_) *
+ static_cast<double>(table_.max_bucket_count()))) -
+ 1;
}
// modifiers
@@ -1355,7 +1548,10 @@ template <class K, class T, class H, class P, class A>
template <class InputIt>
void unordered_map<K, T, H, P, A>::insert(InputIt first, InputIt last)
{
- table_.insert_range(first, last);
+ if (first != last) {
+ table_.insert_range_unique(
+ table::extractor::extract(*first), first, last);
+ }
}
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
@@ -1363,39 +1559,56 @@ template <class K, class T, class H, class P, class A>
void unordered_map<K, T, H, P, A>::insert(
std::initializer_list<value_type> list)
{
- table_.insert_range(list.begin(), list.end());
+ this->insert(list.begin(), list.end());
}
#endif
template <class K, class T, class H, class P, class A>
typename unordered_map<K, T, H, P, A>::iterator
+unordered_map<K, T, H, P, A>::erase(iterator position)
+{
+ node_pointer node = table::get_node(position);
+ BOOST_ASSERT(node);
+ node_pointer next = table::next_node(node);
+ table_.erase_nodes_unique(node, next);
+ return iterator(next);
+}
+
+template <class K, class T, class H, class P, class A>
+typename unordered_map<K, T, H, P, A>::iterator
unordered_map<K, T, H, P, A>::erase(const_iterator position)
{
- return table_.erase(position);
+ node_pointer node = table::get_node(position);
+ BOOST_ASSERT(node);
+ node_pointer next = table::next_node(node);
+ table_.erase_nodes_unique(node, next);
+ return iterator(next);
}
template <class K, class T, class H, class P, class A>
typename unordered_map<K, T, H, P, A>::size_type
unordered_map<K, T, H, P, A>::erase(const key_type& k)
{
- return table_.erase_key(k);
+ return table_.erase_key_unique(k);
}
template <class K, class T, class H, class P, class A>
typename unordered_map<K, T, H, P, A>::iterator
unordered_map<K, T, H, P, A>::erase(const_iterator first, const_iterator last)
{
- return table_.erase_range(first, last);
-}
-
-template <class K, class T, class H, class P, class A>
-void unordered_map<K, T, H, P, A>::clear()
-{
- table_.clear();
+ node_pointer last_node = table::get_node(last);
+ if (first == last)
+ return iterator(last_node);
+ table_.erase_nodes_unique(table::get_node(first), last_node);
+ return iterator(last_node);
}
template <class K, class T, class H, class P, class A>
void unordered_map<K, T, H, P, A>::swap(unordered_map& other)
+// C++17 support: BOOST_NOEXCEPT_IF(
+// value_allocator_traits::is_always_equal::value &&
+// is_nothrow_move_assignable_v<H> &&
+// is_nothrow_move_assignable_v<P>)
{
table_.swap(other.table_);
}
@@ -1405,7 +1618,7 @@ template <typename H2, typename P2>
void unordered_map<K, T, H, P, A>::merge(
boost::unordered_map<K, T, H2, P2, A>& source)
{
- table_.merge_impl(source.table_);
+ table_.merge_unique(source.table_);
}
#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
@@ -1414,17 +1627,16 @@ template <typename H2, typename P2>
void unordered_map<K, T, H, P, A>::merge(
boost::unordered_map<K, T, H2, P2, A>&& source)
{
- table_.merge_impl(source.table_);
+ table_.merge_unique(source.table_);
}
#endif
-#if BOOST_UNORDERED_INTEROPERABLE_NODES
template <class K, class T, class H, class P, class A>
template <typename H2, typename P2>
void unordered_map<K, T, H, P, A>::merge(
boost::unordered_multimap<K, T, H2, P2, A>& source)
{
- table_.merge_impl(source.table_);
+ table_.merge_unique(source.table_);
}
#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
@@ -1433,10 +1645,9 @@ template <typename H2, typename P2>
void unordered_map<K, T, H, P, A>::merge(
boost::unordered_multimap<K, T, H2, P2, A>&& source)
{
- table_.merge_impl(source.table_);
+ table_.merge_unique(source.table_);
}
#endif
-#endif
// observers
@@ -1454,27 +1665,6 @@ unordered_map<K, T, H, P, A>::key_eq() const
return table_.key_eq();
}
-template <class K, class T, class H, class P, class A>
-typename unordered_map<K, T, H, P, A>::mapped_type&
- unordered_map<K, T, H, P, A>::operator[](const key_type& k)
-{
- return table_.try_emplace_impl(k).first->second;
-}
-
-template <class K, class T, class H, class P, class A>
-typename unordered_map<K, T, H, P, A>::mapped_type&
-unordered_map<K, T, H, P, A>::at(const key_type& k)
-{
- return table_.at(k).second;
-}
-
-template <class K, class T, class H, class P, class A>
-typename unordered_map<K, T, H, P, A>::mapped_type const&
-unordered_map<K, T, H, P, A>::at(const key_type& k) const
-{
- return table_.at(k).second;
-}
-
// lookup
template <class K, class T, class H, class P, class A>
@@ -1497,7 +1687,8 @@ typename unordered_map<K, T, H, P, A>::iterator
unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
CompatibleHash const& hash, CompatiblePredicate const& eq)
{
- return iterator(table_.generic_find_node(k, hash, eq));
+ return iterator(
+ table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
}
template <class K, class T, class H, class P, class A>
@@ -1506,14 +1697,15 @@ typename unordered_map<K, T, H, P, A>::const_iterator
unordered_map<K, T, H, P, A>::find(CompatibleKey const& k,
CompatibleHash const& hash, CompatiblePredicate const& eq) const
{
- return const_iterator(table_.generic_find_node(k, hash, eq));
+ return const_iterator(
+ table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
}
template <class K, class T, class H, class P, class A>
typename unordered_map<K, T, H, P, A>::size_type
unordered_map<K, T, H, P, A>::count(const key_type& k) const
{
- return table_.count(k);
+ return table_.find_node(k) ? 1 : 0;
}
template <class K, class T, class H, class P, class A>
@@ -1521,7 +1713,8 @@ std::pair<typename unordered_map<K, T, H, P, A>::iterator,
typename unordered_map<K, T, H, P, A>::iterator>
unordered_map<K, T, H, P, A>::equal_range(const key_type& k)
{
- return table_.equal_range(k);
+ node_pointer n = table_.find_node(k);
+ return std::make_pair(iterator(n), iterator(n ? table::next_node(n) : n));
}
template <class K, class T, class H, class P, class A>
@@ -1529,7 +1722,51 @@ std::pair<typename unordered_map<K, T, H, P, A>::const_iterator,
typename unordered_map<K, T, H, P, A>::const_iterator>
unordered_map<K, T, H, P, A>::equal_range(const key_type& k) const
{
- return table_.equal_range(k);
+ node_pointer n = table_.find_node(k);
+ return std::make_pair(
+ const_iterator(n), const_iterator(n ? table::next_node(n) : n));
+}
+
+template <class K, class T, class H, class P, class A>
+typename unordered_map<K, T, H, P, A>::mapped_type&
+ unordered_map<K, T, H, P, A>::operator[](const key_type& k)
+{
+ return table_.try_emplace_unique(k).first->second;
+}
+
+template <class K, class T, class H, class P, class A>
+typename unordered_map<K, T, H, P, A>::mapped_type&
+ unordered_map<K, T, H, P, A>::operator[](BOOST_RV_REF(key_type) k)
+{
+ return table_.try_emplace_unique(boost::move(k)).first->second;
+}
+
+template <class K, class T, class H, class P, class A>
+typename unordered_map<K, T, H, P, A>::mapped_type&
+unordered_map<K, T, H, P, A>::at(const key_type& k)
+{
+ if (table_.size_) {
+ node_pointer n = table_.find_node(k);
+ if (n)
+ return n->value().second;
+ }
+
+ boost::throw_exception(
+ std::out_of_range("Unable to find key in unordered_map."));
+}
+
+template <class K, class T, class H, class P, class A>
+typename unordered_map<K, T, H, P, A>::mapped_type const&
+unordered_map<K, T, H, P, A>::at(const key_type& k) const
+{
+ if (table_.size_) {
+ node_pointer n = table_.find_node(k);
+ if (n)
+ return n->value().second;
+ }
+
+ boost::throw_exception(
+ std::out_of_range("Unable to find key in unordered_map."));
}
template <class K, class T, class H, class P, class A>
@@ -1544,7 +1781,9 @@ unordered_map<K, T, H, P, A>::bucket_size(size_type n) const
template <class K, class T, class H, class P, class A>
float unordered_map<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
{
- return table_.load_factor();
+ BOOST_ASSERT(table_.bucket_count_ != 0);
+ return static_cast<float>(table_.size_) /
+ static_cast<float>(table_.bucket_count_);
}
template <class K, class T, class H, class P, class A>
@@ -1562,7 +1801,8 @@ void unordered_map<K, T, H, P, A>::rehash(size_type n)
template <class K, class T, class H, class P, class A>
void unordered_map<K, T, H, P, A>::reserve(size_type n)
{
- table_.reserve(n);
+ table_.rehash(static_cast<std::size_t>(
+ std::ceil(static_cast<double>(n) / table_.mlf_)));
}
template <class K, class T, class H, class P, class A>
@@ -1575,7 +1815,7 @@ inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
unordered_map<K, T, H, P, A> x;
};
#endif
- return m1.table_.equals(m2.table_);
+ return m1.table_.equals_unique(m2.table_);
}
template <class K, class T, class H, class P, class A>
@@ -1588,12 +1828,13 @@ inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
unordered_map<K, T, H, P, A> x;
};
#endif
- return !m1.table_.equals(m2.table_);
+ return !m1.table_.equals_unique(m2.table_);
}
template <class K, class T, class H, class P, class A>
inline void swap(
unordered_map<K, T, H, P, A>& m1, unordered_map<K, T, H, P, A>& m2)
+ BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2)))
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy
@@ -1621,17 +1862,26 @@ unordered_multimap<K, T, H, P, A>::unordered_multimap(size_type n,
}
template <class K, class T, class H, class P, class A>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(
- size_type n, const allocator_type& a)
- : table_(n, hasher(), key_equal(), a)
+template <class InputIt>
+unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
+ size_type n, const hasher& hf, const key_equal& eql,
+ const allocator_type& a)
+ : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
{
+ this->insert(f, l);
}
template <class K, class T, class H, class P, class A>
unordered_multimap<K, T, H, P, A>::unordered_multimap(
- size_type n, const hasher& hf, const allocator_type& a)
- : table_(n, hf, key_equal(), a)
+ unordered_multimap const& other)
+ : table_(other.table_,
+ unordered_multimap::value_allocator_traits::
+ select_on_container_copy_construction(other.get_allocator()))
{
+ if (other.table_.size_) {
+ table_.copy_buckets(
+ other.table_, boost::unordered::detail::false_type());
+ }
}
template <class K, class T, class H, class P, class A>
@@ -1646,45 +1896,52 @@ unordered_multimap<K, T, H, P, A>::unordered_multimap(
unordered_multimap const& other, allocator_type const& a)
: table_(other.table_, a)
{
+ if (other.table_.size_) {
+ table_.copy_buckets(
+ other.table_, boost::unordered::detail::false_type());
+ }
}
template <class K, class T, class H, class P, class A>
-template <class InputIt>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l)
- : table_(boost::unordered::detail::initial_size(f, l), hasher(),
- key_equal(), allocator_type())
+unordered_multimap<K, T, H, P, A>::unordered_multimap(
+ BOOST_RV_REF(unordered_multimap) other, allocator_type const& a)
+ : table_(other.table_, a, boost::unordered::detail::move_tag())
{
- table_.insert_range(f, l);
+ if (table_.node_alloc() == other.table_.node_alloc()) {
+ table_.move_buckets_from(other.table_);
+ } else if (other.table_.size_) {
+ // TODO: Could pick new bucket size?
+ table_.move_buckets_equiv(other.table_);
+ }
}
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+
template <class K, class T, class H, class P, class A>
-template <class InputIt>
unordered_multimap<K, T, H, P, A>::unordered_multimap(
- InputIt f, InputIt l, size_type n, const hasher& hf, const key_equal& eql)
- : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql,
- allocator_type())
+ std::initializer_list<value_type> list, size_type n, const hasher& hf,
+ const key_equal& eql, const allocator_type& a)
+ : table_(
+ boost::unordered::detail::initial_size(list.begin(), list.end(), n),
+ hf, eql, a)
{
- table_.insert_range(f, l);
+ this->insert(list.begin(), list.end());
}
+#endif
+
template <class K, class T, class H, class P, class A>
-template <class InputIt>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
- size_type n, const hasher& hf, const key_equal& eql,
- const allocator_type& a)
- : table_(boost::unordered::detail::initial_size(f, l, n), hf, eql, a)
+unordered_multimap<K, T, H, P, A>::unordered_multimap(
+ size_type n, const allocator_type& a)
+ : table_(n, hasher(), key_equal(), a)
{
- table_.insert_range(f, l);
}
template <class K, class T, class H, class P, class A>
-template <class InputIt>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
+unordered_multimap<K, T, H, P, A>::unordered_multimap(
size_type n, const hasher& hf, const allocator_type& a)
- : table_(
- boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
+ : table_(n, hf, key_equal(), a)
{
- table_.insert_range(f, l);
}
template <class K, class T, class H, class P, class A>
@@ -1694,39 +1951,30 @@ unordered_multimap<K, T, H, P, A>::unordered_multimap(
: table_(boost::unordered::detail::initial_size(f, l, n), hasher(),
key_equal(), a)
{
- table_.insert_range(f, l);
+ this->insert(f, l);
}
template <class K, class T, class H, class P, class A>
-unordered_multimap<K, T, H, P, A>::~unordered_multimap() BOOST_NOEXCEPT
-{
-}
-
-template <class K, class T, class H, class P, class A>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(
- unordered_multimap const& other)
- : table_(other.table_)
-{
-}
-
-template <class K, class T, class H, class P, class A>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(
- BOOST_RV_REF(unordered_multimap) other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered::detail::move_tag())
+template <class InputIt>
+unordered_multimap<K, T, H, P, A>::unordered_multimap(InputIt f, InputIt l,
+ size_type n, const hasher& hf, const allocator_type& a)
+ : table_(
+ boost::unordered::detail::initial_size(f, l, n), hf, key_equal(), a)
{
+ this->insert(f, l);
}
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
template <class K, class T, class H, class P, class A>
unordered_multimap<K, T, H, P, A>::unordered_multimap(
- std::initializer_list<value_type> list, size_type n, const hasher& hf,
- const key_equal& eql, const allocator_type& a)
+ std::initializer_list<value_type> list, size_type n,
+ const allocator_type& a)
: table_(
boost::unordered::detail::initial_size(list.begin(), list.end(), n),
- hf, eql, a)
+ hasher(), key_equal(), a)
{
- table_.insert_range(list.begin(), list.end());
+ this->insert(list.begin(), list.end());
}
template <class K, class T, class H, class P, class A>
@@ -1737,26 +1985,24 @@ unordered_multimap<K, T, H, P, A>::unordered_multimap(
boost::unordered::detail::initial_size(list.begin(), list.end(), n),
hf, key_equal(), a)
{
- table_.insert_range(list.begin(), list.end());
+ this->insert(list.begin(), list.end());
}
+#endif
+
template <class K, class T, class H, class P, class A>
-unordered_multimap<K, T, H, P, A>::unordered_multimap(
- std::initializer_list<value_type> list, size_type n,
- const allocator_type& a)
- : table_(
- boost::unordered::detail::initial_size(list.begin(), list.end(), n),
- hasher(), key_equal(), a)
+unordered_multimap<K, T, H, P, A>::~unordered_multimap() BOOST_NOEXCEPT
{
- table_.insert_range(list.begin(), list.end());
}
+#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
+
template <class K, class T, class H, class P, class A>
unordered_multimap<K, T, H, P, A>& unordered_multimap<K, T, H, P, A>::operator=(
std::initializer_list<value_type> list)
{
- table_.clear();
- table_.insert_range(list.begin(), list.end());
+ this->clear();
+ this->insert(list.begin(), list.end());
return *this;
}
@@ -1767,7 +2013,13 @@ unordered_multimap<K, T, H, P, A>& unordered_multimap<K, T, H, P, A>::operator=(
template <class K, class T, class H, class P, class A>
std::size_t unordered_multimap<K, T, H, P, A>::max_size() const BOOST_NOEXCEPT
{
- return table_.max_size();
+ using namespace std;
+
+ // size <= mlf_ * count
+ return boost::unordered::detail::double_to_size(
+ ceil(static_cast<double>(table_.mlf_) *
+ static_cast<double>(table_.max_bucket_count()))) -
+ 1;
}
// modifiers
@@ -1776,7 +2028,7 @@ template <class K, class T, class H, class P, class A>
template <class InputIt>
void unordered_multimap<K, T, H, P, A>::insert(InputIt first, InputIt last)
{
- table_.insert_range(first, last);
+ table_.insert_range_equiv(first, last);
}
#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
@@ -1784,22 +2036,37 @@ template <class K, class T, class H, class P, class A>
void unordered_multimap<K, T, H, P, A>::insert(
std::initializer_list<value_type> list)
{
- table_.insert_range(list.begin(), list.end());
+ this->insert(list.begin(), list.end());
}
#endif
template <class K, class T, class H, class P, class A>
typename unordered_multimap<K, T, H, P, A>::iterator
+unordered_multimap<K, T, H, P, A>::erase(iterator position)
+{
+ node_pointer node = table::get_node(position);
+ BOOST_ASSERT(node);
+ node_pointer next = table::next_node(node);
+ table_.erase_nodes_equiv(node, next);
+ return iterator(next);
+}
+
+template <class K, class T, class H, class P, class A>
+typename unordered_multimap<K, T, H, P, A>::iterator
unordered_multimap<K, T, H, P, A>::erase(const_iterator position)
{
- return table_.erase(position);
+ node_pointer node = table::get_node(position);
+ BOOST_ASSERT(node);
+ node_pointer next = table::next_node(node);
+ table_.erase_nodes_equiv(node, next);
+ return iterator(next);
}
template <class K, class T, class H, class P, class A>
typename unordered_multimap<K, T, H, P, A>::size_type
unordered_multimap<K, T, H, P, A>::erase(const key_type& k)
{
- return table_.erase_key(k);
+ return table_.erase_key_equiv(k);
}
template <class K, class T, class H, class P, class A>
@@ -1807,17 +2074,19 @@ typename unordered_multimap<K, T, H, P, A>::iterator
unordered_multimap<K, T, H, P, A>::erase(
const_iterator first, const_iterator last)
{
- return table_.erase_range(first, last);
-}
-
-template <class K, class T, class H, class P, class A>
-void unordered_multimap<K, T, H, P, A>::clear()
-{
- table_.clear();
+ node_pointer last_node = table::get_node(last);
+ if (first == last)
+ return iterator(last_node);
+ table_.erase_nodes_equiv(table::get_node(first), last_node);
+ return iterator(last_node);
}
template <class K, class T, class H, class P, class A>
void unordered_multimap<K, T, H, P, A>::swap(unordered_multimap& other)
+// C++17 support: BOOST_NOEXCEPT_IF(
+// value_allocator_traits::is_always_equal::value &&
+// is_nothrow_move_assignable_v<H> &&
+// is_nothrow_move_assignable_v<P>)
{
table_.swap(other.table_);
}
@@ -1860,7 +2129,6 @@ void unordered_multimap<K, T, H, P, A>::merge(
}
#endif
-#if BOOST_UNORDERED_INTEROPERABLE_NODES
template <class K, class T, class H, class P, class A>
template <typename H2, typename P2>
void unordered_multimap<K, T, H, P, A>::merge(
@@ -1882,7 +2150,6 @@ void unordered_multimap<K, T, H, P, A>::merge(
}
}
#endif
-#endif
// lookup
@@ -1906,7 +2173,8 @@ typename unordered_multimap<K, T, H, P, A>::iterator
unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
CompatibleHash const& hash, CompatiblePredicate const& eq)
{
- return iterator(table_.generic_find_node(k, hash, eq));
+ return iterator(
+ table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
}
template <class K, class T, class H, class P, class A>
@@ -1915,14 +2183,16 @@ typename unordered_multimap<K, T, H, P, A>::const_iterator
unordered_multimap<K, T, H, P, A>::find(CompatibleKey const& k,
CompatibleHash const& hash, CompatiblePredicate const& eq) const
{
- return const_iterator(table_.generic_find_node(k, hash, eq));
+ return const_iterator(
+ table_.find_node_impl(table::policy::apply_hash(hash, k), k, eq));
}
template <class K, class T, class H, class P, class A>
typename unordered_multimap<K, T, H, P, A>::size_type
unordered_multimap<K, T, H, P, A>::count(const key_type& k) const
{
- return table_.count(k);
+ node_pointer n = table_.find_node(k);
+ return n ? table_.group_count(n) : 0;
}
template <class K, class T, class H, class P, class A>
@@ -1930,7 +2200,8 @@ std::pair<typename unordered_multimap<K, T, H, P, A>::iterator,
typename unordered_multimap<K, T, H, P, A>::iterator>
unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k)
{
- return table_.equal_range(k);
+ node_pointer n = table_.find_node(k);
+ return std::make_pair(iterator(n), iterator(n ? table_.next_group(n) : n));
}
template <class K, class T, class H, class P, class A>
@@ -1938,7 +2209,9 @@ std::pair<typename unordered_multimap<K, T, H, P, A>::const_iterator,
typename unordered_multimap<K, T, H, P, A>::const_iterator>
unordered_multimap<K, T, H, P, A>::equal_range(const key_type& k) const
{
- return table_.equal_range(k);
+ node_pointer n = table_.find_node(k);
+ return std::make_pair(
+ const_iterator(n), const_iterator(n ? table_.next_group(n) : n));
}
template <class K, class T, class H, class P, class A>
@@ -1953,7 +2226,9 @@ unordered_multimap<K, T, H, P, A>::bucket_size(size_type n) const
template <class K, class T, class H, class P, class A>
float unordered_multimap<K, T, H, P, A>::load_factor() const BOOST_NOEXCEPT
{
- return table_.load_factor();
+ BOOST_ASSERT(table_.bucket_count_ != 0);
+ return static_cast<float>(table_.size_) /
+ static_cast<float>(table_.bucket_count_);
}
template <class K, class T, class H, class P, class A>
@@ -1971,7 +2246,8 @@ void unordered_multimap<K, T, H, P, A>::rehash(size_type n)
template <class K, class T, class H, class P, class A>
void unordered_multimap<K, T, H, P, A>::reserve(size_type n)
{
- table_.reserve(n);
+ table_.rehash(static_cast<std::size_t>(
+ std::ceil(static_cast<double>(n) / table_.mlf_)));
}
template <class K, class T, class H, class P, class A>
@@ -1984,7 +2260,7 @@ inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
unordered_multimap<K, T, H, P, A> x;
};
#endif
- return m1.table_.equals(m2.table_);
+ return m1.table_.equals_equiv(m2.table_);
}
template <class K, class T, class H, class P, class A>
@@ -1997,12 +2273,13 @@ inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
unordered_multimap<K, T, H, P, A> x;
};
#endif
- return !m1.table_.equals(m2.table_);
+ return !m1.table_.equals_equiv(m2.table_);
}
template <class K, class T, class H, class P, class A>
inline void swap(unordered_multimap<K, T, H, P, A>& m1,
unordered_multimap<K, T, H, P, A>& m2)
+ BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT_EXPR(m1.swap(m2)))
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy
@@ -2017,10 +2294,11 @@ template <typename N, class K, class T, class A> class node_handle_map
{
BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle_map)
- template <typename Types>
- friend struct ::boost::unordered::detail::table_impl;
- template <typename Types>
- friend struct ::boost::unordered::detail::grouped_table_impl;
+ template <typename Types> friend struct ::boost::unordered::detail::table;
+ template <class K2, class T2, class H2, class P2, class A2>
+ friend class boost::unordered::unordered_map;
+ template <class K2, class T2, class H2, class P2, class A2>
+ friend class boost::unordered::unordered_multimap;
typedef typename boost::unordered::detail::rebind_wrap<A,
std::pair<K const, T> >::type value_allocator;
@@ -2043,13 +2321,7 @@ template <typename N, class K, class T, class A> class node_handle_map
bool has_alloc_;
boost::unordered::detail::value_base<value_allocator> alloc_;
- public:
- BOOST_CONSTEXPR node_handle_map() BOOST_NOEXCEPT : ptr_(), has_alloc_(false)
- {
- }
-
- /*BOOST_CONSTEXPR */ node_handle_map(
- node_pointer ptr, allocator_type const& a)
+ node_handle_map(node_pointer ptr, allocator_type const& a)
: ptr_(ptr), has_alloc_(false)
{
if (ptr_) {
@@ -2058,6 +2330,11 @@ template <typename N, class K, class T, class A> class node_handle_map
}
}
+ public:
+ BOOST_CONSTEXPR node_handle_map() BOOST_NOEXCEPT : ptr_(), has_alloc_(false)
+ {
+ }
+
~node_handle_map()
{
if (has_alloc_ && ptr_) {