STL 平衡树数据结构容器-白红宇

STL 平衡树数据结构容器

阅读量：4325 次

发布时间：2019-06-06

本文共 3084 字，大约阅读时间需要 10 分钟。

1.map

key只能对应一个映射值，支持插入，删除，查找（count, find), 修改（先删除此值，再插入修改后的值），排序，映射（离散话） multimap同样的键值可有多个映射

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
          using namespace std; map
          
           mp; int main( ) {
    int N,M, t; char str[1000]; while( scanf("%d%d",&N,&M) != EOF )   {
        mp.clear( ); for( int i = 1; i <= N; i++)     {
            scanf("%d",&t);         mp[t]++;     } for( int i = 1; i <= M; i++)     {
           scanf("%s",str); if( str[0] == 'D' )         scanf("%d",&t),mp.erase(t); else if( str[0] == 'F')        {
             scanf("%d",&t); if( mp.find(t) != mp.end( ))              puts("1"); else              puts("-1");        } else if( str[0] == 'P')        {
              map
           
            ::iterator iter = mp.begin( ); printf("%d",iter->first); for( int i = 1; i < iter->second; i++) printf(" %d",iter->first); while( iter++ != mp.end( )) { for( int i = 1; i <= iter->second; i++) printf(" %d",iter->first); } puts(""); } } } return 0; }

2.set/multiset

一个集合(set)是一个容器，它其中所包含的元素的值是唯一的。这在收集一个数据的具体值的时候是有用的。集合中的元素按一定的顺序排列，并被作为集合中的实例。一个集合通过一个链表来组织，在插入操作和删除操作上比向量(vector)快，但查找或添加末尾的元素时会有些慢。具体实现采用了红黑树的平衡二叉树的。(百度百科）

multiset所包含的元素值不唯一

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; multiset
          
           p; int main( ) {
    int N,M, t; char str[1000]; while( scanf("%d%d",&N,&M) != EOF )   {
        p.clear( ); for( int i = 1; i <= N; i++)     {
            scanf("%d",&t);         p.insert( t );     } for( int i = 1; i <= M; i++)     {
           scanf("%s",str); if( str[0] == 'D' )         scanf("%d",&t),p.erase(t); else if( str[0] == 'F')        {
             scanf("%d",&t); if( p.find(t) != p.end( ))              puts("1"); else              puts("-1");        } else if( str[0] == 'P')        {
              multiset
           
            ::iterator iter = p.begin( ); printf("%d",*iter); while( ++iter != p.end( )) { printf(" %d",*iter); } puts(""); } } } return 0; }

3.HNOI 2004

set,lower_bound强大应用

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            using namespace std; #define MOD 1000000 set
           
            p; typedef set
            
             ::iterator it; const int inf=~0U>>2; //const int inf = 0x7f7f7f7f; /*这样赋值会报错，runtime error, 随便改一个大点或小点也能过。 原因可能是插入的宠物特点值为这个时会把它删除。 */ int main( ) { int N, a, b, c,sum = 0; scanf("%d",&N); p.insert(inf), p.insert(-inf); while( N-- ) { scanf("%d%d",&a,&b); if( p.size() == 2) p.insert(b),c = a; else if( a == c ) p.insert(b); else { it x = p.lower_bound(b); int r = *x - b; int l = b - *(--x); if( l <= r ) sum += l, p.erase(x); else sum += r, p.erase(++x); if( sum >= MOD ) sum %= MOD; } } printf("%d\n", sum); return 0; }

转载于:https://www.cnblogs.com/tangcong/archive/2012/03/04/2379245.html

你可能感兴趣的文章