diff options
Diffstat (limited to '3rdParty/Boost/src/boost/unordered/detail/fwd.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/unordered/detail/fwd.hpp | 935 |
1 files changed, 13 insertions, 922 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp index 471d1d2..ee8966b 100644 --- a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp +++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp @@ -1,932 +1,23 @@ -// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. -// Copyright (C) 2005-2009 Daniel James +// Copyright (C) 2008-2011 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_FWD_HPP_INCLUDED +#define BOOST_UNORDERED_FWD_HPP_INCLUDED -#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) +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once #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; - }; -}} +namespace boost +{ +namespace unordered +{ + struct piecewise_construct_t {}; + const piecewise_construct_t piecewise_construct = piecewise_construct_t(); +} +} #endif |