软件设计模式课程设计

《软件设计模式课程设计》由会员分享，可在线阅读，更多相关《软件设计模式课程设计（14页珍藏版）》请在金锄头文库上搜索。

1、2020级软件设计模式课程设计（基于迭代器、适配器、策略模式的hashmap设计）指导教师： 蒋湘涛 小组成员： 刘应华（）王紫龙（陈理平（）2020年7月4日目的及简要介绍大伙儿都明白，C+为广大爱好者提供了诸如It era tor、list等容器供大伙儿利 用，大大的方便了大伙儿处置数据。那个地址，咱们一样为大伙儿提供一个知足 STL要求的容器来供大伙儿利用，让大伙儿在数据处置的进程中能更方便快捷。C+标准对容器提出了许多需求，只有知足这些需求，才能算得上是STL容器。大体hashmap（散列表）：STL中的最大的疏忽吗？在STL中，没有概念hashmap容器，那个 地址咱们实现了。散列表

2、在平均情形下能够提供常量时刻的插入、删除和查找。散列表并非是将元素有序地存 储，而是把各元素散列（hash）或映射至某个桶（bucket）。只要所存储的元素个数不比桶数大 太多，插入、删除和查找操作都能在常量时刻内运行。Hashmap也存储键/值对，它提供的操作与map几乎一样，那个hashmap实现利用链式散列 （也称开放散列），而且没有提供诸如再散列等高级操作。二、程序实现Hashmap的访问操作：标准要求为键比较和值比较对象提供访问方式：Operator与STL中的map的原型相似。若是原先的hashmap中没有该键对应的值，那 么会插入一个，它会挪用被映射的元素的默许构造函数进行填充，

3、而且反回那个值。模板的分离编译：在模板类的声明文件（一样是.h文件）的最后添加一个include语句，将模板类的 实现文件包括进来，例如：#include“”将模板类的实现类文件从项目中移除（使工程中不含模板的实现文件.cpp）,但并 非从磁盘上移除，不改变其途径。使它不能显示的参与编译。在声明main函数的文件中包括要利用的模板类的声明文件。三、设计模式四、相关内容一、Hashmap应当许诺客户指定自己的散列函数和桶数，而针对特定工作负载制定散列 行为。另一方面，客户若是没有这种需求，或没有能力来编写一个好的散列函数及选择 桶数，也应该能够不做任何定制地直接利用容器。一种解决方案是许诺客户在

4、hashmap 构造函数中提供散列函数和桶数，并为之提供默许值。另外，把散列函数和桶数包装在 一个散列类中也是一种合理的做法:Hash ()的实现要难一些，部份缘故在于它必需应用于任何类型的键，它要把键映射至某 个mNumBuckets桶。此函数利用了除留余数法来完成散列，即键所对应的桶(号)是键 对桶数取余后取得的一个整数值。遗憾的是，前面的方式无法应用于st ring，因为不同的st ring对象可能包括相同的 st ring值。因此相同的st ring值就可能散列到不同的桶中。如此一来，能够想到，专 门针对st ring提供Defaul tHash类的一个部份特殊化。二、它支持3个大体操

5、作：插入、删除、查找。比较器：hashmap许诺客户指定比较类型作为模板参数，而且能在构造函数中传递该类 的一个特定比较对象Hashmap可不能按键对元素排序，而是必需比较键的相等性。因 此，它利用的是equal_to,比较对象只是用于检测是不是试图向容器中插入重复键。 散列器：许诺客户概念自己的类，以便构造此类对象传入构造函数，现在必需明确如安 在构造函数中指定该参数的类型。散列模板参数：利用typedef概念：键类型，值类型，比较类型，散列类型 3、大体散列表结构通常包括固定数量桶，每一个桶能够存储一个或多个元素。应当能 够基于一个bucket-id在常量时刻内访问桶。因此vector是对

6、桶最为适合的容器。每 一个桶必需存储一个元素列表，因此STL list能够用作桶类型。查找操作利用findElement帮忙完成查找工作：findElement()第一利用散列对象将键 散列至一个特定的桶。然后，在该桶中查找是不是有元素的键与给定键匹配。所存储的 元素是键/值对，因此具体的比较会在元素第一个字段上进行。构造函数中指定的比较 函数对象确实是用于完成那个比较。List需要完成线性查找来寻觅匹配的元素，因此能 够利用find（）算法而不是一个显式的for循环。Insert操作必需第一检查hashmap中是不是已经存在此键的元素。若是没有，会把元素 插入到适当的桶中的list。需要说明

7、，findElement（）会按引用返回散列到的那个桶， 即在该桶中并无找到此键的元素。4、 将 hashmap 作为容器有关 typedef 的容器需求类型名说明Value_type容器中存储的元素类型Reference容器中存储的元素类型的一个引用Const_reference容器中存储的const元素类型的一个引用Iterator迭代处理容器中兀素的“智能指针”类型Const_iteratorIt era tor的另一个版本，用以迭代处理容器中的const元素Size_type可以表示容器中兀素个类的类型，通常就是 size_ t（在cs tddef中声明Difference. type

