C++(数据结构与算法):39---字典介绍

一、字典

• 字典（dictionary）是由一些形如(k,v)的数对所组成的集合，其中：
  • k：是关键字
  • v：是与关键字k对应的值
• 任意两个数对，其关键字都不等
• 多重字典：两个或更多的数对可以具有相同的关键字
• 有关字典的操作如下：
  • 确定字典是否为空
  • 确定字典有多少数对
  • 寻找一个指定了关键字的数对
  • 插入一个数对
  • 删除一个指定了关键字的数对

二、字典的抽象数据类型（ADT）

• 下图是字典的抽象数据类型：
  • p.first：表示数对p的关键字
  • p.second：表示数对p的值
  • insert方法：当没有字典中没有p.first时，insert(p)把数对p插入字典；如果字典中已经存在关键字p.first，那么用新值取代旧的值。这种方法与STL中的hash_map的insert方法一致
  • find方法：返回值是指针，指向与给定关键字相匹配的数对。这种方法与STL中的hash_map的insert方法一致

三、字典的抽象类

• pair容器介绍见文章：https://blog.csdn.net/qq_41453285/article/details/100628402

  

   

    

     

    
    

     

      template<
      class K,class E>
     
    
   

    

     

    
    

     

      class 
      dictionary
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      public:
     
    
   

    

     

    
    

     
	
      virtual ~dictionary() = 
      default;
     
    
   

    

     

    
    

     
	
      virtual bool empty()const = 
      0; 
      //判断字典是否为空
     
    
   

    

     

    
    

     
	
      virtual int size()const = 
      0; 
      //返回字典中数对的数目
     
    
   

    

     

    
    

     
	
      virtual 
      std::pair<
      const K, E>* find(
      const K&)
      const = 
      0; 
      //返回匹配数对的指针
     
    
   

    

     

    
    

     
	
      virtual void erase(const K&) = 
      0; 
      //删除匹配的数对
     
    
   

    

     

    
    

     
	
      virtual void insert(const std::pair<const K, E>&) = 
      0; 
      //往字典中插入一个数对
     
    
   

    

     

    
    

     

      };