ycpp_set.hpp

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

inline bool operator==( const set<Key, Compare, Allocator>& lhs,
                        const set<Key, Compare, Allocator>& rhs )
{
    return lhs.size() == rhs.size()
           && std::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 )
{
    return std::lexicographical_compare( lhs.begin(), lhs.end(),
                                         rhs.begin(), rhs.end(), Compare() );
}

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 = std::less<Key>,
          typename Allocator = std::allocator<Key> >
class multiset
{
public:
    typedef  multiset<Key, Compare, Allocator>   self;

    typedef  Key            key_type;
    typedef  Key            value_type;
    typedef  Compare        key_compare;
    typedef  Compare        value_compare;
    typedef  Allocator      allocator_type;

    typedef  size_t         size_type;
    typedef  ptrdiff_t      difference_type;
    typedef  const Key&     reference;
    typedef  const Key&     const_reference;
    typedef  const Key*     pointer;
    typedef  const Key*     const_pointer;

    typedef  set_iterator<Key, Compare, Allocator>  iterator;
    typedef  set_iterator<Key, Compare, Allocator>  const_iterator;
    typedef  std::reverse_iterator<iterator>        reverse_iterator;
    typedef  std::reverse_iterator<const_iterator>  const_reverse_iterator;

    multiset()  {  init();  }

    template< typename InputIterator >
    multiset( InputIterator first, InputIterator last )
    {
        init();
        for( ; first != last; ++first )
        {
            if( !bbstree_insert_equal_value(&m_tree, &(*first)) )
            {
                bbstree_destroy( &m_tree );
                throw std::bad_alloc();
            }
        }
    }

    multiset( const self& rhs )
    {
        if( bbstree_init_copy( &m_tree, &(rhs.m_tree) ) == 0 )
            throw std::bad_alloc();
    }

    self& operator=( const self& rhs )
    {
        if( bbstree_assign_copy( &m_tree, &(rhs.m_tree) ) == 0 )
            throw std::bad_alloc();
        return *this;
    }

    ~multiset()  {  bbstree_destroy( &m_tree );  }

    static void init_move( void* uninit_dst, void* src )
    {
        bbstree_init_move( &( static_cast<self*>(uninit_dst)->m_tree ),
                           &( static_cast<self*>(src)->m_tree ) );
    }

    static void assign_move( void* dst, void* src )
    {
        bbstree_assign_move( &( static_cast<self*>(dst)->m_tree ),
                             &( static_cast<self*>(src)->m_tree ) );
    }

    iterator begin() const           {  return bbstree_begin(&m_tree);  }
    iterator end() const             {  return bbstree_end(&m_tree);  }
    reverse_iterator rbegin() const  {  return reverse_iterator( end() );  }
    reverse_iterator rend() const    {  return reverse_iterator( begin() );  }

    void clear()                  {  bbstree_destroy(&m_tree);  }
    bool empty() const            {  return bbstree_size(&m_tree) == 0;  }
    size_type size() const        {  return bbstree_size(&m_tree);  }
    size_type max_size() const    {  return youngc::bbstree_max_size();  }
    void swap( const self& rhs )  {  bbstree_swap( &m_tree, &(rhs.m_tree) );  }

    void erase( iterator position )
        {  bbstree_erase_pos( &m_tree, position.itr );  }
    void erase( iterator first, iterator last )
        {  bbstree_erase_range( &m_tree, first.itr, last.itr );  }
    size_type erase( const key_type& k )
        {  return bbstree_erase_key( &m_tree, &k );  }

    iterator insert( const value_type& v )
    {
        youngc::bbstree_iterator p = bbstree_insert_equal_value(&m_tree, &v);
        if( !p )
            throw std::bad_alloc();
        return p;
    }
    iterator insert( iterator pos, const value_type& v )
    {
        youngc::bbstree_iterator p = bbstree_insert_equal_pos( &m_tree,
                                                               pos.itr, &v );
        if( !p )
            throw std::bad_alloc();
        return p;
    }
    template< typename InputIterator >
    void insert( InputIterator first, InputIterator last )
    {
        for( ; first != last; ++first )
        {
            if( !bbstree_insert_equal_value(&m_tree, &(*first)) )
                throw std::bad_alloc();
        }
    }

    size_type count( const key_type& k ) const
        {  return bbstree_count( &m_tree, &k );  }

    iterator find( const key_type& k ) const
        {  return bbstree_find( &m_tree, &k );  }

    iterator lower_bound( const key_type& k ) const
        {  return bbstree_lower_bound( &m_tree, &k );  }

    iterator upper_bound( const key_type& k ) const
        {  return bbstree_upper_bound( &m_tree, &k );  }

    std::pair<iterator, iterator> equal_range( const key_type& k ) const
    {
        youngc::bbstree_pair_iterator pr = bbstree_equal_range( &m_tree, &k );
        return std::pair<iterator, iterator>( pr.first, pr.second );
    }

    void replace_key( iterator position, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        bbstree_replace_key_equal_pos( &m_tree, position.itr, &new_key,
                                       assign_copy_adapter<key_type> );
    }
    void replace_key( const key_type& old_key, const key_type& new_key )
    {
        typedef  typename property_traits<key_type>::has_trivial_assign  assign;

        bbstree_replace_key_equal( &m_tree, &old_key, &new_key,
                                   assign_copy_adapter<key_type> );
    }

private:
    mutable youngc::bbstree m_tree;

    void init()
    {
        youngc::ylib_fp_copy_t cp = init_copy_adapter<value_type>;
        youngc::ylib_fp_oper_t dsty = destroy_adapter<value_type>;

        bbstree_init( &m_tree, sizeof(value_type),
                      property_traits<value_type>::trivial_copy ? NULL : cp,
                      property_traits<value_type>::trivial_destructor ? NULL : dsty,
                      NULL, cmp_adapter<Key, Compare>,
                      alloc_adapter<Allocator>, dealloc_adapter<Allocator> );
    }
};



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()
           && std::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 )
{
    return std::lexicographical_compare( lhs.begin(), lhs.end(),
                                         rhs.begin(), rhs.end(), Compare() );
}

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

//------------------------------------------------------------------------------
//------------------------------------------------------------------------------
}  //end namespace
#endif
//------------------------------------------------------------------------------
//------------------------------------------------------------------------------