|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r71327 - in trunk: boost/unordered boost/unordered/detail libs/unordered/test/helpers
From: dnljms_at_[hidden]
Date: 2011-04-16 14:47:35
Author: danieljames
Date: 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
New Revision: 71327
URL: http://svn.boost.org/trac/boost/changeset/71327
Log:
Unordered: Overhaul the implementation.
Store nodes in a single linked list, with hash values so that their
buckets can be found when needed. Iterators now only have to store a
pointer to the node and don't have to iterate over empty buckets to
reach the next node. This allows the container to meet the iterator
requirements - fixing the speed issues with `equal_range` and `erase`.
Also, define iterators in their own namespace, so that they don't
accidentally pull in detail functions via ADL.
I've simplified the code slightly by removing some of the special
cases for empty containers. Renamed a few things as well and other
minor changes that were made as I went along.
Removed:
trunk/boost/unordered/detail/fwd.hpp
Text files modified:
trunk/boost/unordered/detail/allocator_helpers.hpp | 4
trunk/boost/unordered/detail/buckets.hpp | 740 ++++++++++++++---
trunk/boost/unordered/detail/equivalent.hpp | 393 ++++-----
trunk/boost/unordered/detail/extract_key.hpp | 11
trunk/boost/unordered/detail/move.hpp | 38
trunk/boost/unordered/detail/node.hpp | 462 +++++++---
trunk/boost/unordered/detail/table.hpp | 1363 +++++++++++++++++---------------
trunk/boost/unordered/detail/unique.hpp | 696 ++++++---------
trunk/boost/unordered/detail/util.hpp | 284 ++----
trunk/boost/unordered/unordered_map.hpp | 1666 +++++++++++++++++++++++++--------------
trunk/boost/unordered/unordered_set.hpp | 1493 ++++++++++++++++++++++------------
trunk/libs/unordered/test/helpers/invariants.hpp | 49
trunk/libs/unordered/test/helpers/memory.hpp | 2
13 files changed, 4239 insertions(+), 2962 deletions(-)
Modified: trunk/boost/unordered/detail/allocator_helpers.hpp
==============================================================================
--- trunk/boost/unordered/detail/allocator_helpers.hpp (original)
+++ trunk/boost/unordered/detail/allocator_helpers.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -23,7 +23,7 @@
# include <boost/detail/allocator_utilities.hpp>
#endif
-namespace boost { namespace unordered_detail {
+namespace boost { namespace unordered { namespace detail {
// rebind_wrap
//
@@ -102,7 +102,7 @@
allocator_array_constructor& operator=(
allocator_array_constructor const&);
};
-}}
+}}}
#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES)
# undef BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES
Modified: trunk/boost/unordered/detail/buckets.hpp
==============================================================================
--- trunk/boost/unordered/detail/buckets.hpp (original)
+++ trunk/boost/unordered/detail/buckets.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -7,177 +7,665 @@
#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED
-#include <boost/config.hpp>
-#include <boost/assert.hpp>
#include <boost/unordered/detail/node.hpp>
-#include <boost/unordered/detail/util.hpp>
-namespace boost { namespace unordered_detail {
+namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////////
- // Buckets
+ //
+ // Now the main data structure:
+ //
+ // buckets<A, Unique> buffered_functions<H, P>
+ // | |
+ // +---------------+--------------+
+ // |
+ // table<T>
+ //
+ // T is a class which contains typedefs for all the types we need.
- template <class A, class G>
- inline std::size_t hash_buckets<A, G>::max_bucket_count() const {
- // -1 to account for the sentinel.
- return prev_prime(this->bucket_alloc().max_size() - 1);
- }
+ // buckets
+ //
+ // This is responsible for allocating and deallocating buckets and nodes.
+ //
+ // Notes:
+ // 1. For the sake exception safety the consturctors don't allocate
+ // anything.
+ // 2. It's the callers responsibility to allocate the buckets before calling
+ // any of the methods (other than getters and setters).
+
+ template <class A, bool Unique>
+ class buckets
+ {
+ buckets(buckets const&);
+ buckets& operator=(buckets const&);
+ public:
+ // Types
+
+ typedef BOOST_DEDUCED_TYPENAME ::boost::detail::if_true<Unique>::
+ BOOST_NESTED_TEMPLATE then<
+ ::boost::unordered::detail::ungrouped_node<A>,
+ ::boost::unordered::detail::grouped_node<A>
+ >::type node;
+
+ typedef A value_allocator;
+ typedef ::boost::unordered::detail::bucket<A> bucket;
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+
+ typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator
+ bucket_allocator;
+ typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
+
+ typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type
+ node_allocator;
+ typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;
+
+ // Members
+
+ bucket_ptr buckets_;
+ std::size_t bucket_count_;
+ ::boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
+
+ // Data access
+
+ bucket_allocator const& bucket_alloc() const
+ {
+ return allocators_.first();
+ }
- template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
- hash_buckets<A, G>::get_bucket(std::size_t num) const
- {
- return buckets_ + static_cast<std::ptrdiff_t>(num);
- }
+ node_allocator const& node_alloc() const
+ {
+ return allocators_.second();
+ }
- template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr
- hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const
- {
- return get_bucket(hashed % bucket_count_);
- }
+ bucket_allocator& bucket_alloc()
+ {
+ return allocators_.first();
+ }
+
+ node_allocator& node_alloc()
+ {
+ return allocators_.second();
+ }
+
+ std::size_t max_bucket_count() const
+ {
+ // -1 to account for the start bucket.
+ return prev_prime(this->bucket_alloc().max_size() - 1);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Constructors and Destructors
+
+ buckets(node_allocator const& a, std::size_t bucket_count)
+ : buckets_(),
+ bucket_count_(bucket_count),
+ allocators_(a,a)
+ {
+ }
- template <class A, class G>
- std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const
- {
- if(!buckets_) return 0;
- bucket_ptr ptr = get_bucket(index)->next_;
- std::size_t count = 0;
- while(ptr) {
- ++count;
+ inline ~buckets()
+ {
+ if(this->buckets_) { this->delete_buckets(); }
+ }
+
+ void create_buckets()
+ {
+ // The array constructor will clean up in the event of an
+ // exception.
+ allocator_array_constructor<bucket_allocator>
+ constructor(bucket_alloc());
+
+ // Creates an extra bucket to act as the start node.
+ constructor.construct(bucket(), this->bucket_count_ + 1);
+
+ // Only release the buckets once everything is successfully
+ // done.
+ this->buckets_ = constructor.release();
+ }
+
+ // no throw
+ void swap(buckets& other)
+ {
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ std::swap(buckets_, other.buckets_);
+ std::swap(bucket_count_, other.bucket_count_);
+ }
+
+ void move(buckets& other)
+ {
+ BOOST_ASSERT(node_alloc() == other.node_alloc());
+ if(this->buckets_) { this->delete_buckets(); }
+ this->buckets_ = other.buckets_;
+ this->bucket_count_ = other.bucket_count_;
+ other.buckets_ = bucket_ptr();
+ other.bucket_count_ = 0;
+ }
+
+ std::size_t bucket_size(std::size_t index) const
+ {
+ if (!this->buckets_) return 0;
+ node_ptr ptr = this->buckets_[index].next_;
+ if (!ptr) return 0;
ptr = ptr->next_;
+
+ std::size_t count = 0;
+ while(BOOST_UNORDERED_BORLAND_BOOL(ptr) &&
+ node::get_hash(ptr) % this->bucket_count_ == index)
+ {
+ ++count;
+ ptr = ptr->next_;
+ }
+
+ return count;
}
- return count;
- }
- template <class A, class G>
- inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr
- hash_buckets<A, G>::bucket_begin(std::size_t num) const
- {
- return buckets_ ? get_bucket(num)->next_ : node_ptr();
- }
+ node_ptr bucket_begin(std::size_t bucket_index) const
+ {
+ if (!this->buckets_) return node_ptr();
+ bucket& b = this->buckets_[bucket_index];
+ if (!b.next_) return node_ptr();
+ return b.next_->next_;
+ }
- ////////////////////////////////////////////////////////////////////////////
- // Delete
+ // For the remaining functions, buckets_ must not be null.
+
+ bucket_ptr get_bucket(std::size_t bucket_index) const
+ {
+ return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
+ }
- template <class A, class G>
- inline void hash_buckets<A, G>::delete_node(node_ptr b)
- {
- node* raw_ptr = static_cast<node*>(&*b);
- boost::unordered_detail::destroy(raw_ptr->value_ptr());
- real_node_ptr n(node_alloc().address(*raw_ptr));
- node_alloc().destroy(n);
- node_alloc().deallocate(n, 1);
- }
+ ////////////////////////////////////////////////////////////////////////
+ // Delete
+
+ void delete_node(node_ptr n)
+ {
+ node* raw_ptr = static_cast<node*>(&*n);
+ real_node_ptr real_ptr(node_alloc().address(*raw_ptr));
+
+ ::boost::unordered::detail::destroy(raw_ptr->value_ptr());
+ node_alloc().destroy(real_ptr);
+ node_alloc().deallocate(real_ptr, 1);
+ }
- template <class A, class G>
- inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b)
- {
- node_ptr node_it = b->next_;
- b->next_ = node_ptr();
+ void delete_buckets()
+ {
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+
+ node_ptr n = (end)->next_;
+ while(BOOST_UNORDERED_BORLAND_BOOL(n))
+ {
+ node_ptr node_to_delete = n;
+ n = n->next_;
+ delete_node(node_to_delete);
+ }
+
+ ++end;
+ for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
+ bucket_alloc().destroy(begin);
+ }
+
+ bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1);
+
+ this->buckets_ = bucket_ptr();
+ }
- while(node_it) {
- node_ptr node_to_delete = node_it;
- node_it = node_it->next_;
- delete_node(node_to_delete);
+ std::size_t delete_nodes(node_ptr begin, node_ptr end)
+ {
+ std::size_t count = 0;
+ while(begin != end) {
+ node_ptr n = begin;
+ begin = begin->next_;
+ delete_node(n);
+ ++count;
+ }
+ return count;
}
- }
- template <class A, class G>
- inline void hash_buckets<A, G>::delete_buckets()
- {
- bucket_ptr end = this->get_bucket(this->bucket_count_);
+ // This is called after erasing a node or group of nodes to fix up
+ // the bucket pointers.
+ void fix_buckets(bucket_ptr bucket, node_ptr prev, node_ptr next)
+ {
+ if (!next)
+ {
+ if (bucket->next_ == prev) bucket->next_ = node_ptr();
+ }
+ else
+ {
+ bucket_ptr next_bucket = this->get_bucket(
+ node::get_hash(next) % this->bucket_count_);
+ if (next_bucket != bucket)
+ {
+ next_bucket->next_ = prev;
+ if (bucket->next_ == prev) bucket->next_ = node_ptr();
+ }
+ }
+ }
- for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
- clear_bucket(begin);
+ // This is called after erasing a range of nodes to fix any bucket
+ // pointers into that range.
+ void fix_buckets_range(
+ std::size_t bucket_index, node_ptr prev, node_ptr begin, node_ptr end)
+ {
+ node_ptr n = begin;
+
+ // If we're not at the start of the current bucket, then
+ // go to the start of the next bucket.
+ if (this->get_bucket(bucket_index)->next_ != prev)
+ {
+ for(;;) {
+ n = n->next_;
+ if (n == end) return;
+
+ std::size_t new_bucket_index =
+ node::get_hash(n) % this->bucket_count_;
+ if (bucket_index != new_bucket_index) {
+ bucket_index = new_bucket_index;
+ break;
+ }
+ }
+ }
+
+ // Iterate through the remaining nodes, clearing out the bucket
+ // pointers.
+ this->buckets_[bucket_index].next_ = bucket_ptr();
+ for(;;) {
+ n = n->next_;
+ if (n == end) break;
+
+ std::size_t new_bucket_index =
+ node::get_hash(n) % this->bucket_count_;
+ if (bucket_index != new_bucket_index) {
+ bucket_index = new_bucket_index;
+ this->buckets_[bucket_index].next_ = bucket_ptr();
+ }
+ };
+
+ // Finally fix the bucket containing the trailing node.
+ if (BOOST_UNORDERED_BORLAND_BOOL(n)) {
+ this->buckets_[node::get_hash(n) % this->bucket_count_].next_
+ = prev;
+ }
+ }
+
+ // Iterate through the nodes placing them in the correct buckets.
+ // pre: prev->next_ is not null.
+ node_ptr place_in_bucket(node_ptr prev, node_ptr end) {
+ bucket_ptr b = this->get_bucket(node::get_hash(prev->next_) % this->bucket_count_);
+
+ if (!b->next_) {
+ b->next_ = prev;
+ return end;
+ }
+ else {
+ node_ptr next = end->next_;
+ end->next_ = b->next_->next_;
+ b->next_->next_ = prev->next_;
+ prev->next_ = next;
+ return prev;
+ }
+ }
+
+ void copy_buckets_to(buckets&) const;
+ };
+
+ // Assigning and swapping the equality and hash function objects
+ // needs strong exception safety. To implement that normally we'd
+ // require one of them to be known to not throw and the other to
+ // guarantee strong exception safety. Unfortunately they both only
+ // have basic exception safety. So to acheive strong exception
+ // safety we have storage space for two copies, and assign the new
+ // copies to the unused space. Then switch to using that to use
+ // them. This is implemented in 'set_hash_functions' which
+ // atomically assigns the new function objects in a strongly
+ // exception safe manner.
+
+ template <class H, class P> class set_hash_functions;
+
+ template <class H, class P>
+ class buffered_functions
+ {
+ friend class set_hash_functions<H, P>;
+ buffered_functions& operator=(buffered_functions const&);
+
+ typedef ::boost::compressed_pair<H, P> function_pair;
+ typedef BOOST_DEDUCED_TYPENAME ::boost::aligned_storage<
+ sizeof(function_pair),
+ ::boost::alignment_of<function_pair>::value>::type aligned_function;
+
+ bool current_; // The currently active functions.
+ aligned_function funcs_[2];
+
+ function_pair const& current() const {
+ return *static_cast<function_pair const*>(
+ static_cast<void const*>(&funcs_[current_]));
}
- // Destroy the buckets (including the sentinel bucket).
- ++end;
- for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
- bucket_alloc().destroy(begin);
+ void construct(bool which, H const& hf, P const& eq)
+ {
+ new((void*) &funcs_[which]) function_pair(hf, eq);
}
- bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1);
+ void construct(bool which, function_pair const& f)
+ {
+ new((void*) &funcs_[which]) function_pair(f);
+ }
+
+ void destroy(bool which)
+ {
+ ::boost::unordered::detail::destroy((function_pair*)(&funcs_[which]));
+ }
+
+ public:
- this->buckets_ = bucket_ptr();
- }
+ buffered_functions(H const& hf, P const& eq)
+ : current_(false)
+ {
+ construct(current_, hf, eq);
+ }
+
+ buffered_functions(buffered_functions const& bf)
+ : current_(false)
+ {
+ construct(current_, bf.current());
+ }
+
+ ~buffered_functions() {
+ destroy(current_);
+ }
+
+ H const& hash_function() const {
+ return current().first();
+ }
- template <class A, class G>
- inline std::size_t hash_buckets<A, G>::delete_nodes(
- node_ptr begin, node_ptr end)
+ P const& key_eq() const {
+ return current().second();
+ }
+ };
+
+ template <class H, class P>
+ class set_hash_functions
{
- std::size_t count = 0;
- while(begin != end) {
- node_ptr n = begin;
- begin = begin->next_;
- delete_node(n);
- ++count;
+ set_hash_functions(set_hash_functions const&);
+ set_hash_functions& operator=(set_hash_functions const&);
+
+ typedef buffered_functions<H, P> buffered_functions;
+ buffered_functions& buffered_functions_;
+ bool tmp_functions_;
+
+ public:
+
+ set_hash_functions(buffered_functions& f, H const& h, P const& p)
+ : buffered_functions_(f),
+ tmp_functions_(!f.current_)
+ {
+ f.construct(tmp_functions_, h, p);
+ }
+
+ set_hash_functions(buffered_functions& f,
+ buffered_functions const& other)
+ : buffered_functions_(f),
+ tmp_functions_(!f.current_)
+ {
+ f.construct(tmp_functions_, other.current());
}
- return count;
- }
+
+ ~set_hash_functions()
+ {
+ buffered_functions_.destroy(tmp_functions_);
+ }
+
+ void commit()
+ {
+ buffered_functions_.current_ = tmp_functions_;
+ tmp_functions_ = !tmp_functions_;
+ }
+ };
////////////////////////////////////////////////////////////////////////////
- // Constructors and Destructors
+ // Node Constructors
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
- template <class A, class G>
- inline hash_buckets<A, G>::hash_buckets(
- node_allocator const& a, std::size_t bucket_count)
- : buckets_(),
- bucket_count_(bucket_count),
- allocators_(a,a)
+ template <class T, class... Args>
+ inline void construct_impl(T*, void* address, Args&&... args)
{
+ new(address) T(std::forward<Args>(args)...);
}
- template <class A, class G>
- inline hash_buckets<A, G>::~hash_buckets()
+#if defined(BOOST_UNORDERED_CPP0X_PAIR)
+ template <class First, class Second, class Key, class Arg0, class... Args>
+ inline void construct_impl(std::pair<First, Second>*, void* address,
+ Key&& k, Arg0&& arg0, Args&&... args)
+ )
{
- if(this->buckets_) { this->delete_buckets(); }
+ new(address) std::pair<First, Second>(k,
+ Second(arg0, std::forward<Args>(args)...);
}
+#endif
+
+#else
+
+#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
+ template < \
+ class T, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ inline void construct_impl( \
+ T*, void* address, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ ) \
+ { \
+ new(address) T( \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ } \
+ \
+ template <class First, class Second, class Key, \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ inline void construct_impl( \
+ std::pair<First, Second>*, void* address, \
+ Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ new(address) std::pair<First, Second>(k, \
+ Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT_IMPL, _)
+
+#undef BOOST_UNORDERED_CONSTRUCT_IMPL
+#endif
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Node construction
+
+ template <class Alloc, bool Unique>
+ class node_constructor
+ {
+ typedef ::boost::unordered::detail::buckets<Alloc, Unique> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type;
+
+ buckets& buckets_;
+ real_node_ptr node_;
+ bool node_constructed_;
+ bool value_constructed_;
+
+ public:
+
+ node_constructor(buckets& m) :
+ buckets_(m),
+ node_(),
+ node_constructed_(false),
+ value_constructed_(false)
+ {
+ }
+
+ ~node_constructor();
+ void construct_preamble();
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+ template <class... Args>
+ void construct(Args&&... args)
+ {
+ construct_preamble();
+ construct_impl((value_type*) 0, node_->address(),
+ std::forward<Args>(args)...);
+ value_constructed_ = true;
+ }
+#else
+
+#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ > \
+ void construct( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ ) \
+ { \
+ construct_preamble(); \
+ construct_impl( \
+ (value_type*) 0, node_->address(), \
+ BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
+ ); \
+ value_constructed_ = true; \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_CONSTRUCT, _)
+
+#undef BOOST_UNORDERED_CONSTRUCT
+
+#endif
+ template <class K, class M>
+ void construct_pair(K const& k, M*)
+ {
+ construct_preamble();
+ new(node_->address()) value_type(k, M());
+ value_constructed_ = true;
+ }
+
+ value_type& value() const
+ {
+ BOOST_ASSERT(node_);
+ return node_->value();
+ }
+
+ // no throw
+ BOOST_DEDUCED_TYPENAME buckets::node_ptr release()
+ {
+ real_node_ptr p = node_;
+ node_ = real_node_ptr();
+ // node_ptr cast
+ return buckets_.bucket_alloc().address(*p);
+ }
+
+ private:
+ node_constructor(node_constructor const&);
+ node_constructor& operator=(node_constructor const&);
+ };
- template <class A, class G>
- inline void hash_buckets<A, G>::create_buckets()
+ // node_constructor
+
+ template <class Alloc, bool Unique>
+ inline node_constructor<Alloc, Unique>::~node_constructor()
{
- // The array constructor will clean up in the event of an
- // exception.
- allocator_array_constructor<bucket_allocator>
- constructor(bucket_alloc());
+ if (node_) {
+ if (value_constructed_) {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { node<Alloc, Grouped> x; };
+#endif
+ ::boost::unordered::detail::destroy(node_->value_ptr());
+ }
- // Creates an extra bucket to act as a sentinel.
- constructor.construct(bucket(), this->bucket_count_ + 1);
+ if (node_constructed_)
+ buckets_.node_alloc().destroy(node_);
- // Set up the sentinel (node_ptr cast)
- bucket_ptr sentinel = constructor.get() +
- static_cast<std::ptrdiff_t>(this->bucket_count_);
- sentinel->next_ = sentinel;
+ buckets_.node_alloc().deallocate(node_, 1);
+ }
+ }
+
+ template <class Alloc, bool Unique>
+ inline void node_constructor<Alloc, Unique>::construct_preamble()
+ {
+ if(!node_) {
+ node_constructed_ = false;
+ value_constructed_ = false;
+
+ node_ = buckets_.node_alloc().allocate(1);
+ buckets_.node_alloc().construct(node_, node());
+ node_->init(buckets_.bucket_alloc().address(*node_));
- // Only release the buckets once everything is successfully
- // done.
- this->buckets_ = constructor.release();
+ node_constructed_ = true;
+ }
+ else {
+ BOOST_ASSERT(node_constructed_ && value_constructed_);
+ ::boost::unordered::detail::destroy(node_->value_ptr());
+ value_constructed_ = false;
+ }
}
////////////////////////////////////////////////////////////////////////////
- // Constructors and Destructors
+ // copy_buckets_to
+ //
+ // basic excpetion safety. If an exception is thrown this will
+ // leave dst partially filled and the buckets unset.
- // no throw
- template <class A, class G>
- inline void hash_buckets<A, G>::move(hash_buckets& other)
+ template <class A, bool Unique>
+ void buckets<A, Unique>::copy_buckets_to(buckets& dst) const
{
- BOOST_ASSERT(node_alloc() == other.node_alloc());
- if(this->buckets_) { this->delete_buckets(); }
- this->buckets_ = other.buckets_;
- this->bucket_count_ = other.bucket_count_;
- other.buckets_ = bucket_ptr();
- other.bucket_count_ = 0;
- }
+ BOOST_ASSERT(!dst.buckets_);
- template <class A, class G>
- inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other)
- {
- BOOST_ASSERT(node_alloc() == other.node_alloc());
- std::swap(buckets_, other.buckets_);
- std::swap(bucket_count_, other.bucket_count_);
+ dst.create_buckets();
+ bucket_ptr dst_start = dst.get_bucket(dst.bucket_count_);
+
+ {
+ node_constructor<A, Unique> a(dst);
+
+ node_ptr n = this->buckets_[this->bucket_count_].next_;
+ node_ptr prev = dst_start;
+
+ while(n) {
+ std::size_t hash = node::get_hash(n);
+ node_ptr group_end = node::next_group(n);
+
+ a.construct(node::get_value(n));
+ node_ptr first_node = a.release();
+ node::set_hash(first_node, hash);
+ node_ptr end = prev->next_ = first_node;
+
+ for(n = n->next_; n != group_end; n = n->next_) {
+ a.construct(node::get_value(n));
+ end = a.release();
+ node::set_hash(end, hash);
+ node::add_after_node(end, first_node);
+ }
+
+ prev = dst.place_in_bucket(prev, end);
+ }
+ }
}
-}}
+
+ ///////////////////////////////////////////////////////////////////
+ //
+ // Iterators
+
+ // iterator_access is used to access the internal iterator without
+ // making it publicly available.
+
+ class iterator_access
+ {
+ public:
+ template <class Iterator>
+ static BOOST_DEDUCED_TYPENAME Iterator::node_ptr const&
+ get(Iterator const& it)
+ {
+ return it.node_;
+ }
+ };
+}}}
#endif
Modified: trunk/boost/unordered/detail/equivalent.hpp
==============================================================================
--- trunk/boost/unordered/detail/equivalent.hpp (original)
+++ trunk/boost/unordered/detail/equivalent.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -7,13 +7,12 @@
#ifndef BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED
-#include <boost/unordered/detail/table.hpp>
#include <boost/unordered/detail/extract_key.hpp>
-namespace boost { namespace unordered_detail {
+namespace boost { namespace unordered { namespace detail {
template <class T>
- class hash_equivalent_table : public T::table
+ class equivalent_table : public T::table
{
public:
typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
@@ -27,278 +26,230 @@
typedef BOOST_DEDUCED_TYPENAME T::node node;
typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base;
typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
// Constructors
- hash_equivalent_table(std::size_t n,
+ equivalent_table(std::size_t n,
hasher const& hf, key_equal const& eq, value_allocator const& a)
: table(n, hf, eq, a) {}
- hash_equivalent_table(hash_equivalent_table const& x)
+ equivalent_table(equivalent_table const& x)
: table(x, x.node_alloc()) {}
- hash_equivalent_table(hash_equivalent_table const& x,
+ equivalent_table(equivalent_table const& x,
value_allocator const& a)
: table(x, a) {}
- hash_equivalent_table(hash_equivalent_table& x, move_tag m)
+ equivalent_table(equivalent_table& x, move_tag m)
: table(x, m) {}
- hash_equivalent_table(hash_equivalent_table& x,
+ equivalent_table(equivalent_table& x,
value_allocator const& a, move_tag m)
: table(x, a, m) {}
- ~hash_equivalent_table() {}
+ ~equivalent_table() {}
- // Insert methods
-
- iterator_base emplace_impl(node_constructor& a);
- void emplace_impl_no_rehash(node_constructor& a);
-
- // equals
-
- bool equals(hash_equivalent_table const&) const;
-
- inline node_ptr add_node(node_constructor& a,
- bucket_ptr bucket, node_ptr pos);
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- template <class... Args>
- iterator_base emplace(Args&&... args);
-
-#else
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
- iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
+ // Equality
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
-
-#undef BOOST_UNORDERED_INSERT_IMPL
-#endif
-
- template <class I>
- void insert_for_range(I i, I j, forward_traversal_tag);
- template <class I>
- void insert_for_range(I i, I j, boost::incrementable_traversal_tag);
- template <class I>
- void insert_range(I i, I j);
- };
-
- template <class H, class P, class A>
- struct multiset : public types<
- BOOST_DEDUCED_TYPENAME A::value_type,
- BOOST_DEDUCED_TYPENAME A::value_type,
- H, P, A,
- set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>,
- grouped>
- {
- typedef hash_equivalent_table<multiset<H, P, A> > impl;
- typedef hash_table<multiset<H, P, A> > table;
- };
-
- template <class K, class H, class P, class A>
- struct multimap : public types<
- K, BOOST_DEDUCED_TYPENAME A::value_type,
- H, P, A,
- map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>,
- grouped>
- {
- typedef hash_equivalent_table<multimap<K, H, P, A> > impl;
- typedef hash_table<multimap<K, H, P, A> > table;
- };
-
- ////////////////////////////////////////////////////////////////////////////
- // Equality
-
- template <class T>
- bool hash_equivalent_table<T>
- ::equals(hash_equivalent_table<T> const& other) const
- {
- if(this->size_ != other.size_) return false;
- if(!this->size_) return true;
-
- bucket_ptr end = this->get_bucket(this->bucket_count_);
- for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i)
+ bool equals(equivalent_table const& other) const
{
- node_ptr it1 = i->next_;
- while(BOOST_UNORDERED_BORLAND_BOOL(it1))
+ if(this->size_ != other.size_) return false;
+ if(!this->size_) return true;
+
+ for(node_ptr n1 = this->buckets_[this->bucket_count_].next_; n1;)
{
- node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1));
- if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
-
- node_ptr end1 = node::next_group(it1);
- node_ptr end2 = node::next_group(it2);
-
+ node_ptr n2 = other.find_matching_node(n1);
+ if(!n2) return false;
+
+ node_ptr end1 = node::next_group(n1);
+ node_ptr end2 = node::next_group(n2);
+
do {
if(!extractor::compare_mapped(
- node::get_value(it1), node::get_value(it2)))
+ node::get_value(n1), node::get_value(n2)))
return false;
- it1 = it1->next_;
- it2 = it2->next_;
- } while(it1 != end1 && it2 != end2);
- if(it1 != end1 || it2 != end2) return false;
+ n1 = n1->next_;
+ n2 = n2->next_;
+ } while(n1 != end1 && n2 != end2);
+ if(n1 != end1 || n2 != end2) return false;
}
+
+ return true;
}
- return true;
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // A convenience method for adding nodes.
+ ////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
- template <class T>
- inline BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::node_ptr
- hash_equivalent_table<T>
- ::add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos)
- {
- node_ptr n = a.release();
- if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- node::add_after_node(n, pos);
- }
- else {
- node::add_to_bucket(n, *bucket);
- if(bucket < this->cached_begin_bucket_)
- this->cached_begin_bucket_ = bucket;
+ inline node_ptr add_node(
+ node_constructor& a,
+ std::size_t bucket_index,
+ std::size_t hash,
+ node_ptr pos)
+ {
+ node_ptr n = a.release();
+ node::set_hash(n, hash);
+
+ if(BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ node::add_after_node(n, pos);
+ if (n->next_) {
+ std::size_t next_bucket =
+ node::get_hash(n->next_) % this->bucket_count_;
+ if (next_bucket != bucket_index) {
+ this->buckets_[next_bucket].next_ = n;
+ }
+ }
+ }
+ else {
+ bucket_ptr b = this->get_bucket(bucket_index);
+
+ if (!b->next_)
+ {
+ bucket_ptr start_node =
+ this->get_bucket(this->bucket_count_);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(start_node->next_)) {
+ this->buckets_[
+ node::get_hash(start_node->next_) %
+ this->bucket_count_].next_ = n;
+ }
+
+ b->next_ = start_node;
+ n->next_ = start_node->next_;
+ start_node->next_ = n;
+ }
+ else
+ {
+ n->next_ = b->next_->next_;
+ b->next_->next_ = n;
+ }
+ }
+ ++this->size_;
+ return n;
}
- ++this->size_;
- return n;
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Insert methods
- template <class T>
- inline BOOST_DEDUCED_TYPENAME
- hash_equivalent_table<T>::iterator_base
- hash_equivalent_table<T>::emplace_impl(node_constructor& a)
- {
- key_type const& k = this->get_key(a.value());
- std::size_t hash_value = this->hash_function()(k);
-
- if(!this->size_) {
- return this->emplace_empty_impl_with_node(a, 1);
- }
- else {
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr position = this->find_iterator(bucket, k);
+ ////////////////////////////////////////////////////////////////////////
+ // Insert methods
+ node_ptr emplace_impl(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ node_ptr position = this->find_node(bucket_index, hash, k);
+
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
- if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
+ if(this->reserve_for_insert(this->size_ + 1)) {
+ bucket_index = hash % this->bucket_count_;
+ }
+
+ return add_node(a, bucket_index, hash, position);
+ }
- return iterator_base(bucket, add_node(a, bucket, position));
+ void emplace_impl_no_rehash(node_constructor& a)
+ {
+ key_type const& k = this->get_key(a.value());
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ add_node(a, bucket_index, hash,
+ this->find_node(bucket_index, hash, k));
}
- }
-
- template <class T>
- inline void hash_equivalent_table<T>
- ::emplace_impl_no_rehash(node_constructor& a)
- {
- key_type const& k = this->get_key(a.value());
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- add_node(a, bucket, this->find_iterator(bucket, k));
- }
#if defined(BOOST_UNORDERED_STD_FORWARD)
- // Emplace (equivalent key containers)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template <class T>
- template <class... Args>
- BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base
- hash_equivalent_table<T>
- ::emplace(Args&&... args)
- {
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
-
- return emplace_impl(a);
- }
+ template <class... Args>
+ node_ptr emplace(Args&&... args)
+ {
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+
+ return emplace_impl(a);
+ }
#else
#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
- template <class T> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base \
- hash_equivalent_table<T> \
- ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- return emplace_impl(a); \
- }
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
+ node_ptr emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
+ return emplace_impl(a); \
+ }
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT_IMPL, _)
#undef BOOST_UNORDERED_INSERT_IMPL
#endif
- ////////////////////////////////////////////////////////////////////////////
- // Insert range methods
+ ////////////////////////////////////////////////////////////////////////
+ // Insert range methods
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class T>
- template <class I>
- inline void hash_equivalent_table<T>
- ::insert_for_range(I i, I j, forward_traversal_tag)
- {
- if(i == j) return;
- std::size_t distance = unordered_detail::distance(i, j);
- if(distance == 1) {
- emplace(*i);
- }
- else {
- node_constructor a(*this);
-
- // Only require basic exception safety here
- if(this->size_) {
- this->reserve_for_insert(this->size_ + distance);
+ // if hash function throws, or inserting > 1 element, basic exception
+ // safety. Strong otherwise
+ template <class I>
+ void insert_for_range(I i, I j, forward_traversal_tag)
+ {
+ if(i == j) return;
+ std::size_t distance = ::boost::unordered::detail::distance(i, j);
+ if(distance == 1) {
+ emplace(*i);
}
else {
- a.construct(*i++);
- this->emplace_empty_impl_with_node(a, distance);
+ // Only require basic exception safety here
+ this->reserve_for_insert(this->size_ + distance);
+
+ node_constructor a(*this);
+ for (; i != j; ++i) {
+ a.construct(*i);
+ emplace_impl_no_rehash(a);
+ }
}
+ }
+ template <class I>
+ void insert_for_range(I i, I j, ::boost::incrementable_traversal_tag)
+ {
+ node_constructor a(*this);
for (; i != j; ++i) {
a.construct(*i);
- emplace_impl_no_rehash(a);
+ emplace_impl(a);
}
}
- }
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class T>
- template <class I>
- inline void hash_equivalent_table<T>
- ::insert_for_range(I i, I j, boost::incrementable_traversal_tag)
- {
- node_constructor a(*this);
- for (; i != j; ++i) {
- a.construct(*i);
- emplace_impl(a);
+ // If hash function throws, or inserting > 1 element, basic exception
+ // safety. Strong otherwise
+ template <class I>
+ void insert_range(I i, I j)
+ {
+ BOOST_DEDUCED_TYPENAME ::boost::iterator_traversal<I>::type
+ iterator_traversal_tag;
+ insert_for_range(i, j, iterator_traversal_tag);
}
- }
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class T>
- template <class I>
- void hash_equivalent_table<T>::insert_range(I i, I j)
+ };
+
+ template <class H, class P, class A>
+ struct multiset : public types<
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ H, P, A,
+ set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>,
+ false>
{
- BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
- iterator_traversal_tag;
- insert_for_range(i, j, iterator_traversal_tag);
- }
-}}
+ typedef equivalent_table<multiset<H, P, A> > impl;
+ typedef table<multiset<H, P, A> > table;
+ };
+
+ template <class K, class H, class P, class A>
+ struct multimap : public types<
+ K, BOOST_DEDUCED_TYPENAME A::value_type,
+ H, P, A,
+ map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>,
+ false>
+ {
+ typedef equivalent_table<multimap<K, H, P, A> > impl;
+ typedef table<multimap<K, H, P, A> > table;
+ };
+}}}
#endif
Modified: trunk/boost/unordered/detail/extract_key.hpp
==============================================================================
--- trunk/boost/unordered/detail/extract_key.hpp (original)
+++ trunk/boost/unordered/detail/extract_key.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -6,12 +6,11 @@
#ifndef BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED
-#include <boost/config.hpp>
-#include <boost/type_traits/remove_const.hpp>
-#include <boost/unordered/detail/fwd.hpp>
+#include <boost/unordered/detail/table.hpp>
namespace boost {
-namespace unordered_detail {
+namespace unordered {
+namespace detail {
// key extractors
//
@@ -75,7 +74,7 @@
struct map_extractor
{
typedef ValueType value_type;
- typedef BOOST_DEDUCED_TYPENAME boost::remove_const<Key>::type key_type;
+ typedef BOOST_DEDUCED_TYPENAME ::boost::remove_const<Key>::type key_type;
static key_type const& extract(value_type const& v)
{
@@ -143,6 +142,6 @@
return x.second == y.second;
}
};
-}}
+}}}
#endif
Deleted: trunk/boost/unordered/detail/fwd.hpp
==============================================================================
--- trunk/boost/unordered/detail/fwd.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
+++ (empty file)
@@ -1,932 +0,0 @@
-
-// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
-// Copyright (C) 2005-2009 Daniel James
-// 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)
-
-// This contains the basic data structure, apart from the actual values. There's
-// no construction or deconstruction here. So this only depends on the pointer
-// type.
-
-#ifndef BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED
-#define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED
-
-#include <boost/config.hpp>
-#include <boost/iterator.hpp>
-#include <boost/compressed_pair.hpp>
-#include <boost/type_traits/aligned_storage.hpp>
-#include <boost/type_traits/alignment_of.hpp>
-#include <boost/unordered/detail/allocator_helpers.hpp>
-#include <algorithm>
-
-// This header defines most of the classes used to implement the unordered
-// containers. It doesn't include the insert methods as they require a lot
-// of preprocessor metaprogramming - they are in unique.hpp and equivalent.hpp.
-
-// Template parameters:
-//
-// H = Hash Function
-// P = Predicate
-// A = Value Allocator
-// G = Bucket group policy, 'grouped' or 'ungrouped'
-// E = Key Extractor
-
-#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
-# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION)
- // STLport doesn't have std::forward.
-# else
-# define BOOST_UNORDERED_STD_FORWARD
-# endif
-#endif
-
-#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT)
-#define BOOST_UNORDERED_EMPLACE_LIMIT 10
-#endif
-
-#if !defined(BOOST_UNORDERED_STD_FORWARD)
-
-#include <boost/preprocessor/repetition/enum_params.hpp>
-#include <boost/preprocessor/repetition/enum_binary_params.hpp>
-#include <boost/preprocessor/repetition/repeat_from_to.hpp>
-
-#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
- BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg)
-#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
- BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg)
-#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
- BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg)
-
-#endif
-
-namespace boost { namespace unordered_detail {
-
- static const float minimum_max_load_factor = 1e-3f;
- static const std::size_t default_bucket_count = 11;
- struct move_tag {};
-
- template <class T> class hash_unique_table;
- template <class T> class hash_equivalent_table;
- template <class Alloc, class Grouped>
- class hash_node_constructor;
- template <class ValueType>
- struct set_extractor;
- template <class Key, class ValueType>
- struct map_extractor;
- struct no_key;
-
- // Explicitly call a destructor
-
-#if defined(BOOST_MSVC)
-#pragma warning(push)
-#pragma warning(disable:4100) // unreferenced formal parameter
-#endif
-
- template <class T>
- inline void destroy(T* x) {
- x->~T();
- }
-
-#if defined(BOOST_MSVC)
-#pragma warning(pop)
-#endif
-
- ////////////////////////////////////////////////////////////////////////////
- //
- // This section implements buckets and nodes. Here's a rough
- // inheritance diagram, to show how they pull together.
- //
- // For unordered_set/unordered_map:
- //
- // hash_bucket<A>
- // |
- // ungrouped_node_base<A> value_base<A::value_type>
- // | |
- // +--------------+-------------+
- // |
- // hash_node<A, ungrouped>
- //
- // For unordered_multiset/unordered_multimap:
- //
- // hash_bucket<A>
- // |
- // grouped_node_base<A> value_base<A::value_type>
- // | |
- // +--------------+-------------+
- // |
- // hash_node<A, grouped>
-
- // hash_bucket
- //
- // hash_bucket is used for both the buckets and as a base class for
- // nodes. By using 'bucket_ptr' for 'node_ptr', 'next_' can point
- // to either a bucket or a node. This is used later to implement a
- // sentinel at the end of the bucket array.
-
- template <class A>
- class hash_bucket
- {
- hash_bucket& operator=(hash_bucket const&);
- public:
- typedef hash_bucket<A> bucket;
- typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<A, bucket>::type
- bucket_allocator;
- typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr;
- typedef bucket_ptr node_ptr;
-
- node_ptr next_;
-
- hash_bucket() : next_() {}
- };
-
- // In containers with equivalent keys (unordered_multimap and
- // unordered_multiset) equivalent nodes are grouped together, in
- // containers with unique keys (unordered_map and unordered_set)
- // individual nodes are treated as groups of one. The following two
- // classes implement the data structure.
-
- // This is used for containers with unique keys. There are no groups
- // so it doesn't add any extra members, and just treats individual
- // nodes as groups of one.
-
- template <class A>
- struct ungrouped_node_base : hash_bucket<A> {
- typedef hash_bucket<A> bucket;
- typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
-
- ungrouped_node_base() : bucket() {}
- static inline node_ptr& next_group(node_ptr ptr);
- static inline std::size_t group_count(node_ptr ptr);
- static inline void add_to_bucket(node_ptr n, bucket& b);
- static inline void add_after_node(node_ptr n, node_ptr position);
- static void unlink_node(bucket& b, node_ptr n);
- static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end);
- static void unlink_nodes(bucket& b, node_ptr end);
- };
-
- // This is used for containers with equivalent keys. It implements a
- // circular list running in the opposite direction to the linked
- // list through the nodes.
-
- template <class A>
- struct grouped_node_base : hash_bucket<A>
- {
- typedef hash_bucket<A> bucket;
- typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
-
- node_ptr group_prev_;
-
- grouped_node_base() : bucket(), group_prev_() {}
- static inline node_ptr& next_group(node_ptr ptr);
- static inline node_ptr first_in_group(node_ptr n);
- static inline std::size_t group_count(node_ptr ptr);
- static inline void add_to_bucket(node_ptr n, bucket& b);
- static inline void add_after_node(node_ptr n, node_ptr position);
- static void unlink_node(bucket& b, node_ptr n);
- static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end);
- static void unlink_nodes(bucket& b, node_ptr end);
-
- private:
- static inline node_ptr split_group(node_ptr split);
- static inline grouped_node_base& get(node_ptr ptr) {
- return static_cast<grouped_node_base&>(*ptr);
- }
- };
-
- // These two classes implement an easy way to pass around the node
- // group policy classes without the messy template parameters.
- // Whenever you see the template parameter 'G' it's one of these.
-
- struct ungrouped
- {
- template <class A>
- struct base {
- typedef ungrouped_node_base<A> type;
- };
- };
-
- struct grouped
- {
- template <class A>
- struct base {
- typedef grouped_node_base<A> type;
- };
- };
-
- // The space used to store values in a node.
-
- template <class ValueType>
- struct value_base
- {
- typedef ValueType value_type;
- BOOST_DEDUCED_TYPENAME boost::aligned_storage<
- sizeof(value_type),
- ::boost::alignment_of<value_type>::value>::type data_;
-
- void* address() {
- return this;
- }
- value_type& value() {
- return *(ValueType*) this;
- }
- value_type* value_ptr() {
- return (ValueType*) this;
- }
- private:
- value_base& operator=(value_base const&);
- };
-
- // Node
-
- template <class A, class G>
- class hash_node :
- public G::BOOST_NESTED_TEMPLATE base<A>::type,
- public value_base<BOOST_DEDUCED_TYPENAME A::value_type>
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr;
-
- static value_type& get_value(node_ptr p) {
- return static_cast<hash_node&>(*p).value();
- }
- static value_type* get_value_ptr(node_ptr p) {
- return static_cast<hash_node&>(*p).value_ptr();
- }
- private:
- hash_node& operator=(hash_node const&);
- };
-
- ////////////////////////////////////////////////////////////////////////////
- //
- // Iterator Base
- //
- // This is the iterator used internally, the external iterators are
- // provided by lightweight wrappers (hash_iterator and
- // hast_const_iterator) which provide the full iterator interface.
-
- template <class A, class G>
- class hash_iterator_base
- {
- public:
- typedef A value_allocator;
- typedef hash_bucket<A> bucket;
- typedef hash_node<A, G> node;
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
-
- bucket_ptr bucket_;
- node_ptr node_;
-
- hash_iterator_base() : bucket_(), node_() {}
- explicit hash_iterator_base(bucket_ptr b)
- : bucket_(b),
- node_(b ? b->next_ : node_ptr()) {}
- hash_iterator_base(bucket_ptr b, node_ptr n)
- : bucket_(b),
- node_(n) {}
-
- bool operator==(hash_iterator_base const& x) const {
- return node_ == x.node_; }
- bool operator!=(hash_iterator_base const& x) const {
- return node_ != x.node_; }
- value_type& operator*() const {
- return node::get_value(node_);
- }
-
- void increment_bucket(node_ptr n) {
- while(!n) {
- ++bucket_;
- n = bucket_->next_;
- }
- node_ = bucket_ == n ? node_ptr() : n;
- }
-
- void increment() {
- increment_bucket(node_->next_);
- }
- };
-
- ////////////////////////////////////////////////////////////////////////////
- //
- // Now the main data structure:
- //
- // hash_buckets<A, G> hash_buffered_functions<H, P>
- // | |
- // +-------------+--------------+
- // |
- // hash_table<T>
- //
- // T is a class which contains typedefs for all the types we need.
-
- // hash_buckets
- //
- // This is responsible for allocating and deallocating buckets and nodes.
- //
- // Notes:
- // 1. For the sake exception safety the consturctors don't allocate
- // anything.
- // 2. It's the callers responsibility to allocate the buckets before calling
- // any of the methods (other than getters and setters).
-
- template <class A, class G>
- class hash_buckets
- {
- hash_buckets(hash_buckets const&);
- hash_buckets& operator=(hash_buckets const&);
- public:
- // Types
-
- typedef A value_allocator;
- typedef hash_bucket<A> bucket;
- typedef hash_iterator_base<A, G> iterator_base;
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME iterator_base::node node;
-
- typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator
- bucket_allocator;
- typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
-
- typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type
- node_allocator;
- typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;
-
- // Members
-
- bucket_ptr buckets_;
- std::size_t bucket_count_;
- boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
-
- // Data access
-
- bucket_allocator const& bucket_alloc() const {
- return allocators_.first(); }
- node_allocator const& node_alloc() const {
- return allocators_.second(); }
- bucket_allocator& bucket_alloc() {
- return allocators_.first(); }
- node_allocator& node_alloc() {
- return allocators_.second(); }
- std::size_t max_bucket_count() const;
-
- // Constructors
-
- hash_buckets(node_allocator const& a, std::size_t n);
- void create_buckets();
- ~hash_buckets();
-
- // no throw
- void swap(hash_buckets& other);
- void move(hash_buckets& other);
-
- // For the remaining functions, buckets_ must not be null.
-
- bucket_ptr get_bucket(std::size_t n) const;
- bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const;
- std::size_t bucket_size(std::size_t index) const;
- node_ptr bucket_begin(std::size_t n) const;
-
- // Alloc/Dealloc
-
- void delete_node(node_ptr);
-
- //
- void delete_buckets();
- void clear_bucket(bucket_ptr);
- std::size_t delete_nodes(node_ptr begin, node_ptr end);
- std::size_t delete_to_bucket_end(node_ptr begin);
- };
-
- // Assigning and swapping the equality and hash function objects
- // needs strong exception safety. To implement that normally we'd
- // require one of them to be known to not throw and the other to
- // guarantee strong exception safety. Unfortunately they both only
- // have basic exception safety. So to acheive strong exception
- // safety we have storage space for two copies, and assign the new
- // copies to the unused space. Then switch to using that to use
- // them. This is implemented in 'set_hash_functions' which
- // atomically assigns the new function objects in a strongly
- // exception safe manner.
-
- template <class H, class P> class set_hash_functions;
-
- template <class H, class P>
- class hash_buffered_functions
- {
- friend class set_hash_functions<H, P>;
- hash_buffered_functions& operator=(hash_buffered_functions const&);
-
- typedef boost::compressed_pair<H, P> function_pair;
- typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage<
- sizeof(function_pair),
- ::boost::alignment_of<function_pair>::value>::type aligned_function;
-
- bool current_; // The currently active functions.
- aligned_function funcs_[2];
-
- function_pair const& current() const {
- return *static_cast<function_pair const*>(
- static_cast<void const*>(&funcs_[current_]));
- }
-
- void construct(bool which, H const& hf, P const& eq)
- {
- new((void*) &funcs_[which]) function_pair(hf, eq);
- }
-
- void construct(bool which, function_pair const& f)
- {
- new((void*) &funcs_[which]) function_pair(f);
- }
-
- void destroy(bool which)
- {
- boost::unordered_detail::destroy((function_pair*)(&funcs_[which]));
- }
-
- public:
-
- hash_buffered_functions(H const& hf, P const& eq)
- : current_(false)
- {
- construct(current_, hf, eq);
- }
-
- hash_buffered_functions(hash_buffered_functions const& bf)
- : current_(false)
- {
- construct(current_, bf.current());
- }
-
- ~hash_buffered_functions() {
- destroy(current_);
- }
-
- H const& hash_function() const {
- return current().first();
- }
-
- P const& key_eq() const {
- return current().second();
- }
- };
-
- template <class H, class P>
- class set_hash_functions
- {
- set_hash_functions(set_hash_functions const&);
- set_hash_functions& operator=(set_hash_functions const&);
-
- typedef hash_buffered_functions<H, P> buffered_functions;
- buffered_functions& buffered_functions_;
- bool tmp_functions_;
-
- public:
-
- set_hash_functions(buffered_functions& f, H const& h, P const& p)
- : buffered_functions_(f),
- tmp_functions_(!f.current_)
- {
- f.construct(tmp_functions_, h, p);
- }
-
- set_hash_functions(buffered_functions& f,
- buffered_functions const& other)
- : buffered_functions_(f),
- tmp_functions_(!f.current_)
- {
- f.construct(tmp_functions_, other.current());
- }
-
- ~set_hash_functions()
- {
- buffered_functions_.destroy(tmp_functions_);
- }
-
- void commit()
- {
- buffered_functions_.current_ = tmp_functions_;
- tmp_functions_ = !tmp_functions_;
- }
- };
-
- // This implements almost all of the required functionality, apart
- // from some things that are specific to containers with unique and
- // equivalent keys which is implemented in hash_unique_table and
- // hash_equivalent_table. See unique.hpp and equivalent.hpp for
- // their declaration and implementation.
-
- template <class T>
- class hash_table : public T::buckets, public T::buffered_functions
- {
- hash_table(hash_table const&);
- public:
- typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
- typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal;
- typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator;
- typedef BOOST_DEDUCED_TYPENAME T::key_type key_type;
- typedef BOOST_DEDUCED_TYPENAME T::value_type value_type;
- typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base;
- typedef BOOST_DEDUCED_TYPENAME T::buckets buckets;
- typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
- typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor;
-
- typedef BOOST_DEDUCED_TYPENAME T::node node;
- typedef BOOST_DEDUCED_TYPENAME T::bucket bucket;
- typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base;
- typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator;
- typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair;
-
- // Members
-
- std::size_t size_;
- float mlf_;
- // Cached data - invalid if !this->buckets_
- bucket_ptr cached_begin_bucket_;
- std::size_t max_load_;
-
- // Helper methods
-
- key_type const& get_key(value_type const& v) const {
- return extractor::extract(v);
- }
- key_type const& get_key_from_ptr(node_ptr n) const {
- return extractor::extract(node::get_value(n));
- }
- bool equal(key_type const& k, value_type const& v) const;
- template <class Key, class Pred>
- node_ptr find_iterator(bucket_ptr bucket, Key const& k,
- Pred const&) const;
- node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const;
- node_ptr find_iterator(key_type const& k) const;
- node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const;
-
- // Load methods
-
- std::size_t max_size() const;
- std::size_t bucket_index(key_type const& k) const;
- void max_load_factor(float z);
- std::size_t min_buckets_for_size(std::size_t n) const;
- std::size_t calculate_max_load();
-
- // Constructors
-
- hash_table(std::size_t n, hasher const& hf, key_equal const& eq,
- node_allocator const& a);
- hash_table(hash_table const& x, node_allocator const& a);
- hash_table(hash_table& x, move_tag m);
- hash_table(hash_table& x, node_allocator const& a, move_tag m);
- ~hash_table() {}
- hash_table& operator=(hash_table const&);
-
- // Iterators
-
- iterator_base begin() const {
- return this->size_ ?
- iterator_base(this->cached_begin_bucket_) :
- iterator_base();
- }
- iterator_base end() const {
- return iterator_base();
- }
-
- // Swap & Move
-
- void swap(hash_table& x);
- void fast_swap(hash_table& other);
- void slow_swap(hash_table& other);
- void partial_swap(hash_table& other);
- void move(hash_table& x);
-
- // Reserve and rehash
-
- void create_for_insert(std::size_t n);
- bool reserve_for_insert(std::size_t n);
- void rehash(std::size_t n);
- void rehash_impl(std::size_t n);
-
- // Move/copy buckets
-
- void move_buckets_to(buckets& dst);
- void copy_buckets_to(buckets& dst) const;
-
- // Misc. key methods
-
- std::size_t count(key_type const& k) const;
- iterator_base find(key_type const& k) const;
- template <class Key, class Hash, class Pred>
- iterator_base find(Key const& k, Hash const& h, Pred const& eq) const;
- value_type& at(key_type const& k) const;
- iterator_pair equal_range(key_type const& k) const;
-
- // Erase
- //
- // no throw
-
- void clear();
- std::size_t erase_key(key_type const& k);
- iterator_base erase_return_iterator(iterator_base r);
- void erase(iterator_base r);
- std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
- iterator_base erase_range(iterator_base r1, iterator_base r2);
-
- // recompute_begin_bucket
-
- void init_buckets();
-
- // After an erase cached_begin_bucket_ might be left pointing to
- // an empty bucket, so this is called to update it
- //
- // no throw
-
- void recompute_begin_bucket(bucket_ptr b);
-
- // This is called when a range has been erased
- //
- // no throw
-
- void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2);
-
- // no throw
- float load_factor() const;
-
- iterator_base emplace_empty_impl_with_node(
- node_constructor&, std::size_t);
- };
-
- ///////////////////////////////////////////////////////////////////
- //
- // Iterators
-
- // iterator_access is used to access the internal iterator without
- // making it publicly available.
-
- class iterator_access
- {
- public:
- template <class Iterator>
- static BOOST_DEDUCED_TYPENAME Iterator::base const&
- get(Iterator const& it)
- {
- return it.base_;
- }
- };
-
- template <class A, class G> class hash_iterator;
- template <class A, class G> class hash_const_iterator;
- template <class A, class G> class hash_local_iterator;
- template <class A, class G> class hash_const_local_iterator;
-
- // Local Iterators
- //
- // all no throw
-
- template <class A, class G>
- class hash_local_iterator
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME A::value_type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME A::pointer,
- BOOST_DEDUCED_TYPENAME A::reference>
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
-
- private:
- typedef hash_buckets<A, G> buckets;
- typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME buckets::node node;
- typedef hash_const_local_iterator<A, G> const_local_iterator;
-
- friend class hash_const_local_iterator<A, G>;
- node_ptr ptr_;
-
- public:
- hash_local_iterator() : ptr_() {}
- explicit hash_local_iterator(node_ptr x) : ptr_(x) {}
- BOOST_DEDUCED_TYPENAME A::reference operator*() const {
- return node::get_value(ptr_);
- }
- value_type* operator->() const {
- return node::get_value_ptr(ptr_);
- }
- hash_local_iterator& operator++() {
- ptr_ = ptr_->next_; return *this;
- }
- hash_local_iterator operator++(int) {
- hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
- bool operator==(hash_local_iterator x) const {
- return ptr_ == x.ptr_;
- }
- bool operator==(const_local_iterator x) const {
- return ptr_ == x.ptr_;
- }
- bool operator!=(hash_local_iterator x) const {
- return ptr_ != x.ptr_;
- }
- bool operator!=(const_local_iterator x) const {
- return ptr_ != x.ptr_;
- }
- };
-
- template <class A, class G>
- class hash_const_local_iterator
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME A::value_type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME A::const_pointer,
- BOOST_DEDUCED_TYPENAME A::const_reference >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
-
- private:
- typedef hash_buckets<A, G> buckets;
- typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr;
- typedef BOOST_DEDUCED_TYPENAME buckets::node node;
- typedef hash_local_iterator<A, G> local_iterator;
- friend class hash_local_iterator<A, G>;
- ptr ptr_;
-
- public:
- hash_const_local_iterator() : ptr_() {}
- explicit hash_const_local_iterator(ptr x) : ptr_(x) {}
- hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {}
- BOOST_DEDUCED_TYPENAME A::const_reference
- operator*() const {
- return node::get_value(ptr_);
- }
- value_type const* operator->() const {
- return node::get_value_ptr(ptr_);
- }
- hash_const_local_iterator& operator++() {
- ptr_ = ptr_->next_; return *this;
- }
- hash_const_local_iterator operator++(int) {
- hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp;
- }
- bool operator==(local_iterator x) const {
- return ptr_ == x.ptr_;
- }
- bool operator==(hash_const_local_iterator x) const {
- return ptr_ == x.ptr_;
- }
- bool operator!=(local_iterator x) const {
- return ptr_ != x.ptr_;
- }
- bool operator!=(hash_const_local_iterator x) const {
- return ptr_ != x.ptr_;
- }
- };
-
- // Iterators
- //
- // all no throw
-
-
- template <class A, class G>
- class hash_iterator
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME A::value_type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME A::pointer,
- BOOST_DEDUCED_TYPENAME A::reference >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
-
- private:
- typedef hash_buckets<A, G> buckets;
- typedef BOOST_DEDUCED_TYPENAME buckets::node node;
- typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
- typedef hash_const_iterator<A, G> const_iterator;
- friend class hash_const_iterator<A, G>;
- base base_;
-
- public:
-
- hash_iterator() : base_() {}
- explicit hash_iterator(base const& x) : base_(x) {}
- BOOST_DEDUCED_TYPENAME A::reference operator*() const {
- return *base_;
- }
- value_type* operator->() const {
- return &*base_;
- }
- hash_iterator& operator++() {
- base_.increment(); return *this;
- }
- hash_iterator operator++(int) {
- hash_iterator tmp(base_); base_.increment(); return tmp;
- }
- bool operator==(hash_iterator const& x) const {
- return base_ == x.base_;
- }
- bool operator==(const_iterator const& x) const {
- return base_ == x.base_;
- }
- bool operator!=(hash_iterator const& x) const {
- return base_ != x.base_;
- }
- bool operator!=(const_iterator const& x) const {
- return base_ != x.base_;
- }
- };
-
- template <class A, class G>
- class hash_const_iterator
- : public boost::iterator <
- std::forward_iterator_tag,
- BOOST_DEDUCED_TYPENAME A::value_type,
- std::ptrdiff_t,
- BOOST_DEDUCED_TYPENAME A::const_pointer,
- BOOST_DEDUCED_TYPENAME A::const_reference >
- {
- public:
- typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
-
- private:
- typedef hash_buckets<A, G> buckets;
- typedef BOOST_DEDUCED_TYPENAME buckets::node node;
- typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
- typedef hash_iterator<A, G> iterator;
- friend class hash_iterator<A, G>;
- friend class iterator_access;
- base base_;
-
- public:
-
- hash_const_iterator() : base_() {}
- explicit hash_const_iterator(base const& x) : base_(x) {}
- hash_const_iterator(iterator const& x) : base_(x.base_) {}
- BOOST_DEDUCED_TYPENAME A::const_reference operator*() const {
- return *base_;
- }
- value_type const* operator->() const {
- return &*base_;
- }
- hash_const_iterator& operator++() {
- base_.increment(); return *this;
- }
- hash_const_iterator operator++(int) {
- hash_const_iterator tmp(base_); base_.increment(); return tmp;
- }
- bool operator==(iterator const& x) const {
- return base_ == x.base_;
- }
- bool operator==(hash_const_iterator const& x) const {
- return base_ == x.base_;
- }
- bool operator!=(iterator const& x) const {
- return base_ != x.base_;
- }
- bool operator!=(hash_const_iterator const& x) const {
- return base_ != x.base_;
- }
- };
-
- ////////////////////////////////////////////////////////////////////////////
- //
- // types
- //
- // This is used to convieniently pass around a container's typedefs
- // without having 7 template parameters.
-
- template <class K, class V, class H, class P, class A, class E, class G>
- struct types
- {
- public:
- typedef K key_type;
- typedef V value_type;
- typedef H hasher;
- typedef P key_equal;
- typedef A value_allocator;
- typedef E extractor;
- typedef G group_type;
-
- typedef hash_node_constructor<value_allocator, group_type>
- node_constructor;
- typedef hash_buckets<value_allocator, group_type> buckets;
- typedef hash_buffered_functions<hasher, key_equal> buffered_functions;
-
- typedef BOOST_DEDUCED_TYPENAME buckets::node node;
- typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket;
- typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
- typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base;
- typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator;
-
- typedef std::pair<iterator_base, iterator_base> iterator_pair;
- };
-}}
-
-#endif
Modified: trunk/boost/unordered/detail/move.hpp
==============================================================================
--- trunk/boost/unordered/detail/move.hpp (original)
+++ trunk/boost/unordered/detail/move.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -38,7 +38,8 @@
/*************************************************************************************************/
namespace boost {
-namespace unordered_detail {
+namespace unordered {
+namespace detail {
/*************************************************************************************************/
@@ -69,7 +70,7 @@
/*************************************************************************************************/
template<typename T>
-struct has_move_assign : boost::mpl::and_<boost::is_class<T>, class_has_move_assign<T> > {};
+struct has_move_assign : ::boost::mpl::and_<boost::is_class<T>, class_has_move_assign<T> > {};
/*************************************************************************************************/
@@ -83,13 +84,13 @@
/*
REVISIT (sparent_at_[hidden]): This is a work around for Boost 1.34.1 and VC++ 2008 where
- boost::is_convertible<T, T> fails to compile.
+ ::boost::is_convertible<T, T> fails to compile.
*/
template <typename T, typename U>
-struct is_convertible : boost::mpl::or_<
- boost::is_same<T, U>,
- boost::is_convertible<T, U>
+struct is_convertible : ::boost::mpl::or_<
+ ::boost::is_same<T, U>,
+ ::boost::is_convertible<T, U>
> { };
/*************************************************************************************************/
@@ -124,10 +125,10 @@
\brief The is_movable trait can be used to identify movable types.
*/
template <typename T>
-struct is_movable : boost::mpl::and_<
- boost::is_convertible<move_from<T>, T>,
+struct is_movable : ::boost::mpl::and_<
+ ::boost::is_convertible<move_from<T>, T>,
move_detail::has_move_assign<T>,
- boost::mpl::not_<boost::is_convertible<move_detail::test_can_convert_anything, T> >
+ ::boost::mpl::not_<boost::is_convertible<move_detail::test_can_convert_anything, T> >
> { };
/*************************************************************************************************/
@@ -138,7 +139,7 @@
// unless the trait is specialized.
template <typename T>
-struct is_movable : boost::mpl::false_ { };
+struct is_movable : ::boost::mpl::false_ { };
#endif
@@ -158,10 +159,10 @@
template <typename T,
typename U = T,
typename R = void*>
-struct copy_sink : boost::enable_if<
- boost::mpl::and_<
- boost::unordered_detail::move_detail::is_convertible<T, U>,
- boost::mpl::not_<is_movable<T> >
+struct copy_sink : ::boost::enable_if<
+ ::boost::mpl::and_<
+ ::boost::unordered::detail::move_detail::is_convertible<T, U>,
+ ::boost::mpl::not_<is_movable<T> >
>,
R
>
@@ -179,9 +180,9 @@
template <typename T,
typename U = T,
typename R = void*>
-struct move_sink : boost::enable_if<
- boost::mpl::and_<
- boost::unordered_detail::move_detail::is_convertible<T, U>,
+struct move_sink : ::boost::enable_if<
+ ::boost::mpl::and_<
+ ::boost::unordered::detail::move_detail::is_convertible<T, U>,
is_movable<T>
>,
R
@@ -233,7 +234,8 @@
#endif // BOOST_NO_SFINAE
-} // namespace unordered_detail
+} // namespace detail
+} // namespace unordered
} // namespace boost
/*************************************************************************************************/
Modified: trunk/boost/unordered/detail/node.hpp
==============================================================================
--- trunk/boost/unordered/detail/node.hpp (original)
+++ trunk/boost/unordered/detail/node.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -11,10 +11,7 @@
#ifndef BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED
-#include <boost/config.hpp>
-#include <boost/assert.hpp>
-#include <boost/detail/workaround.hpp>
-#include <boost/unordered/detail/fwd.hpp>
+#include <boost/unordered/detail/util.hpp>
#if BOOST_WORKAROUND(__BORLANDC__, <= 0X0582)
#define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x)
@@ -22,205 +19,342 @@
#define BOOST_UNORDERED_BORLAND_BOOL(x) x
#endif
-namespace boost { namespace unordered_detail {
+namespace boost { namespace unordered { namespace detail {
////////////////////////////////////////////////////////////////////////////
- // ungrouped node implementation
+ //
+ // This section implements buckets and nodes. Here's a rough
+ // inheritance diagram, to show how they pull together.
+ //
+ // For unordered_set/unordered_map:
+ //
+ // bucket<A> value_base<A::value_type>
+ // | |
+ // +--------------+-------------+
+ // |
+ // ungrouped_node<A>
+ //
+ // For unordered_multiset/unordered_multimap:
+ //
+ // bucket<A> value_base<A::value_type>
+ // | |
+ // +--------------+-------------+
+ // |
+ // grouped_node<A>
+
+ // bucket
+ //
+ // bucket is used for both the buckets and as a base class for
+ // nodes. By using 'bucket_ptr' for 'node_ptr', 'next_' can point
+ // to either a bucket or a node. This is used later to implement a
+ // sentinel at the end of the bucket array.
template <class A>
- inline BOOST_DEDUCED_TYPENAME ungrouped_node_base<A>::node_ptr&
- ungrouped_node_base<A>::next_group(node_ptr ptr)
+ class bucket
{
- return ptr->next_;
- }
+ bucket& operator=(bucket const&);
+ public:
+ typedef BOOST_DEDUCED_TYPENAME
+ ::boost::unordered::detail::rebind_wrap<A, bucket>::type
+ bucket_allocator;
+ typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr;
+ typedef bucket_ptr node_ptr;
+
+ node_ptr next_;
- template <class A>
- inline std::size_t ungrouped_node_base<A>::group_count(node_ptr)
- {
- return 1;
- }
+ bucket() : next_() {}
+ };
- template <class A>
- inline void ungrouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b)
- {
- n->next_ = b.next_;
- b.next_ = n;
- }
+ // The space used to store values in a node.
- template <class A>
- inline void ungrouped_node_base<A>::add_after_node(node_ptr n,
- node_ptr position)
- {
- n->next_ = position->next_;
- position->next_ = position;
- }
-
- template <class A>
- inline void ungrouped_node_base<A>::unlink_nodes(bucket& b,
- node_ptr begin, node_ptr end)
+ template <class ValueType>
+ struct value_base
{
- node_ptr* pos = &b.next_;
- while(*pos != begin) pos = &(*pos)->next_;
- *pos = end;
- }
+ typedef ValueType value_type;
+ BOOST_DEDUCED_TYPENAME ::boost::aligned_storage<
+ sizeof(value_type),
+ ::boost::alignment_of<value_type>::value>::type data_;
- template <class A>
- inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end)
- {
- b.next_ = end;
- }
+ void* address() {
+ return this;
+ }
+ value_type& value() {
+ return *(ValueType*) this;
+ }
+ value_type* value_ptr() {
+ return (ValueType*) this;
+ }
+ private:
+ value_base& operator=(value_base const&);
+ };
- template <class A>
- inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr n)
- {
- unlink_nodes(b, n, n->next_);
- }
+ // In containers with equivalent keys (unordered_multimap and
+ // unordered_multiset) equivalent nodes are grouped together, in
+ // containers with unique keys (unordered_map and unordered_set)
+ // individual nodes are treated as groups of one. The following two
+ // classes implement the data structure.
- ////////////////////////////////////////////////////////////////////////////
- // grouped node implementation
-
- // If ptr is the first element in a group, return pointer to next group.
- // Otherwise returns a pointer to ptr.
- template <class A>
- inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr&
- grouped_node_base<A>::next_group(node_ptr ptr)
- {
- return get(ptr).group_prev_->next_;
- }
+ // This is used for containers with unique keys. There are no groups
+ // so it doesn't add any extra members, and just treats individual
+ // nodes as groups of one.
template <class A>
- inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr
- grouped_node_base<A>::first_in_group(node_ptr ptr)
+ struct ungrouped_node
+ : ::boost::unordered::detail::bucket<A>,
+ value_base<BOOST_DEDUCED_TYPENAME A::value_type>
{
- while(next_group(ptr) == ptr)
- ptr = get(ptr).group_prev_;
- return ptr;
- }
+ typedef ::boost::unordered::detail::bucket<A> bucket;
+ typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
- template <class A>
- inline std::size_t grouped_node_base<A>::group_count(node_ptr ptr)
- {
- node_ptr start = ptr;
- std::size_t size = 0;
- do {
- ++size;
- ptr = get(ptr).group_prev_;
- } while(ptr != start);
- return size;
- }
+ std::size_t hash_;
- template <class A>
- inline void grouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b)
- {
- n->next_ = b.next_;
- get(n).group_prev_ = n;
- b.next_ = n;
- }
+ ungrouped_node() : bucket() {}
- template <class A>
- inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos)
- {
- n->next_ = next_group(pos);
- get(n).group_prev_ = get(pos).group_prev_;
- next_group(pos) = n;
- get(pos).group_prev_ = n;
- }
-
- // Break a ciruclar list into two, with split as the beginning
- // of the second group (if split is at the beginning then don't
- // split).
- template <class A>
- inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr
- grouped_node_base<A>::split_group(node_ptr split)
- {
- node_ptr first = first_in_group(split);
- if(first == split) return split;
+ void init(node_ptr) {}
+
+ static node_ptr next_group(node_ptr ptr)
+ {
+ return ptr->next_;
+ }
+
+ static node_ptr next_group2(node_ptr ptr)
+ {
+ return ptr->next_;
+ }
+
+ static std::size_t group_count(node_ptr n)
+ {
+ return !n ? 0 : 1;
+ }
+
+ static void add_after_node(node_ptr n, node_ptr position)
+ {
+ n->next_ = position->next_;
+ position->next_ = position;
+ }
+
+ static node_ptr unlink_node(bucket& b, node_ptr n)
+ {
+ return unlink_nodes(b, n, n->next_);
+ }
+
+ static node_ptr unlink_nodes(bucket& b, node_ptr begin, node_ptr end)
+ {
+ node_ptr prev = b.next_;
+ while(prev->next_ != begin) prev = prev->next_;
+ prev->next_ = end;
+ return prev;
+ }
+
+ static std::size_t get_hash(node_ptr p)
+ {
+ return static_cast<ungrouped_node&>(*p).hash_;
+ }
+
+ static void set_hash(node_ptr p, std::size_t hash)
+ {
+ static_cast<ungrouped_node&>(*p).hash_ = hash;
+ }
+
+ static value_type& get_value(node_ptr p)
+ {
+ return static_cast<ungrouped_node&>(*p).value();
+ }
- node_ptr last = get(first).group_prev_;
- get(first).group_prev_ = get(split).group_prev_;
- get(split).group_prev_ = last;
+ static value_type* get_value_ptr(node_ptr p)
+ {
+ return static_cast<ungrouped_node&>(*p).value_ptr();
+ }
+ };
- return first;
- }
+ // This is used for containers with equivalent keys. It implements a
+ // circular list running in the opposite direction to the linked
+ // list through the nodes.
template <class A>
- void grouped_node_base<A>::unlink_node(bucket& b, node_ptr n)
+ struct grouped_node
+ : ::boost::unordered::detail::bucket<A>,
+ value_base<BOOST_DEDUCED_TYPENAME A::value_type>
{
- node_ptr next = n->next_;
- node_ptr* pos = &next_group(n);
+ typedef ::boost::unordered::detail::bucket<A> bucket;
+ typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+
+ std::size_t hash_;
+ node_ptr group_prev_;
+
+ grouped_node() : bucket(), group_prev_() {}
+ void init(node_ptr n)
+ {
+ group_prev_ = n;
+ }
+
+ static node_ptr next_group(node_ptr ptr)
+ {
+ return get(ptr).group_prev_->next_;
+ }
- if(*pos != n) {
- // The node is at the beginning of a group.
+ static node_ptr next_group2(node_ptr ptr)
+ {
+ return get(ptr->next_).group_prev_;
+ }
- // Find the previous node pointer:
- pos = &b.next_;
- while(*pos != n) pos = &next_group(*pos);
+ static std::size_t group_count(node_ptr ptr)
+ {
+ if (!ptr) return 0;
+
+ node_ptr start = ptr;
+ std::size_t size = 0;
+ do {
+ ++size;
+ ptr = get(ptr).group_prev_;
+ } while(ptr != start);
+ return size;
+ }
- // Remove from group
- if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
+ static void add_after_node(node_ptr n, node_ptr pos)
+ {
+ n->next_ = get(pos).group_prev_->next_;
+ get(n).group_prev_ = get(pos).group_prev_;
+ get(pos).group_prev_->next_ = n;
+ get(pos).group_prev_ = n;
+ }
+
+ static node_ptr unlink_node(bucket& b, node_ptr n)
+ {
+ node_ptr next = n->next_;
+ node_ptr prev = get(n).group_prev_;
+
+ if(prev->next_ != n) {
+ // The node is at the beginning of a group.
+
+ // Find the previous node pointer:
+ prev = b.next_;
+ while(prev->next_ != n) {
+ prev = next_group2(prev);
+ }
+
+ // Remove from group
+ if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
+ get(next).group_prev_ == n)
+ {
+ get(next).group_prev_ = get(n).group_prev_;
+ }
+ }
+ else if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
get(next).group_prev_ == n)
{
+ // The deleted node is not at the end of the group, so
+ // change the link from the next node.
get(next).group_prev_ = get(n).group_prev_;
}
+ else {
+ // The deleted node is at the end of the group, so the
+ // first node in the group is pointing to it.
+ // Find that to change its pointer.
+ node_ptr x = get(n).group_prev_;
+ while(get(x).group_prev_ != n) {
+ x = get(x).group_prev_;
+ }
+ get(x).group_prev_ = get(n).group_prev_;
+ }
+ prev->next_ = next;
+
+ return prev;
}
- else if(BOOST_UNORDERED_BORLAND_BOOL(next) &&
- get(next).group_prev_ == n)
+
+ static node_ptr unlink_nodes(bucket& b, node_ptr begin, node_ptr end)
{
- // The deleted node is not at the end of the group, so
- // change the link from the next node.
- get(next).group_prev_ = get(n).group_prev_;
- }
- else {
- // The deleted node is at the end of the group, so the
- // first node in the group is pointing to it.
- // Find that to change its pointer.
- node_ptr x = get(n).group_prev_;
- while(get(x).group_prev_ != n) {
- x = get(x).group_prev_;
+ node_ptr prev = get(begin).group_prev_;
+
+ if(prev->next_ != begin) {
+ // The node is at the beginning of a group.
+
+ // Find the previous node pointer:
+ prev = b.next_;
+ while(prev->next_ != begin) prev = next_group2(prev);
+
+ if(BOOST_UNORDERED_BORLAND_BOOL(end)) split_group(end);
+ }
+ else {
+ node_ptr group1 = split_group(begin);
+ if(BOOST_UNORDERED_BORLAND_BOOL(end)) {
+ node_ptr group2 = split_group(end);
+
+ if(begin == group2) {
+ node_ptr end1 = get(group1).group_prev_;
+ node_ptr end2 = get(group2).group_prev_;
+ get(group1).group_prev_ = end2;
+ get(group2).group_prev_ = end1;
+ }
+ }
}
- get(x).group_prev_ = get(n).group_prev_;
+
+ prev->next_ = end;
+
+ return prev;
}
- *pos = next;
- }
- template <class A>
- void grouped_node_base<A>::unlink_nodes(bucket& b,
- node_ptr begin, node_ptr end)
- {
- node_ptr* pos = &next_group(begin);
+ // Break a ciruclar list into two, with split as the beginning
+ // of the second group (if split is at the beginning then don't
+ // split).
+ static node_ptr split_group(node_ptr split)
+ {
+ // Find first node in group.
+ node_ptr first = split;
+ while(next_group(first) == first)
+ first = get(first).group_prev_;
- if(*pos != begin) {
- // The node is at the beginning of a group.
+ if(first == split) return split;
+
+ node_ptr last = get(first).group_prev_;
+ get(first).group_prev_ = get(split).group_prev_;
+ get(split).group_prev_ = last;
+
+ return first;
+ }
- // Find the previous node pointer:
- pos = &b.next_;
- while(*pos != begin) pos = &next_group(*pos);
-
- // Remove from group
- if(BOOST_UNORDERED_BORLAND_BOOL(end)) split_group(end);
- }
- else {
- node_ptr group1 = split_group(begin);
- if(BOOST_UNORDERED_BORLAND_BOOL(end)) {
- node_ptr group2 = split_group(end);
-
- if(begin == group2) {
- node_ptr end1 = get(group1).group_prev_;
- node_ptr end2 = get(group2).group_prev_;
- get(group1).group_prev_ = end2;
- get(group2).group_prev_ = end1;
- }
- }
+ static std::size_t get_hash(node_ptr p) {
+ return static_cast<grouped_node&>(*p).hash_;
+ }
+ static void set_hash(node_ptr p, std::size_t hash) {
+ static_cast<grouped_node&>(*p).hash_ = hash;
+ }
+ static value_type& get_value(node_ptr p) {
+ return static_cast<grouped_node&>(*p).value();
+ }
+ static value_type* get_value_ptr(node_ptr p) {
+ return static_cast<grouped_node&>(*p).value_ptr();
}
- *pos = end;
- }
- template <class A>
- void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end)
+ static grouped_node& get(node_ptr ptr) {
+ return static_cast<grouped_node&>(*ptr);
+ }
+ };
+
+ // These two classes implement an easy way to pass around the node
+ // group policy classes without the messy template parameters.
+ // Whenever you see the template parameter 'G' it's one of these.
+
+ struct ungrouped
{
- split_group(end);
- b.next_ = end;
- }
-}}
+ template <class A>
+ struct node {
+ typedef ungrouped_node<A> type;
+ };
+ };
+
+ struct grouped
+ {
+ template <class A>
+ struct node {
+ typedef grouped_node<A> type;
+ };
+ };
+
+}}}
#endif
Modified: trunk/boost/unordered/detail/table.hpp
==============================================================================
--- trunk/boost/unordered/detail/table.hpp (original)
+++ trunk/boost/unordered/detail/table.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -7,439 +7,502 @@
#ifndef BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED
-#include <cstddef>
-#include <stdexcept>
-#include <algorithm>
-#include <boost/config/no_tr1/cmath.hpp>
-#include <boost/iterator/iterator_categories.hpp>
-#include <boost/throw_exception.hpp>
-
#include <boost/unordered/detail/buckets.hpp>
-namespace boost { namespace unordered_detail {
-
- ////////////////////////////////////////////////////////////////////////////
- // Helper methods
+namespace boost { namespace unordered { namespace detail {
- // strong exception safety, no side effects
- template <class T>
- inline bool hash_table<T>::equal(
- key_type const& k, value_type const& v) const
- {
- return this->key_eq()(k, get_key(v));
- }
+ // This implements almost all of the required functionality, apart
+ // from some things that are specific to containers with unique and
+ // equivalent keys which is implemented in unique_table and
+ // equivalent_table. See unique.hpp and equivalent.hpp for
+ // their declaration and implementation.
+
+ template <class T>
+ class table : public T::buckets, public T::buffered_functions
+ {
+ table(table const&);
+ public:
+ typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
+ typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal;
+ typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator;
+ typedef BOOST_DEDUCED_TYPENAME T::key_type key_type;
+ typedef BOOST_DEDUCED_TYPENAME T::value_type value_type;
+ typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base;
+ typedef BOOST_DEDUCED_TYPENAME T::buckets buckets;
+ typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
+ typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor;
+
+ typedef BOOST_DEDUCED_TYPENAME T::node node;
+ typedef BOOST_DEDUCED_TYPENAME T::bucket bucket;
+ typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator;
+ typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair;
- // strong exception safety, no side effects
- template <class T>
- template <class Key, class Pred>
- inline BOOST_DEDUCED_TYPENAME T::node_ptr
- hash_table<T>::find_iterator(bucket_ptr bucket, Key const& k,
- Pred const& eq) const
- {
- node_ptr it = bucket->next_;
- while (BOOST_UNORDERED_BORLAND_BOOL(it) &&
- !eq(k, get_key(node::get_value(it))))
+ // Members
+
+ std::size_t size_;
+ float mlf_;
+ std::size_t max_load_;
+
+ // Helper methods
+
+ key_type const& get_key(value_type const& v) const {
+ return extractor::extract(v);
+ }
+
+ private:
+ // pre: this->buckets_ != null
+ template <class Key, class Pred>
+ node_ptr find_node_impl(
+ std::size_t bucket_index,
+ std::size_t hash,
+ Key const& k,
+ Pred const& eq) const
{
- it = node::next_group(it);
+ node_ptr n = this->buckets_[bucket_index].next_;
+ if (!n) return n;
+ n = n->next_;
+
+ for (;;)
+ {
+ if (!n) return n;
+ std::size_t node_hash = node::get_hash(n);
+ if (hash == node_hash)
+ {
+ if (eq(k, get_key(node::get_value(n))))
+ return n;
+ }
+ else
+ {
+ if (node_hash % this->bucket_count_ != bucket_index)
+ return node_ptr();
+ }
+ n = node::next_group(n);
+ }
}
- return it;
- }
-
- // strong exception safety, no side effects
- template <class T>
- inline BOOST_DEDUCED_TYPENAME T::node_ptr
- hash_table<T>::find_iterator(
- bucket_ptr bucket, key_type const& k) const
- {
- node_ptr it = bucket->next_;
- while (BOOST_UNORDERED_BORLAND_BOOL(it) &&
- !equal(k, node::get_value(it)))
+ public:
+ template <class Key, class Hash, class Pred>
+ node_ptr generic_find_node(
+ Key const& k,
+ Hash const& hash_function,
+ Pred const& eq) const
{
- it = node::next_group(it);
+ if (!this->size_) return node_ptr();
+ std::size_t hash = hash_function(k);
+ return find_node_impl(hash % this->bucket_count_, hash, k, eq);
}
-
- return it;
- }
-
- // strong exception safety, no side effects
- // pre: this->buckets_
- template <class T>
- inline BOOST_DEDUCED_TYPENAME T::node_ptr
- hash_table<T>::find_iterator(key_type const& k) const
- {
- return find_iterator(this->get_bucket(this->bucket_index(k)), k);
- }
-
- // strong exception safety, no side effects
- template <class T>
- inline BOOST_DEDUCED_TYPENAME T::node_ptr*
- hash_table<T>::find_for_erase(
- bucket_ptr bucket, key_type const& k) const
- {
- node_ptr* it = &bucket->next_;
- while(BOOST_UNORDERED_BORLAND_BOOL(*it) &&
- !equal(k, node::get_value(*it)))
+
+ node_ptr find_node(
+ std::size_t bucket_index,
+ std::size_t hash,
+ key_type const& k) const
{
- it = &node::next_group(*it);
+ if (!this->size_) return node_ptr();
+ return find_node_impl(bucket_index, hash, k, this->key_eq());
}
- return it;
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Load methods
-
- // no throw
- template <class T>
- std::size_t hash_table<T>::max_size() const
- {
- using namespace std;
-
- // size < mlf_ * count
- return double_to_size_t(ceil(
- (double) this->mlf_ * this->max_bucket_count())) - 1;
- }
-
- // strong safety
- template <class T>
- inline std::size_t hash_table<T>::bucket_index(
- key_type const& k) const
- {
- // hash_function can throw:
- return this->hash_function()(k) % this->bucket_count_;
- }
-
-
- // no throw
- template <class T>
- inline std::size_t hash_table<T>::calculate_max_load()
- {
- using namespace std;
-
- // From 6.3.1/13:
- // Only resize when size >= mlf_ * count
- return double_to_size_t(ceil((double) mlf_ * this->bucket_count_));
- }
-
- template <class T>
- void hash_table<T>::max_load_factor(float z)
- {
- BOOST_ASSERT(z > 0);
- mlf_ = (std::max)(z, minimum_max_load_factor);
- this->max_load_ = this->calculate_max_load();
- }
+ node_ptr find_node(key_type const& k) const
+ {
+ if (!this->size_) return node_ptr();
+ std::size_t hash = this->hash_function()(k);
+ return find_node_impl(hash % this->bucket_count_, hash, k,
+ this->key_eq());
+ }
- // no throw
- template <class T>
- inline std::size_t hash_table<T>::min_buckets_for_size(
- std::size_t size) const
- {
- BOOST_ASSERT(this->mlf_ != 0);
+ node_ptr find_matching_node(node_ptr n) const
+ {
+ // For some stupid reason, I decided to support equality comparison
+ // when different hash functions are used. So I can't use the hash
+ // value from the node here.
+
+ return find_node(get_key(node::get_value(n)));
+ }
- using namespace std;
+ ////////////////////////////////////////////////////////////////////////
+ // Load methods
- // From 6.3.1/13:
- // size < mlf_ * count
- // => count > size / mlf_
- //
- // Or from rehash post-condition:
- // count > size / mlf_
- return next_prime(double_to_size_t(floor(size / (double) mlf_)) + 1);
- }
+ std::size_t max_size() const
+ {
+ using namespace std;
+
+ // size < mlf_ * count
+ return double_to_size_t(ceil(
+ (double) this->mlf_ * this->max_bucket_count())) - 1;
+ }
- ////////////////////////////////////////////////////////////////////////////
- // recompute_begin_bucket
+ std::size_t calculate_max_load()
+ {
+ BOOST_ASSERT(this->buckets_);
- // init_buckets
+ using namespace std;
+
+ // From 6.3.1/13:
+ // Only resize when size >= mlf_ * count
+ return double_to_size_t(ceil((double) mlf_ * this->bucket_count_));
+ }
- template <class T>
- inline void hash_table<T>::init_buckets()
- {
- if (this->size_) {
- this->cached_begin_bucket_ = this->buckets_;
- while (!this->cached_begin_bucket_->next_)
- ++this->cached_begin_bucket_;
- } else {
- this->cached_begin_bucket_ = this->get_bucket(this->bucket_count_);
+ void max_load_factor(float z)
+ {
+ BOOST_ASSERT(z > 0);
+ mlf_ = (std::max)(z, minimum_max_load_factor);
+ if (BOOST_UNORDERED_BORLAND_BOOL(this->buckets_))
+ this->max_load_ = this->calculate_max_load();
}
- this->max_load_ = calculate_max_load();
- }
- // After an erase cached_begin_bucket_ might be left pointing to
- // an empty bucket, so this is called to update it
- //
- // no throw
+ std::size_t min_buckets_for_size(std::size_t size) const
+ {
+ BOOST_ASSERT(this->mlf_ != 0);
+
+ using namespace std;
+
+ // From 6.3.1/13:
+ // size < mlf_ * count
+ // => count > size / mlf_
+ //
+ // Or from rehash post-condition:
+ // count > size / mlf_
+ return next_prime(double_to_size_t(floor(size / (double) mlf_)) + 1);
+ }
- template <class T>
- inline void hash_table<T>::recompute_begin_bucket(bucket_ptr b)
- {
- BOOST_ASSERT(!(b < this->cached_begin_bucket_));
+ float load_factor() const
+ {
+ BOOST_ASSERT(this->bucket_count_ != 0);
+ return static_cast<float>(this->size_)
+ / static_cast<float>(this->bucket_count_);
+ }
+
+ ////////////////////////////////////////////////////////////////////////
+ // Constructors
+
+ table(
+ std::size_t num_buckets,
+ hasher const& hf,
+ key_equal const& eq,
+ node_allocator const& a)
+ : buckets(a, next_prime(num_buckets)),
+ base(hf, eq),
+ size_(),
+ mlf_(1.0f),
+ max_load_(0)
+ {
+ }
- if(b == this->cached_begin_bucket_)
+ table(table const& x, node_allocator const& a)
+ : buckets(a, x.min_buckets_for_size(x.size_)),
+ base(x),
+ size_(x.size_),
+ mlf_(x.mlf_),
+ max_load_(0)
{
- if (this->size_ != 0) {
- while (!this->cached_begin_bucket_->next_)
- ++this->cached_begin_bucket_;
- } else {
- this->cached_begin_bucket_ =
- this->get_bucket(this->bucket_count_);
+ if(x.size_) {
+ x.copy_buckets_to(*this);
+ this->max_load_ = calculate_max_load();
}
}
- }
-
- // This is called when a range has been erased
- //
- // no throw
- template <class T>
- inline void hash_table<T>::recompute_begin_bucket(
- bucket_ptr b1, bucket_ptr b2)
- {
- BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1));
- BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_));
-
- if(b1 == this->cached_begin_bucket_ && !b1->next_)
- this->cached_begin_bucket_ = b2;
- }
+ table(table& x, move_tag)
+ : buckets(x.node_alloc(), x.bucket_count_),
+ base(x),
+ size_(0),
+ mlf_(1.0f),
+ max_load_(0)
+ {
+ this->partial_swap(x);
+ }
- // no throw
- template <class T>
- inline float hash_table<T>::load_factor() const
- {
- BOOST_ASSERT(this->bucket_count_ != 0);
- return static_cast<float>(this->size_)
- / static_cast<float>(this->bucket_count_);
- }
+ table(table& x, node_allocator const& a, move_tag)
+ : buckets(a, x.bucket_count_),
+ base(x),
+ size_(0),
+ mlf_(x.mlf_),
+ max_load_(0)
+ {
+ if(a == x.node_alloc()) {
+ this->partial_swap(x);
+ }
+ else if(x.size_) {
+ x.copy_buckets_to(*this);
+ this->size_ = x.size_;
+ this->max_load_ = calculate_max_load();
+ }
+ }
- ////////////////////////////////////////////////////////////////////////////
- // Constructors
+ ~table()
+ {}
- template <class T>
- hash_table<T>::hash_table(std::size_t num_buckets,
- hasher const& hf, key_equal const& eq, node_allocator const& a)
- : buckets(a, next_prime(num_buckets)),
- base(hf, eq),
- size_(),
- mlf_(1.0f),
- cached_begin_bucket_(),
- max_load_(0)
- {
- }
+ table& operator=(table const& x)
+ {
+ table tmp(x, this->node_alloc());
+ this->fast_swap(tmp);
+ return *this;
+ }
- // Copy Construct with allocator
+ // Iterators
- template <class T>
- hash_table<T>::hash_table(hash_table const& x,
- node_allocator const& a)
- : buckets(a, x.min_buckets_for_size(x.size_)),
- base(x),
- size_(x.size_),
- mlf_(x.mlf_),
- cached_begin_bucket_(),
- max_load_(0)
- {
- if(x.size_) {
- x.copy_buckets_to(*this);
- this->init_buckets();
+ node_ptr begin() const {
+ return !this->buckets_ ?
+ node_ptr() : this->buckets_[this->bucket_count_].next_;
}
- }
- // Move Construct
+ ////////////////////////////////////////////////////////////////////////
+ // Swap & Move
- template <class T>
- hash_table<T>::hash_table(hash_table& x, move_tag)
- : buckets(x.node_alloc(), x.bucket_count_),
- base(x),
- size_(0),
- mlf_(1.0f),
- cached_begin_bucket_(),
- max_load_(0)
- {
- this->partial_swap(x);
- }
+ void swap(table& x)
+ {
+ if(this->node_alloc() == x.node_alloc()) {
+ if(this != &x) this->fast_swap(x);
+ }
+ else {
+ this->slow_swap(x);
+ }
+ }
- template <class T>
- hash_table<T>::hash_table(hash_table& x,
- node_allocator const& a, move_tag)
- : buckets(a, x.bucket_count_),
- base(x),
- size_(0),
- mlf_(x.mlf_),
- cached_begin_bucket_(),
- max_load_(0)
- {
- if(a == x.node_alloc()) {
- this->partial_swap(x);
+ void fast_swap(table& x)
+ {
+ // These can throw, but they only affect the function objects
+ // that aren't in use so it is strongly exception safe, via.
+ // double buffering.
+ {
+ set_hash_functions<hasher, key_equal> op1(*this, x);
+ set_hash_functions<hasher, key_equal> op2(x, *this);
+ op1.commit();
+ op2.commit();
+ }
+ this->buckets::swap(x); // No throw
+ std::swap(this->size_, x.size_);
+ std::swap(this->mlf_, x.mlf_);
+ std::swap(this->max_load_, x.max_load_);
}
- else if(x.size_) {
- x.copy_buckets_to(*this);
- this->size_ = x.size_;
- this->init_buckets();
+
+ void slow_swap(table& x)
+ {
+ if(this == &x) return;
+
+ {
+ // These can throw, but they only affect the function objects
+ // that aren't in use so it is strongly exception safe, via.
+ // double buffering.
+ set_hash_functions<hasher, key_equal> op1(*this, x);
+ set_hash_functions<hasher, key_equal> op2(x, *this);
+
+ // Create new buckets in separate buckets objects
+ // which will clean up if anything throws an exception.
+ // (all can throw, but with no effect as these are new objects).
+
+ buckets b1(this->node_alloc(), x.min_buckets_for_size(x.size_));
+ if (x.size_) x.copy_buckets_to(b1);
+
+ buckets b2(x.node_alloc(), this->min_buckets_for_size(this->size_));
+ if (this->size_) this->copy_buckets_to(b2);
+
+ // Modifying the data, so no throw from now on.
+
+ b1.swap(*this);
+ b2.swap(x);
+ op1.commit();
+ op2.commit();
+ }
+
+ std::swap(this->size_, x.size_);
+
+ this->max_load_ = !this->buckets_ ? 0 : this->calculate_max_load();
+ x.max_load_ = !x.buckets_ ? 0 : x.calculate_max_load();
}
- }
- template <class T>
- hash_table<T>& hash_table<T>::operator=(
- hash_table const& x)
- {
- hash_table tmp(x, this->node_alloc());
- this->fast_swap(tmp);
- return *this;
- }
+ void partial_swap(table& x)
+ {
+ this->buckets::swap(x); // No throw
+ std::swap(this->size_, x.size_);
+ std::swap(this->mlf_, x.mlf_);
+ std::swap(this->max_load_, x.max_load_);
+ }
- ////////////////////////////////////////////////////////////////////////////
- // Swap & Move
+ void move(table& x)
+ {
+ // This can throw, but it only affects the function objects
+ // that aren't in use so it is strongly exception safe, via.
+ // double buffering.
+ set_hash_functions<hasher, key_equal> new_func_this(*this, x);
- // Swap
- //
- // Strong exception safety
- //
- // Can throw if hash or predicate object's copy constructor throws
- // or if allocators are unequal.
+ if(this->node_alloc() == x.node_alloc()) {
+ this->buckets::move(x); // no throw
+ this->size_ = x.size_;
+ this->max_load_ = x.max_load_;
+ x.size_ = 0;
+ }
+ else {
+ // Create new buckets in separate buckets
+ // which will clean up if anything throws an exception.
+ // (all can throw, but with no effect as these are new objects).
+
+ buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_));
+ if (x.size_) x.copy_buckets_to(b);
+
+ // Start updating the data here, no throw from now on.
+ this->size_ = x.size_;
+ b.swap(*this);
+ this->max_load_ = x.size_ ? calculate_max_load() : 0;
+ }
+
+ // We've made it, the rest is no throw.
+ this->mlf_ = x.mlf_;
+ new_func_this.commit();
+ }
- template <class T>
- inline void hash_table<T>::partial_swap(hash_table& x)
- {
- this->buckets::swap(x); // No throw
- std::swap(this->size_, x.size_);
- std::swap(this->mlf_, x.mlf_);
- std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_);
- std::swap(this->max_load_, x.max_load_);
- }
+ ////////////////////////////////////////////////////////////////////////
+ // Key methods
- template <class T>
- inline void hash_table<T>::fast_swap(hash_table& x)
- {
- // These can throw, but they only affect the function objects
- // that aren't in use so it is strongly exception safe, via.
- // double buffering.
- {
- set_hash_functions<hasher, key_equal> op1(*this, x);
- set_hash_functions<hasher, key_equal> op2(x, *this);
- op1.commit();
- op2.commit();
- }
- this->buckets::swap(x); // No throw
- std::swap(this->size_, x.size_);
- std::swap(this->mlf_, x.mlf_);
- std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_);
- std::swap(this->max_load_, x.max_load_);
- }
+ std::size_t count(key_type const& k) const
+ {
+ if(!this->size_) return 0;
+ return node::group_count(find_node(k));
+ }
- template <class T>
- inline void hash_table<T>::slow_swap(hash_table& x)
- {
- if(this == &x) return;
+ value_type& at(key_type const& k) const
+ {
+ if (this->size_) {
+ node_ptr it = find_node(k);
+ if (BOOST_UNORDERED_BORLAND_BOOL(it))
+ return node::get_value(it);
+ }
+
+ ::boost::throw_exception(
+ std::out_of_range("Unable to find key in unordered_map."));
+ }
+ iterator_pair equal_range(key_type const& k) const
{
- // These can throw, but they only affect the function objects
- // that aren't in use so it is strongly exception safe, via.
- // double buffering.
- set_hash_functions<hasher, key_equal> op1(*this, x);
- set_hash_functions<hasher, key_equal> op2(x, *this);
-
- // Create new buckets in separate hash_buckets objects
- // which will clean up if anything throws an exception.
- // (all can throw, but with no effect as these are new objects).
-
- buckets b1(this->node_alloc(), x.min_buckets_for_size(x.size_));
- if(x.size_) x.copy_buckets_to(b1);
-
- buckets b2(x.node_alloc(), this->min_buckets_for_size(this->size_));
- if(this->size_) copy_buckets_to(b2);
-
- // Modifying the data, so no throw from now on.
-
- b1.swap(*this);
- b2.swap(x);
- op1.commit();
- op2.commit();
+ if(!this->size_)
+ return iterator_pair(node_ptr(), node_ptr());
+
+ node_ptr ptr = find_node(k);
+ return iterator_pair(ptr, !ptr ? ptr : node::next_group(ptr));
}
-
- std::swap(this->size_, x.size_);
- if(this->buckets_) this->init_buckets();
- if(x.buckets_) x.init_buckets();
- }
+ // Erase
+ //
+ // no throw
- template <class T>
- void hash_table<T>::swap(hash_table& x)
- {
- if(this->node_alloc() == x.node_alloc()) {
- if(this != &x) this->fast_swap(x);
- }
- else {
- this->slow_swap(x);
+ void clear()
+ {
+ if(!this->size_) return;
+
+ bucket_ptr end = this->get_bucket(this->bucket_count_);
+
+ node_ptr n = (end)->next_;
+ while(BOOST_UNORDERED_BORLAND_BOOL(n))
+ {
+ node_ptr node_to_delete = n;
+ n = n->next_;
+ delete_node(node_to_delete);
+ }
+
+ ++end;
+ for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
+ begin->next_ = bucket_ptr();
+ }
+
+ this->size_ = 0;
}
- }
+ std::size_t erase_key(key_type const& k)
+ {
+ if(!this->size_) return 0;
- // Move
- //
- // Strong exception safety (might change unused function objects)
- //
- // Can throw if hash or predicate object's copy constructor throws
- // or if allocators are unequal.
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ bucket_ptr bucket = this->get_bucket(bucket_index);
+
+ node_ptr prev = bucket->next_;
+ if (!prev) return 0;
+
+ for (;;)
+ {
+ if (!prev->next_) return 0;
+ std::size_t node_hash = node::get_hash(prev->next_);
+ if (node_hash % this->bucket_count_ != bucket_index)
+ return 0;
+ if (node_hash == hash &&
+ this->key_eq()(k, get_key(node::get_value(prev->next_))))
+ break;
+ prev = node::next_group2(prev);
+ }
+
+ node_ptr pos = prev->next_;
+ node_ptr end = node::next_group(pos);
+ prev->next_ = end;
+
+ this->fix_buckets(bucket, prev, end);
+
+ std::size_t count = this->delete_nodes(pos, end);
+ this->size_ -= count;
+
+ return count;
+ }
- template <class T>
- void hash_table<T>::move(hash_table& x)
- {
- // This can throw, but it only affects the function objects
- // that aren't in use so it is strongly exception safe, via.
- // double buffering.
- set_hash_functions<hasher, key_equal> new_func_this(*this, x);
-
- if(this->node_alloc() == x.node_alloc()) {
- this->buckets::move(x); // no throw
- this->size_ = x.size_;
- this->cached_begin_bucket_ = x.cached_begin_bucket_;
- this->max_load_ = x.max_load_;
- x.size_ = 0;
+ node_ptr erase(node_ptr r)
+ {
+ BOOST_ASSERT(r);
+ node_ptr next = r->next_;
+
+ bucket_ptr bucket = this->get_bucket(
+ node::get_hash(r) % this->bucket_count_);
+ node_ptr prev = node::unlink_node(*bucket, r);
+
+ this->fix_buckets(bucket, prev, next);
+
+ this->delete_node(r);
+ --this->size_;
+
+ return next;
}
- else {
- // Create new buckets in separate HASH_TABLE_DATA objects
- // which will clean up if anything throws an exception.
- // (all can throw, but with no effect as these are new objects).
-
- buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_));
- if(x.size_) x.copy_buckets_to(b);
- // Start updating the data here, no throw from now on.
- this->size_ = x.size_;
- b.swap(*this);
- this->init_buckets();
+ node_ptr erase_range(node_ptr r1, node_ptr r2)
+ {
+ if (r1 == r2) return r2;
+
+ std::size_t bucket_index = node::get_hash(r1) % this->bucket_count_;
+ node_ptr prev = node::unlink_nodes(
+ this->buckets_[bucket_index], r1, r2);
+ this->fix_buckets_range(bucket_index, prev, r1, r2);
+ this->size_ -= this->delete_nodes(r1, r2);
+
+ return r2;
}
- // We've made it, the rest is no throw.
- this->mlf_ = x.mlf_;
- new_func_this.commit();
- }
+ // Reserve and rehash
+
+ bool reserve_for_insert(std::size_t);
+ void rehash(std::size_t);
+ void rehash_impl(std::size_t);
+ };
////////////////////////////////////////////////////////////////////////////
// Reserve & Rehash
// basic exception safety
template <class T>
- inline void hash_table<T>::create_for_insert(std::size_t size)
- {
- this->bucket_count_ = (std::max)(this->bucket_count_,
- this->min_buckets_for_size(size));
- this->create_buckets();
- this->init_buckets();
- }
-
- // basic exception safety
- template <class T>
- inline bool hash_table<T>::reserve_for_insert(std::size_t size)
+ inline bool table<T>::reserve_for_insert(std::size_t size)
{
if(size >= max_load_) {
- std::size_t num_buckets
- = this->min_buckets_for_size((std::max)(size,
- this->size_ + (this->size_ >> 1)));
- if(num_buckets != this->bucket_count_) {
- rehash_impl(num_buckets);
- return true;
+ if (!this->buckets_) {
+ std::size_t old_bucket_count = this->bucket_count_;
+ this->bucket_count_ = (std::max)(this->bucket_count_,
+ this->min_buckets_for_size(size));
+ this->create_buckets();
+ this->max_load_ = calculate_max_load();
+ return old_bucket_count != this->bucket_count_;
+ }
+ else {
+ std::size_t num_buckets
+ = this->min_buckets_for_size((std::max)(size,
+ this->size_ + (this->size_ >> 1)));
+ if (num_buckets != this->bucket_count_) {
+ rehash_impl(num_buckets);
+ return true;
+ }
}
}
@@ -450,13 +513,14 @@
// strong otherwise.
template <class T>
- inline void hash_table<T>::rehash(std::size_t min_buckets)
+ void table<T>::rehash(std::size_t min_buckets)
{
using namespace std;
if(!this->size_) {
if(this->buckets_) this->delete_buckets();
this->bucket_count_ = next_prime(min_buckets);
+ this->max_load_ = 0;
}
else {
// no throw:
@@ -466,313 +530,308 @@
}
}
- // if hash function throws, basic exception safety
- // strong otherwise
-
+ // strong otherwise exception safety
template <class T>
- void hash_table<T>
- ::rehash_impl(std::size_t num_buckets)
- {
- hasher const& hf = this->hash_function();
+ void table<T>::rehash_impl(std::size_t num_buckets)
+ {
std::size_t size = this->size_;
- bucket_ptr end = this->get_bucket(this->bucket_count_);
+ BOOST_ASSERT(size);
buckets dst(this->node_alloc(), num_buckets);
dst.create_buckets();
+
+ bucket_ptr src_start = this->get_bucket(this->bucket_count_);
+ bucket_ptr dst_start = dst.get_bucket(dst.bucket_count_);
- buckets src(this->node_alloc(), this->bucket_count_);
- src.swap(*this);
- this->size_ = 0;
-
- for(bucket_ptr bucket = this->cached_begin_bucket_;
- bucket != end; ++bucket)
- {
- node_ptr group = bucket->next_;
- while(group) {
- // Move the first group of equivalent nodes in bucket to dst.
-
- // This next line throws iff the hash function throws.
- bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
- hf(get_key_from_ptr(group)));
+ dst_start->next_ = src_start->next_;
+ src_start->next_ = bucket_ptr();
+ // No need to do this, since the following is 'no throw'.
+ //this->size_ = 0;
+
+ node_ptr prev = dst_start;
+ while (BOOST_UNORDERED_BORLAND_BOOL(prev->next_))
+ prev = dst.place_in_bucket(prev, node::next_group2(prev));
- node_ptr& next_group = node::next_group(group);
- bucket->next_ = next_group;
- next_group = dst_bucket->next_;
- dst_bucket->next_ = group;
- group = bucket->next_;
- }
- }
-
- // Swap the new nodes back into the container and setup the local
+ // Swap the new nodes back into the container and setup the
// variables.
+ dst.swap(*this); // no throw
this->size_ = size;
- dst.swap(*this); // no throw
- this->init_buckets();
+ this->max_load_ = calculate_max_load();
}
////////////////////////////////////////////////////////////////////////////
- // copy_buckets_to
-
- // copy_buckets_to
//
- // basic excpetion safety. If an exception is thrown this will
- // leave dst partially filled.
+ // types
+ //
+ // This is used to convieniently pass around a container's typedefs
+ // without having 7 template parameters.
- template <class T>
- void hash_table<T>
- ::copy_buckets_to(buckets& dst) const
+ template <class K, class V, class H, class P, class A, class E, bool Unique>
+ struct types
{
- BOOST_ASSERT(this->buckets_ && !dst.buckets_);
-
- hasher const& hf = this->hash_function();
- bucket_ptr end = this->get_bucket(this->bucket_count_);
-
- node_constructor a(dst);
- dst.create_buckets();
-
- // no throw:
- for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) {
- // no throw:
- for(node_ptr it = i->next_; it;) {
- // hash function can throw.
- bucket_ptr dst_bucket = dst.bucket_ptr_from_hash(
- hf(get_key_from_ptr(it)));
- // throws, strong
-
- node_ptr group_end = node::next_group(it);
-
- a.construct(node::get_value(it));
- node_ptr n = a.release();
- node::add_to_bucket(n, *dst_bucket);
+ public:
+ typedef K key_type;
+ typedef V value_type;
+ typedef H hasher;
+ typedef P key_equal;
+ typedef A value_allocator;
+ typedef E extractor;
- for(it = it->next_; it != group_end; it = it->next_) {
- a.construct(node::get_value(it));
- node::add_after_node(a.release(), n);
- }
- }
- }
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Misc. key methods
-
- // strong exception safety
+ typedef ::boost::unordered::detail::node_constructor<value_allocator, Unique> node_constructor;
+ typedef ::boost::unordered::detail::buckets<value_allocator, Unique> buckets;
+ typedef ::boost::unordered::detail::buffered_functions<hasher, key_equal> buffered_functions;
+
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator;
+
+ typedef std::pair<node_ptr, node_ptr> iterator_pair;
+ };
+}}}
- // count
- //
- // strong exception safety, no side effects
-
- template <class T>
- std::size_t hash_table<T>::count(key_type const& k) const
- {
- if(!this->size_) return 0;
- node_ptr it = find_iterator(k); // throws, strong
- return BOOST_UNORDERED_BORLAND_BOOL(it) ? node::group_count(it) : 0;
- }
+namespace boost { namespace unordered { namespace iterator_detail {
- // find
+ // Iterators
//
- // strong exception safety, no side effects
- template <class T>
- BOOST_DEDUCED_TYPENAME T::iterator_base
- hash_table<T>::find(key_type const& k) const
- {
- if(!this->size_) return this->end();
-
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- node_ptr it = find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(it))
- return iterator_base(bucket, it);
- else
- return this->end();
- }
+ // all no throw
- template <class T>
- template <class Key, class Hash, class Pred>
- BOOST_DEDUCED_TYPENAME T::iterator_base hash_table<T>::find(Key const& k,
- Hash const& h, Pred const& eq) const
- {
- if(!this->size_) return this->end();
-
- bucket_ptr bucket = this->get_bucket(h(k) % this->bucket_count_);
- node_ptr it = find_iterator(bucket, k, eq);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(it))
- return iterator_base(bucket, it);
- else
- return this->end();
- }
-
- template <class T>
- BOOST_DEDUCED_TYPENAME T::value_type&
- hash_table<T>::at(key_type const& k) const
- {
- if(!this->size_)
- boost::throw_exception(std::out_of_range("Unable to find key in unordered_map."));
-
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- node_ptr it = find_iterator(bucket, k);
-
- if (!it)
- boost::throw_exception(std::out_of_range("Unable to find key in unordered_map."));
+ template <class A, bool Unique> class iterator;
+ template <class A, bool Unique> class c_iterator;
+ template <class A, bool Unique> class l_iterator;
+ template <class A, bool Unique> class cl_iterator;
- return node::get_value(it);
- }
-
- // equal_range
+ // Local Iterators
//
- // strong exception safety, no side effects
- template <class T>
- BOOST_DEDUCED_TYPENAME T::iterator_pair
- hash_table<T>::equal_range(key_type const& k) const
- {
- if(!this->size_)
- return iterator_pair(this->end(), this->end());
+ // all no throw
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- node_ptr it = find_iterator(bucket, k);
- if (BOOST_UNORDERED_BORLAND_BOOL(it)) {
- iterator_base first(iterator_base(bucket, it));
- iterator_base second(first);
- second.increment_bucket(node::next_group(second.node_));
- return iterator_pair(first, second);
- }
- else {
- return iterator_pair(this->end(), this->end());
+ template <class A, bool Unique>
+ class l_iterator
+ : public ::boost::iterator <
+ std::forward_iterator_tag,
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ std::ptrdiff_t,
+ BOOST_DEDUCED_TYPENAME A::pointer,
+ BOOST_DEDUCED_TYPENAME A::reference>
+ {
+ public:
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+
+ private:
+ typedef ::boost::unordered::detail::buckets<A, Unique> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef cl_iterator<A, Unique> const_local_iterator;
+
+ friend class cl_iterator<A, Unique>;
+ node_ptr ptr_;
+ std::size_t bucket_;
+ std::size_t bucket_count_;
+
+ public:
+ l_iterator() : ptr_() {}
+ l_iterator(node_ptr x, std::size_t b, std::size_t c)
+ : ptr_(x), bucket_(b), bucket_count_(c) {}
+ BOOST_DEDUCED_TYPENAME A::reference operator*() const {
+ return node::get_value(ptr_);
+ }
+ value_type* operator->() const {
+ return node::get_value_ptr(ptr_);
+ }
+ l_iterator& operator++() {
+ ptr_ = ptr_->next_;
+ if (ptr_ && node::get_hash(ptr_) % bucket_count_ != bucket_)
+ ptr_ = node_ptr();
+ return *this;
+ }
+ l_iterator operator++(int) {
+ l_iterator tmp(*this);
+ ptr_ = ptr_->next_;
+ if (ptr_ && node::get_hash(ptr_) % bucket_count_ != bucket_)
+ ptr_ = node_ptr();
+ return tmp;
+ }
+ bool operator==(l_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator==(const_local_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator!=(l_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ bool operator!=(const_local_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ };
+
+ template <class A, bool Unique>
+ class cl_iterator
+ : public ::boost::iterator <
+ std::forward_iterator_tag,
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ std::ptrdiff_t,
+ BOOST_DEDUCED_TYPENAME A::const_pointer,
+ BOOST_DEDUCED_TYPENAME A::const_reference >
+ {
+ public:
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+
+ private:
+ typedef ::boost::unordered::detail::buckets<A, Unique> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef l_iterator<A, Unique> local_iterator;
+ friend class l_iterator<A, Unique>;
+
+ node_ptr ptr_;
+ std::size_t bucket_;
+ std::size_t bucket_count_;
+
+ public:
+ cl_iterator() : ptr_() {}
+ cl_iterator(node_ptr x, std::size_t b, std::size_t c)
+ : ptr_(x), bucket_(b), bucket_count_(c) {}
+ cl_iterator(local_iterator x)
+ : ptr_(x.ptr_), bucket_(x.bucket_), bucket_count_(x.bucket_count_)
+ {}
+ BOOST_DEDUCED_TYPENAME A::const_reference
+ operator*() const {
+ return node::get_value(ptr_);
+ }
+ value_type const* operator->() const {
+ return node::get_value_ptr(ptr_);
+ }
+ cl_iterator& operator++() {
+ ptr_ = ptr_->next_;
+ if (ptr_ && node::get_hash(ptr_) % bucket_count_ != bucket_)
+ ptr_ = node_ptr();
+ return *this;
+ }
+ cl_iterator operator++(int) {
+ cl_iterator tmp(*this);
+ ptr_ = ptr_->next_;
+ if (ptr_ && node::get_hash(ptr_) % bucket_count_ != bucket_)
+ ptr_ = node_ptr();
+ return tmp;
+ }
+ bool operator==(local_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator==(cl_iterator x) const {
+ return ptr_ == x.ptr_;
+ }
+ bool operator!=(local_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ bool operator!=(cl_iterator x) const {
+ return ptr_ != x.ptr_;
+ }
+ };
+
+ template <class A, bool Unique>
+ class iterator
+ : public ::boost::iterator <
+ std::forward_iterator_tag,
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ std::ptrdiff_t,
+ BOOST_DEDUCED_TYPENAME A::pointer,
+ BOOST_DEDUCED_TYPENAME A::reference >
+ {
+ public:
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+
+ private:
+ typedef ::boost::unordered::detail::buckets<A, Unique> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
+ typedef c_iterator<A, Unique> const_iterator;
+ friend class c_iterator<A, Unique>;
+ node_ptr node_;
+
+ public:
+
+ iterator() : node_() {}
+ explicit iterator(node_ptr const& x) : node_(x) {}
+ BOOST_DEDUCED_TYPENAME A::reference operator*() const {
+ return node::get_value(node_);
+ }
+ value_type* operator->() const {
+ return &node::get_value(node_);
+ }
+ iterator& operator++() {
+ node_ = node_->next_; return *this;
+ }
+ iterator operator++(int) {
+ iterator tmp(node_); node_ = node_->next_; return tmp;
+ }
+ bool operator==(iterator const& x) const {
+ return node_ == x.node_;
+ }
+ bool operator==(const_iterator const& x) const {
+ return node_ == x.node_;
+ }
+ bool operator!=(iterator const& x) const {
+ return node_ != x.node_;
+ }
+ bool operator!=(const_iterator const& x) const {
+ return node_ != x.node_;
+ }
+ };
+
+ template <class A, bool Unique>
+ class c_iterator
+ : public ::boost::iterator <
+ std::forward_iterator_tag,
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ std::ptrdiff_t,
+ BOOST_DEDUCED_TYPENAME A::const_pointer,
+ BOOST_DEDUCED_TYPENAME A::const_reference >
+ {
+ public:
+ typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
+
+ private:
+ typedef ::boost::unordered::detail::buckets<A, Unique> buckets;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node node;
+ typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
+ typedef ::boost::unordered::iterator_detail::iterator<A, Unique>
+ iterator;
+ friend class ::boost::unordered::iterator_detail::iterator<A, Unique>;
+ friend class ::boost::unordered::detail::iterator_access;
+ node_ptr node_;
+
+ public:
+
+ c_iterator() : node_() {}
+ explicit c_iterator(node_ptr const& x) : node_(x) {}
+ c_iterator(iterator const& x) : node_(x.node_) {}
+ BOOST_DEDUCED_TYPENAME A::const_reference operator*() const {
+ return node::get_value(node_);
+ }
+ value_type const* operator->() const {
+ return &node::get_value(node_);
+ }
+ c_iterator& operator++() {
+ node_ = node_->next_; return *this;
+ }
+ c_iterator operator++(int) {
+ c_iterator tmp(node_); node_ = node_->next_; return tmp;
+ }
+ bool operator==(iterator const& x) const {
+ return node_ == x.node_;
+ }
+ bool operator==(c_iterator const& x) const {
+ return node_ == x.node_;
}
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Erase methods
-
- template <class T>
- void hash_table<T>::clear()
- {
- if(!this->size_) return;
-
- bucket_ptr end = this->get_bucket(this->bucket_count_);
- for(bucket_ptr begin = this->buckets_; begin != end; ++begin) {
- this->clear_bucket(begin);
+ bool operator!=(iterator const& x) const {
+ return node_ != x.node_;
}
-
- this->size_ = 0;
- this->cached_begin_bucket_ = end;
- }
-
- template <class T>
- inline std::size_t hash_table<T>::erase_group(
- node_ptr* it, bucket_ptr bucket)
- {
- node_ptr pos = *it;
- node_ptr end = node::next_group(pos);
- *it = end;
- std::size_t count = this->delete_nodes(pos, end);
- this->size_ -= count;
- this->recompute_begin_bucket(bucket);
- return count;
- }
-
- template <class T>
- std::size_t hash_table<T>::erase_key(key_type const& k)
- {
- if(!this->size_) return 0;
-
- // No side effects in initial section
- bucket_ptr bucket = this->get_bucket(this->bucket_index(k));
- node_ptr* it = this->find_for_erase(bucket, k);
-
- // No throw.
- return *it ? this->erase_group(it, bucket) : 0;
- }
-
- template <class T>
- void hash_table<T>::erase(iterator_base r)
- {
- BOOST_ASSERT(r.node_);
- --this->size_;
- node::unlink_node(*r.bucket_, r.node_);
- this->delete_node(r.node_);
- // r has been invalidated but its bucket is still valid
- this->recompute_begin_bucket(r.bucket_);
- }
-
- template <class T>
- BOOST_DEDUCED_TYPENAME T::iterator_base
- hash_table<T>::erase_return_iterator(iterator_base r)
- {
- BOOST_ASSERT(r.node_);
- iterator_base next = r;
- next.increment();
- --this->size_;
- node::unlink_node(*r.bucket_, r.node_);
- this->delete_node(r.node_);
- // r has been invalidated but its bucket is still valid
- this->recompute_begin_bucket(r.bucket_, next.bucket_);
- return next;
- }
-
- template <class T>
- BOOST_DEDUCED_TYPENAME T::iterator_base
- hash_table<T>::erase_range(
- iterator_base r1, iterator_base r2)
- {
- if(r1 != r2)
- {
- BOOST_ASSERT(r1.node_);
- if (r1.bucket_ == r2.bucket_) {
- node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_);
- this->size_ -= this->delete_nodes(r1.node_, r2.node_);
-
- // No need to call recompute_begin_bucket because
- // the nodes are only deleted from one bucket, which
- // still contains r2 after the erase.
- BOOST_ASSERT(r1.bucket_->next_);
- }
- else {
- bucket_ptr end_bucket = r2.node_ ?
- r2.bucket_ : this->get_bucket(this->bucket_count_);
- BOOST_ASSERT(r1.bucket_ < end_bucket);
- node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr());
- this->size_ -= this->delete_nodes(r1.node_, node_ptr());
-
- bucket_ptr i = r1.bucket_;
- for(++i; i != end_bucket; ++i) {
- this->size_ -= this->delete_nodes(i->next_, node_ptr());
- i->next_ = node_ptr();
- }
-
- if(r2.node_) {
- node_ptr first = r2.bucket_->next_;
- node::unlink_nodes(*r2.bucket_, r2.node_);
- this->size_ -= this->delete_nodes(first, r2.node_);
- }
-
- // r1 has been invalidated but its bucket is still
- // valid.
- this->recompute_begin_bucket(r1.bucket_, end_bucket);
- }
+ bool operator!=(c_iterator const& x) const {
+ return node_ != x.node_;
}
-
- return r2;
- }
-
- template <class T>
- BOOST_DEDUCED_TYPENAME hash_table<T>::iterator_base
- hash_table<T>::emplace_empty_impl_with_node(
- node_constructor& a, std::size_t size)
- {
- key_type const& k = get_key(a.value());
- std::size_t hash_value = this->hash_function()(k);
- if(this->buckets_) this->reserve_for_insert(size);
- else this->create_for_insert(size);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr n = a.release();
- node::add_to_bucket(n, *bucket);
- ++this->size_;
- this->cached_begin_bucket_ = bucket;
- return iterator_base(bucket, n);
- }
-}}
+ };
+}}}
#endif
Modified: trunk/boost/unordered/detail/unique.hpp
==============================================================================
--- trunk/boost/unordered/detail/unique.hpp (original)
+++ trunk/boost/unordered/detail/unique.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -7,13 +7,12 @@
#ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED
-#include <boost/unordered/detail/table.hpp>
#include <boost/unordered/detail/extract_key.hpp>
-namespace boost { namespace unordered_detail {
+namespace boost { namespace unordered { namespace detail {
template <class T>
- class hash_unique_table : public T::table
+ class unique_table : public T::table
{
public:
typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
@@ -27,487 +26,372 @@
typedef BOOST_DEDUCED_TYPENAME T::node node;
typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
- typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base;
typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
- typedef std::pair<iterator_base, bool> emplace_return;
+ typedef std::pair<node_ptr, bool> emplace_return;
// Constructors
- hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq,
+ unique_table(std::size_t n, hasher const& hf, key_equal const& eq,
value_allocator const& a)
: table(n, hf, eq, a) {}
- hash_unique_table(hash_unique_table const& x)
+ unique_table(unique_table const& x)
: table(x, x.node_alloc()) {}
- hash_unique_table(hash_unique_table const& x, value_allocator const& a)
+ unique_table(unique_table const& x, value_allocator const& a)
: table(x, a) {}
- hash_unique_table(hash_unique_table& x, move_tag m)
+ unique_table(unique_table& x, move_tag m)
: table(x, m) {}
- hash_unique_table(hash_unique_table& x, value_allocator const& a,
+ unique_table(unique_table& x, value_allocator const& a,
move_tag m)
: table(x, a, m) {}
- ~hash_unique_table() {}
-
- // Insert methods
-
- emplace_return emplace_impl_with_node(node_constructor& a);
- value_type& operator[](key_type const& k);
+ ~unique_table() {}
// equals
- bool equals(hash_unique_table const&) const;
-
- node_ptr add_node(node_constructor& a, bucket_ptr bucket);
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- template<class... Args>
- emplace_return emplace(Args&&... args);
- template<class... Args>
- emplace_return emplace_impl(key_type const& k, Args&&... args);
- template<class... Args>
- emplace_return emplace_impl(no_key, Args&&... args);
- template<class... Args>
- emplace_return emplace_empty_impl(Args&&... args);
-#else
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
- emplace_return emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
- emplace_return emplace_impl(key_type const& k, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
- emplace_return emplace_impl(no_key, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
- emplace_return emplace_empty_impl( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, n));
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
-
-#undef BOOST_UNORDERED_INSERT_IMPL
-
-#endif
-
- // if hash function throws, or inserting > 1 element, basic exception
- // safety strong otherwise
- template <class InputIt>
- void insert_range(InputIt i, InputIt j);
- template <class InputIt>
- void insert_range_impl(key_type const&, InputIt i, InputIt j);
- template <class InputIt>
- void insert_range_impl2(node_constructor&, key_type const&, InputIt i, InputIt j);
- template <class InputIt>
- void insert_range_impl(no_key, InputIt i, InputIt j);
- };
-
- template <class H, class P, class A>
- struct set : public types<
- BOOST_DEDUCED_TYPENAME A::value_type,
- BOOST_DEDUCED_TYPENAME A::value_type,
- H, P, A,
- set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>,
- ungrouped>
- {
- typedef hash_unique_table<set<H, P, A> > impl;
- typedef hash_table<set<H, P, A> > table;
- };
-
- template <class K, class H, class P, class A>
- struct map : public types<
- K, BOOST_DEDUCED_TYPENAME A::value_type,
- H, P, A,
- map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>,
- ungrouped>
- {
- typedef hash_unique_table<map<K, H, P, A> > impl;
- typedef hash_table<map<K, H, P, A> > table;
- };
-
- ////////////////////////////////////////////////////////////////////////////
- // Equality
-
- template <class T>
- bool hash_unique_table<T>
- ::equals(hash_unique_table<T> const& other) const
- {
- if(this->size_ != other.size_) return false;
- if(!this->size_) return true;
-
- bucket_ptr end = this->get_bucket(this->bucket_count_);
- for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i)
+ bool equals(unique_table const& other) const
{
- node_ptr it1 = i->next_;
- while(BOOST_UNORDERED_BORLAND_BOOL(it1))
+ if(this->size_ != other.size_) return false;
+ if(!this->size_) return true;
+
+ for(node_ptr n1 = this->get_bucket(this->bucket_count_)->next_;
+ n1; n1 = n1->next_)
{
- node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1));
- if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false;
+ node_ptr n2 = other.find_matching_node(n1);
+ if(!BOOST_UNORDERED_BORLAND_BOOL(n2)) return false;
if(!extractor::compare_mapped(
- node::get_value(it1), node::get_value(it2)))
+ node::get_value(n1), node::get_value(n2)))
return false;
- it1 = it1->next_;
}
+
+ return true;
}
- return true;
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // A convenience method for adding nodes.
+ ////////////////////////////////////////////////////////////////////////
+ // A convenience method for adding nodes.
- template <class T>
- inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::node_ptr
- hash_unique_table<T>::add_node(node_constructor& a,
- bucket_ptr bucket)
- {
- node_ptr n = a.release();
- node::add_to_bucket(n, *bucket);
- ++this->size_;
- if(bucket < this->cached_begin_bucket_)
- this->cached_begin_bucket_ = bucket;
- return n;
- }
-
- ////////////////////////////////////////////////////////////////////////////
- // Insert methods
-
- // if hash function throws, basic exception safety
- // strong otherwise
- template <class T>
- BOOST_DEDUCED_TYPENAME hash_unique_table<T>::value_type&
- hash_unique_table<T>::operator[](key_type const& k)
- {
- typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
-
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
-
- if(!this->buckets_) {
- node_constructor a(*this);
- a.construct_pair(k, (mapped_type*) 0);
- return *this->emplace_empty_impl_with_node(a, 1);
+ node_ptr add_node(
+ node_constructor& a,
+ std::size_t bucket_index,
+ std::size_t hash)
+ {
+ bucket_ptr b = this->get_bucket(bucket_index);
+ node_ptr n = a.release();
+ node::set_hash(n, hash);
+
+ if (!b->next_)
+ {
+ bucket_ptr start_node = this->get_bucket(this->bucket_count_);
+
+ if (start_node->next_) {
+ this->buckets_[
+ node::get_hash(start_node->next_) % this->bucket_count_
+ ].next_ = n;
+ }
+
+ b->next_ = start_node;
+ n->next_ = start_node->next_;
+ start_node->next_ = n;
+ }
+ else
+ {
+ n->next_ = b->next_->next_;
+ b->next_->next_ = n;
+ }
+
+ ++this->size_;
+ return n;
}
- node_ptr pos = this->find_iterator(bucket, k);
+ ////////////////////////////////////////////////////////////////////////////
+ // Insert methods
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- return node::get_value(pos);
- }
- else {
- // Side effects only in this block.
+ // if hash function throws, basic exception safety
+ // strong otherwise
+ value_type& operator[](key_type const& k)
+ {
+ typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type;
+
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ node_ptr pos = this->find_node(bucket_index, hash, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ return node::get_value(pos);
+ }
+
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(*this);
a.construct_pair(k, (mapped_type*) 0);
-
+
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
+ bucket_index = hash % this->bucket_count_;
+
// Nothing after this point can throw.
-
- return node::get_value(add_node(a, bucket));
+
+ return node::get_value(add_node(a, bucket_index, hash));
}
- }
- template <class T>
- inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
- hash_unique_table<T>::emplace_impl_with_node(node_constructor& a)
- {
- // No side effects in this initial code
- key_type const& k = this->get_key(a.value());
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Found an existing key, return it (no throw).
- return emplace_return(iterator_base(bucket, pos), false);
- } else {
+ emplace_return emplace_impl_with_node(node_constructor& a)
+ {
+ // No side effects in this initial code
+ key_type const& k = this->get_key(a.value());
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ node_ptr pos = this->find_node(bucket_index, hash, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(pos, false);
+ }
+
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
+ bucket_index = hash % this->bucket_count_;
+
// Nothing after this point can throw.
+
+ return emplace_return(add_node(a, bucket_index, hash), true);
+ }
- return emplace_return(
- iterator_base(bucket, add_node(a, bucket)),
- true);
+ emplace_return insert(value_type const& v)
+ {
+ key_type const& k = extractor::extract(v);
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ node_ptr pos = this->find_node(bucket_index, hash, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(pos, false);
+ }
+
+ // Isn't in table, add to bucket.
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ node_constructor a(*this);
+ a.construct(v);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->reserve_for_insert(this->size_ + 1))
+ bucket_index = hash % this->bucket_count_;
+
+ // Nothing after this point can throw.
+
+ return emplace_return(add_node(a, bucket_index, hash), true);
}
- }
+
#if defined(BOOST_UNORDERED_STD_FORWARD)
- template <class T>
- template<class... Args>
- inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
- hash_unique_table<T>::emplace_impl(key_type const& k,
- Args&&... args)
- {
- // No side effects in this initial code
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
-
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Found an existing key, return it (no throw).
- return emplace_return(iterator_base(bucket, pos), false);
+ template<class... Args>
+ emplace_return emplace(Args&&... args)
+ {
+ return emplace_impl(
+ extractor::extract(std::forward<Args>(args)...),
+ std::forward<Args>(args)...);
+ }
- } else {
+ template<class... Args>
+ emplace_return emplace_impl(key_type const& k, Args&&... args)
+ {
+ // No side effects in this initial code
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ node_ptr pos = this->find_node(bucket_index, hash, k);
+
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Found an existing key, return it (no throw).
+ return emplace_return(pos, false);
+ }
+
// Doesn't already exist, add to bucket.
// Side effects only in this block.
-
+
// Create the node before rehashing in case it throws an
// exception (need strong safety in such a case).
node_constructor a(*this);
a.construct(std::forward<Args>(args)...);
-
+
// reserve has basic exception safety if the hash function
// throws, strong otherwise.
if(this->reserve_for_insert(this->size_ + 1))
- bucket = this->bucket_ptr_from_hash(hash_value);
-
+ bucket_index = hash % this->bucket_count_;
+
// Nothing after this point can throw.
-
- return emplace_return(
- iterator_base(bucket, add_node(a, bucket)),
- true);
+
+ return emplace_return(add_node(a, bucket_index, hash), true);
}
- }
-
- template <class T>
- template<class... Args>
- inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
- hash_unique_table<T>::emplace_impl(no_key, Args&&... args)
- {
- // Construct the node regardless - in order to get the key.
- // It will be discarded if it isn't used
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
- return emplace_impl_with_node(a);
- }
-
- template <class T>
- template<class... Args>
- inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
- hash_unique_table<T>::emplace_empty_impl(Args&&... args)
- {
- node_constructor a(*this);
- a.construct(std::forward<Args>(args)...);
- return emplace_return(this->emplace_empty_impl_with_node(a, 1), true);
- }
+ template<class... Args>
+ emplace_return emplace_impl(no_key, Args&&... args)
+ {
+ // Construct the node regardless - in order to get the key.
+ // It will be discarded if it isn't used
+ node_constructor a(*this);
+ a.construct(std::forward<Args>(args)...);
+ return emplace_impl_with_node(a);
+ }
#else
-#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
- template <class T> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- inline BOOST_DEDUCED_TYPENAME \
- hash_unique_table<T>::emplace_return \
- hash_unique_table<T>::emplace_impl( \
- key_type const& k, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- std::size_t hash_value = this->hash_function()(k); \
- bucket_ptr bucket \
- = this->bucket_ptr_from_hash(hash_value); \
- node_ptr pos = this->find_iterator(bucket, k); \
- \
- if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
- return emplace_return(iterator_base(bucket, pos), false); \
- } else { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- \
- if(this->reserve_for_insert(this->size_ + 1)) \
- bucket = this->bucket_ptr_from_hash(hash_value); \
- \
- return emplace_return(iterator_base(bucket, \
- add_node(a, bucket)), true); \
- } \
- } \
- \
- template <class T> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- inline BOOST_DEDUCED_TYPENAME \
- hash_unique_table<T>::emplace_return \
- hash_unique_table<T>:: \
- emplace_impl(no_key, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- return emplace_impl_with_node(a); \
- } \
- \
- template <class T> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- inline BOOST_DEDUCED_TYPENAME \
- hash_unique_table<T>::emplace_return \
- hash_unique_table<T>:: \
- emplace_empty_impl( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- node_constructor a(*this); \
- a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
-
-#undef BOOST_UNORDERED_INSERT_IMPL
-
-#endif
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- // Emplace (unique keys)
- // (I'm using an overloaded emplace for both 'insert' and 'emplace')
-
- // if hash function throws, basic exception safety
- // strong otherwise
-
- template <class T>
- template<class... Args>
- BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
- hash_unique_table<T>::emplace(Args&&... args)
- {
- return this->size_ ?
- emplace_impl(
- extractor::extract(std::forward<Args>(args)...),
- std::forward<Args>(args)...) :
- emplace_empty_impl(std::forward<Args>(args)...);
- }
+ template <class Arg0>
+ emplace_return emplace(Arg0 const& arg0)
+ {
+ return emplace_impl(extractor::extract(arg0), arg0);
+ }
-#else
+#define BOOST_UNORDERED_INSERT1_IMPL(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return emplace_impl(extractor::extract(arg0, arg1), \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ }
- template <class T>
- template <class Arg0>
- BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return
- hash_unique_table<T>::emplace(Arg0 const& arg0)
- {
- return this->size_ ?
- emplace_impl(extractor::extract(arg0), arg0) :
- emplace_empty_impl(arg0);
- }
-
-#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \
- template <class T> \
- template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \
- BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return \
- hash_unique_table<T>::emplace( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- return this->size_ ? \
- emplace_impl(extractor::extract(arg0, arg1), \
- BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \
- emplace_empty_impl( \
- BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- }
+#define BOOST_UNORDERED_INSERT2_IMPL(z, n, _) \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_impl(key_type const& k, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ std::size_t hash = this->hash_function()(k); \
+ std::size_t bucket_index = hash % this->bucket_count_; \
+ node_ptr pos = this->find_node(bucket_index, hash, k); \
+ \
+ if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \
+ return emplace_return(pos, false); \
+ } else { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ \
+ if(this->reserve_for_insert(this->size_ + 1)) \
+ bucket_index = hash % this->bucket_count_; \
+ \
+ return emplace_return( \
+ add_node(a, bucket_index, hash), \
+ true); \
+ } \
+ } \
+ \
+ template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \
+ emplace_return emplace_impl(no_key, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ node_constructor a(*this); \
+ a.construct(BOOST_UNORDERED_CALL_PARAMS(z, n)); \
+ return emplace_impl_with_node(a); \
+ }
- BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_INSERT_IMPL, _)
+ BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT1_IMPL, _)
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_INSERT2_IMPL, _)
-#undef BOOST_UNORDERED_INSERT_IMPL
+#undef BOOST_UNORDERED_INSERT1_IMPL
+#undef BOOST_UNORDERED_INSERT2_IMPL
#endif
-
- ////////////////////////////////////////////////////////////////////////////
- // Insert range methods
- template <class T>
- template <class InputIt>
- inline void hash_unique_table<T>::insert_range_impl2(
- node_constructor& a, key_type const& k, InputIt i, InputIt j)
- {
- // No side effects in this initial code
- std::size_t hash_value = this->hash_function()(k);
- bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value);
- node_ptr pos = this->find_iterator(bucket, k);
+ ////////////////////////////////////////////////////////////////////////
+ // Insert range methods
+ //
+ // if hash function throws, or inserting > 1 element, basic exception
+ // safety strong otherwise
- if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
- // Doesn't already exist, add to bucket.
- // Side effects only in this block.
+ template <class InputIt>
+ void insert_range(InputIt i, InputIt j)
+ {
+ if(i != j)
+ return insert_range_impl(extractor::extract(*i), i, j);
+ }
- // Create the node before rehashing in case it throws an
- // exception (need strong safety in such a case).
- a.construct(*i);
+ template <class InputIt>
+ void insert_range_impl(key_type const&, InputIt i, InputIt j)
+ {
+ node_constructor a(*this);
+
+ do {
+ // Note: can't use get_key as '*i' might not be value_type - it
+ // could be a pair with first_types as key_type without const or a
+ // different second_type.
+ //
+ // TODO: Might be worth storing the value_type instead of the key
+ // here. Could be more efficient if '*i' is expensive. Could be
+ // less efficient if copying the full value_type is expensive.
+ insert_range_impl2(a, extractor::extract(*i), i, j);
+ } while(++i != j);
+ }
- // reserve has basic exception safety if the hash function
- // throws, strong otherwise.
- if(this->size_ + 1 >= this->max_load_) {
- this->reserve_for_insert(this->size_ + insert_size(i, j));
- bucket = this->bucket_ptr_from_hash(hash_value);
+ template <class InputIt>
+ void insert_range_impl2(node_constructor& a, key_type const& k,
+ InputIt i, InputIt j)
+ {
+ // No side effects in this initial code
+ std::size_t hash = this->hash_function()(k);
+ std::size_t bucket_index = hash % this->bucket_count_;
+ node_ptr pos = this->find_node(bucket_index, hash, k);
+
+ if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) {
+ // Doesn't already exist, add to bucket.
+ // Side effects only in this block.
+
+ // Create the node before rehashing in case it throws an
+ // exception (need strong safety in such a case).
+ a.construct(*i);
+
+ // reserve has basic exception safety if the hash function
+ // throws, strong otherwise.
+ if(this->size_ + 1 >= this->max_load_) {
+ this->reserve_for_insert(this->size_ + insert_size(i, j));
+ bucket_index = hash % this->bucket_count_;
+ }
+
+ // Nothing after this point can throw.
+ add_node(a, bucket_index, hash);
}
-
- // Nothing after this point can throw.
- add_node(a, bucket);
}
- }
- template <class T>
- template <class InputIt>
- inline void hash_unique_table<T>::insert_range_impl(
- key_type const&, InputIt i, InputIt j)
- {
- node_constructor a(*this);
-
- if(!this->size_) {
- a.construct(*i);
- this->emplace_empty_impl_with_node(a, 1);
- ++i;
- if(i == j) return;
- }
-
- do {
- // Note: can't use get_key as '*i' might not be value_type - it
- // could be a pair with first_types as key_type without const or a
- // different second_type.
- //
- // TODO: Might be worth storing the value_type instead of the key
- // here. Could be more efficient if '*i' is expensive. Could be
- // less efficient if copying the full value_type is expensive.
- insert_range_impl2(a, extractor::extract(*i), i, j);
- } while(++i != j);
- }
-
- template <class T>
- template <class InputIt>
- inline void hash_unique_table<T>::insert_range_impl(
- no_key, InputIt i, InputIt j)
- {
- node_constructor a(*this);
+ template <class InputIt>
+ void insert_range_impl(no_key, InputIt i, InputIt j)
+ {
+ node_constructor a(*this);
- if(!this->size_) {
- a.construct(*i);
- this->emplace_empty_impl_with_node(a, 1);
- ++i;
- if(i == j) return;
+ do {
+ // No side effects in this initial code
+ a.construct(*i);
+ emplace_impl_with_node(a);
+ } while(++i != j);
}
+ };
- do {
- // No side effects in this initial code
- a.construct(*i);
- emplace_impl_with_node(a);
- } while(++i != j);
- }
+ template <class H, class P, class A>
+ struct set : public types<
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ BOOST_DEDUCED_TYPENAME A::value_type,
+ H, P, A,
+ set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>,
+ true>
+ {
+ typedef ::boost::unordered::detail::unique_table<set<H, P, A> > impl;
+ typedef ::boost::unordered::detail::table<set<H, P, A> > table;
+ };
- // if hash function throws, or inserting > 1 element, basic exception safety
- // strong otherwise
- template <class T>
- template <class InputIt>
- void hash_unique_table<T>::insert_range(InputIt i, InputIt j)
+ template <class K, class H, class P, class A>
+ struct map : public types<
+ K, BOOST_DEDUCED_TYPENAME A::value_type,
+ H, P, A,
+ map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>,
+ true>
{
- if(i != j)
- return insert_range_impl(extractor::extract(*i), i, j);
- }
-}}
+ typedef ::boost::unordered::detail::unique_table<map<K, H, P, A> > impl;
+ typedef ::boost::unordered::detail::table<map<K, H, P, A> > table;
+ };
+}}}
#endif
Modified: trunk/boost/unordered/detail/util.hpp
==============================================================================
--- trunk/boost/unordered/detail/util.hpp (original)
+++ trunk/boost/unordered/detail/util.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -7,16 +7,93 @@
#ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
+#include <algorithm>
#include <cstddef>
+#include <stdexcept>
#include <utility>
-#include <algorithm>
#include <boost/limits.hpp>
+#include <boost/config.hpp>
+#include <boost/config/no_tr1/cmath.hpp>
+#include <boost/detail/workaround.hpp>
+#include <boost/detail/select_type.hpp>
+#include <boost/assert.hpp>
+#include <boost/iterator.hpp>
#include <boost/iterator/iterator_categories.hpp>
+#include <boost/compressed_pair.hpp>
+#include <boost/type_traits/aligned_storage.hpp>
+#include <boost/type_traits/alignment_of.hpp>
+#include <boost/type_traits/remove_const.hpp>
+#include <boost/throw_exception.hpp>
+#include <boost/unordered/detail/allocator_helpers.hpp>
#include <boost/preprocessor/seq/size.hpp>
#include <boost/preprocessor/seq/enum.hpp>
-#include <boost/unordered/detail/fwd.hpp>
-namespace boost { namespace unordered_detail {
+// Template parameters:
+//
+// H = Hash Function
+// P = Predicate
+// A = Value Allocator
+// G = Bucket group policy, 'grouped' or 'ungrouped'
+// E = Key Extractor
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES) && \
+ !defined(BOOST_NO_VARIADIC_TEMPLATES)
+# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION)
+ // STLport doesn't have std::forward.
+# else
+# define BOOST_UNORDERED_STD_FORWARD
+# endif
+#endif
+
+#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT)
+#define BOOST_UNORDERED_EMPLACE_LIMIT 10
+#endif
+
+#if !defined(BOOST_UNORDERED_STD_FORWARD)
+
+#include <boost/preprocessor/repetition/enum_params.hpp>
+#include <boost/preprocessor/repetition/enum_binary_params.hpp>
+#include <boost/preprocessor/repetition/repeat_from_to.hpp>
+
+#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg)
+#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
+ BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg)
+#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
+ BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg)
+
+#endif
+
+namespace boost { namespace unordered { namespace detail {
+
+ static const float minimum_max_load_factor = 1e-3f;
+ static const std::size_t default_bucket_count = 11;
+ struct move_tag {};
+
+ template <class T> class unique_table;
+ template <class T> class equivalent_table;
+ template <class Alloc, bool Unique> class node_constructor;
+ template <class ValueType>
+ struct set_extractor;
+ template <class Key, class ValueType>
+ struct map_extractor;
+ struct no_key;
+
+ // Explicitly call a destructor
+
+#if defined(BOOST_MSVC)
+#pragma warning(push)
+#pragma warning(disable:4100) // unreferenced formal parameter
+#endif
+
+ template <class T>
+ inline void destroy(T* x) {
+ x->~T();
+ }
+
+#if defined(BOOST_MSVC)
+#pragma warning(pop)
+#endif
////////////////////////////////////////////////////////////////////////////
// convert double to std::size_t
@@ -95,12 +172,19 @@
////////////////////////////////////////////////////////////////////////////
// pair_cast - because some libraries don't have the full pair constructors.
+#if 0
template <class Dst1, class Dst2, class Src1, class Src2>
inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x)
{
return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second));
}
+#define BOOST_UNORDERED_PAIR_CAST(First, Last, Argument) \
+ ::boost::unordered::detail::pair_cast<First, Last>(Argument)
+#else
+#define BOOST_UNORDERED_PAIR_CAST(First, Last, Argument) \
+ Argument
+#endif
////////////////////////////////////////////////////////////////////////////
// insert_size/initial_size
@@ -116,13 +200,13 @@
#endif
template <class I>
- inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag)
+ inline std::size_t insert_size(I i, I j, ::boost::forward_traversal_tag)
{
return std::distance(i, j);
}
template <class I>
- inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag)
+ inline std::size_t insert_size(I, I, ::boost::incrementable_traversal_tag)
{
return 1;
}
@@ -130,202 +214,18 @@
template <class I>
inline std::size_t insert_size(I i, I j)
{
- BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type
+ BOOST_DEDUCED_TYPENAME ::boost::iterator_traversal<I>::type
iterator_traversal_tag;
return insert_size(i, j, iterator_traversal_tag);
}
template <class I>
inline std::size_t initial_size(I i, I j,
- std::size_t num_buckets = boost::unordered_detail::default_bucket_count)
+ std::size_t num_buckets = ::boost::unordered::detail::default_bucket_count)
{
return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1,
num_buckets);
}
-
- ////////////////////////////////////////////////////////////////////////////
- // Node Constructors
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
-
- template <class T, class... Args>
- inline void construct_impl(T*, void* address, Args&&... args)
- {
- new(address) T(std::forward<Args>(args)...);
- }
-
-#if defined(BOOST_UNORDERED_CPP0X_PAIR)
- template <class First, class Second, class Key, class Arg0, class... Args>
- inline void construct_impl(std::pair<First, Second>*, void* address,
- Key&& k, Arg0&& arg0, Args&&... args)
- )
- {
- new(address) std::pair<First, Second>(k,
- Second(arg0, std::forward<Args>(args)...);
- }
-#endif
-
-#else
-
-#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
- template < \
- class T, \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
- > \
- inline void construct_impl( \
- T*, void* address, \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
- ) \
- { \
- new(address) T( \
- BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \
- } \
- \
- template <class First, class Second, class Key, \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
- > \
- inline void construct_impl( \
- std::pair<First, Second>*, void* address, \
- Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \
- { \
- new(address) std::pair<First, Second>(k, \
- Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \
- }
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_CONSTRUCT_IMPL, _)
-
-#undef BOOST_UNORDERED_CONSTRUCT_IMPL
-#endif
-
- // hash_node_constructor
- //
- // Used to construct nodes in an exception safe manner.
-
- template <class Alloc, class Grouped>
- class hash_node_constructor
- {
- typedef hash_buckets<Alloc, Grouped> buckets;
- typedef BOOST_DEDUCED_TYPENAME buckets::node node;
- typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr;
- typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type;
-
- buckets& buckets_;
- real_node_ptr node_;
- bool node_constructed_;
- bool value_constructed_;
-
- public:
-
- hash_node_constructor(buckets& m) :
- buckets_(m),
- node_(),
- node_constructed_(false),
- value_constructed_(false)
- {
- }
-
- ~hash_node_constructor();
- void construct_preamble();
-
-#if defined(BOOST_UNORDERED_STD_FORWARD)
- template <class... Args>
- void construct(Args&&... args)
- {
- construct_preamble();
- construct_impl((value_type*) 0, node_->address(),
- std::forward<Args>(args)...);
- value_constructed_ = true;
- }
-#else
-
-#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \
- template < \
- BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
- > \
- void construct( \
- BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
- ) \
- { \
- construct_preamble(); \
- construct_impl( \
- (value_type*) 0, node_->address(), \
- BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
- ); \
- value_constructed_ = true; \
- }
-
- BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
- BOOST_UNORDERED_CONSTRUCT, _)
-
-#undef BOOST_UNORDERED_CONSTRUCT
-
-#endif
- template <class K, class M>
- void construct_pair(K const& k, M*)
- {
- construct_preamble();
- new(node_->address()) value_type(k, M());
- value_constructed_ = true;
- }
-
- value_type& value() const
- {
- BOOST_ASSERT(node_);
- return node_->value();
- }
-
- // no throw
- BOOST_DEDUCED_TYPENAME buckets::node_ptr release()
- {
- real_node_ptr p = node_;
- node_ = real_node_ptr();
- // node_ptr cast
- return buckets_.bucket_alloc().address(*p);
- }
-
- private:
- hash_node_constructor(hash_node_constructor const&);
- hash_node_constructor& operator=(hash_node_constructor const&);
- };
-
- // hash_node_constructor
-
- template <class Alloc, class Grouped>
- inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor()
- {
- if (node_) {
- if (value_constructed_) {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { hash_node<Alloc, Grouped> x; };
-#endif
- boost::unordered_detail::destroy(node_->value_ptr());
- }
-
- if (node_constructed_)
- buckets_.node_alloc().destroy(node_);
-
- buckets_.node_alloc().deallocate(node_, 1);
- }
- }
-
- template <class Alloc, class Grouped>
- inline void hash_node_constructor<Alloc, Grouped>::construct_preamble()
- {
- if(!node_) {
- node_constructed_ = false;
- value_constructed_ = false;
-
- node_ = buckets_.node_alloc().allocate(1);
- buckets_.node_alloc().construct(node_, node());
- node_constructed_ = true;
- }
- else {
- BOOST_ASSERT(node_constructed_ && value_constructed_);
- boost::unordered_detail::destroy(node_->value_ptr());
- value_constructed_ = false;
- }
- }
-}}
+}}}
#endif
Modified: trunk/boost/unordered/unordered_map.hpp
==============================================================================
--- trunk/boost/unordered/unordered_map.hpp (original)
+++ trunk/boost/unordered/unordered_map.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -54,15 +54,15 @@
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<
+ ::boost::unordered::detail::rebind_wrap<
allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::map<K, H, P,
+ typedef ::boost::unordered::detail::map<K, H, P,
value_allocator> types;
typedef BOOST_DEDUCED_TYPENAME types::impl table;
- typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME types::node_ptr node_ptr;
public:
@@ -78,18 +78,14 @@
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::ungrouped>
- const_local_iterator;
- typedef boost::unordered_detail::hash_local_iterator<
- value_allocator, boost::unordered_detail::ungrouped>
- local_iterator;
- typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::ungrouped>
- const_iterator;
- typedef boost::unordered_detail::hash_iterator<
- value_allocator, boost::unordered_detail::ungrouped>
- iterator;
+ typedef ::boost::unordered::iterator_detail::cl_iterator<
+ value_allocator, true> const_local_iterator;
+ typedef ::boost::unordered::iterator_detail::l_iterator<
+ value_allocator, true> local_iterator;
+ typedef ::boost::unordered::iterator_detail::c_iterator<
+ value_allocator, true> const_iterator;
+ typedef ::boost::unordered::iterator_detail::iterator<
+ value_allocator, true> iterator;
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
private:
@@ -97,10 +93,10 @@
table table_;
- BOOST_DEDUCED_TYPENAME types::iterator_base const&
+ BOOST_DEDUCED_TYPENAME types::node_ptr const&
get(const_iterator const& it)
{
- return boost::unordered_detail::iterator_access::get(it);
+ return ::boost::unordered::detail::iterator_access::get(it);
}
public:
@@ -108,120 +104,59 @@
// construct/destroy/copy
explicit unordered_map(
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(n, hf, eql, a)
- {
- }
+ size_type = ::boost::unordered::detail::default_bucket_count,
+ const hasher& = hasher(),
+ const key_equal& = key_equal(),
+ const allocator_type& = allocator_type());
- explicit unordered_map(allocator_type const& a)
- : table_(boost::unordered_detail::default_bucket_count,
- hasher(), key_equal(), a)
- {
- }
+ explicit unordered_map(allocator_type const&);
- unordered_map(unordered_map const& other, allocator_type const& a)
- : table_(other.table_, a)
- {
- }
+ unordered_map(unordered_map const&, allocator_type const&);
template <class InputIt>
- unordered_map(InputIt f, InputIt l)
- : table_(boost::unordered_detail::initial_size(f, l),
- hasher(), key_equal(), allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_map(InputIt f, InputIt l);
template <class InputIt>
- unordered_map(InputIt f, InputIt l,
- size_type n,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n),
- hf, eql, allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_map(
+ InputIt, InputIt,
+ size_type,
+ const hasher& = hasher(),
+ const key_equal& = key_equal());
template <class InputIt>
- 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)
- {
- table_.insert_range(f, l);
- }
-
- ~unordered_map() {}
+ unordered_map(
+ InputIt, InputIt,
+ size_type,
+ const hasher&,
+ const key_equal&,
+ const allocator_type&);
+
+ ~unordered_map();
#if !defined(BOOST_NO_RVALUE_REFERENCES)
- unordered_map(unordered_map const& other)
- : table_(other.table_)
- {
- }
-
- unordered_map(unordered_map&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_map(unordered_map&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_map& operator=(unordered_map const& x)
- {
- table_ = x.table_;
- return *this;
- }
-
- unordered_map& operator=(unordered_map&& x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_map(unordered_map const&);
+ unordered_map(unordered_map&&);
+ unordered_map(unordered_map&&, allocator_type const&);
+ unordered_map& operator=(unordered_map const&);
+ unordered_map& operator=(unordered_map&&);
#else
- unordered_map(boost::unordered_detail::move_from<
- unordered_map<K, T, H, P, A>
- > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
- {
- }
-
+ unordered_map(::boost::unordered::detail::move_from<
+ unordered_map<K,T,H,P,A>
+ >);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
- unordered_map& operator=(unordered_map x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_map& operator=(unordered_map);
#endif
#endif
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- unordered_map(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(
- list.begin(), list.end(), n),
- hf, eql, a)
- {
- table_.insert_range(list.begin(), list.end());
- }
-
- unordered_map& operator=(std::initializer_list<value_type> list)
- {
- table_.clear();
- table_.insert_range(list.begin(), list.end());
- return *this;
- }
+ 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& operator=(std::initializer_list<value_type>);
#endif
allocator_type get_allocator() const
@@ -241,10 +176,7 @@
return table_.size_;
}
- size_type max_size() const
- {
- return table_.max_size();
- }
+ size_type max_size() const;
// iterators
@@ -260,12 +192,12 @@
iterator end()
{
- return iterator(table_.end());
+ return iterator();
}
const_iterator end() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
const_iterator cbegin() const
@@ -275,38 +207,21 @@
const_iterator cend() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
// modifiers
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <class... Args>
- std::pair<iterator, bool> emplace(Args&&... args)
- {
- return boost::unordered_detail::pair_cast<iterator, bool>(
- table_.emplace(std::forward<Args>(args)...));
- }
-
+ std::pair<iterator, bool> emplace(Args&&...);
template <class... Args>
- iterator emplace_hint(const_iterator, Args&&... args)
- {
- return iterator(table_.emplace(std::forward<Args>(args)...).first);
- }
+ iterator emplace_hint(const_iterator, Args&&...);
#else
#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
- std::pair<iterator, bool> emplace(value_type const& v = value_type())
- {
- return boost::unordered_detail::pair_cast<iterator, bool>(
- table_.emplace(v));
- }
-
- iterator emplace_hint(const_iterator,
- value_type const& v = value_type())
- {
- return iterator(table_.emplace(v).first);
- }
+ std::pair<iterator, bool> emplace(value_type const& = value_type());
+ iterator emplace_hint(const_iterator, value_type const& = value_type());
#endif
#define BOOST_UNORDERED_EMPLACE(z, n, _) \
@@ -315,24 +230,14 @@
> \
std::pair<iterator, bool> emplace( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return boost::unordered_detail::pair_cast<iterator, bool>( \
- table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- } \
+ ); \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator emplace_hint(const_iterator, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
- }
+ );
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_EMPLACE, _)
@@ -341,144 +246,57 @@
#endif
- std::pair<iterator, bool> insert(const value_type& obj)
- {
- return boost::unordered_detail::pair_cast<iterator, bool>(
- table_.emplace(obj));
- }
-
- iterator insert(const_iterator, const value_type& obj)
- {
- return iterator(table_.emplace(obj).first);
- }
-
- template <class InputIt>
- void insert(InputIt first, InputIt last)
- {
- table_.insert_range(first, last);
- }
+ std::pair<iterator, bool> insert(const value_type&);
+ iterator insert(const_iterator, const value_type&);
+ template <class InputIt> void insert(InputIt, InputIt);
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- void insert(std::initializer_list<value_type> list)
- {
- table_.insert_range(list.begin(), list.end());
- }
+ void insert(std::initializer_list<value_type>);
#endif
- iterator erase(const_iterator position)
- {
- return iterator(table_.erase_return_iterator(get(position)));
- }
-
- size_type erase(const key_type& k)
- {
- return table_.erase_key(k);
- }
-
- iterator erase(const_iterator first, const_iterator last)
- {
- return iterator(table_.erase_range(get(first), get(last)));
- }
-
- void quick_erase(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void erase_return_void(const_iterator position)
- {
- table_.erase(get(position));
- }
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+ void quick_erase(const_iterator it) { erase(it); }
+ void erase_return_void(const_iterator it) { erase(it); }
- void clear()
- {
- table_.clear();
- }
-
- void swap(unordered_map& other)
- {
- table_.swap(other.table_);
- }
+ void clear();
+ void swap(unordered_map&);
// observers
- hasher hash_function() const
- {
- return table_.hash_function();
- }
-
- key_equal key_eq() const
- {
- return table_.key_eq();
- }
-
- mapped_type& operator[](const key_type &k)
- {
- return table_[k].second;
- }
-
- mapped_type& at(const key_type& k)
- {
- return table_.at(k).second;
- }
+ hasher hash_function() const;
+ key_equal key_eq() const;
- mapped_type const& at(const key_type& k) const
- {
- return table_.at(k).second;
- }
+ 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& k)
- {
- return iterator(table_.find(k));
- }
-
- const_iterator find(const key_type& k) const
- {
- return const_iterator(table_.find(k));
- }
+ iterator find(const key_type&);
+ const_iterator find(const key_type&) const;
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
iterator find(
- CompatibleKey const& k,
- CompatibleHash const& hash,
- CompatiblePredicate const& eq)
- {
- return iterator(table_.find(k, hash, eq));
- }
+ CompatibleKey const&,
+ CompatibleHash const&,
+ CompatiblePredicate const&);
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
const_iterator find(
- CompatibleKey const& k,
- CompatibleHash const& hash,
- CompatiblePredicate const& eq) const
- {
- return iterator(table_.find(k, hash, eq));
- }
+ CompatibleKey const&,
+ CompatibleHash const&,
+ CompatiblePredicate const&) const;
- size_type count(const key_type& k) const
- {
- return table_.count(k);
- }
+ size_type count(const key_type&) const;
std::pair<iterator, iterator>
- equal_range(const key_type& k)
- {
- return boost::unordered_detail::pair_cast<
- iterator, iterator>(
- table_.equal_range(k));
- }
-
+ equal_range(const key_type&);
std::pair<const_iterator, const_iterator>
- equal_range(const key_type& k) const
- {
- return boost::unordered_detail::pair_cast<
- const_iterator, const_iterator>(
- table_.equal_range(k));
- }
+ equal_range(const key_type&) const;
// bucket interface
@@ -492,24 +310,23 @@
return table_.max_bucket_count();
}
- size_type bucket_size(size_type n) const
- {
- return table_.bucket_size(n);
- }
+ size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const
{
- return table_.bucket_index(k);
+ return table_.hash_function()(k) % table_.bucket_count_;
}
local_iterator begin(size_type n)
{
- return local_iterator(table_.bucket_begin(n));
+ return local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -524,7 +341,8 @@
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
@@ -534,65 +352,24 @@
// hash policy
- float load_factor() const
- {
- return table_.load_factor();
- }
-
float max_load_factor() const
{
return table_.mlf_;
}
- void max_load_factor(float m)
- {
- table_.max_load_factor(m);
- }
+ float load_factor() const;
+ void max_load_factor(float);
+ void rehash(size_type n);
- void rehash(size_type n)
- {
- table_.rehash(n);
- }
-
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<K, T, H, P, A>(
- unordered_map const&, unordered_map const&);
- friend bool operator!=<K, T, H, P, A>(
- unordered_map const&, unordered_map const&);
+ friend bool operator==<K,T,H,P,A>(
+ unordered_map const&, unordered_map const&);
+ friend bool operator!=<K,T,H,P,A>(
+ unordered_map const&, unordered_map const&);
#endif
}; // class template unordered_map
template <class K, class T, class H, class P, class A>
- inline bool operator==(unordered_map<K, T, H, P, A> const& m1,
- unordered_map<K, T, H, P, A> const& m2)
- {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { unordered_map<K,T,H,P,A> x; };
-#endif
- return m1.table_.equals(m2.table_);
- }
-
- template <class K, class T, class H, class P, class A>
- inline bool operator!=(unordered_map<K, T, H, P, A> const& m1,
- unordered_map<K, T, H, P, A> const& m2)
- {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { unordered_map<K,T,H,P,A> x; };
-#endif
- return !m1.table_.equals(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)
- {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { unordered_map<K,T,H,P,A> x; };
-#endif
- m1.swap(m2);
- }
-
- template <class K, class T, class H, class P, class A>
class unordered_multimap
{
public:
@@ -609,15 +386,15 @@
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<
+ ::boost::unordered::detail::rebind_wrap<
allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::multimap<K, H, P,
+ typedef ::boost::unordered::detail::multimap<K, H, P,
value_allocator> types;
typedef BOOST_DEDUCED_TYPENAME types::impl table;
- typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME types::node_ptr node_ptr;
public:
@@ -633,18 +410,14 @@
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::grouped>
- const_local_iterator;
- typedef boost::unordered_detail::hash_local_iterator<
- value_allocator, boost::unordered_detail::grouped>
- local_iterator;
- typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::grouped>
- const_iterator;
- typedef boost::unordered_detail::hash_iterator<
- value_allocator, boost::unordered_detail::grouped>
- iterator;
+ typedef ::boost::unordered::iterator_detail::cl_iterator<
+ value_allocator, false> const_local_iterator;
+ typedef ::boost::unordered::iterator_detail::l_iterator<
+ value_allocator, false> local_iterator;
+ typedef ::boost::unordered::iterator_detail::c_iterator<
+ value_allocator, false> const_iterator;
+ typedef ::boost::unordered::iterator_detail::iterator<
+ value_allocator, false> iterator;
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
private:
@@ -652,10 +425,10 @@
table table_;
- BOOST_DEDUCED_TYPENAME types::iterator_base const&
+ BOOST_DEDUCED_TYPENAME types::node_ptr const&
get(const_iterator const& it)
{
- return boost::unordered_detail::iterator_access::get(it);
+ return ::boost::unordered::detail::iterator_access::get(it);
}
public:
@@ -663,121 +436,60 @@
// construct/destroy/copy
explicit unordered_multimap(
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(n, hf, eql, a)
- {
- }
+ size_type = ::boost::unordered::detail::default_bucket_count,
+ const hasher& = hasher(),
+ const key_equal& = key_equal(),
+ const allocator_type& = allocator_type());
- explicit unordered_multimap(allocator_type const& a)
- : table_(boost::unordered_detail::default_bucket_count,
- hasher(), key_equal(), a)
- {
- }
+ explicit unordered_multimap(allocator_type const&);
- unordered_multimap(unordered_multimap const& other,
- allocator_type const& a)
- : table_(other.table_, a)
- {
- }
+ unordered_multimap(unordered_multimap const&, allocator_type const&);
template <class InputIt>
- unordered_multimap(InputIt f, InputIt l)
- : table_(boost::unordered_detail::initial_size(f, l),
- hasher(), key_equal(), allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_multimap(InputIt, InputIt);
template <class InputIt>
- unordered_multimap(InputIt f, InputIt l,
- size_type n,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n),
- hf, eql, allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_multimap(
+ InputIt, InputIt,
+ size_type,
+ const hasher& = hasher(),
+ const key_equal& = key_equal());
template <class InputIt>
- 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)
- {
- table_.insert_range(f, l);
- }
+ unordered_multimap(
+ InputIt, InputIt,
+ size_type,
+ const hasher&,
+ const key_equal&,
+ const allocator_type&);
- ~unordered_multimap() {}
+ ~unordered_multimap();
#if !defined(BOOST_NO_RVALUE_REFERENCES)
- unordered_multimap(unordered_multimap const& other)
- : table_(other.table_)
- {
- }
-
- unordered_multimap(unordered_multimap&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_multimap(unordered_multimap&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_multimap& operator=(unordered_multimap const& x)
- {
- table_ = x.table_;
- return *this;
- }
-
- unordered_multimap& operator=(unordered_multimap&& x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_multimap(unordered_multimap const&);
+ unordered_multimap(unordered_multimap&&);
+ unordered_multimap(unordered_multimap&&, allocator_type const&);
+ unordered_multimap& operator=(unordered_multimap const&);
+ unordered_multimap& operator=(unordered_multimap&&);
#else
- unordered_multimap(boost::unordered_detail::move_from<
- unordered_multimap<K, T, H, P, A>
- > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
- {
- }
+ unordered_multimap(::boost::unordered::detail::move_from<
+ unordered_multimap<K,T,H,P,A>
+ >);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
- unordered_multimap& operator=(unordered_multimap x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_multimap& operator=(unordered_multimap);
#endif
#endif
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- unordered_multimap(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(
- list.begin(), list.end(), n),
- hf, eql, a)
- {
- table_.insert_range(list.begin(), list.end());
- }
-
- unordered_multimap& operator=(std::initializer_list<value_type> list)
- {
- table_.clear();
- table_.insert_range(list.begin(), list.end());
- return *this;
- }
+ 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& operator=(std::initializer_list<value_type>);
#endif
allocator_type get_allocator() const
@@ -797,10 +509,7 @@
return table_.size_;
}
- size_type max_size() const
- {
- return table_.max_size();
- }
+ size_type max_size() const;
// iterators
@@ -816,12 +525,12 @@
iterator end()
{
- return iterator(table_.end());
+ return iterator();
}
const_iterator end() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
const_iterator cbegin() const
@@ -831,36 +540,21 @@
const_iterator cend() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
// modifiers
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <class... Args>
- iterator emplace(Args&&... args)
- {
- return iterator(table_.emplace(std::forward<Args>(args)...));
- }
-
+ iterator emplace(Args&&...);
template <class... Args>
- iterator emplace_hint(const_iterator, Args&&... args)
- {
- return iterator(table_.emplace(std::forward<Args>(args)...));
- }
+ iterator emplace_hint(const_iterator, Args&&...);
#else
#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
- iterator emplace(value_type const& v = value_type())
- {
- return iterator(table_.emplace(v));
- }
-
- iterator emplace_hint(const_iterator,
- value_type const& v = value_type())
- {
- return iterator(table_.emplace(v));
- }
+ iterator emplace(value_type const& = value_type());
+ iterator emplace_hint(const_iterator, value_type const& = value_type());
#endif
#define BOOST_UNORDERED_EMPLACE(z, n, _) \
@@ -869,25 +563,14 @@
> \
iterator emplace( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator( \
- table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- } \
+ ); \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator emplace_hint(const_iterator, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- }
+ );
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_EMPLACE, _)
@@ -896,128 +579,54 @@
#endif
- iterator insert(const value_type& obj)
- {
- return iterator(table_.emplace(obj));
- }
-
- iterator insert(const_iterator, const value_type& obj)
- {
- return iterator(table_.emplace(obj));
- }
-
+ iterator insert(const value_type&);
+ iterator insert(const_iterator, const value_type&);
template <class InputIt>
- void insert(InputIt first, InputIt last)
- {
- table_.insert_range(first, last);
- }
+ void insert(InputIt, InputIt);
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- void insert(std::initializer_list<value_type> list)
- {
- table_.insert_range(list.begin(), list.end());
- }
+ void insert(std::initializer_list<value_type>);
#endif
- iterator erase(const_iterator position)
- {
- return iterator(table_.erase_return_iterator(get(position)));
- }
-
- size_type erase(const key_type& k)
- {
- return table_.erase_key(k);
- }
-
- iterator erase(const_iterator first, const_iterator last)
- {
- return iterator(table_.erase_range(get(first), get(last)));
- }
-
- void quick_erase(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void erase_return_void(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void clear()
- {
- table_.clear();
- }
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+ void quick_erase(const_iterator position) { erase(position); }
+ void erase_return_void(const_iterator position) { erase(position); }
- void swap(unordered_multimap& other)
- {
- table_.swap(other.table_);
- }
+ void clear();
+ void swap(unordered_multimap&);
// observers
- hasher hash_function() const
- {
- return table_.hash_function();
- }
-
- key_equal key_eq() const
- {
- return table_.key_eq();
- }
+ hasher hash_function() const;
+ key_equal key_eq() const;
// lookup
- iterator find(const key_type& k)
- {
- return iterator(table_.find(k));
- }
-
- const_iterator find(const key_type& k) const
- {
- return const_iterator(table_.find(k));
- }
+ iterator find(const key_type&);
+ const_iterator find(const key_type&) const;
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
iterator find(
- CompatibleKey const& k,
- CompatibleHash const& hash,
- CompatiblePredicate const& eq)
- {
- return iterator(table_.find(k, hash, eq));
- }
+ CompatibleKey const&,
+ CompatibleHash const&,
+ CompatiblePredicate const&);
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
const_iterator find(
- CompatibleKey const& k,
- CompatibleHash const& hash,
- CompatiblePredicate const& eq) const
- {
- return iterator(table_.find(k, hash, eq));
- }
+ CompatibleKey const&,
+ CompatibleHash const&,
+ CompatiblePredicate const&) const;
- size_type count(const key_type& k) const
- {
- return table_.count(k);
- }
+ size_type count(const key_type&) const;
std::pair<iterator, iterator>
- equal_range(const key_type& k)
- {
- return boost::unordered_detail::pair_cast<
- iterator, iterator>(
- table_.equal_range(k));
- }
-
+ equal_range(const key_type&);
std::pair<const_iterator, const_iterator>
- equal_range(const key_type& k) const
- {
- return boost::unordered_detail::pair_cast<
- const_iterator, const_iterator>(
- table_.equal_range(k));
- }
+ equal_range(const key_type&) const;
// bucket interface
@@ -1031,24 +640,23 @@
return table_.max_bucket_count();
}
- size_type bucket_size(size_type n) const
- {
- return table_.bucket_size(n);
- }
+ size_type bucket_size(size_type) const;
size_type bucket(const key_type& k) const
{
- return table_.bucket_index(k);
+ return table_.hash_function()(k) % table_.bucket_count_;
}
local_iterator begin(size_type n)
{
- return local_iterator(table_.bucket_begin(n));
+ return local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -1063,7 +671,8 @@
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
@@ -1073,37 +682,879 @@
// hash policy
- float load_factor() const
- {
- return table_.load_factor();
- }
-
float max_load_factor() const
{
return table_.mlf_;
}
- void max_load_factor(float m)
- {
- table_.max_load_factor(m);
- }
-
- void rehash(size_type n)
- {
- table_.rehash(n);
- }
+ float load_factor() const;
+ void max_load_factor(float);
+ void rehash(size_type);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<K, T, H, P, A>(
+ friend bool operator==<K,T,H,P,A>(
unordered_multimap const&, unordered_multimap const&);
- friend bool operator!=<K, T, H, P, A>(
+ friend bool operator!=<K,T,H,P,A>(
unordered_multimap const&, unordered_multimap const&);
#endif
}; // class template unordered_multimap
+////////////////////////////////////////////////////////////////////////////////
+
+ 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 key_equal &eql,
+ const allocator_type &a)
+ : table_(n, hf, eql, a)
+ {
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_map<K,T,H,P,A>::unordered_map(allocator_type const& a)
+ : table_(::boost::unordered::detail::default_bucket_count,
+ hasher(), key_equal(), a)
+ {
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_map<K,T,H,P,A>::unordered_map(
+ unordered_map const& other, allocator_type const& a)
+ : table_(other.table_, a)
+ {
+ }
+
+ 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())
+ {
+ 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 key_equal &eql)
+ : table_(::boost::unordered::detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
+ {
+ 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 key_equal &eql,
+ const allocator_type &a)
+ : table_(::boost::unordered::detail::initial_size(f, l, n), hf, eql, 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() {}
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES)
+ 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(unordered_map&& other)
+ : table_(other.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_map<K,T,H,P,A>::unordered_map(
+ unordered_map&& other, allocator_type const& a)
+ : table_(other.table_, a, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ 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=(unordered_map const& x)
+ {
+ table_ = x.table_;
+ return *this;
+ }
+
+ 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=(unordered_map&& x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#else
+ template <class K, class T, class H, class P, class A>
+ unordered_map<K,T,H,P,A>::unordered_map(
+ ::boost::unordered::detail::move_from<unordered_map<K,T,H,P,A> >
+ other)
+ : table_(other.source.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
+ 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=(unordered_map x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#endif
+#endif
+
+#if !defined(BOOST_NO_0X_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)
+ : table_(
+ ::boost::unordered::detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, a)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+
+ 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());
+ return *this;
+ }
+#endif
+
+ // size and capacity
+
+ template <class K, class T, class H, class P, class A>
+ std::size_t unordered_map<K,T,H,P,A>::max_size() const
+ {
+ return table_.max_size();
+ }
+
+ // modifiers
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+ template <class K, class T, class H, class P, class A>
+ template <class... Args>
+ std::pair<BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator, bool>
+ unordered_map<K,T,H,P,A>::emplace(Args&&... args)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, bool,
+ table_.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator
+ unordered_map<K,T,H,P,A>::emplace_hint(const_iterator, Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...).first);
+ }
+#else
+
+#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
template <class K, class T, class H, class P, class A>
- inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1,
- unordered_multimap<K, T, H, P, A> const& m2)
+ std::pair<BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator, bool>
+ unordered_map<K,T,H,P,A>::emplace(value_type const& v)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, bool, table_.emplace(v));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator
+ unordered_map<K,T,H,P,A>::emplace_hint(
+ const_iterator, value_type const& v)
+ {
+ return iterator(table_.emplace(v).first);
+ }
+#endif
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template <class K, class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ std::pair< \
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator, \
+ bool> \
+ unordered_map<K,T,H,P,A>::emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return \
+ BOOST_UNORDERED_PAIR_CAST(iterator, bool, \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ } \
+ \
+ template <class K, class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator \
+ unordered_map<K,T,H,P,A>::emplace_hint( \
+ const_iterator, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ template <class K, class T, class H, class P, class A>
+ std::pair<BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator, bool>
+ unordered_map<K,T,H,P,A>::insert(const value_type& obj)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, bool, table_.insert(obj));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator
+ unordered_map<K,T,H,P,A>::insert(const_iterator, const value_type& obj)
+ {
+ return iterator(table_.emplace(obj).first);
+ }
+
+ 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 !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ 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());
+ }
+#endif
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator
+ unordered_map<K,T,H,P,A>::erase(const_iterator position)
+ {
+ return iterator(table_.erase(get(position)));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_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);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator
+ unordered_map<K,T,H,P,A>::erase(
+ const_iterator first, const_iterator last)
+ {
+ return iterator(table_.erase_range(get(first), get(last)));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_map<K,T,H,P,A>::clear()
+ {
+ table_.clear();
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_map<K,T,H,P,A>::swap(unordered_map& other)
+ {
+ table_.swap(other.table_);
+ }
+
+ // observers
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::hasher
+ unordered_map<K,T,H,P,A>::hash_function() const
+ {
+ return table_.hash_function();
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::key_equal
+ 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>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::mapped_type&
+ unordered_map<K,T,H,P,A>::operator[](const key_type &k)
+ {
+ return table_[k].second;
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_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>
+ BOOST_DEDUCED_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>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator
+ unordered_map<K,T,H,P,A>::find(const key_type& k)
+ {
+ return iterator(table_.find_node(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::const_iterator
+ unordered_map<K,T,H,P,A>::find(const key_type& k) const
+ {
+ return const_iterator(table_.find_node(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ BOOST_DEDUCED_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));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ BOOST_DEDUCED_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));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_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);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ std::pair<
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator,
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::iterator>
+ unordered_map<K,T,H,P,A>::equal_range(const key_type& k)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, iterator,
+ table_.equal_range(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ std::pair<
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::const_iterator,
+ BOOST_DEDUCED_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 BOOST_UNORDERED_PAIR_CAST(const_iterator, const_iterator,
+ table_.equal_range(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_map<K,T,H,P,A>::size_type
+ unordered_map<K,T,H,P,A>::bucket_size(size_type n) const
+ {
+ return table_.bucket_size(n);
+ }
+
+ // hash policy
+
+ template <class K, class T, class H, class P, class A>
+ float unordered_map<K,T,H,P,A>::load_factor() const
+ {
+ return table_.load_factor();
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_map<K,T,H,P,A>::max_load_factor(float m)
+ {
+ table_.max_load_factor(m);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_map<K,T,H,P,A>::rehash(size_type n)
+ {
+ table_.rehash(n);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator==(
+ unordered_map<K,T,H,P,A> const& m1,
+ unordered_map<K,T,H,P,A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_map<K,T,H,P,A> x; };
+#endif
+ return m1.table_.equals(m2.table_);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator!=(
+ unordered_map<K,T,H,P,A> const& m1,
+ unordered_map<K,T,H,P,A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_map<K,T,H,P,A> x; };
+#endif
+ return !m1.table_.equals(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)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_map<K,T,H,P,A> x; };
+#endif
+ m1.swap(m2);
+ }
+
+////////////////////////////////////////////////////////////////////////////////
+
+ 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 key_equal &eql,
+ const allocator_type &a)
+ : table_(n, hf, eql, a)
+ {
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_multimap<K,T,H,P,A>::unordered_multimap(allocator_type const& a)
+ : table_(::boost::unordered::detail::default_bucket_count,
+ hasher(), key_equal(), a)
+ {
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_multimap<K,T,H,P,A>::unordered_multimap(
+ unordered_multimap const& other, allocator_type const& a)
+ : table_(other.table_, a)
+ {
+ }
+
+ 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())
+ {
+ 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,
+ size_type n,
+ const hasher &hf,
+ const key_equal &eql)
+ : table_(::boost::unordered::detail::initial_size(f, l, n),
+ hf, eql, allocator_type())
+ {
+ 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,
+ 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)
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_multimap<K,T,H,P,A>::~unordered_multimap() {}
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES)
+ 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(
+ unordered_multimap&& other)
+ : table_(other.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ template <class K, class T, class H, class P, class A>
+ unordered_multimap<K,T,H,P,A>::unordered_multimap(
+ unordered_multimap&& other, allocator_type const& a)
+ : table_(other.table_, a, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ 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=(unordered_multimap const& x)
+ {
+ table_ = x.table_;
+ return *this;
+ }
+
+ 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=(unordered_multimap&& x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+
+#else
+
+ template <class K, class T, class H, class P, class A>
+ unordered_multimap<K,T,H,P,A>::unordered_multimap(
+ ::boost::unordered::detail::move_from<
+ unordered_multimap<K,T,H,P,A> > other)
+ : table_(other.source.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
+ 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=(unordered_multimap x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#endif
+#endif
+
+#if !defined(BOOST_NO_0X_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)
+ : table_(
+ ::boost::unordered::detail::initial_size(
+ list.begin(), list.end(), n),
+ hf, eql, a)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+
+ 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());
+ return *this;
+ }
+#endif
+
+ // size and capacity
+
+ template <class K, class T, class H, class P, class A>
+ std::size_t unordered_multimap<K,T,H,P,A>::max_size() const
+ {
+ return table_.max_size();
+ }
+
+ // modifiers
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template <class K, class T, class H, class P, class A>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::emplace(Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::emplace_hint(
+ const_iterator, Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...));
+ }
+
+#else
+
+#if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100))
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::emplace(value_type const& v)
+ {
+ return iterator(table_.emplace(v));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::emplace_hint(
+ const_iterator, value_type const& v)
+ {
+ return iterator(table_.emplace(v));
+ }
+#endif
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template <class K, class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator \
+ unordered_multimap<K,T,H,P,A>::emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ } \
+ \
+ template <class K, class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator \
+ unordered_multimap<K,T,H,P,A>::emplace_hint( \
+ const_iterator, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::insert(const value_type& obj)
+ {
+ return iterator(table_.emplace(obj));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::insert(
+ const_iterator, const value_type& obj)
+ {
+ return iterator(table_.emplace(obj));
+ }
+
+ 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);
+ }
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ 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());
+ }
+#endif
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::erase(const_iterator position)
+ {
+ return iterator(table_.erase(get(position)));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_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);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::erase(
+ const_iterator first, const_iterator last)
+ {
+ return iterator(table_.erase_range(get(first), get(last)));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_multimap<K,T,H,P,A>::clear()
+ {
+ table_.clear();
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_multimap<K,T,H,P,A>::swap(unordered_multimap& other)
+ {
+ table_.swap(other.table_);
+ }
+
+ // observers
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::hasher
+ unordered_multimap<K,T,H,P,A>::hash_function() const
+ {
+ return table_.hash_function();
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::key_equal
+ unordered_multimap<K,T,H,P,A>::key_eq() const
+ {
+ return table_.key_eq();
+ }
+
+ // lookup
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator
+ unordered_multimap<K,T,H,P,A>::find(const key_type& k)
+ {
+ return iterator(table_.find_node(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::const_iterator
+ unordered_multimap<K,T,H,P,A>::find(const key_type& k) const
+ {
+ return const_iterator(table_.find_node(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ BOOST_DEDUCED_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));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ BOOST_DEDUCED_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));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_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);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ std::pair<
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator,
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::iterator>
+ unordered_multimap<K,T,H,P,A>::equal_range(const key_type& k)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, iterator,
+ table_.equal_range(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ std::pair<
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::const_iterator,
+ BOOST_DEDUCED_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 BOOST_UNORDERED_PAIR_CAST(const_iterator, const_iterator,
+ table_.equal_range(k));
+ }
+
+ template <class K, class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multimap<K,T,H,P,A>::size_type
+ unordered_multimap<K,T,H,P,A>::bucket_size(size_type n) const
+ {
+ return table_.bucket_size(n);
+ }
+
+ // hash policy
+
+ template <class K, class T, class H, class P, class A>
+ float unordered_multimap<K,T,H,P,A>::load_factor() const
+ {
+ return table_.load_factor();
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_multimap<K,T,H,P,A>::max_load_factor(float m)
+ {
+ table_.max_load_factor(m);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ void unordered_multimap<K,T,H,P,A>::rehash(size_type n)
+ {
+ table_.rehash(n);
+ }
+
+ template <class K, class T, class H, class P, class A>
+ inline bool operator==(
+ unordered_multimap<K,T,H,P,A> const& m1,
+ unordered_multimap<K,T,H,P,A> const& m2)
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy { unordered_multimap<K,T,H,P,A> x; };
@@ -1112,8 +1563,9 @@
}
template <class K, class T, class H, class P, class A>
- inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1,
- unordered_multimap<K, T, H, P, A> const& m2)
+ inline bool operator!=(
+ unordered_multimap<K,T,H,P,A> const& m1,
+ unordered_multimap<K,T,H,P,A> const& m2)
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy { unordered_multimap<K,T,H,P,A> x; };
@@ -1122,8 +1574,9 @@
}
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)
+ inline void swap(
+ unordered_multimap<K,T,H,P,A> &m1,
+ unordered_multimap<K,T,H,P,A> &m2)
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy { unordered_multimap<K,T,H,P,A> x; };
@@ -1131,6 +1584,7 @@
m1.swap(m2);
}
+
} // namespace boost
#if defined(BOOST_MSVC)
Modified: trunk/boost/unordered/unordered_set.hpp
==============================================================================
--- trunk/boost/unordered/unordered_set.hpp (original)
+++ trunk/boost/unordered/unordered_set.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -54,15 +54,15 @@
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<
+ ::boost::unordered::detail::rebind_wrap<
allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::set<H, P,
+ typedef ::boost::unordered::detail::set<H, P,
value_allocator> types;
typedef BOOST_DEDUCED_TYPENAME types::impl table;
- typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME types::node_ptr node_ptr;
public:
@@ -78,12 +78,10 @@
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::ungrouped>
- const_local_iterator;
- typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::ungrouped>
- const_iterator;
+ typedef ::boost::unordered::iterator_detail::cl_iterator<
+ value_allocator, true> const_local_iterator;
+ typedef ::boost::unordered::iterator_detail::c_iterator<
+ value_allocator, true> const_iterator;
typedef const_local_iterator local_iterator;
typedef const_iterator iterator;
@@ -93,10 +91,10 @@
table table_;
- BOOST_DEDUCED_TYPENAME types::iterator_base const&
+ BOOST_DEDUCED_TYPENAME types::node_ptr const&
get(const_iterator const& it)
{
- return boost::unordered_detail::iterator_access::get(it);
+ return ::boost::unordered::detail::iterator_access::get(it);
}
public:
@@ -104,118 +102,59 @@
// construct/destroy/copy
explicit unordered_set(
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(n, hf, eql, a)
- {
- }
+ size_type = ::boost::unordered::detail::default_bucket_count,
+ const hasher& = hasher(),
+ const key_equal& = key_equal(),
+ const allocator_type& = allocator_type());
- explicit unordered_set(allocator_type const& a)
- : table_(boost::unordered_detail::default_bucket_count,
- hasher(), key_equal(), a)
- {
- }
+ explicit unordered_set(allocator_type const&);
- unordered_set(unordered_set const& other, allocator_type const& a)
- : table_(other.table_, a)
- {
- }
+ unordered_set(unordered_set const&, allocator_type const&);
template <class InputIt>
- unordered_set(InputIt f, InputIt l)
- : table_(boost::unordered_detail::initial_size(f, l),
- hasher(), key_equal(), allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_set(InputIt f, InputIt l);
template <class InputIt>
- unordered_set(InputIt f, InputIt l, size_type n,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n),
- hf, eql, allocator_type())
- {
- table_.insert_range(f, l);
- }
-
+ unordered_set(
+ InputIt, InputIt,
+ size_type,
+ const hasher& = hasher(),
+ const key_equal& = key_equal());
+
template <class InputIt>
- unordered_set(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)
- {
- table_.insert_range(f, l);
- }
+ unordered_set(
+ InputIt, InputIt,
+ size_type,
+ const hasher&,
+ const key_equal&,
+ const allocator_type&);
- ~unordered_set() {}
+ ~unordered_set();
#if !defined(BOOST_NO_RVALUE_REFERENCES)
- unordered_set(unordered_set const& other)
- : table_(other.table_)
- {
- }
-
- unordered_set(unordered_set&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_set(unordered_set&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_set& operator=(unordered_set const& x)
- {
- table_ = x.table_;
- return *this;
- }
-
- unordered_set& operator=(unordered_set&& x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_set(unordered_set const&);
+ unordered_set(unordered_set&&);
+ unordered_set(unordered_set&&, allocator_type const&);
+ unordered_set& operator=(unordered_set const&);
+ unordered_set& operator=(unordered_set&&);
#else
- unordered_set(boost::unordered_detail::move_from<
- unordered_set<T, H, P, A>
- > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
- {
- }
-
+ unordered_set(::boost::unordered::detail::move_from<
+ unordered_set<T,H,P,A>
+ >);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
- unordered_set& operator=(unordered_set x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_set& operator=(unordered_set);
#endif
#endif
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- unordered_set(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(
- list.begin(), list.end(), n),
- hf, eql, a)
- {
- table_.insert_range(list.begin(), list.end());
- }
-
- unordered_set& operator=(std::initializer_list<value_type> list)
- {
- table_.clear();
- table_.insert_range(list.begin(), list.end());
- return *this;
- }
+ unordered_set(
+ 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_set& operator=(std::initializer_list<value_type>);
#endif
allocator_type get_allocator() const
@@ -235,10 +174,7 @@
return table_.size_;
}
- size_type max_size() const
- {
- return table_.max_size();
- }
+ size_type max_size() const;
// iterators
@@ -254,12 +190,12 @@
iterator end()
{
- return iterator(table_.end());
+ return iterator();
}
const_iterator end() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
const_iterator cbegin() const
@@ -269,37 +205,20 @@
const_iterator cend() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
// modifiers
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <class... Args>
- std::pair<iterator, bool> emplace(Args&&... args)
- {
- return boost::unordered_detail::pair_cast<iterator, bool>(
- table_.emplace(std::forward<Args>(args)...));
- }
-
+ std::pair<iterator, bool> emplace(Args&&...);
template <class... Args>
- iterator emplace_hint(const_iterator, Args&&... args)
- {
- return iterator(table_.emplace(std::forward<Args>(args)...).first);
- }
+ iterator emplace_hint(const_iterator, Args&&...);
#else
- std::pair<iterator, bool> emplace(value_type const& v = value_type())
- {
- return boost::unordered_detail::pair_cast<iterator, bool>(
- table_.emplace(v));
- }
-
- iterator emplace_hint(const_iterator,
- value_type const& v = value_type())
- {
- return iterator(table_.emplace(v).first);
- }
+ std::pair<iterator, bool> emplace(value_type const& = value_type());
+ iterator emplace_hint(const_iterator, value_type const& = value_type());
#define BOOST_UNORDERED_EMPLACE(z, n, _) \
template < \
@@ -307,24 +226,14 @@
> \
std::pair<iterator, bool> emplace( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return boost::unordered_detail::pair_cast<iterator, bool>( \
- table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- } \
+ ); \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator emplace_hint(const_iterator, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
- }
+ );
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_EMPLACE, _)
@@ -333,105 +242,42 @@
#endif
- std::pair<iterator, bool> insert(const value_type& obj)
- {
- return boost::unordered_detail::pair_cast<iterator, bool>(
- table_.emplace(obj));
- }
-
- iterator insert(const_iterator, const value_type& obj)
- {
- return iterator(table_.emplace(obj).first);
- }
-
- template <class InputIt>
- void insert(InputIt first, InputIt last)
- {
- table_.insert_range(first, last);
- }
+ std::pair<iterator, bool> insert(const value_type&);
+ iterator insert(const_iterator, const value_type&);
+ template <class InputIt> void insert(InputIt, InputIt);
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- void insert(std::initializer_list<value_type> list)
- {
- table_.insert_range(list.begin(), list.end());
- }
+ void insert(std::initializer_list<value_type>);
#endif
- iterator erase(const_iterator position)
- {
- return iterator(table_.erase_return_iterator(get(position)));
- }
-
- size_type erase(const key_type& k)
- {
- return table_.erase_key(k);
- }
-
- iterator erase(const_iterator first, const_iterator last)
- {
- return iterator(table_.erase_range(get(first), get(last)));
- }
-
- void quick_erase(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void erase_return_void(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void clear()
- {
- table_.clear();
- }
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+ void quick_erase(const_iterator it) { erase(it); }
+ void erase_return_void(const_iterator it) { erase(it); }
- void swap(unordered_set& other)
- {
- table_.swap(other.table_);
- }
+ void clear();
+ void swap(unordered_set&);
// observers
- hasher hash_function() const
- {
- return table_.hash_function();
- }
-
- key_equal key_eq() const
- {
- return table_.key_eq();
- }
+ hasher hash_function() const;
+ key_equal key_eq() const;
// lookup
- const_iterator find(const key_type& k) const
- {
- return const_iterator(table_.find(k));
- }
+ const_iterator find(const key_type&) const;
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
const_iterator find(
- CompatibleKey const& k,
- CompatibleHash const& hash,
- CompatiblePredicate const& eq) const
- {
- return iterator(table_.find(k, hash, eq));
- }
- size_type count(const key_type& k) const
- {
- return table_.count(k);
- }
+ CompatibleKey const&,
+ CompatibleHash const&,
+ CompatiblePredicate const&) const;
+ size_type count(const key_type&) const;
std::pair<const_iterator, const_iterator>
- equal_range(const key_type& k) const
- {
- return boost::unordered_detail::pair_cast<
- const_iterator, const_iterator>(
- table_.equal_range(k));
- }
+ equal_range(const key_type&) const;
// bucket interface
@@ -445,24 +291,23 @@
return table_.max_bucket_count();
}
- size_type bucket_size(size_type n) const
- {
- return table_.bucket_size(n);
- }
+ size_type bucket_size(size_type n) const;
size_type bucket(const key_type& k) const
{
- return table_.bucket_index(k);
+ return table_.hash_function()(k) % table_.bucket_count_;
}
local_iterator begin(size_type n)
{
- return local_iterator(table_.bucket_begin(n));
+ return local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -477,7 +322,8 @@
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
@@ -487,65 +333,24 @@
// hash policy
- float load_factor() const
- {
- return table_.load_factor();
- }
-
float max_load_factor() const
{
return table_.mlf_;
}
- void max_load_factor(float m)
- {
- table_.max_load_factor(m);
- }
-
- void rehash(size_type n)
- {
- table_.rehash(n);
- }
+ float load_factor() const;
+ void max_load_factor(float);
+ void rehash(size_type n);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<T, H, P, A>(
- unordered_set const&, unordered_set const&);
- friend bool operator!=<T, H, P, A>(
- unordered_set const&, unordered_set const&);
+ friend bool operator==<T,H,P,A>(
+ unordered_set const&, unordered_set const&);
+ friend bool operator!=<T,H,P,A>(
+ unordered_set const&, unordered_set const&);
#endif
}; // class template unordered_set
template <class T, class H, class P, class A>
- inline bool operator==(unordered_set<T, H, P, A> const& m1,
- unordered_set<T, H, P, A> const& m2)
- {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { unordered_set<T,H,P,A> x; };
-#endif
- return m1.table_.equals(m2.table_);
- }
-
- template <class T, class H, class P, class A>
- inline bool operator!=(unordered_set<T, H, P, A> const& m1,
- unordered_set<T, H, P, A> const& m2)
- {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { unordered_set<T,H,P,A> x; };
-#endif
- return !m1.table_.equals(m2.table_);
- }
-
- template <class T, class H, class P, class A>
- inline void swap(unordered_set<T, H, P, A> &m1,
- unordered_set<T, H, P, A> &m2)
- {
-#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
- struct dummy { unordered_set<T,H,P,A> x; };
-#endif
- m1.swap(m2);
- }
-
- template <class T, class H, class P, class A>
class unordered_multiset
{
public:
@@ -561,15 +366,15 @@
#endif
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<
+ ::boost::unordered::detail::rebind_wrap<
allocator_type, value_type>::type
value_allocator;
- typedef boost::unordered_detail::multiset<H, P,
+ typedef ::boost::unordered::detail::multiset<H, P,
value_allocator> types;
typedef BOOST_DEDUCED_TYPENAME types::impl table;
- typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base;
+ typedef BOOST_DEDUCED_TYPENAME types::node_ptr node_ptr;
public:
@@ -585,12 +390,10 @@
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
- typedef boost::unordered_detail::hash_const_local_iterator<
- value_allocator, boost::unordered_detail::grouped>
- const_local_iterator;
- typedef boost::unordered_detail::hash_const_iterator<
- value_allocator, boost::unordered_detail::grouped>
- const_iterator;
+ typedef ::boost::unordered::iterator_detail::cl_iterator<
+ value_allocator, false> const_local_iterator;
+ typedef ::boost::unordered::iterator_detail::c_iterator<
+ value_allocator, false> const_iterator;
typedef const_local_iterator local_iterator;
typedef const_iterator iterator;
@@ -600,10 +403,10 @@
table table_;
- BOOST_DEDUCED_TYPENAME types::iterator_base const&
+ BOOST_DEDUCED_TYPENAME types::node_ptr const&
get(const_iterator const& it)
{
- return boost::unordered_detail::iterator_access::get(it);
+ return ::boost::unordered::detail::iterator_access::get(it);
}
public:
@@ -611,119 +414,60 @@
// construct/destroy/copy
explicit unordered_multiset(
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(n, hf, eql, a)
- {
- }
+ size_type = ::boost::unordered::detail::default_bucket_count,
+ const hasher& = hasher(),
+ const key_equal& = key_equal(),
+ const allocator_type& = allocator_type());
- explicit unordered_multiset(allocator_type const& a)
- : table_(boost::unordered_detail::default_bucket_count,
- hasher(), key_equal(), a)
- {
- }
+ explicit unordered_multiset(allocator_type const&);
- unordered_multiset(unordered_multiset const& other,
- allocator_type const& a)
- : table_(other.table_, a)
- {
- }
+ unordered_multiset(unordered_multiset const&, allocator_type const&);
template <class InputIt>
- unordered_multiset(InputIt f, InputIt l)
- : table_(boost::unordered_detail::initial_size(f, l),
- hasher(), key_equal(), allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_multiset(InputIt, InputIt);
template <class InputIt>
- unordered_multiset(InputIt f, InputIt l, size_type n,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal())
- : table_(boost::unordered_detail::initial_size(f, l, n),
- hf, eql, allocator_type())
- {
- table_.insert_range(f, l);
- }
+ unordered_multiset(
+ InputIt, InputIt,
+ size_type,
+ const hasher& = hasher(),
+ const key_equal& = key_equal());
template <class InputIt>
- unordered_multiset(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)
- {
- table_.insert_range(f, l);
- }
+ unordered_multiset(
+ InputIt, InputIt,
+ size_type,
+ const hasher&,
+ const key_equal&,
+ const allocator_type&);
- ~unordered_multiset() {}
+ ~unordered_multiset();
#if !defined(BOOST_NO_RVALUE_REFERENCES)
- unordered_multiset(unordered_multiset const& other)
- : table_(other.table_)
- {
- }
-
- unordered_multiset(unordered_multiset&& other)
- : table_(other.table_, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_multiset(unordered_multiset&& other, allocator_type const& a)
- : table_(other.table_, a, boost::unordered_detail::move_tag())
- {
- }
-
- unordered_multiset& operator=(unordered_multiset const& x)
- {
- table_ = x.table_;
- return *this;
- }
-
- unordered_multiset& operator=(unordered_multiset&& x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_multiset(unordered_multiset const&);
+ unordered_multiset(unordered_multiset&&);
+ unordered_multiset(unordered_multiset&&, allocator_type const&);
+ unordered_multiset& operator=(unordered_multiset const&);
+ unordered_multiset& operator=(unordered_multiset&&);
#else
- unordered_multiset(boost::unordered_detail::move_from<
- unordered_multiset<T, H, P, A>
- > other)
- : table_(other.source.table_, boost::unordered_detail::move_tag())
- {
- }
+ unordered_multiset(::boost::unordered::detail::move_from<
+ unordered_multiset<T,H,P,A>
+ >);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
- unordered_multiset& operator=(unordered_multiset x)
- {
- table_.move(x.table_);
- return *this;
- }
+ unordered_multiset& operator=(unordered_multiset);
#endif
#endif
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- unordered_multiset(std::initializer_list<value_type> list,
- size_type n = boost::unordered_detail::default_bucket_count,
- const hasher &hf = hasher(),
- const key_equal &eql = key_equal(),
- const allocator_type &a = allocator_type())
- : table_(boost::unordered_detail::initial_size(
- list.begin(), list.end(), n),
- hf, eql, a)
- {
- table_.insert_range(list.begin(), list.end());
- }
-
- unordered_multiset& operator=(std::initializer_list<value_type> list)
- {
- table_.clear();
- table_.insert_range(list.begin(), list.end());
- return *this;
- }
+ unordered_multiset(
+ 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_multiset& operator=(std::initializer_list<value_type>);
#endif
allocator_type get_allocator() const
@@ -743,10 +487,7 @@
return table_.size_;
}
- size_type max_size() const
- {
- return table_.max_size();
- }
+ size_type max_size() const;
// iterators
@@ -762,12 +503,12 @@
iterator end()
{
- return iterator(table_.end());
+ return iterator();
}
const_iterator end() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
const_iterator cbegin() const
@@ -777,35 +518,20 @@
const_iterator cend() const
{
- return const_iterator(table_.end());
+ return const_iterator();
}
// modifiers
#if defined(BOOST_UNORDERED_STD_FORWARD)
template <class... Args>
- iterator emplace(Args&&... args)
- {
- return iterator(table_.emplace(std::forward<Args>(args)...));
- }
-
+ iterator emplace(Args&&...);
template <class... Args>
- iterator emplace_hint(const_iterator, Args&&... args)
- {
- return iterator(table_.emplace(std::forward<Args>(args)...));
- }
+ iterator emplace_hint(const_iterator, Args&&...);
#else
- iterator emplace(value_type const& v = value_type())
- {
- return iterator(table_.emplace(v));
- }
-
- iterator emplace_hint(const_iterator,
- value_type const& v = value_type())
- {
- return iterator(table_.emplace(v));
- }
+ iterator emplace(value_type const& = value_type());
+ iterator emplace_hint(const_iterator, value_type const& = value_type());
#define BOOST_UNORDERED_EMPLACE(z, n, _) \
template < \
@@ -813,23 +539,14 @@
> \
iterator emplace( \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator( \
- table_.emplace(BOOST_UNORDERED_CALL_PARAMS(z, n))); \
- } \
+ ); \
\
template < \
BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
> \
iterator emplace_hint(const_iterator, \
BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
- ) \
- { \
- return iterator(table_.emplace( \
- BOOST_UNORDERED_CALL_PARAMS(z, n) \
- )); \
- }
+ );
BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
BOOST_UNORDERED_EMPLACE, _)
@@ -838,105 +555,43 @@
#endif
- iterator insert(const value_type& obj)
- {
- return iterator(table_.emplace(obj));
- }
-
- iterator insert(const_iterator, const value_type& obj)
- {
- return iterator(table_.emplace(obj));
- }
-
+ iterator insert(const value_type&);
+ iterator insert(const_iterator, const value_type&);
template <class InputIt>
- void insert(InputIt first, InputIt last)
- {
- table_.insert_range(first, last);
- }
+ void insert(InputIt, InputIt);
#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
- void insert(std::initializer_list<value_type> list)
- {
- table_.insert_range(list.begin(), list.end());
- }
+ void insert(std::initializer_list<value_type>);
#endif
- iterator erase(const_iterator position)
- {
- return iterator(table_.erase_return_iterator(get(position)));
- }
-
- size_type erase(const key_type& k)
- {
- return table_.erase_key(k);
- }
-
- iterator erase(const_iterator first, const_iterator last)
- {
- return iterator(table_.erase_range(get(first), get(last)));
- }
-
- void quick_erase(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void erase_return_void(const_iterator position)
- {
- table_.erase(get(position));
- }
-
- void clear()
- {
- table_.clear();
- }
+ iterator erase(const_iterator);
+ size_type erase(const key_type&);
+ iterator erase(const_iterator, const_iterator);
+ void quick_erase(const_iterator position) { erase(position); }
+ void erase_return_void(const_iterator position) { erase(position); }
- void swap(unordered_multiset& other)
- {
- table_.swap(other.table_);
- }
+ void clear();
+ void swap(unordered_multiset&);
// observers
- hasher hash_function() const
- {
- return table_.hash_function();
- }
-
- key_equal key_eq() const
- {
- return table_.key_eq();
- }
+ hasher hash_function() const;
+ key_equal key_eq() const;
// lookup
- const_iterator find(const key_type& k) const
- {
- return const_iterator(table_.find(k));
- }
+ const_iterator find(const key_type&) const;
template <class CompatibleKey, class CompatibleHash,
class CompatiblePredicate>
const_iterator find(
- CompatibleKey const& k,
- CompatibleHash const& hash,
- CompatiblePredicate const& eq) const
- {
- return iterator(table_.find(k, hash, eq));
- }
-
- size_type count(const key_type& k) const
- {
- return table_.count(k);
- }
+ CompatibleKey const&,
+ CompatibleHash const&,
+ CompatiblePredicate const&) const;
+ size_type count(const key_type&) const;
std::pair<const_iterator, const_iterator>
- equal_range(const key_type& k) const
- {
- return boost::unordered_detail::pair_cast<
- const_iterator, const_iterator>(
- table_.equal_range(k));
- }
+ equal_range(const key_type&) const;
// bucket interface
@@ -950,24 +605,23 @@
return table_.max_bucket_count();
}
- size_type bucket_size(size_type n) const
- {
- return table_.bucket_size(n);
- }
+ size_type bucket_size(size_type) const;
size_type bucket(const key_type& k) const
{
- return table_.bucket_index(k);
+ return table_.hash_function()(k) % table_.bucket_count_;
}
local_iterator begin(size_type n)
{
- return local_iterator(table_.bucket_begin(n));
+ return local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator begin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
local_iterator end(size_type)
@@ -982,7 +636,8 @@
const_local_iterator cbegin(size_type n) const
{
- return const_local_iterator(table_.bucket_begin(n));
+ return const_local_iterator(
+ table_.bucket_begin(n), n, table_.bucket_count_);
}
const_local_iterator cend(size_type) const
@@ -992,37 +647,791 @@
// hash policy
- float load_factor() const
- {
- return table_.load_factor();
- }
-
float max_load_factor() const
{
return table_.mlf_;
}
- void max_load_factor(float m)
- {
- table_.max_load_factor(m);
- }
-
- void rehash(size_type n)
- {
- table_.rehash(n);
- }
+ float load_factor() const;
+ void max_load_factor(float);
+ void rehash(size_type);
#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582)
- friend bool operator==<T, H, P, A>(
- unordered_multiset const&, unordered_multiset const&);
- friend bool operator!=<T, H, P, A>(
- unordered_multiset const&, unordered_multiset const&);
+ friend bool operator==<T,H,P,A>(
+ unordered_multiset const&, unordered_multiset const&);
+ friend bool operator!=<T,H,P,A>(
+ unordered_multiset const&, unordered_multiset const&);
#endif
}; // class template unordered_multiset
+////////////////////////////////////////////////////////////////////////////////
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(
+ size_type n, const hasher &hf, const key_equal &eql,
+ const allocator_type &a)
+ : table_(n, hf, eql, a)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(allocator_type const& a)
+ : table_(::boost::unordered::detail::default_bucket_count,
+ hasher(), key_equal(), a)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(
+ unordered_set const& other, allocator_type const& a)
+ : table_(other.table_, a)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ unordered_set<T,H,P,A>::unordered_set(InputIt f, InputIt l)
+ : table_(::boost::unordered::detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ unordered_set<T,H,P,A>::unordered_set(
+ 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())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ unordered_set<T,H,P,A>::unordered_set(
+ 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)
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::~unordered_set() {}
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES)
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(unordered_set const& other)
+ : table_(other.table_)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(unordered_set&& other)
+ : table_(other.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(
+ unordered_set&& other, allocator_type const& a)
+ : table_(other.table_, a, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>& unordered_set<T,H,P,A>::
+ operator=(unordered_set const& x)
+ {
+ table_ = x.table_;
+ return *this;
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>& unordered_set<T,H,P,A>::
+ operator=(unordered_set&& x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#else
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(
+ ::boost::unordered::detail::move_from<unordered_set<T,H,P,A> >
+ other)
+ : table_(other.source.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>& unordered_set<T,H,P,A>::
+ operator=(unordered_set x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#endif
+#endif
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>::unordered_set(
+ 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(list.begin(), list.end());
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_set<T,H,P,A>& unordered_set<T,H,P,A>::operator=(
+ std::initializer_list<value_type> list)
+ {
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
+ return *this;
+ }
+#endif
+
+ // size and capacity
+
+ template <class T, class H, class P, class A>
+ std::size_t unordered_set<T,H,P,A>::max_size() const
+ {
+ return table_.max_size();
+ }
+
+ // modifiers
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+ template <class T, class H, class P, class A>
+ template <class... Args>
+ std::pair<BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator, bool>
+ unordered_set<T,H,P,A>::emplace(Args&&... args)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, bool,
+ table_.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class T, class H, class P, class A>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator
+ unordered_set<T,H,P,A>::emplace_hint(const_iterator, Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...).first);
+ }
+#else
+
+ template <class T, class H, class P, class A>
+ std::pair<BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator, bool>
+ unordered_set<T,H,P,A>::emplace(value_type const& v)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, bool, table_.emplace(v));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator
+ unordered_set<T,H,P,A>::emplace_hint(
+ const_iterator, value_type const& v)
+ {
+ return iterator(table_.emplace(v).first);
+ }
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template <class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ std::pair< \
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator, \
+ bool> \
+ unordered_set<T,H,P,A>::emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return \
+ BOOST_UNORDERED_PAIR_CAST(iterator, bool, \
+ table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ } \
+ \
+ template <class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator \
+ unordered_set<T,H,P,A>::emplace_hint( \
+ const_iterator, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \
+ ) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ template <class T, class H, class P, class A>
+ std::pair<BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator, bool>
+ unordered_set<T,H,P,A>::insert(const value_type& obj)
+ {
+ return BOOST_UNORDERED_PAIR_CAST(iterator, bool, table_.insert(obj));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator
+ unordered_set<T,H,P,A>::insert(const_iterator, const value_type& obj)
+ {
+ return iterator(table_.emplace(obj).first);
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ void unordered_set<T,H,P,A>::insert(InputIt first, InputIt last)
+ {
+ table_.insert_range(first, last);
+ }
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ template <class T, class H, class P, class A>
+ void unordered_set<T,H,P,A>::insert(std::initializer_list<value_type> list)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+#endif
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator
+ unordered_set<T,H,P,A>::erase(const_iterator position)
+ {
+ return iterator(table_.erase(get(position)));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::size_type
+ unordered_set<T,H,P,A>::erase(const key_type& k)
+ {
+ return table_.erase_key(k);
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::iterator
+ unordered_set<T,H,P,A>::erase(const_iterator first, const_iterator last)
+ {
+ return iterator(table_.erase_range(get(first), get(last)));
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_set<T,H,P,A>::clear()
+ {
+ table_.clear();
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_set<T,H,P,A>::swap(unordered_set& other)
+ {
+ table_.swap(other.table_);
+ }
+
+ // observers
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::hasher
+ unordered_set<T,H,P,A>::hash_function() const
+ {
+ return table_.hash_function();
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::key_equal
+ unordered_set<T,H,P,A>::key_eq() const
+ {
+ return table_.key_eq();
+ }
+
+ // lookup
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::const_iterator
+ unordered_set<T,H,P,A>::find(const key_type& k) const
+ {
+ return const_iterator(table_.find_node(k));
+ }
+
+ template <class T, class H, class P, class A>
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::const_iterator
+ unordered_set<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));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::size_type
+ unordered_set<T,H,P,A>::count(const key_type& k) const
+ {
+ return table_.count(k);
+ }
+
+ template <class T, class H, class P, class A>
+ std::pair<
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::const_iterator,
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::const_iterator>
+ unordered_set<T,H,P,A>::equal_range(const key_type& k) const
+ {
+ return BOOST_UNORDERED_PAIR_CAST(const_iterator, const_iterator,
+ table_.equal_range(k));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_set<T,H,P,A>::size_type
+ unordered_set<T,H,P,A>::bucket_size(size_type n) const
+ {
+ return table_.bucket_size(n);
+ }
+
+ // hash policy
+
+ template <class T, class H, class P, class A>
+ float unordered_set<T,H,P,A>::load_factor() const
+ {
+ return table_.load_factor();
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_set<T,H,P,A>::max_load_factor(float m)
+ {
+ table_.max_load_factor(m);
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_set<T,H,P,A>::rehash(size_type n)
+ {
+ table_.rehash(n);
+ }
+
+ template <class T, class H, class P, class A>
+ inline bool operator==(
+ unordered_set<T,H,P,A> const& m1,
+ unordered_set<T,H,P,A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_set<T,H,P,A> x; };
+#endif
+ return m1.table_.equals(m2.table_);
+ }
+
+ template <class T, class H, class P, class A>
+ inline bool operator!=(
+ unordered_set<T,H,P,A> const& m1,
+ unordered_set<T,H,P,A> const& m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_set<T,H,P,A> x; };
+#endif
+ return !m1.table_.equals(m2.table_);
+ }
+
+ template <class T, class H, class P, class A>
+ inline void swap(
+ unordered_set<T,H,P,A> &m1,
+ unordered_set<T,H,P,A> &m2)
+ {
+#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
+ struct dummy { unordered_set<T,H,P,A> x; };
+#endif
+ m1.swap(m2);
+ }
+
+////////////////////////////////////////////////////////////////////////////////
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ size_type n, const hasher &hf, const key_equal &eql,
+ const allocator_type &a)
+ : table_(n, hf, eql, a)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(allocator_type const& a)
+ : table_(::boost::unordered::detail::default_bucket_count,
+ hasher(), key_equal(), a)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ unordered_multiset const& other, allocator_type const& a)
+ : table_(other.table_, a)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ unordered_multiset<T,H,P,A>::unordered_multiset(InputIt f, InputIt l)
+ : table_(::boost::unordered::detail::initial_size(f, l),
+ hasher(), key_equal(), allocator_type())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ 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())
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ 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)
+ {
+ table_.insert_range(f, l);
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::~unordered_multiset() {}
+
+#if !defined(BOOST_NO_RVALUE_REFERENCES)
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ unordered_multiset const& other)
+ : table_(other.table_)
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ unordered_multiset&& other)
+ : table_(other.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ unordered_multiset&& other, allocator_type const& a)
+ : table_(other.table_, a, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>& unordered_multiset<T,H,P,A>::
+ operator=(unordered_multiset const& x)
+ {
+ table_ = x.table_;
+ return *this;
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>& unordered_multiset<T,H,P,A>::
+ operator=(unordered_multiset&& x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+
+#else
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ ::boost::unordered::detail::move_from<unordered_multiset<T,H,P,A> >
+ other)
+ : table_(other.source.table_, ::boost::unordered::detail::move_tag())
+ {
+ }
+
+#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593)
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>& unordered_multiset<T,H,P,A>::
+ operator=(unordered_multiset x)
+ {
+ table_.move(x.table_);
+ return *this;
+ }
+#endif
+#endif
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>::unordered_multiset(
+ 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(list.begin(), list.end());
+ }
+
+ template <class T, class H, class P, class A>
+ unordered_multiset<T,H,P,A>& unordered_multiset<T,H,P,A>::operator=(
+ std::initializer_list<value_type> list)
+ {
+ table_.clear();
+ table_.insert_range(list.begin(), list.end());
+ return *this;
+ }
+#endif
+
+ // size and capacity
+
+ template <class T, class H, class P, class A>
+ std::size_t unordered_multiset<T,H,P,A>::max_size() const
+ {
+ return table_.max_size();
+ }
+
+ // modifiers
+
+#if defined(BOOST_UNORDERED_STD_FORWARD)
+
+ template <class T, class H, class P, class A>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::emplace(Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...));
+ }
+
+ template <class T, class H, class P, class A>
+ template <class... Args>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::emplace_hint(
+ const_iterator, Args&&... args)
+ {
+ return iterator(table_.emplace(std::forward<Args>(args)...));
+ }
+
+#else
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::emplace(value_type const& v)
+ {
+ return iterator(table_.emplace(v));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::emplace_hint(
+ const_iterator, value_type const& v)
+ {
+ return iterator(table_.emplace(v));
+ }
+
+#define BOOST_UNORDERED_EMPLACE(z, n, _) \
+ template <class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator \
+ unordered_multiset<T,H,P,A>::emplace( \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ } \
+ \
+ template <class T, class H, class P, class A> \
+ template < \
+ BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \
+ > \
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator \
+ unordered_multiset<T,H,P,A>::emplace_hint( \
+ const_iterator, \
+ BOOST_UNORDERED_FUNCTION_PARAMS(z, n)) \
+ { \
+ return iterator(table_.emplace( \
+ BOOST_UNORDERED_CALL_PARAMS(z, n))); \
+ }
+
+ BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT,
+ BOOST_UNORDERED_EMPLACE, _)
+
+#undef BOOST_UNORDERED_EMPLACE
+
+#endif
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::insert(const value_type& obj)
+ {
+ return iterator(table_.emplace(obj));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::insert(const_iterator, const value_type& obj)
+ {
+ return iterator(table_.emplace(obj));
+ }
+
+ template <class T, class H, class P, class A>
+ template <class InputIt>
+ void unordered_multiset<T,H,P,A>::insert(InputIt first, InputIt last)
+ {
+ table_.insert_range(first, last);
+ }
+
+#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST)
+ template <class T, class H, class P, class A>
+ void unordered_multiset<T,H,P,A>::insert(std::initializer_list<value_type> list)
+ {
+ table_.insert_range(list.begin(), list.end());
+ }
+#endif
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::erase(const_iterator position)
+ {
+ return iterator(table_.erase(get(position)));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::size_type
+ unordered_multiset<T,H,P,A>::erase(const key_type& k)
+ {
+ return table_.erase_key(k);
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::iterator
+ unordered_multiset<T,H,P,A>::erase(const_iterator first, const_iterator last)
+ {
+ return iterator(table_.erase_range(get(first), get(last)));
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_multiset<T,H,P,A>::clear()
+ {
+ table_.clear();
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_multiset<T,H,P,A>::swap(unordered_multiset& other)
+ {
+ table_.swap(other.table_);
+ }
+
+ // observers
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::hasher
+ unordered_multiset<T,H,P,A>::hash_function() const
+ {
+ return table_.hash_function();
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::key_equal
+ unordered_multiset<T,H,P,A>::key_eq() const
+ {
+ return table_.key_eq();
+ }
+
+ // lookup
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::const_iterator
+ unordered_multiset<T,H,P,A>::find(const key_type& k) const
+ {
+ return const_iterator(table_.find_node(k));
+ }
+
+ template <class T, class H, class P, class A>
+ template <class CompatibleKey, class CompatibleHash,
+ class CompatiblePredicate>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::const_iterator
+ unordered_multiset<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));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::size_type
+ unordered_multiset<T,H,P,A>::count(const key_type& k) const
+ {
+ return table_.count(k);
+ }
+
+ template <class T, class H, class P, class A>
+ std::pair<
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::const_iterator,
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::const_iterator>
+ unordered_multiset<T,H,P,A>::equal_range(const key_type& k) const
+ {
+ return BOOST_UNORDERED_PAIR_CAST(const_iterator, const_iterator,
+ table_.equal_range(k));
+ }
+
+ template <class T, class H, class P, class A>
+ BOOST_DEDUCED_TYPENAME unordered_multiset<T,H,P,A>::size_type
+ unordered_multiset<T,H,P,A>::bucket_size(size_type n) const
+ {
+ return table_.bucket_size(n);
+ }
+
+ // hash policy
+
+ template <class T, class H, class P, class A>
+ float unordered_multiset<T,H,P,A>::load_factor() const
+ {
+ return table_.load_factor();
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_multiset<T,H,P,A>::max_load_factor(float m)
+ {
+ table_.max_load_factor(m);
+ }
+
+ template <class T, class H, class P, class A>
+ void unordered_multiset<T,H,P,A>::rehash(size_type n)
+ {
+ table_.rehash(n);
+ }
+
template <class T, class H, class P, class A>
- inline bool operator==(unordered_multiset<T, H, P, A> const& m1,
- unordered_multiset<T, H, P, A> const& m2)
+ inline bool operator==(
+ unordered_multiset<T,H,P,A> const& m1,
+ unordered_multiset<T,H,P,A> const& m2)
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy { unordered_multiset<T,H,P,A> x; };
@@ -1031,8 +1440,9 @@
}
template <class T, class H, class P, class A>
- inline bool operator!=(unordered_multiset<T, H, P, A> const& m1,
- unordered_multiset<T, H, P, A> const& m2)
+ inline bool operator!=(
+ unordered_multiset<T,H,P,A> const& m1,
+ unordered_multiset<T,H,P,A> const& m2)
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy { unordered_multiset<T,H,P,A> x; };
@@ -1041,8 +1451,9 @@
}
template <class T, class H, class P, class A>
- inline void swap(unordered_multiset<T, H, P, A> &m1,
- unordered_multiset<T, H, P, A> &m2)
+ inline void swap(
+ unordered_multiset<T,H,P,A> &m1,
+ unordered_multiset<T,H,P,A> &m2)
{
#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613))
struct dummy { unordered_multiset<T,H,P,A> x; };
Modified: trunk/libs/unordered/test/helpers/invariants.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/invariants.hpp (original)
+++ trunk/libs/unordered/test/helpers/invariants.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -65,37 +65,32 @@
std::cerr<<x1.count(key)<<","<<count<<"\n";
}
- // I'm not bothering with the following test for now, as the
- // previous test is probably more enough to catch the kind of
- // errors that this would catch (if an element was in the wrong
- // bucket it not be found by the call to count, if elements are not
- // adjacent then they would be caught when checking against
- // found_.
-
- // // Check that the keys are in the correct bucket and are
- // // adjacent in the bucket.
- // BOOST_DEDUCED_TYPENAME X::size_type bucket = x1.bucket(key);
- // BOOST_DEDUCED_TYPENAME X::const_local_iterator
- // lit = x1.begin(bucket), lend = x1.end(bucket);
- // for(; lit != lend && !eq(get_key<X>(*lit), key); ++lit) continue;
- // if(lit == lend)
- // BOOST_ERROR("Unable to find element with a local_iterator");
- // unsigned int count2 = 0;
- // for(; lit != lend && eq(get_key<X>(*lit), key); ++lit) ++count2;
- // if(count != count2)
- // BOOST_ERROR("Element count doesn't match local_iterator.");
- // for(; lit != lend; ++lit) {
- // if(eq(get_key<X>(*lit), key)) {
- // BOOST_ERROR("Non-adjacent element with equivalent key "
- // "in bucket.");
- // break;
- // }
- // }
+ // Check that the keys are in the correct bucket and are
+ // adjacent in the bucket.
+ BOOST_DEDUCED_TYPENAME X::size_type bucket = x1.bucket(key);
+ BOOST_DEDUCED_TYPENAME X::const_local_iterator
+ lit = x1.begin(bucket), lend = x1.end(bucket);
+ for(; lit != lend && !eq(get_key<X>(*lit), key); ++lit) continue;
+ if(lit == lend)
+ BOOST_ERROR("Unable to find element with a local_iterator");
+ unsigned int count2 = 0;
+ for(; lit != lend && eq(get_key<X>(*lit), key); ++lit) ++count2;
+ if(count != count2)
+ BOOST_ERROR("Element count doesn't match local_iterator.");
+ for(; lit != lend; ++lit) {
+ if(eq(get_key<X>(*lit), key)) {
+ BOOST_ERROR("Non-adjacent element with equivalent key "
+ "in bucket.");
+ break;
+ }
+ }
};
// Finally, check that size matches up.
- if(x1.size() != size)
+ if(x1.size() != size) {
BOOST_ERROR("x1.size() doesn't match actual size.");
+ std::cout<<x1.size()<<"/"<<size<<std::endl;
+ }
float load_factor =
static_cast<float>(size) / static_cast<float>(x1.bucket_count());
using namespace std;
Modified: trunk/libs/unordered/test/helpers/memory.hpp
==============================================================================
--- trunk/libs/unordered/test/helpers/memory.hpp (original)
+++ trunk/libs/unordered/test/helpers/memory.hpp 2011-04-16 14:47:33 EDT (Sat, 16 Apr 2011)
@@ -70,7 +70,7 @@
template <class Alloc = std::allocator<int> >
struct memory_tracker {
typedef BOOST_DEDUCED_TYPENAME
- boost::unordered_detail::rebind_wrap<Alloc,
+ ::boost::unordered::detail::rebind_wrap<Alloc,
std::pair<memory_area const, memory_track> >::type
allocator_type;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk