Boost C++ Libraries

boost/unordered/detail/fwd.hpp

// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
// Copyright (C) 2005-2009 Daniel James
// Distributed under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

// This contains the basic data structure, apart from the actual values. There's
// no construction or deconstruction here. So this only depends on the pointer
// type.

#ifndef BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED
#define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED

#include <boost/config.hpp>
#include <boost/iterator.hpp>
#include <boost/compressed_pair.hpp>
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/unordered/detail/allocator_helpers.hpp>
#include <algorithm>

// This header defines most of the classes used to implement the unordered
// containers. It doesn't include the insert methods as they require a lot
// of preprocessor metaprogramming - they are in unique.hpp and equivalent.hpp.

// Template parameters:
//
// H = Hash Function
// P = Predicate
// A = Value Allocator
// G = Bucket group policy, 'grouped' or 'ungrouped'
// E = Key Extractor

#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES)
#   if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION)
        // STLport doesn't have std::forward.
#   else
#       define BOOST_UNORDERED_STD_FORWARD
#   endif
#endif

#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT)
#define BOOST_UNORDERED_EMPLACE_LIMIT 10
#endif

#if !defined(BOOST_UNORDERED_STD_FORWARD)

#include <boost/preprocessor/repetition/enum_params.hpp>
#include <boost/preprocessor/repetition/enum_binary_params.hpp>
#include <boost/preprocessor/repetition/repeat_from_to.hpp>

#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \
    BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg)
#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \
    BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg)
#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \
    BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg)

#endif

namespace boost { namespace unordered_detail {

    static const float minimum_max_load_factor = 1e-3f;
    static const std::size_t default_bucket_count = 11;
    struct move_tag {};

    template <class T> class hash_unique_table;
    template <class T> class hash_equivalent_table;
    template <class Alloc, class Grouped>
    class hash_node_constructor;
    template <class ValueType>
    struct set_extractor;
    template <class Key, class ValueType>
    struct map_extractor;
    struct no_key;

    // Explicitly call a destructor

#if defined(BOOST_MSVC)
#pragma warning(push)
#pragma warning(disable:4100) // unreferenced formal parameter
#endif

    template <class T>
    inline void destroy(T* x) {
        x->~T();
    }

#if defined(BOOST_MSVC)
#pragma warning(pop)
#endif

    ////////////////////////////////////////////////////////////////////////////
    //
    // This section implements buckets and nodes. Here's a rough
    // inheritance diagram, to show how they pull together.
    //
    // For unordered_set/unordered_map:
    //
    // hash_bucket<A>
    //     |
    // ungrouped_node_base<A>     value_base<A::value_type>
    //     |                            |
    //     +--------------+-------------+
    //                    |
    //         hash_node<A, ungrouped>
    //
    // For unordered_multiset/unordered_multimap:
    //
    // hash_bucket<A>
    //     |
    // grouped_node_base<A>       value_base<A::value_type>
    //     |                            |
    //     +--------------+-------------+
    //                    |
    //         hash_node<A, grouped>

    // hash_bucket
    //
    // hash_bucket is used for both the buckets and as a base class for
    // nodes. By using 'bucket_ptr' for 'node_ptr', 'next_' can point
    // to either a bucket or a node. This is used later to implement a
    // sentinel at the end of the bucket array.
    
    template <class A>
    class hash_bucket
    {
        hash_bucket& operator=(hash_bucket const&);
    public:
        typedef hash_bucket<A> bucket;
        typedef BOOST_DEDUCED_TYPENAME
            boost::unordered_detail::rebind_wrap<A, bucket>::type
            bucket_allocator;
        typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr;
        typedef bucket_ptr node_ptr;
    
        node_ptr next_;

        hash_bucket() : next_() {}
    };

    // In containers with equivalent keys (unordered_multimap and
    // unordered_multiset) equivalent nodes are grouped together, in
    // containers with unique keys (unordered_map and unordered_set)
    // individual nodes are treated as groups of one. The following two
    // classes implement the data structure.

    // This is used for containers with unique keys. There are no groups
    // so it doesn't add any extra members, and just treats individual
    // nodes as groups of one.

    template <class A>
    struct ungrouped_node_base : hash_bucket<A> {
        typedef hash_bucket<A> bucket;
        typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
        typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;

