mstl_map.hpp

一个类STL的多平台可移植的算法容器库,主要用于嵌入式系统编程时的内存管理等方面

/*
The young Library
Copyright (c) 2005 by 杨桓

Permission to use, copy, modify, distribute and sell this software for any
purpose is hereby granted without fee, provided that the above copyright
notice appear in all copies and that both that copyright notice and this
permission notice appear in supporting documentation.
The author make no representations about the suitability of this software
for any purpose. It is provided "as is" without express or implied warranty.
*/

/*
 * This file is derived from software bearing the following
 * restrictions:
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this
 * software and its documentation for any purpose is hereby
 * granted without fee, provided that the above copyright notice
 * appear in all copies and that both that copyright notice and
 * this permission notice appear in supporting documentation.
 * Hewlett-Packard Company makes no representations about the
 * suitability of this software for any purpose. It is provided
 * "as is" without express or implied warranty.
 */

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#ifndef __MACRO_CPLUSPLUS_MINI_STL_MAP_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_MAP_HEADER_FILE__
//-----------------------------------------------------------------------------
#include "mstl_pair.hpp"
#include "mstl_functional.hpp"
#include "tree/mstl_red_black_tree.hpp"
#include "algorithm/mstl_algorithm_compare.hpp"
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_BEGIN_NAMESPACE__
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename Key, typename Value, typename Compare = less<Key>,
          typename Allocator = allocator<Value> >
class map
{
private:
    typedef  pair<const Key, Value>  value_t;
    typedef  rb_tree_node<value_t>   node;
    typedef  typename Allocator::template rebind<node>::other  node_alloc;
    typedef  rb_tree<Key, value_t, select1st<value_t>, Compare, node_alloc>
             tree;
//    typedef  rb_tree<Key, value_t, select1st<value_t>, Compare>  tree;

    tree con;

public:
    typedef  map<Key, Value, Compare, Allocator>  self;

    typedef  Value                          mapped_type;
    typedef  typename tree::key_type        key_type;
    typedef  typename tree::value_type      value_type;
    typedef  typename tree::key_compare     key_compare;
    typedef  typename tree::get_key         get_key;
    typedef  typename tree::allocator_type  allocator_type;

    typedef  typename tree::size_type               size_type;
    typedef  typename tree::difference_type         difference_type;
    typedef  typename tree::reference               reference;
    typedef  typename tree::const_reference         const_reference;
    typedef  typename tree::pointer                 pointer;
    typedef  typename tree::const_pointer           cons_pointer;
    typedef  typename tree::iterator                iterator;
    typedef  typename tree::const_iterator          const_iterator;
    typedef  typename tree::reverse_iterator        reverse_iterator;
    typedef  typename tree::const_reverse_iterator  const_reverse_iterator;

    class value_compare : public binary_function<value_type, value_type, bool>
    {
    private:
        key_compare comp;
    public:
        value_compare( const key_compare& c ) : comp(c)  {}
        bool operator()( const value_type& lhs, const value_type& rhs ) const
        {
            return comp( lhs.first, rhs.first );
        }
    };

public:
    map() : con( key_compare() )  {}

    explicit map( const key_compare& comp ) : con(comp)  {}

    template< typename InputIterator >
    map( InputIterator first, InputIterator last ) : con( key_compare() )
    {
        con.insert_unique( first, last );
    }

    template< typename InputIterator >
    map( InputIterator first, InputIterator last, const key_compare& comp )
    : con(comp)
    {
        con.insert_unique( first, last );
    }

    map( const self& rhs ) : con(rhs.con)  {}

    self& operator=( const self& rhs )
        {  con = rhs.con;  return *this;  }

    key_compare key_comp() const
        {  return con.key_comp();  }

    value_compare value_comp() const
        {  return value_compare( con.key_comp() );  }

    iterator begin()              {  return con.begin();  }
    iterator end()                {  return con.end();  }
    const_iterator begin() const  {  return con.begin();  }
    const_iterator end() const    {  return con.end();  }

