STL 平衡树数据结构容器

淩亂°似流年 2021-10-23 12:12 251阅读 0赞

1.map

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <stdio.h>
    #include <stdlib.h>
    #include <algorithm>
    #include <map>
    
    using namespace std;
    map<int, int>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<int,int>::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)快，但查找或添加末尾的元素时会有些慢。具体实现采用了红黑树的平 衡二叉树的[数据结构][Link 1]。(百度百科）

multiset所包含的元素值不唯一

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    multiset<int>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<int>::iterator iter = p.begin( );
              printf("%d",*iter);
    while( ++iter != p.end( ))
              { 
                 printf(" %d",*iter);
    
              }
              puts("");
           }
        }  
      }
    return 0;
    
    }

3.HNOI 2004

set,lower\_bound强大应用

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <set>
    #include <algorithm>
    
    using namespace std;
    
    #define MOD 1000000
    set<int>p;
    typedef set<int>::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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211023/e7f5c2796f4f40d6b5cabcae86efd933.png
[Link 1]: http://baike.baidu.com/view/9900.htm