week14_readme
今日c++学习心得
理论课
学习了关联容器的有关内容
关联容器支持高效的关键字查找和访问,主要有map和set两类
map中储存键-值对,可以高效地通过关键字查找值,而set只保存关键字,支持高效的关键字查询
他们都可以选择可重复(multi
)和无序(umordered_
)的前缀,所以一共有2^3=8种关联容器
有序保存的关联容器底层是红黑树,无序保存的关联容器底层是哈希函数
相比之下,无序储存效率更高,因此,如果不严格要求一直有序,最好选择无序储存
关联容器是根据关键字存储的,所以不支持顺序容器的push_back
等位置相关的操作
作为有序容器的关键字的类型必须定义了元素比较的方法,即严格弱序;作为无序容器关键字则要定义相等关系
map类型的元素是pair
,pair有两个public成员,分别是first
和second
,可以用点运算符获得
或者用关联容器的迭代器的箭头运算符得到,即it->first
和it->second
一些泛型算法可以用于关联容器,但通常是一个坏主意,因为它们定义了更高效的成员函数版本的算法
向map类型插入元素可以用insert
函数,更直观的是用下标运算符和at()函数
区别在于当本不存在该关键字时,下标操作会创建之,而at会抛出异常,要根据我们的目的来选择
对于multimap
,由于关键字可重复,下标运算是无意义的,所以不能使用
要访问multimap中所有相同关键字,由于它们是相邻储存的(即使是unordered也会把相同的key放在一个桶里)
可以用find
函数找到第一个,count
函数找到数目,得到一个范围
或者使用lower_bound
和upper_bound
得到迭代器范围;或者用equal_range
返回的pair得到迭代器范围
实践课
完成了利用unordered_map
重写单词计数和单词转换,以及找到特定值并删除的编程题
用今天学的哈希表的写法重写了第九周的从文件中统计单词的程序,效率获得了很大提升
将leetcode上做过的哈希表有关的题目进行了修改,减少了用时