1 files changed, 856 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp
new file mode 100644
index 0000000..be4d5e1
--- /dev/null
+++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp
@@ -0,0 +1,856 @@
+
+// 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 insert.hpp
+
+// Template parameters:
+//
+// H = Hash Function
+// P = Predicate
+// A = Value Allocator
+// G = Grouped/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
+
+    // hash_bucket
+    
+    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_() {}
+    };
+
+    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);
+    };
+
+    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);
+        }
+    };
+
+    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;
+        };
+    };
+
+    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;
+        }
+    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();
+        }
+    private:
+        hash_node& operator=(hash_node const&);
+    };
+
+    // Iterator Base
+
+    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_);
+        }
+    };
+
+    // hash_buckets
+    //
+    // This is responsible for allocating and deallocating buckets and nodes.
+    //
+    // Notes:
+    // 1. For the sake exception safety the allocators themselves 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);
+    };
+
+    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_;
+        }
+    };
+
+    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);
+    };
+
+    // Iterator Access
+
+#if !defined(__clang__)
+    class iterator_access
+    {
+    public:
+        template <class Iterator>
+        static BOOST_DEDUCED_TYPENAME Iterator::base const&
+            get(Iterator const& it)
+        {
+            return it.base_;
+        }
+    };
+#else
+    class iterator_access
+    {
+    public:
+        // Note: we access Iterator::base here, rather than in the function
+        // signature to work around a bug in the friend support of an
+        // early version of clang.
+
+        template <class Iterator>
+        struct base
+        {
+            typedef BOOST_DEDUCED_TYPENAME Iterator::base type;
+        };
+    
+        template <class Iterator>
+        static BOOST_DEDUCED_TYPENAME base<Iterator>::type const&
+            get(Iterator const& it)
+        {
+            return it.base_;
+        }
+    };
+#endif
+
+    // Iterators
+
+    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_);
+        }
+        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_);
+        }
+        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
+
+    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