/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2012
+// (C) Copyright Ion Gaztanaga 2006-2014
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
#ifndef BOOST_INTRUSIVE_UNORDERED_SET_HPP
#define BOOST_INTRUSIVE_UNORDERED_SET_HPP
+#if defined(_MSC_VER)
+# pragma once
+#endif
+
#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/intrusive/intrusive_fwd.hpp>
#include <boost/intrusive/hashtable.hpp>
-#include <boost/move/move.hpp>
-#include <iterator>
-
+#include <boost/move/utility_core.hpp>
+#include <boost/static_assert.hpp>
namespace boost {
namespace intrusive {
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
template<class T, class ...Options>
#else
-template<class Config>
+template<class ValueTraits, class Hash, class Equal, class SizeType, class BucketTraits, std::size_t BoolFlags>
#endif
class unordered_set_impl
+ : public hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags>
{
/// @cond
private:
- typedef hashtable_impl<Config> table_type;
+ typedef hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags> table_type;
//! This class is
//! movable
typedef typename implementation_defined::const_node_ptr const_node_ptr;
typedef typename implementation_defined::node_algorithms node_algorithms;
- /// @cond
- private:
- table_type table_;
- /// @endcond
-
public:
//! <b>Requires</b>: buckets must not be being used by any other resource.
//!
//! <b>Notes</b>: buckets array must be disposed only after
//! *this is disposed.
- unordered_set_impl( const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
- : table_(b_traits, hash_func, equal_func, v_traits)
+ explicit unordered_set_impl( const bucket_traits &b_traits
+ , const hasher & hash_func = hasher()
+ , const key_equal &equal_func = key_equal()
+ , const value_traits &v_traits = value_traits())
+ : table_type(b_traits, hash_func, equal_func, v_traits)
{}
//! <b>Requires</b>: buckets must not be being used by any other resource
, const hasher & hash_func = hasher()
, const key_equal &equal_func = key_equal()
, const value_traits &v_traits = value_traits())
- : table_(b_traits, hash_func, equal_func, v_traits)
- { table_.insert_unique(b, e); }
+ : table_type(b_traits, hash_func, equal_func, v_traits)
+ { table_type::insert_unique(b, e); }
//! <b>Effects</b>: to-do
//!
unordered_set_impl(BOOST_RV_REF(unordered_set_impl) x)
- : table_(::boost::move(x.table_))
+ : table_type(::boost::move(static_cast<table_type&>(x)))
{}
//! <b>Effects</b>: to-do
//!
unordered_set_impl& operator=(BOOST_RV_REF(unordered_set_impl) x)
- { table_ = ::boost::move(x.table_); return *this; }
+ { return static_cast<unordered_set_impl&>(table_type::operator=(::boost::move(static_cast<table_type&>(x)))); }
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_set
//! are not deleted (i.e. no destructors are called).
//!
//!
//! <b>Throws</b>: Nothing.
iterator begin()
- { return table_.begin(); }
+ { return table_type::begin(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning
//! of the unordered_set.
//!
//! <b>Throws</b>: Nothing.
const_iterator begin() const
- { return table_.begin(); }
+ { return table_type::begin(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning
//! of the unordered_set.
//!
//! <b>Throws</b>: Nothing.
const_iterator cbegin() const
- { return table_.cbegin(); }
+ { return table_type::cbegin(); }
//! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_set.
//!
//!
//! <b>Throws</b>: Nothing.
iterator end()
- { return table_.end(); }
+ { return table_type::end(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set.
//!
//!
//! <b>Throws</b>: Nothing.
const_iterator end() const
- { return table_.end(); }
+ { return table_type::end(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set.
//!
//!
//! <b>Throws</b>: Nothing.
const_iterator cend() const
- { return table_.cend(); }
+ { return table_type::cend(); }
//! <b>Effects</b>: Returns the hasher object used by the unordered_set.
//!
//!
//! <b>Throws</b>: If hasher copy-constructor throws.
hasher hash_function() const
- { return table_.hash_function(); }
+ { return table_type::hash_function(); }
//! <b>Effects</b>: Returns the key_equal object used by the unordered_set.
//!
//!
//! <b>Throws</b>: If key_equal copy-constructor throws.
key_equal key_eq() const
- { return table_.key_eq(); }
+ { return table_type::key_eq(); }
//! <b>Effects</b>: Returns true if the container is empty.
//!
//!
//! <b>Throws</b>: Nothing.
bool empty() const
- { return table_.empty(); }
+ { return table_type::empty(); }
//! <b>Effects</b>: Returns the number of elements stored in the unordered_set.
//!
//!
//! <b>Throws</b>: Nothing.
size_type size() const
- { return table_.size(); }
+ { return table_type::size(); }
//! <b>Requires</b>: the hasher and the equality function unqualified swap
//! call should not throw.
//! <b>Throws</b>: If the swap() call for the comparison or hash functors
//! found using ADL throw. Basic guarantee.
void swap(unordered_set_impl& other)
- { table_.swap(other.table_); }
+ { table_type::swap(other.table_); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//! Cloner should yield to nodes that compare equal and produce the same
//! throws. Basic guarantee.
template <class Cloner, class Disposer>
void clone_from(const unordered_set_impl &src, Cloner cloner, Disposer disposer)
- { table_.clone_from(src.table_, cloner, disposer); }
+ { table_type::clone_from(src.table_, cloner, disposer); }
+
+ #endif //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Requires</b>: value must be an lvalue
//!
//! <b>Note</b>: Does not affect the validity of iterators and references.
//! No copy-constructors are called.
std::pair<iterator, bool> insert(reference value)
- { return table_.insert_unique(value); }
+ { return table_type::insert_unique(value); }
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue
//! of type value_type.
//! No copy-constructors are called.
template<class Iterator>
void insert(Iterator b, Iterator e)
- { table_.insert_unique(b, e); }
+ { table_type::insert_unique(b, e); }
//! <b>Requires</b>: "hasher" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
template<class KeyType, class KeyHasher, class KeyValueEqual>
std::pair<iterator, bool> insert_check
(const KeyType &key, KeyHasher hasher, KeyValueEqual key_value_equal, insert_commit_data &commit_data)
- { return table_.insert_unique_check(key, hasher, key_value_equal, commit_data); }
+ { return table_type::insert_unique_check(key, hasher, key_value_equal, commit_data); }
//! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
//! must have been obtained from a previous call to "insert_check".
//!
//! After a successful rehashing insert_commit_data remains valid.
iterator insert_commit(reference value, const insert_commit_data &commit_data)
- { return table_.insert_unique_commit(value, commit_data); }
+ { return table_type::insert_unique_commit(value, commit_data); }
+
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Effects</b>: Erases the element pointed to by i.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased element. No destructors are called.
void erase(const_iterator i)
- { table_.erase(i); }
+ { table_type::erase(i); }
//! <b>Effects</b>: Erases the range pointed to by b end e.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
void erase(const_iterator b, const_iterator e)
- { table_.erase(b, e); }
+ { table_type::erase(b, e); }
//! <b>Effects</b>: Erases all the elements with the given value.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
size_type erase(const_reference value)
- { return table_.erase(value); }
+ { return table_type::erase(value); }
//! <b>Requires</b>: "hasher" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! to the erased elements. No destructors are called.
template<class KeyType, class KeyHasher, class KeyValueEqual>
size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
- { return table_.erase(key, hash_func, equal_func); }
+ { return table_type::erase(key, hash_func, equal_func); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
, typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0
/// @endcond
)
- { table_.erase_and_dispose(i, disposer); }
+ { table_type::erase_and_dispose(i, disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements.
template<class Disposer>
void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
- { table_.erase_and_dispose(b, e, disposer); }
+ { table_type::erase_and_dispose(b, e, disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements. No destructors are called.
template<class Disposer>
size_type erase_and_dispose(const_reference value, Disposer disposer)
- { return table_.erase_and_dispose(value, disposer); }
+ { return table_type::erase_and_dispose(value, disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements.
template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer>
size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer)
- { return table_.erase_and_dispose(key, hash_func, equal_func, disposer); }
+ { return table_type::erase_and_dispose(key, hash_func, equal_func, disposer); }
//! <b>Effects</b>: Erases all of the elements.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
void clear()
- { return table_.clear(); }
+ { return table_type::clear(); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements. No destructors are called.
template<class Disposer>
void clear_and_dispose(Disposer disposer)
- { return table_.clear_and_dispose(disposer); }
+ { return table_type::clear_and_dispose(disposer); }
//! <b>Effects</b>: Returns the number of contained elements with the given value
//!
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
size_type count(const_reference value) const
- { return table_.find(value) != end(); }
+ { return table_type::find(value) != end(); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! <b>Throws</b>: If hash_func or equal_func throw.
template<class KeyType, class KeyHasher, class KeyValueEqual>
size_type count(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
- { return table_.find(key, hash_func, equal_func) != end(); }
+ { return table_type::find(key, hash_func, equal_func) != end(); }
//! <b>Effects</b>: Finds an iterator to the first element is equal to
//! "value" or end() if that element does not exist.
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
iterator find(const_reference value)
- { return table_.find(value); }
+ { return table_type::find(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! key type. Usually this key is part of the value_type.
template<class KeyType, class KeyHasher, class KeyValueEqual>
iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
- { return table_.find(key, hash_func, equal_func); }
+ { return table_type::find(key, hash_func, equal_func); }
//! <b>Effects</b>: Finds a const_iterator to the first element whose key is
//! "key" or end() if that element does not exist.
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
const_iterator find(const_reference value) const
- { return table_.find(value); }
+ { return table_type::find(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! key type. Usually this key is part of the value_type.
template<class KeyType, class KeyHasher, class KeyValueEqual>
const_iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
- { return table_.find(key, hash_func, equal_func); }
+ { return table_type::find(key, hash_func, equal_func); }
//! <b>Effects</b>: Returns a range containing all elements with values equivalent
//! to value. Returns std::make_pair(this->end(), this->end()) if no such
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
std::pair<iterator,iterator> equal_range(const_reference value)
- { return table_.equal_range(value); }
+ { return table_type::equal_range(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! key type. Usually this key is part of the value_type.
template<class KeyType, class KeyHasher, class KeyValueEqual>
std::pair<iterator,iterator> equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
- { return table_.equal_range(key, hash_func, equal_func); }
+ { return table_type::equal_range(key, hash_func, equal_func); }
//! <b>Effects</b>: Returns a range containing all elements with values equivalent
//! to value. Returns std::make_pair(this->end(), this->end()) if no such
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
std::pair<const_iterator, const_iterator>
equal_range(const_reference value) const
- { return table_.equal_range(value); }
+ { return table_type::equal_range(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
template<class KeyType, class KeyHasher, class KeyValueEqual>
std::pair<const_iterator, const_iterator>
equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
- { return table_.equal_range(key, hash_func, equal_func); }
+ { return table_type::equal_range(key, hash_func, equal_func); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: If the internal hash function throws.
iterator iterator_to(reference value)
- { return table_.iterator_to(value); }
+ { return table_type::iterator_to(value); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: If the internal hash function throws.
const_iterator iterator_to(const_reference value) const
- { return table_.iterator_to(value); }
+ { return table_type::iterator_to(value); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: Nothing.
local_iterator local_iterator_to(reference value)
- { return table_.local_iterator_to(value); }
+ { return table_type::local_iterator_to(value); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: Nothing.
const_local_iterator local_iterator_to(const_reference value) const
- { return table_.local_iterator_to(value); }
+ { return table_type::local_iterator_to(value); }
//! <b>Effects</b>: Returns the number of buckets passed in the constructor
//! or the last rehash function.
//!
//! <b>Throws</b>: Nothing.
size_type bucket_count() const
- { return table_.bucket_count(); }
+ { return table_type::bucket_count(); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//!
//! <b>Throws</b>: Nothing.
size_type bucket_size(size_type n) const
- { return table_.bucket_size(n); }
+ { return table_type::bucket_size(n); }
//! <b>Effects</b>: Returns the index of the bucket in which elements
//! with keys equivalent to k would be found, if any such element existed.
//!
//! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
size_type bucket(const value_type& k) const
- { return table_.bucket(k); }
+ { return table_type::bucket(k); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
template<class KeyType, class KeyHasher>
size_type bucket(const KeyType& k, KeyHasher hash_func) const
- { return table_.bucket(k, hash_func); }
+ { return table_type::bucket(k, hash_func); }
//! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
//! or the last rehash function.
//!
//! <b>Throws</b>: Nothing.
bucket_ptr bucket_pointer() const
- { return table_.bucket_pointer(); }
+ { return table_type::bucket_pointer(); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
local_iterator begin(size_type n)
- { return table_.begin(n); }
+ { return table_type::begin(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator begin(size_type n) const
- { return table_.begin(n); }
+ { return table_type::begin(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator cbegin(size_type n) const
- { return table_.cbegin(n); }
+ { return table_type::cbegin(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
local_iterator end(size_type n)
- { return table_.end(n); }
+ { return table_type::end(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator end(size_type n) const
- { return table_.end(n); }
+ { return table_type::end(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator cend(size_type n) const
- { return table_.cend(n); }
+ { return table_type::cend(n); }
//! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
//! or the same as the old bucket array. new_size is the length of the
//!
//! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
void rehash(const bucket_traits &new_bucket_traits)
- { table_.rehash(new_bucket_traits); }
+ { table_type::rehash(new_bucket_traits); }
//! <b>Requires</b>:
//!
//!
//! <b>Note</b>: this method is only available if incremental<true> option is activated.
bool incremental_rehash(bool grow = true)
- { return table_.incremental_rehash(grow); }
+ { return table_type::incremental_rehash(grow); }
//! <b>Note</b>: this method is only available if incremental<true> option is activated.
bool incremental_rehash(const bucket_traits &new_bucket_traits)
- { return table_.incremental_rehash(new_bucket_traits); }
+ { return table_type::incremental_rehash(new_bucket_traits); }
//! <b>Requires</b>:
//!
//!
//! <b>Throws</b>:
size_type split_count() const
- { return table_.split_count(); }
+ { return table_type::split_count(); }
//! <b>Effects</b>: Returns the nearest new bucket count optimized for
//! the container that is bigger than n. This suggestion can be used
//! <b>Throws</b>: Nothing.
static size_type suggested_lower_bucket_count(size_type n)
{ return table_type::suggested_lower_bucket_count(n); }
+
+ #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
//! Helper metafunction to define an \c unordered_set that yields to the same type when the
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
template<class T, class ...Options>
#else
-template<class T, class O1 = none, class O2 = none
- , class O3 = none, class O4 = none
- , class O5 = none, class O6 = none
- , class O7 = none, class O8 = none
- , class O9 = none, class O10= none
+template<class T, class O1 = void, class O2 = void
+ , class O3 = void, class O4 = void
+ , class O5 = void, class O6 = void
+ , class O7 = void, class O8 = void
+ , class O9 = void, class O10= void
>
#endif
struct make_unordered_set
{
/// @cond
+ typedef typename pack_options
+ < hashtable_defaults,
+ #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
+ O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
+ #else
+ Options...
+ #endif
+ >::type packed_options;
+
+ typedef typename detail::get_value_traits
+ <T, typename packed_options::proto_value_traits>::type value_traits;
+
+ typedef typename make_bucket_traits
+ <T, true, packed_options>::type bucket_traits;
+
typedef unordered_set_impl
- < typename make_hashtable_opt
- <T, true,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
- #else
- Options...
- #endif
- >::type
+ < value_traits
+ , typename packed_options::hash
+ , typename packed_options::equal
+ , typename packed_options::size_type
+ , bucket_traits
+ , (std::size_t(true)*hash_bool_flags::unique_keys_pos)
+ | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
+ | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
+ | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
+ | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
+ | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
> implementation_defined;
+
/// @endcond
typedef implementation_defined type;
};
typedef typename Base::hasher hasher;
typedef typename Base::key_equal key_equal;
- unordered_set ( const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
+ explicit unordered_set ( const bucket_traits &b_traits
+ , const hasher & hash_func = hasher()
+ , const key_equal &equal_func = key_equal()
+ , const value_traits &v_traits = value_traits())
: Base(b_traits, hash_func, equal_func, v_traits)
{}
{}
unordered_set& operator=(BOOST_RV_REF(unordered_set) x)
- { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
+ { return static_cast<unordered_set&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); }
};
#endif
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
template<class T, class ...Options>
#else
-template<class Config>
+template<class ValueTraits, class Hash, class Equal, class SizeType, class BucketTraits, std::size_t BoolFlags>
#endif
class unordered_multiset_impl
+ : public hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags>
{
/// @cond
private:
- typedef hashtable_impl<Config> table_type;
+ typedef hashtable_impl<ValueTraits, Hash, Equal, SizeType, BucketTraits, BoolFlags> table_type;
/// @endcond
//Movable
typedef typename implementation_defined::const_node_ptr const_node_ptr;
typedef typename implementation_defined::node_algorithms node_algorithms;
- /// @cond
- private:
- table_type table_;
- /// @endcond
-
public:
//! <b>Requires</b>: buckets must not be being used by any other resource.
//!
//! <b>Notes</b>: buckets array must be disposed only after
//! *this is disposed.
- unordered_multiset_impl ( const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
- : table_(b_traits, hash_func, equal_func, v_traits)
+ explicit unordered_multiset_impl ( const bucket_traits &b_traits
+ , const hasher & hash_func = hasher()
+ , const key_equal &equal_func = key_equal()
+ , const value_traits &v_traits = value_traits())
+ : table_type(b_traits, hash_func, equal_func, v_traits)
{}
//! <b>Requires</b>: buckets must not be being used by any other resource
, const hasher & hash_func = hasher()
, const key_equal &equal_func = key_equal()
, const value_traits &v_traits = value_traits())
- : table_(b_traits, hash_func, equal_func, v_traits)
- { table_.insert_equal(b, e); }
+ : table_type(b_traits, hash_func, equal_func, v_traits)
+ { table_type::insert_equal(b, e); }
//! <b>Effects</b>: to-do
//!
unordered_multiset_impl(BOOST_RV_REF(unordered_multiset_impl) x)
- : table_(::boost::move(x.table_))
+ : table_type(::boost::move(static_cast<table_type&>(x)))
{}
//! <b>Effects</b>: to-do
//!
unordered_multiset_impl& operator=(BOOST_RV_REF(unordered_multiset_impl) x)
- { table_ = ::boost::move(x.table_); return *this; }
+ { return static_cast<unordered_multiset_impl&>(table_type::operator=(::boost::move(static_cast<table_type&>(x)))); }
+
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_multiset
//! are not deleted (i.e. no destructors are called).
//!
//! <b>Throws</b>: Nothing.
iterator begin()
- { return table_.begin(); }
+ { return table_type::begin(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning
//! of the unordered_multiset.
//!
//! <b>Throws</b>: Nothing.
const_iterator begin() const
- { return table_.begin(); }
+ { return table_type::begin(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the beginning
//! of the unordered_multiset.
//!
//! <b>Throws</b>: Nothing.
const_iterator cbegin() const
- { return table_.cbegin(); }
+ { return table_type::cbegin(); }
//! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_multiset.
//!
//!
//! <b>Throws</b>: Nothing.
iterator end()
- { return table_.end(); }
+ { return table_type::end(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_multiset.
//!
//!
//! <b>Throws</b>: Nothing.
const_iterator end() const
- { return table_.end(); }
+ { return table_type::end(); }
//! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_multiset.
//!
//!
//! <b>Throws</b>: Nothing.
const_iterator cend() const
- { return table_.cend(); }
+ { return table_type::cend(); }
//! <b>Effects</b>: Returns the hasher object used by the unordered_set.
//!
//!
//! <b>Throws</b>: If hasher copy-constructor throws.
hasher hash_function() const
- { return table_.hash_function(); }
+ { return table_type::hash_function(); }
//! <b>Effects</b>: Returns the key_equal object used by the unordered_multiset.
//!
//!
//! <b>Throws</b>: If key_equal copy-constructor throws.
key_equal key_eq() const
- { return table_.key_eq(); }
+ { return table_type::key_eq(); }
//! <b>Effects</b>: Returns true if the container is empty.
//!
//!
//! <b>Throws</b>: Nothing.
bool empty() const
- { return table_.empty(); }
+ { return table_type::empty(); }
//! <b>Effects</b>: Returns the number of elements stored in the unordered_multiset.
//!
//!
//! <b>Throws</b>: Nothing.
size_type size() const
- { return table_.size(); }
+ { return table_type::size(); }
//! <b>Requires</b>: the hasher and the equality function unqualified swap
//! call should not throw.
//! <b>Throws</b>: If the swap() call for the comparison or hash functors
//! found using ADL throw. Basic guarantee.
void swap(unordered_multiset_impl& other)
- { table_.swap(other.table_); }
+ { table_type::swap(other.table_); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//! Cloner should yield to nodes that compare equal and produce the same
//! throws. Basic guarantee.
template <class Cloner, class Disposer>
void clone_from(const unordered_multiset_impl &src, Cloner cloner, Disposer disposer)
- { table_.clone_from(src.table_, cloner, disposer); }
+ { table_type::clone_from(src.table_, cloner, disposer); }
+
+ #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Requires</b>: value must be an lvalue
//!
//! <b>Note</b>: Does not affect the validity of iterators and references.
//! No copy-constructors are called.
iterator insert(reference value)
- { return table_.insert_equal(value); }
+ { return table_type::insert_equal(value); }
//! <b>Requires</b>: Dereferencing iterator must yield an lvalue
//! of type value_type.
//! No copy-constructors are called.
template<class Iterator>
void insert(Iterator b, Iterator e)
- { table_.insert_equal(b, e); }
+ { table_type::insert_equal(b, e); }
+
+ #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
//! <b>Effects</b>: Erases the element pointed to by i.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased element. No destructors are called.
void erase(const_iterator i)
- { table_.erase(i); }
+ { table_type::erase(i); }
//! <b>Effects</b>: Erases the range pointed to by b end e.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
void erase(const_iterator b, const_iterator e)
- { table_.erase(b, e); }
+ { table_type::erase(b, e); }
//! <b>Effects</b>: Erases all the elements with the given value.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
size_type erase(const_reference value)
- { return table_.erase(value); }
+ { return table_type::erase(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! to the erased elements. No destructors are called.
template<class KeyType, class KeyHasher, class KeyValueEqual>
size_type erase(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
- { return table_.erase(key, hash_func, equal_func); }
+ { return table_type::erase(key, hash_func, equal_func); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
, typename detail::enable_if_c<!detail::is_convertible<Disposer, const_iterator>::value >::type * = 0
/// @endcond
)
- { table_.erase_and_dispose(i, disposer); }
+ { table_type::erase_and_dispose(i, disposer); }
#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
template<class Disposer>
//! to the erased elements.
template<class Disposer>
void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
- { table_.erase_and_dispose(b, e, disposer); }
+ { table_type::erase_and_dispose(b, e, disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements. No destructors are called.
template<class Disposer>
size_type erase_and_dispose(const_reference value, Disposer disposer)
- { return table_.erase_and_dispose(value, disposer); }
+ { return table_type::erase_and_dispose(value, disposer); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements.
template<class KeyType, class KeyHasher, class KeyValueEqual, class Disposer>
size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func, Disposer disposer)
- { return table_.erase_and_dispose(key, hash_func, equal_func, disposer); }
+ { return table_type::erase_and_dispose(key, hash_func, equal_func, disposer); }
//! <b>Effects</b>: Erases all the elements of the container.
//!
//! <b>Note</b>: Invalidates the iterators (but not the references)
//! to the erased elements. No destructors are called.
void clear()
- { return table_.clear(); }
+ { return table_type::clear(); }
//! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
//!
//! to the erased elements. No destructors are called.
template<class Disposer>
void clear_and_dispose(Disposer disposer)
- { return table_.clear_and_dispose(disposer); }
+ { return table_type::clear_and_dispose(disposer); }
//! <b>Effects</b>: Returns the number of contained elements with the given key
//!
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
size_type count(const_reference value) const
- { return table_.count(value); }
+ { return table_type::count(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
template<class KeyType, class KeyHasher, class KeyValueEqual>
size_type count(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
- { return table_.count(key, hash_func, equal_func); }
+ { return table_type::count(key, hash_func, equal_func); }
//! <b>Effects</b>: Finds an iterator to the first element whose value is
//! "value" or end() if that element does not exist.
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
iterator find(const_reference value)
- { return table_.find(value); }
+ { return table_type::find(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! key type. Usually this key is part of the value_type.
template<class KeyType, class KeyHasher, class KeyValueEqual>
iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
- { return table_.find(key, hash_func, equal_func); }
+ { return table_type::find(key, hash_func, equal_func); }
//! <b>Effects</b>: Finds a const_iterator to the first element whose key is
//! "key" or end() if that element does not exist.
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
const_iterator find(const_reference value) const
- { return table_.find(value); }
+ { return table_type::find(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! key type. Usually this key is part of the value_type.
template<class KeyType, class KeyHasher, class KeyValueEqual>
const_iterator find(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
- { return table_.find(key, hash_func, equal_func); }
+ { return table_type::find(key, hash_func, equal_func); }
//! <b>Effects</b>: Returns a range containing all elements with values equivalent
//! to value. Returns std::make_pair(this->end(), this->end()) if no such
//!
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
std::pair<iterator,iterator> equal_range(const_reference value)
- { return table_.equal_range(value); }
+ { return table_type::equal_range(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
template<class KeyType, class KeyHasher, class KeyValueEqual>
std::pair<iterator,iterator> equal_range
(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func)
- { return table_.equal_range(key, hash_func, equal_func); }
+ { return table_type::equal_range(key, hash_func, equal_func); }
//! <b>Effects</b>: Returns a range containing all elements with values equivalent
//! to value. Returns std::make_pair(this->end(), this->end()) if no such
//! <b>Throws</b>: If the internal hasher or the equality functor throws.
std::pair<const_iterator, const_iterator>
equal_range(const_reference value) const
- { return table_.equal_range(value); }
+ { return table_type::equal_range(value); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
template<class KeyType, class KeyHasher, class KeyValueEqual>
std::pair<const_iterator, const_iterator>
equal_range(const KeyType& key, KeyHasher hash_func, KeyValueEqual equal_func) const
- { return table_.equal_range(key, hash_func, equal_func); }
+ { return table_type::equal_range(key, hash_func, equal_func); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_multiset of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: If the hash function throws.
iterator iterator_to(reference value)
- { return table_.iterator_to(value); }
+ { return table_type::iterator_to(value); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_multiset of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: If the hash function throws.
const_iterator iterator_to(const_reference value) const
- { return table_.iterator_to(value); }
+ { return table_type::iterator_to(value); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: Nothing.
local_iterator local_iterator_to(reference value)
- { return table_.local_iterator_to(value); }
+ { return table_type::local_iterator_to(value); }
//! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
//! appropriate type. Otherwise the behavior is undefined.
//!
//! <b>Throws</b>: Nothing.
const_local_iterator local_iterator_to(const_reference value) const
- { return table_.local_iterator_to(value); }
+ { return table_type::local_iterator_to(value); }
//! <b>Effects</b>: Returns the number of buckets passed in the constructor
//! or the last rehash function.
//!
//! <b>Throws</b>: Nothing.
size_type bucket_count() const
- { return table_.bucket_count(); }
+ { return table_type::bucket_count(); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//!
//! <b>Throws</b>: Nothing.
size_type bucket_size(size_type n) const
- { return table_.bucket_size(n); }
+ { return table_type::bucket_size(n); }
//! <b>Effects</b>: Returns the index of the bucket in which elements
//! with keys equivalent to k would be found, if any such element existed.
//!
//! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
size_type bucket(const value_type& k) const
- { return table_.bucket(k); }
+ { return table_type::bucket(k); }
//! <b>Requires</b>: "hash_func" must be a hash function that induces
//! the same hash values as the stored hasher. The difference is that
//! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
template<class KeyType, class KeyHasher>
size_type bucket(const KeyType& k, const KeyHasher &hash_func) const
- { return table_.bucket(k, hash_func); }
+ { return table_type::bucket(k, hash_func); }
//! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
//! or the last rehash function.
//!
//! <b>Throws</b>: Nothing.
bucket_ptr bucket_pointer() const
- { return table_.bucket_pointer(); }
+ { return table_type::bucket_pointer(); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
local_iterator begin(size_type n)
- { return table_.begin(n); }
+ { return table_type::begin(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator begin(size_type n) const
- { return table_.begin(n); }
+ { return table_type::begin(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator cbegin(size_type n) const
- { return table_.cbegin(n); }
+ { return table_type::cbegin(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
local_iterator end(size_type n)
- { return table_.end(n); }
+ { return table_type::end(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator end(size_type n) const
- { return table_.end(n); }
+ { return table_type::end(n); }
//! <b>Requires</b>: n is in the range [0, this->bucket_count()).
//!
//! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
//! containing all of the elements in the nth bucket.
const_local_iterator cend(size_type n) const
- { return table_.cend(n); }
+ { return table_type::cend(n); }
//! <b>Requires</b>: new_buckets must be a pointer to a new bucket array
//! or the same as the old bucket array. new_size is the length of the
//!
//! <b>Throws</b>: If the hasher functor throws.
void rehash(const bucket_traits &new_bucket_traits)
- { table_.rehash(new_bucket_traits); }
+ { table_type::rehash(new_bucket_traits); }
//! <b>Requires</b>:
//!
//!
//! <b>Note</b>: this method is only available if incremental<true> option is activated.
bool incremental_rehash(bool grow = true)
- { return table_.incremental_rehash(grow); }
+ { return table_type::incremental_rehash(grow); }
//! <b>Note</b>: this method is only available if incremental<true> option is activated.
bool incremental_rehash(const bucket_traits &new_bucket_traits)
- { return table_.incremental_rehash(new_bucket_traits); }
+ { return table_type::incremental_rehash(new_bucket_traits); }
//! <b>Requires</b>:
//!
//!
//! <b>Throws</b>:
size_type split_count() const
- { return table_.split_count(); }
+ { return table_type::split_count(); }
//! <b>Effects</b>: Returns the nearest new bucket count optimized for
//! the container that is bigger than n. This suggestion can be used
//! <b>Throws</b>: Nothing.
static size_type suggested_lower_bucket_count(size_type n)
{ return table_type::suggested_lower_bucket_count(n); }
+
+ #endif // #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
};
//! Helper metafunction to define an \c unordered_multiset that yields to the same type when the
#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
template<class T, class ...Options>
#else
-template<class T, class O1 = none, class O2 = none
- , class O3 = none, class O4 = none
- , class O5 = none, class O6 = none
- , class O7 = none, class O8 = none
- , class O9 = none, class O10= none
+template<class T, class O1 = void, class O2 = void
+ , class O3 = void, class O4 = void
+ , class O5 = void, class O6 = void
+ , class O7 = void, class O8 = void
+ , class O9 = void, class O10= void
>
#endif
struct make_unordered_multiset
{
/// @cond
+ typedef typename pack_options
+ < hashtable_defaults,
+ #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
+ O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
+ #else
+ Options...
+ #endif
+ >::type packed_options;
+
+ typedef typename detail::get_value_traits
+ <T, typename packed_options::proto_value_traits>::type value_traits;
+
+ typedef typename make_bucket_traits
+ <T, true, packed_options>::type bucket_traits;
+
typedef unordered_multiset_impl
- < typename make_hashtable_opt
- <T, false,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
- #else
- Options...
- #endif
- >::type
+ < value_traits
+ , typename packed_options::hash
+ , typename packed_options::equal
+ , typename packed_options::size_type
+ , bucket_traits
+ , (std::size_t(false)*hash_bool_flags::unique_keys_pos)
+ | (std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
+ | (std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
+ | (std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
+ | (std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
+ | (std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
> implementation_defined;
+
/// @endcond
typedef implementation_defined type;
};
typedef typename Base::hasher hasher;
typedef typename Base::key_equal key_equal;
- unordered_multiset( const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
+ explicit unordered_multiset( const bucket_traits &b_traits
+ , const hasher & hash_func = hasher()
+ , const key_equal &equal_func = key_equal()
+ , const value_traits &v_traits = value_traits())
: Base(b_traits, hash_func, equal_func, v_traits)
{}
{}
unordered_multiset& operator=(BOOST_RV_REF(unordered_multiset) x)
- { this->Base::operator=(::boost::move(static_cast<Base&>(x))); return *this; }
+ { return static_cast<unordered_multiset&>(this->Base::operator=(::boost::move(static_cast<Base&>(x)))); }
};
#endif
projects / platform / upstream / boost.git / blobdiff