map.h

Go to the documentation of this file.

/***************************************************************************
 *  include/stxxl/bits/containers/map.h
 *
 *  Part of the STXXL. See http://stxxl.sourceforge.net
 *
 *  Copyright (C) 2006 Roman Dementiev <[email protected]>
 *  Copyright (C) 2008, 2009 Andreas Beckmann <[email protected]>
 *
 *  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)
 **************************************************************************/

#ifndef STXXL_CONTAINERS_MAP_HEADER
#define STXXL_CONTAINERS_MAP_HEADER

#include <stxxl/bits/noncopyable.h>
#include <stxxl/bits/containers/btree/btree.h>


STXXL_BEGIN_NAMESPACE

namespace btree {

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned LogNodeSize,
          unsigned LogLeafSize,
          class PDAllocStrategy
          >
class btree;

} // namespace btree

//! \addtogroup stlcont
//! \{

//! External associative container (map). \n
//! <b> Introduction </b> to map container: see \ref tutorial_map tutorial. \n
//! <b> Design and Internals </b> of map container: see \ref design_map
//!
//! \tparam KeyType key type (POD with no references to internal memory)
//! \tparam DataType data type (POD with no references to internal memory)
//! \tparam CompareType comparison type used to determine
//! whether a key is smaller than another one.
//! If CompareType()(x,y) is true, then x is smaller than y.
//! CompareType must also provide a static \c max_value method, that returns
//! a value of type KeyType that is
//! larger than any key stored in map : i.e. for all \b x in map holds
//! CompareType()(x,CompareType::max_value())
//!
//! <BR>
//! Example: :
//! \verbatim
//! struct CmpIntGreater
//! {
//!   bool operator () (const int & a, const int & b) const { return a>b; }
//!   static int max_value() { return std::numeric_limits<int>::min(); }
//! };
//! \endverbatim
//! Another example:
//! \verbatim
//! struct CmpIntLess
//! {
//!   bool operator () (const int & a, const int & b) const { return a<b; }
//!   static int max_value() const  { return std::numeric_limits<int>::max(); }
//! };
//! \endverbatim
//! Note that CompareType must define a strict weak ordering.
//! (<A HREF="http://www.sgi.com/tech/stl/StrictWeakOrdering.html">see what it is</A>)
//! \tparam RawNodeSize size of internal nodes of map in bytes (btree implementation).
//! \tparam RawLeafSize size of leaves of map in bytes (btree implementation).
//! \tparam PDAllocStrategy parallel disk allocation strategy (\c stxxl::SR is recommended and default)
//!
template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize = 16* 1024,      // 16 KBytes default
          unsigned RawLeafSize = 128* 1024,     // 128 KBytes default
          class PDAllocStrategy = stxxl::SR
          >
class map : private noncopyable
{
    typedef btree::btree<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy> impl_type;

    impl_type Impl;

public:
    typedef typename impl_type::node_block_type node_block_type;
    typedef typename impl_type::leaf_block_type leaf_block_type;

    typedef typename impl_type::key_type key_type;
    typedef typename impl_type::data_type data_type;
    typedef typename impl_type::data_type mapped_type;
    typedef typename impl_type::value_type value_type;
    typedef typename impl_type::key_compare key_compare;
    typedef typename impl_type::value_compare value_compare;
    typedef typename impl_type::pointer pointer;
    typedef typename impl_type::const_pointer const_pointer;
    typedef typename impl_type::reference reference;
    typedef typename impl_type::const_reference const_reference;
    typedef typename impl_type::size_type size_type;
    typedef typename impl_type::difference_type difference_type;
    typedef typename impl_type::iterator iterator;
    typedef typename impl_type::const_iterator const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //! \name Iterators
    //! \{

    iterator begin() { return Impl.begin(); }
    iterator end() { return Impl.end(); }
    const_iterator begin() const { return Impl.begin(); }
    const_iterator end() const { return Impl.end(); }
    const_iterator cbegin() const { return begin(); }
    const_iterator cend() const { return end(); }