8、（两个迭代器相减的结果的类型）可以表示容器的两个it era tor之差别类型， 通常就是ptridiff_t （在cstddef中声明， 两个指针相减的的结果的类型）作为容器必需提供的方式：方法说明复杂性默认构造函数构造一个空的容器常量时间复制构造函数完成一个深复制线性时间赋值操作完成一个深复制线性时间析构函数撤销动态分配的内存，对容器中剩余的所有元素调用析构函数线性时间It era torbegin();返回指示容器中第一个兀素常量时间const_iteratorbegin()const;的一个迭代器Iteratorend();const_iteratorend() cons t;返回指示

9、容器中最后一个兀素的一个迭代器常量时间Operator =Operator !=Operator Operator Operator Operator 二Operator =对两个容器逐个进行比较的比较操作符线性时间Void swap(Container&);将传递至方法的容器的内容 与调用此方法的对象进行交 换应该为常量时间Size_type size() const;返回容器中的兀素个数应该为常量时间Size_typemax_size()const;返回容器可以容纳的最大兀素个数应该为常量时间Bool empty() const;指定容器是否包含兀素常量时间编写一个迭代器：迭代器一样应当是

10、一个看上去像智能指针的类，它要提供重载opera tor *和opera tor -，另外依照其特定行为还要提供其他一些操作。只要迭代器能够提供大体的迭代操作， 应该就能够一切正常了。Hash It era tor 类：每一个HashIterator对象都是hashmap类的一特定货柜的迭代器。为了提供这种一对 一的映射，HashIterator还必需是一个类模板，要针对hashmap类的一样参数模板化。It era tor_ tr ai ts是一个类模板，它为各个迭代器类型概念了5个t ypedef。若是情愿, 能够为你的新迭代器类型对其部份特殊化。还有一种做法，it era tor_t r

11、ai ts类模板的 默许实现只是把这5个typedef从迭代器类本身当中掏出。因此能够直接在迭代器类中概念这些t ypedef。事实上，C+中的it era tor类模板，它会提供t ypedef。如此只需指定迭迭代器类型和元素类型作为模板参数提供给it era tor类模板HashI tera tor是一 个双向迭代器，因此能够指定bidirectional_iterator_tag作为迭代器类型。元素类 型确实是 pairconst Key,T能够不显示地实现拷贝构造函数和赋值操作符，因为默许的行为确实是咱们想要的。关于一个HashIterator自增会让它指示容器中的“下一个”元素。那个

12、方式第一让list 迭代器自新加增，然后检查是不是抵达桶的末尾。倘假设如此，就录找hashmap中的下 一个非控桶，因为下一个桶中能够没有任何元素。若是没有更多的非空桶，mIt会设置 为hashmap中最后一个桶的末尾迭代器，这是Hashmap的特殊“末尾”位置。应当记得， 迭代器没必要比哑指针更平安，因此关于已经处在末尾的迭代器再自增等情形没必要进 行错误检查。自减是自增的逆操作，它使迭代器指示容器中的“前一个”元素。只是，在此存在非对 称性，自减算法第一检查底层list迭代器是不是是当前桶的开始迭代器。若是不是就 能够够自减。不然，代码要检查当前桶之前的第一个非空桶。若是找到了如此一个非空

13、 桶，list迭代器必需设置为指示桶中的最后一个元素，即对末尾迭代器减1。若是没有 找到非空桶，自减确实是非法的，因此代码的行为是未概念的。在实现中，incremen t()和decremen t()都访问了 hashmap类的pro tec ted成员。因此， hashmap 类必 Hash It era tor 是一个 friend 类。Const迭代器：对元素提供只读访问。迭代器typedef和访问方式：Begin() end():若是散列表中没有元素就可返回末尾迭代器。关联容器的typedef需求：类型名说明Key_type键类型，容器利用此键类型实例化Key_compare比较类或函

14、数指针类型，容器利用此类型实例化Value_compare比较两个value_type元素的类咱们的实现还包括一个mapped_type的typedef，因为map容器就提供了如此一个typedef。Value_compare并无实现为一个typedef,而是作为一个嵌套类概念。能够以 采纳另外一种做法，此类能够是hashmap的一个friend类，但那个概念要遵循标准中 所给出的map概念。Value_compare类的用途是对两个元素的键挪用比较函数。5、关联容器的方式需求方法说明复杂性取一个迭代器区间的构造函数构造容器,并插入迭代器区间中 的兀素。迭代器区间不一定指示 另一个同类型的容器

15、。需要注 意，关联容器的所有构造函数都 必须取一个类型为 value_comapre的比较对象。构 造函数应当提供一个默认的构 造对象作为默认值。NlogNKey_compare key_comp() const;Value_compare value_comp() const;返回比较对象来比较键或者比较整个值常量时间Pairiterator,bool insert(value_type&);Iterator insert(iterator ,value_type&); voidinsert(InputIteratorstart,InputIterator end);三种形式的插入。第二个插入方 法中的it era tor位置是一个提 示，此提示可以忽略。第三个插 入方法中的区间不一定是一个 同类型容器中的区间。允许有重 复键的容器只从第一种形式返 回 it era tor,因为 inser t（）总 会成功。对数时间Size_type erase(key_type&);Void erase( iterator