mstl_map.hpp

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

    return ( rhs < lhs );
}

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 !( rhs < lhs );
}

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 = less<Key>,
          typename Allocator = allocator<Value> >
class multimap
{
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  multimap<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:
    multimap() : con( key_compare() )  {}

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

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

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

    multimap( 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();  }

    iterator insert( const key_type& k, const mapped_type& d )
        {  return con.insert_equal( value_type(k, d) );  }

    iterator insert( iterator position, const key_type& k, const mapped_type& d )
        {  return con.insert_equal( position, value_type(k, d) );  }

    iterator insert( const value_type& v )
        {  return con.insert_equal( v );  }

    iterator insert( iterator position, const value_type& v )
        {  return con.insert_equal( position, v );  }

    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
        {  con.insert_equal( 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 );  }

    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 );  }

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

};  //end class



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

template< typename Key, typename Value, typename Compare, typename Allocator >
inline bool operator==( const multimap<Key, Value, Compare, Allocator>& lhs,
                        const multimap<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 multimap<Key, Value, Compare, Allocator>& lhs,
                        const multimap<Key, Value, Compare, Allocator>& rhs )
{
    return !( lhs == rhs );
}

template< typename Key, typename Value, typename Compare, typename Allocator >
inline bool operator<( const multimap<Key, Value, Compare, Allocator>& lhs,
                       const multimap<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 multimap<Key, Value, Compare, Allocator>& lhs,
                       const multimap<Key, Value, Compare, Allocator>& rhs )
{
    return ( rhs < lhs );
}

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

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

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
__MACRO_CPLUSPLUS_MINI_STL_END_NAMESPACE__
#endif
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------