    reverse_iterator rbegin()              {  return con.rbegin();  }
    reverse_iterator rend()                {  return con.rend();  }
    const_reverse_iterator rbegin() const  {  return con.rbegin();  }
    const_reverse_iterator rend() const    {  return con.rend();  }

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

    pair<iterator, bool> insert( const key_type& k, const mapped_type& d )
        {  return con.insert_unique( value_type(k, d) );  }
    iterator insert( iterator position, const key_type& k, const mapped_type& d )
        {  return con.insert_unique( position, value_type(k, d) );  }
    pair<iterator, bool> insert( const value_type& v )
        {  return con.insert_unique( v );  }
    iterator insert( iterator position, const value_type& v )
        {  return con.insert_unique( position, v );  }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
        {  con.insert_unique( first, last );  }

    void erase( iterator position )              {  con.erase( position );  }
    void erase( iterator first, iterator last )  {  con.erase( first, last );  }
    size_type erase( const key_type& k )         {  return con.erase( k );  }

    mapped_type& operator[]( const key_type& k )
    {
        value_type v( k, mapped_type() );
        iterator itr = insert( v ).first;
        return itr->second;
    }

    void clear()                                    {  con.clear();  }
    void swap( self& rhs )                          {  con.swap( rhs.con );  }
    iterator find( const key_type& k )              {  return con.find( k );  }
    const_iterator find( const key_type& k ) const  {  return con.find( k );  }
    size_type count( const key_type& k ) const      {  return con.count( k );  }

    iterator lower_bound( const key_type& k )
        {  return con.lower_bound( k );  }
    const_iterator lower_bound( const key_type& k ) const
        {  return con.lower_bound( k );  }

    iterator upper_bound( const key_type& k )
        {  return con.upper_bound( k );  }
    const_iterator upper_bound( const key_type& k ) const
        {  return con.upper_bound( k );  }

    pair<iterator, iterator> equal_range( const key_type& k )
        {  return con.equal_range( k );  }
    pair<const_iterator, const_iterator> equal_range( const key_type& k ) const
        {  return con.equal_range( k );  }

    bool modify_key( iterator position, const key_type& new_key )
        {  return con.modify_key_unique( position, new_key );  }
    iterator modify_key( const key_type& k, const key_type& new_key )
        {  return con.modify_key_unique( k, new_key );  }

};  //end class



template< typename Key, typename Value, typename Compare, typename Allocator >
inline void swap( map<Key, Value, Compare, Allocator>& lhs,
                  map<Key, Value, Compare, Allocator>& rhs )
{
    lhs.swap( rhs );
}

template< typename Key, typename Value, typename Compare, typename Allocator >
inline bool operator==( const map<Key, Value, Compare, Allocator>& lhs,
                        const map<Key, Value, Compare, Allocator>& rhs )
{
    return ( lhs.size() == rhs.size()
             && equal( lhs.begin(), lhs.end(), rhs.begin() ) );
}

template< typename Key, typename Value, typename Compare, typename Allocator >
inline bool operator!=( const map<Key, Value, Compare, Allocator>& lhs,
                        const map<Key, Value, Compare, Allocator>& rhs )
{
    return !( lhs == rhs );
}

template< typename Key, typename Value, typename Compare, typename Allocator >
inline bool operator<( const map<Key, Value, Compare, Allocator>& lhs,
                       const map<Key, Value, Compare, Allocator>& rhs )
{
    if( lhs.end() == rhs.end() || lhs.size() > rhs.size() )
        return false;
    return lexicographical_compare( lhs.begin(), lhs.end(),
                                    rhs.begin(), rhs.end(), lhs.value_comp() );
}

template< typename Key, typename Value, typename Compare, typename Allocator >
inline bool operator>( const map<Key, Value, Compare, Allocator>& lhs,
                       const map<Key, Value, Compare, Allocator>& rhs )
{