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; //往字典中插入一个数对
};