    reverse_iterator rbegin()
    {
        return reverse_iterator(end());
    }
    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(end());
    }
    const_reverse_iterator crbegin() const
    {
        return const_reverse_iterator(end());
    }
    reverse_iterator rend()
    {
        return reverse_iterator(begin());
    }
    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(begin());
    }
    const_reverse_iterator crend() const
    {
        return const_reverse_iterator(begin());
    }

    //! \}

    //! \name Capacity
    //! \{

    size_type size() const { return Impl.size(); }
    size_type max_size() const { return Impl.max_size(); }
    bool empty() const { return Impl.empty(); }

    //! \}

    //! \name Observers
    //! \{

    key_compare key_comp() const { return Impl.key_comp(); }
    value_compare value_comp() const { return Impl.value_comp(); }

    //! \}

    //! \name Constructors/Destructors
    //! \{

    //! A constructor
    //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
    //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
    map(unsigned_type node_cache_size_in_bytes,
        unsigned_type leaf_cache_size_in_bytes
        ) : Impl(node_cache_size_in_bytes, leaf_cache_size_in_bytes)
    { }

    //! A constructor
    //! \param c_ comparator object
    //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
    //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
    map(const key_compare& c_,
        unsigned_type node_cache_size_in_bytes,
        unsigned_type leaf_cache_size_in_bytes
        ) : Impl(c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes)
    { }

    //! Constructs a map from a given input range
    //! \param b beginning of the range
    //! \param e end of the range
    //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
    //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
    //! \param range_sorted if \c true than the constructor assumes that the range is sorted
    //! and performs a fast bottom-up bulk construction of the map (btree implementation)
    //! \param node_fill_factor node fill factor in [0,1] for bulk construction
    //! \param leaf_fill_factor leaf fill factor in [0,1] for bulk construction
    template <class InputIterator>
    map(InputIterator b,
        InputIterator e,
        unsigned_type node_cache_size_in_bytes,
        unsigned_type leaf_cache_size_in_bytes,
        bool range_sorted = false,
        double node_fill_factor = 0.75,
        double leaf_fill_factor = 0.6
        ) : Impl(b, e, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
                 range_sorted, node_fill_factor, leaf_fill_factor)
    { }

    //! Constructs a map from a given input range
    //! \param b beginning of the range
    //! \param e end of the range
    //! \param c_ comparator object
    //! \param node_cache_size_in_bytes size of node cache in bytes (btree implementation)
    //! \param leaf_cache_size_in_bytes size of leaf cache in bytes (btree implementation)
    //! \param range_sorted if \c true than the constructor assumes that the range is sorted
    //! and performs a fast bottom-up bulk construction of the map (btree implementation)
    //! \param node_fill_factor node fill factor in [0,1] for bulk construction
    //! \param leaf_fill_factor leaf fill factor in [0,1] for bulk construction
    template <class InputIterator>
    map(InputIterator b,
        InputIterator e,
        const key_compare& c_,
        unsigned_type node_cache_size_in_bytes,
        unsigned_type leaf_cache_size_in_bytes,
        bool range_sorted = false,
        double node_fill_factor = 0.75,
        double leaf_fill_factor = 0.6
        ) : Impl(b, e, c_, node_cache_size_in_bytes, leaf_cache_size_in_bytes,
                 range_sorted, node_fill_factor, leaf_fill_factor)
    { }

    //! \}

    //! \name Modifiers
    //! \{

    void swap(map& obj) { std::swap(Impl, obj.Impl); }
    std::pair<iterator, bool> insert(const value_type& x)
    {
        return Impl.insert(x);
    }
    iterator insert(iterator pos, const value_type& x)
    {
        return Impl.insert(pos, x);
    }
    template <class InputIterator>
    void insert(InputIterator b, InputIterator e)
    {
        Impl.insert(b, e);
    }
    void erase(iterator pos)
    {
        Impl.erase(pos);
    }
    size_type erase(const key_type& k)
    {
        return Impl.erase(k);
    }
    void erase(iterator first, iterator last)
    {
        Impl.erase(first, last);
    }
    void clear()
    {
        Impl.clear();
    }

    //! \}

    //! \name Operations
    //! \{

    iterator find(const key_type& k)
    {
        return Impl.find(k);
    }
    const_iterator find(const key_type& k) const
    {
        return Impl.find(k);
    }
    size_type count(const key_type& k)
    {
        return Impl.count(k);
    }
    iterator lower_bound(const key_type& k)
    {
        return Impl.lower_bound(k);
    }
    const_iterator lower_bound(const key_type& k) const
    {
        return Impl.lower_bound(k);
    }
    iterator upper_bound(const key_type& k)
    {
        return Impl.upper_bound(k);
    }
    const_iterator upper_bound(const key_type& k) const
    {
        return Impl.upper_bound(k);
    }
    std::pair<iterator, iterator> equal_range(const key_type& k)
    {
        return Impl.equal_range(k);
    }
    std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
    {
        return Impl.equal_range(k);
    }

    //! \}

    //! \name Operators
    //! \{

    data_type& operator [] (const key_type& k)
    {
        return Impl[k];
    }

    //! \}

    //! \name Miscellaneous
    //! \{

    //! Enables leaf prefetching during scanning
    void enable_prefetching()
    {
        Impl.enable_prefetching();
    }

    //! Disables leaf prefetching during scanning
    void disable_prefetching()
    {
        Impl.disable_prefetching();
    }

    //! Returns the status of leaf prefetching during scanning
    bool prefetching_enabled()
    {
        return Impl.prefetching_enabled();
    }

    //! Prints cache statistics
    void print_statistics(std::ostream& o) const
    {
        Impl.print_statistics(o);
    }

    //! Resets cache statistics
    void reset_statistics()
    {
        Impl.reset_statistics();
    }

    //! \}

    //////////////////////////////////////////////////
    template <class KeyType_,
              class DataType_,
              class CompareType_,
              unsigned RawNodeSize_,
              unsigned RawLeafSize_,
              class PDAllocStrategy_>
    friend bool operator == (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& b);
    //////////////////////////////////////////////////
    template <class KeyType_,
              class DataType_,
              class CompareType_,
              unsigned RawNodeSize_,
              unsigned RawLeafSize_,
              class PDAllocStrategy_>
    friend bool operator < (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
                            const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& b);
    //////////////////////////////////////////////////
    template <class KeyType_,
              class DataType_,
              class CompareType_,
              unsigned RawNodeSize_,
              unsigned RawLeafSize_,
              class PDAllocStrategy_>
    friend bool operator > (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
                            const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& b);
    //////////////////////////////////////////////////
    template <class KeyType_,
              class DataType_,
              class CompareType_,
              unsigned RawNodeSize_,
              unsigned RawLeafSize_,
              class PDAllocStrategy_>
    friend bool operator != (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& b);
    //////////////////////////////////////////////////
    template <class KeyType_,
              class DataType_,
              class CompareType_,
              unsigned RawNodeSize_,
              unsigned RawLeafSize_,
              class PDAllocStrategy_>
    friend bool operator <= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& b);
    //////////////////////////////////////////////////
    template <class KeyType_,
              class DataType_,
              class CompareType_,
              unsigned RawNodeSize_,
              unsigned RawLeafSize_,
              class PDAllocStrategy_>
    friend bool operator >= (const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& a,
                             const map<KeyType_, DataType_, CompareType_, RawNodeSize_, RawLeafSize_, PDAllocStrategy_>& b);
    //////////////////////////////////////////////////
};

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
inline bool operator == (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b)
{
    return a.Impl == b.Impl;
}

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
inline bool operator < (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
                        const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b)
{
    return a.Impl < b.Impl;
}

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
inline bool operator > (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
                        const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b)
{
    return a.Impl > b.Impl;
}

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
inline bool operator != (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b)
{
    return a.Impl != b.Impl;
}

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
inline bool operator <= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b)
{
    return a.Impl <= b.Impl;
}

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
inline bool operator >= (const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
                         const map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b)
{
    return a.Impl >= b.Impl;
}

//! \}

STXXL_END_NAMESPACE

namespace std {

template <class KeyType,
          class DataType,
          class CompareType,
          unsigned RawNodeSize,
          unsigned RawLeafSize,
          class PDAllocStrategy
          >
void swap(stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& a,
          stxxl::map<KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy>& b
          )
{
    a.swap(b);
}

} // namespace std

#endif // !STXXL_CONTAINERS_MAP_HEADER