        ungrouped_node_base() : bucket() {}
        static inline node_ptr& next_group(node_ptr ptr);
        static inline std::size_t group_count(node_ptr ptr);
        static inline void add_to_bucket(node_ptr n, bucket& b);
        static inline void add_after_node(node_ptr n, node_ptr position);
        static void unlink_node(bucket& b, node_ptr n);
        static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end);
        static void unlink_nodes(bucket& b, node_ptr end);
    };

    // This is used for containers with equivalent keys. It implements a
    // circular list running in the opposite direction to the linked
    // list through the nodes.

    template <class A>
    struct grouped_node_base : hash_bucket<A>
    {
        typedef hash_bucket<A> bucket;
        typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
        typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;

        node_ptr group_prev_;

        grouped_node_base() : bucket(), group_prev_() {}
        static inline node_ptr& next_group(node_ptr ptr);
        static inline node_ptr first_in_group(node_ptr n);
        static inline std::size_t group_count(node_ptr ptr);
        static inline void add_to_bucket(node_ptr n, bucket& b);
        static inline void add_after_node(node_ptr n, node_ptr position);
        static void unlink_node(bucket& b, node_ptr n);
        static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end);
        static void unlink_nodes(bucket& b, node_ptr end);

    private:
        static inline node_ptr split_group(node_ptr split);
        static inline grouped_node_base& get(node_ptr ptr) {
            return static_cast<grouped_node_base&>(*ptr);
        }
    };

    // These two classes implement an easy way to pass around the node
    // group policy classes without the messy template parameters.
    // Whenever you see the template parameter 'G' it's one of these.

    struct ungrouped
    {
        template <class A>
        struct base {
            typedef ungrouped_node_base<A> type;
        };
    };

    struct grouped
    {
        template <class A>
        struct base {
            typedef grouped_node_base<A> type;
        };
    };

    // The space used to store values in a node.

    template <class ValueType>
    struct value_base
    {
        typedef ValueType value_type;
        BOOST_DEDUCED_TYPENAME boost::aligned_storage<
            sizeof(value_type),
            ::boost::alignment_of<value_type>::value>::type data_;

        void* address() {
            return this;
        }
        value_type& value() {
            return *(ValueType*) this;
        }
        value_type* value_ptr() {
            return (ValueType*) this;
        }
    private:
        value_base& operator=(value_base const&);
    };

    // Node
    
    template <class A, class G>
    class hash_node :
        public G::BOOST_NESTED_TEMPLATE base<A>::type,
        public value_base<BOOST_DEDUCED_TYPENAME A::value_type>
    {
    public:
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
        typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr;

        static value_type& get_value(node_ptr p) {
            return static_cast<hash_node&>(*p).value();
        }
        static value_type* get_value_ptr(node_ptr p) {
            return static_cast<hash_node&>(*p).value_ptr();
        }
    private:
        hash_node& operator=(hash_node const&);
    };

    ////////////////////////////////////////////////////////////////////////////
    //
    // Iterator Base
    //
    // This is the iterator used internally, the external iterators are
    // provided by lightweight wrappers (hash_iterator and
    // hast_const_iterator) which provide the full iterator interface.

    template <class A, class G>
    class hash_iterator_base
    {
    public:
        typedef A value_allocator;
        typedef hash_bucket<A> bucket;
        typedef hash_node<A, G> node;
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
        typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
        typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;

        bucket_ptr bucket_;
        node_ptr node_;

        hash_iterator_base() : bucket_(), node_() {}
        explicit hash_iterator_base(bucket_ptr b)
          : bucket_(b),
            node_(b ? b->next_ : node_ptr()) {}
        hash_iterator_base(bucket_ptr b, node_ptr n)
          : bucket_(b),
            node_(n) {}
        
        bool operator==(hash_iterator_base const& x) const {
            return node_ == x.node_; }
        bool operator!=(hash_iterator_base const& x) const {
            return node_ != x.node_; }
        value_type& operator*() const {
            return node::get_value(node_);
        }
    
        void increment_bucket(node_ptr n) {
            while(!n) {
                ++bucket_;
                n = bucket_->next_;
            }
            node_ = bucket_ == n ? node_ptr() : n;
        }

        void increment() {
            increment_bucket(node_->next_);
        }
    };

    ////////////////////////////////////////////////////////////////////////////
    //
    // Now the main data structure:
    //
    // hash_buckets<A, G>     hash_buffered_functions<H, P>
    //       |                            |
    //       +-------------+--------------+
    //                     |
    //                hash_table<T>
    //
    // T is a class which contains typedefs for all the types we need.
    
    // hash_buckets
    //
    // This is responsible for allocating and deallocating buckets and nodes.
    //
    // Notes:
    // 1. For the sake exception safety the consturctors don't allocate
    //    anything.
    // 2. It's the callers responsibility to allocate the buckets before calling
    //    any of the methods (other than getters and setters).

    template <class A, class G>
    class hash_buckets
    {
        hash_buckets(hash_buckets const&);
        hash_buckets& operator=(hash_buckets const&);
    public:
        // Types

        typedef A value_allocator;
        typedef hash_bucket<A> bucket;
        typedef hash_iterator_base<A, G> iterator_base;
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;
        typedef BOOST_DEDUCED_TYPENAME iterator_base::node node;

        typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator
            bucket_allocator;
        typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr;
        typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr;

        typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type
            node_allocator;
        typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr;

        // Members

        bucket_ptr buckets_;
        std::size_t bucket_count_;
        boost::compressed_pair<bucket_allocator, node_allocator> allocators_;
        
        // Data access

        bucket_allocator const& bucket_alloc() const {
            return allocators_.first(); }
        node_allocator const& node_alloc() const {
            return allocators_.second(); }
        bucket_allocator& bucket_alloc() {
            return allocators_.first(); }
        node_allocator& node_alloc() {
            return allocators_.second(); }
        std::size_t max_bucket_count() const;

        // Constructors

        hash_buckets(node_allocator const& a, std::size_t n);
        void create_buckets();
        ~hash_buckets();
        
        // no throw
        void swap(hash_buckets& other);
        void move(hash_buckets& other);

        // For the remaining functions, buckets_ must not be null.
        
        bucket_ptr get_bucket(std::size_t n) const;
        bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const;
        std::size_t bucket_size(std::size_t index) const;
        node_ptr bucket_begin(std::size_t n) const;

        // Alloc/Dealloc
        
        void delete_node(node_ptr);

        // 
        void delete_buckets();
        void clear_bucket(bucket_ptr);
        std::size_t delete_nodes(node_ptr begin, node_ptr end);
        std::size_t delete_to_bucket_end(node_ptr begin);
    };

    // Assigning and swapping the equality and hash function objects
    // needs strong exception safety. To implement that normally we'd
    // require one of them to be known to not throw and the other to
    // guarantee strong exception safety. Unfortunately they both only
    // have basic exception safety. So to acheive strong exception
    // safety we have storage space for two copies, and assign the new
    // copies to the unused space. Then switch to using that to use
    // them. This is implemented in 'set_hash_functions' which
    // atomically assigns the new function objects in a strongly
    // exception safe manner.

    template <class H, class P> class set_hash_functions;

    template <class H, class P>
    class hash_buffered_functions
    {
        friend class set_hash_functions<H, P>;
        hash_buffered_functions& operator=(hash_buffered_functions const&);

        typedef boost::compressed_pair<H, P> function_pair;
        typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage<
            sizeof(function_pair),
            ::boost::alignment_of<function_pair>::value>::type aligned_function;

        bool current_; // The currently active functions.
        aligned_function funcs_[2];

        function_pair const& current() const {
            return *static_cast<function_pair const*>(
                static_cast<void const*>(&funcs_[current_]));
        }

        void construct(bool which, H const& hf, P const& eq)
        {
            new((void*) &funcs_[which]) function_pair(hf, eq);
        }

        void construct(bool which, function_pair const& f)
        {
            new((void*) &funcs_[which]) function_pair(f);
        }
        
        void destroy(bool which)
        {
            boost::unordered_detail::destroy((function_pair*)(&funcs_[which]));
        }
        
    public:

        hash_buffered_functions(H const& hf, P const& eq)
            : current_(false)
        {
            construct(current_, hf, eq);
        }

        hash_buffered_functions(hash_buffered_functions const& bf)
            : current_(false)
        {
            construct(current_, bf.current());
        }

        ~hash_buffered_functions() {
            destroy(current_);
        }

        H const& hash_function() const {
            return current().first();
        }

        P const& key_eq() const {
            return current().second();
        }
    };
    
    template <class H, class P>
    class set_hash_functions
    {
        set_hash_functions(set_hash_functions const&);
        set_hash_functions& operator=(set_hash_functions const&);
    
        typedef hash_buffered_functions<H, P> buffered_functions;
        buffered_functions& buffered_functions_;
        bool tmp_functions_;

    public:

        set_hash_functions(buffered_functions& f, H const& h, P const& p)
          : buffered_functions_(f),
            tmp_functions_(!f.current_)
        {
            f.construct(tmp_functions_, h, p);
        }

        set_hash_functions(buffered_functions& f,
            buffered_functions const& other)
          : buffered_functions_(f),
            tmp_functions_(!f.current_)
        {
            f.construct(tmp_functions_, other.current());
        }

        ~set_hash_functions()
        {
            buffered_functions_.destroy(tmp_functions_);
        }

        void commit()
        {
            buffered_functions_.current_ = tmp_functions_;
            tmp_functions_ = !tmp_functions_;
        }
    };

    // This implements almost all of the required functionality, apart
    // from some things that are specific to containers with unique and
    // equivalent keys which is implemented in hash_unique_table and
    // hash_equivalent_table. See unique.hpp and equivalent.hpp for
    // their declaration and implementation.

    template <class T>
    class hash_table : public T::buckets, public T::buffered_functions
    {
        hash_table(hash_table const&);
    public:
        typedef BOOST_DEDUCED_TYPENAME T::hasher hasher;
        typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal;
        typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator;
        typedef BOOST_DEDUCED_TYPENAME T::key_type key_type;
        typedef BOOST_DEDUCED_TYPENAME T::value_type value_type;
        typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base;
        typedef BOOST_DEDUCED_TYPENAME T::buckets buckets;
        typedef BOOST_DEDUCED_TYPENAME T::extractor extractor;
        typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor;

        typedef BOOST_DEDUCED_TYPENAME T::node node;
        typedef BOOST_DEDUCED_TYPENAME T::bucket bucket;
        typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr;
        typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr;
        typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base;
        typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator;
        typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair;

        // Members
        
        std::size_t size_;
        float mlf_;
        // Cached data - invalid if !this->buckets_
        bucket_ptr cached_begin_bucket_;
        std::size_t max_load_;

        // Helper methods

        key_type const& get_key(value_type const& v) const {
            return extractor::extract(v);
        }
        key_type const& get_key_from_ptr(node_ptr n) const {
            return extractor::extract(node::get_value(n));
        }
        bool equal(key_type const& k, value_type const& v) const;
        template <class Key, class Pred>
        node_ptr find_iterator(bucket_ptr bucket, Key const& k,
            Pred const&) const;
        node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const;
        node_ptr find_iterator(key_type const& k) const;
        node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const;
        
        // Load methods

        std::size_t max_size() const;
        std::size_t bucket_index(key_type const& k) const;
        void max_load_factor(float z);
        std::size_t min_buckets_for_size(std::size_t n) const;
        std::size_t calculate_max_load();

        // Constructors

        hash_table(std::size_t n, hasher const& hf, key_equal const& eq,
            node_allocator const& a);
        hash_table(hash_table const& x, node_allocator const& a);
        hash_table(hash_table& x, move_tag m);
        hash_table(hash_table& x, node_allocator const& a, move_tag m);
        ~hash_table() {}
        hash_table& operator=(hash_table const&);

        // Iterators

        iterator_base begin() const {
            return this->size_ ?
                iterator_base(this->cached_begin_bucket_) :
                iterator_base();
        }
        iterator_base end() const {
            return iterator_base();
        }

        // Swap & Move

        void swap(hash_table& x);
        void fast_swap(hash_table& other);
        void slow_swap(hash_table& other);
        void partial_swap(hash_table& other);
        void move(hash_table& x);

        // Reserve and rehash

        void create_for_insert(std::size_t n);
        bool reserve_for_insert(std::size_t n);
        void rehash(std::size_t n);
        void rehash_impl(std::size_t n);

        // Move/copy buckets

        void move_buckets_to(buckets& dst);
        void copy_buckets_to(buckets& dst) const;

        // Misc. key methods

        std::size_t count(key_type const& k) const;
        iterator_base find(key_type const& k) const;
        template <class Key, class Hash, class Pred>
        iterator_base find(Key const& k, Hash const& h, Pred const& eq) const;
        value_type& at(key_type const& k) const;
        iterator_pair equal_range(key_type const& k) const;

        // Erase
        //
        // no throw

        void clear();
        std::size_t erase_key(key_type const& k);
        iterator_base erase_return_iterator(iterator_base r);
        void erase(iterator_base r);
        std::size_t erase_group(node_ptr* it, bucket_ptr bucket);
        iterator_base erase_range(iterator_base r1, iterator_base r2);

        // recompute_begin_bucket

        void init_buckets();

        // After an erase cached_begin_bucket_ might be left pointing to
        // an empty bucket, so this is called to update it
        //
        // no throw

        void recompute_begin_bucket(bucket_ptr b);

        // This is called when a range has been erased
        //
        // no throw

        void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2);
        
        // no throw
        float load_factor() const;
        
        iterator_base emplace_empty_impl_with_node(
            node_constructor&, std::size_t);
    };

    ///////////////////////////////////////////////////////////////////
    //
    // Iterators

    // iterator_access is used to access the internal iterator without
    // making it publicly available.

    class iterator_access
    {
    public:
        template <class Iterator>
        static BOOST_DEDUCED_TYPENAME Iterator::base const&
            get(Iterator const& it)
        {
            return it.base_;
        }
    };

    template <class A, class G> class hash_iterator;
    template <class A, class G> class hash_const_iterator;
    template <class A, class G> class hash_local_iterator;
    template <class A, class G> class hash_const_local_iterator;

    // Local Iterators
    //
    // all no throw

    template <class A, class G>
    class hash_local_iterator
        : public boost::iterator <
            std::forward_iterator_tag,
            BOOST_DEDUCED_TYPENAME A::value_type,
            std::ptrdiff_t,
            BOOST_DEDUCED_TYPENAME A::pointer,
            BOOST_DEDUCED_TYPENAME A::reference>
    {
    public:
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;

    private:
        typedef hash_buckets<A, G> buckets;
        typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
        typedef hash_const_local_iterator<A, G> const_local_iterator;

        friend class hash_const_local_iterator<A, G>;
        node_ptr ptr_;

    public:
        hash_local_iterator() : ptr_() {}
        explicit hash_local_iterator(node_ptr x) : ptr_(x) {}
        BOOST_DEDUCED_TYPENAME A::reference operator*() const {
            return node::get_value(ptr_);
        }
        value_type* operator->() const {
            return node::get_value_ptr(ptr_);
        }
        hash_local_iterator& operator++() {
            ptr_ = ptr_->next_; return *this;
        }
        hash_local_iterator operator++(int) {
            hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; }
        bool operator==(hash_local_iterator x) const {
            return ptr_ == x.ptr_;
        }
        bool operator==(const_local_iterator x) const {
            return ptr_ == x.ptr_;
        }
        bool operator!=(hash_local_iterator x) const {
            return ptr_ != x.ptr_;
        }
        bool operator!=(const_local_iterator x) const {
            return ptr_ != x.ptr_;
        }
    };

    template <class A, class G>
    class hash_const_local_iterator
        : public boost::iterator <
            std::forward_iterator_tag,
            BOOST_DEDUCED_TYPENAME A::value_type,
            std::ptrdiff_t,
            BOOST_DEDUCED_TYPENAME A::const_pointer,
            BOOST_DEDUCED_TYPENAME A::const_reference >
    {
    public:
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;

    private:
        typedef hash_buckets<A, G> buckets;
        typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr;
        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
        typedef hash_local_iterator<A, G> local_iterator;
        friend class hash_local_iterator<A, G>;
        ptr ptr_;

    public:
        hash_const_local_iterator() : ptr_() {}
        explicit hash_const_local_iterator(ptr x) : ptr_(x) {}
        hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {}
        BOOST_DEDUCED_TYPENAME A::const_reference
            operator*() const {
            return node::get_value(ptr_);
        }
        value_type const* operator->() const {
            return node::get_value_ptr(ptr_);
        }
        hash_const_local_iterator& operator++() {
            ptr_ = ptr_->next_; return *this;
        }
        hash_const_local_iterator operator++(int) {
            hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp;
        }
        bool operator==(local_iterator x) const {
            return ptr_ == x.ptr_;
        }
        bool operator==(hash_const_local_iterator x) const {
            return ptr_ == x.ptr_;
        }
        bool operator!=(local_iterator x) const {
            return ptr_ != x.ptr_;
        }
        bool operator!=(hash_const_local_iterator x) const {
            return ptr_ != x.ptr_;
        }
    };

    // Iterators
    //
    // all no throw


    template <class A, class G>
    class hash_iterator
        : public boost::iterator <
            std::forward_iterator_tag,
            BOOST_DEDUCED_TYPENAME A::value_type,
            std::ptrdiff_t,
            BOOST_DEDUCED_TYPENAME A::pointer,
            BOOST_DEDUCED_TYPENAME A::reference >
    {
    public:
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;

    private:
        typedef hash_buckets<A, G> buckets;
        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
        typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
        typedef hash_const_iterator<A, G> const_iterator;
        friend class hash_const_iterator<A, G>;
        base base_;

    public:

        hash_iterator() : base_() {}
        explicit hash_iterator(base const& x) : base_(x) {}
        BOOST_DEDUCED_TYPENAME A::reference operator*() const {
            return *base_;
        }
        value_type* operator->() const {
            return &*base_;
        }
        hash_iterator& operator++() {
            base_.increment(); return *this;
        }
        hash_iterator operator++(int) {
            hash_iterator tmp(base_); base_.increment(); return tmp;
        }
        bool operator==(hash_iterator const& x) const {
            return base_ == x.base_;
        }
        bool operator==(const_iterator const& x) const {
            return base_ == x.base_;
        }
        bool operator!=(hash_iterator const& x) const {
            return base_ != x.base_;
        }
        bool operator!=(const_iterator const& x) const {
            return base_ != x.base_;
        }
    };

    template <class A, class G>
    class hash_const_iterator
        : public boost::iterator <
            std::forward_iterator_tag,
            BOOST_DEDUCED_TYPENAME A::value_type,
            std::ptrdiff_t,
            BOOST_DEDUCED_TYPENAME A::const_pointer,
            BOOST_DEDUCED_TYPENAME A::const_reference >
    {
    public:
        typedef BOOST_DEDUCED_TYPENAME A::value_type value_type;

    private:
        typedef hash_buckets<A, G> buckets;
        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
        typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base;
        typedef hash_iterator<A, G> iterator;
        friend class hash_iterator<A, G>;
        friend class iterator_access;
        base base_;

    public:

        hash_const_iterator() : base_() {}
        explicit hash_const_iterator(base const& x) : base_(x) {}
        hash_const_iterator(iterator const& x) : base_(x.base_) {}
        BOOST_DEDUCED_TYPENAME A::const_reference operator*() const {
            return *base_;
        }
        value_type const* operator->() const {
            return &*base_;
        }
        hash_const_iterator& operator++() {
            base_.increment(); return *this;
        }
        hash_const_iterator operator++(int) {
            hash_const_iterator tmp(base_); base_.increment(); return tmp;
        }
        bool operator==(iterator const& x) const {
            return base_ == x.base_;
        }
        bool operator==(hash_const_iterator const& x) const {
            return base_ == x.base_;
        }
        bool operator!=(iterator const& x) const {
            return base_ != x.base_;
        }
        bool operator!=(hash_const_iterator const& x) const {
            return base_ != x.base_;
        }
    };

    ////////////////////////////////////////////////////////////////////////////
    //
    // types
    //
    // This is used to convieniently pass around a container's typedefs
    // without having 7 template parameters.

    template <class K, class V, class H, class P, class A, class E, class G>
    struct types
    {
    public:
        typedef K key_type;
        typedef V value_type;
        typedef H hasher;
        typedef P key_equal;
        typedef A value_allocator;
        typedef E extractor;
        typedef G group_type;
        
        typedef hash_node_constructor<value_allocator, group_type>
            node_constructor;
        typedef hash_buckets<value_allocator, group_type> buckets;
        typedef hash_buffered_functions<hasher, key_equal> buffered_functions;

        typedef BOOST_DEDUCED_TYPENAME buckets::node node;
        typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket;
        typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr;
        typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr;
        typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base;
        typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator;

        typedef std::pair<iterator_base, iterator_base> iterator_pair;
    };
}}

#endif