mstl_set.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_SET_HEADER_FILE__
#define __MACRO_CPLUSPLUS_MINI_STL_SET_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 Compare = less<Key>,
          typename Allocator = allocator<Key> >
class set
{
private:
    typedef  rb_tree_node<Key>  node;
    typedef  typename Allocator::template rebind<node>::other  node_alloc;
    typedef  rb_tree<Key, Key, identity<Key>, Compare, node_alloc>  tree;
//    typedef  rb_tree<Key, Key, identity<Key>, Compare>  tree;
    typedef  typename tree::iterator  tree_iterator;

    tree con;

public:
    typedef  set<Key, Compare, Allocator>  self;

    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::const_reference         reference;
    typedef  typename tree::const_reference         const_reference;
    typedef  typename tree::const_pointer           pointer;
    typedef  typename tree::const_pointer           cons_pointer;
    typedef  typename tree::const_iterator          iterator;
    typedef  typename tree::const_iterator          const_iterator;
    typedef  typename tree::const_reverse_iterator  reverse_iterator;
    typedef  typename tree::const_reverse_iterator  const_reverse_iterator;

    set() : con( key_compare() )  {}

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

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

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

    set( 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();  }
    key_compare value_comp() const  {  return con.key_comp();  }

    iterator begin() const           {  return con.begin();  }
    iterator end() const             {  return con.end();  }
    reverse_iterator rbegin() const  {  return con.rbegin();  }
    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 value_type& v )
    {
        pair<tree_iterator, bool> p = con.insert_unique( v );
        return pair<iterator, bool>( p.first, p.second );
    }
    iterator insert( iterator position, const value_type& v )
        {  return con.insert_unique( const_iter_cast(position), v );  }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
        {  con.insert_unique( first, last );  }

    void erase( iterator position )
        {  con.erase( const_iter_cast(position) );  }
    void erase( iterator first, iterator last )
        {  con.erase( const_iter_cast(first), const_iter_cast(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 ) const    {  return con.find( k );  }
    size_type count( const key_type& k ) const  {  return con.count( k );  }

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

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

    pair<iterator, 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( const_iter_cast(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 Compare, typename Allocator >
inline void swap( set<Key, Compare, Allocator>& lhs,
                  set<Key, Compare, Allocator>& rhs )
{
    lhs.swap( rhs );
}

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

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

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

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

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

//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------

template< typename Key, typename Compare = less<Key>,
          typename Allocator = allocator<Key> >
class multiset
{
private:
    typedef  rb_tree_node<Key>  node;
    typedef  typename Allocator::template rebind<node>::other  node_alloc;
    typedef  rb_tree<Key, Key, identity<Key>, Compare, node_alloc>  tree;
//    typedef  rb_tree<Key, Key, identity<Key>, Compare>  tree;
    typedef  typename tree::iterator  tree_iterator;

    tree con;

public:
    typedef  multiset<Key, Compare, Allocator>  self;

    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::const_reference         reference;
    typedef  typename tree::const_reference         const_reference;
    typedef  typename tree::const_pointer           pointer;
    typedef  typename tree::const_pointer           cons_pointer;
    typedef  typename tree::const_iterator          iterator;
    typedef  typename tree::const_iterator          const_iterator;
    typedef  typename tree::const_reverse_iterator  reverse_iterator;
    typedef  typename tree::const_reverse_iterator  const_reverse_iterator;

    multiset() : con( key_compare() )  {}

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

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

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

    multiset( 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();  }
    key_compare value_comp() const  {  return con.key_comp();  }

    iterator begin() const           {  return con.begin();  }
    iterator end() const             {  return con.end();  }
    reverse_iterator rbegin() const  {  return con.rbegin();  }
    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 value_type& v )
        {  return con.insert_equal( v );  }
    iterator insert( iterator position, const value_type& v )
        {  return con.insert_equal( const_iter_cast(position), v );  }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
        {  con.insert_equal( first, last );  }

    void erase( iterator position )
        {  con.erase( const_iter_cast(position) );  }
    void erase( iterator first, iterator last )
        {  con.erase( const_iter_cast(first), const_iter_cast(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 ) const    {  return con.find( k );  }
    size_type count( const key_type& k ) const  {  return con.count( k );  }

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

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

    pair<iterator, 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( const_iter_cast(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 Compare, typename Allocator >
inline void swap( multiset<Key, Compare, Allocator>& lhs,
                  multiset<Key, Compare, Allocator>& rhs )
{
    lhs.swap( rhs );
}

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

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

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

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

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

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