人生何处不青山的主页

前言

二刷《代码随想录》数组部分，在第一遍的基础上完善解题思路、补充代码注释、补充算法复杂度分析、查看其它优秀题解。

前言

在了解hashtable之后，下面就可学习基于hashtable的set和map。在之前的介绍中，我们直到set和map主要是为了提升查找效率，所以采用红黑树的底层机制，查找效率可以达到O(logn)。但是这是基于元素的随机性。

而对于hashtable而言，不需要基于元素的随机性假设就可以使得元素的存取和删除达到常数级。

本篇主要是介绍基于hashtable实现的set、map、multiset和multimap。虽然这里介绍时采用的是C++11标准之前的hash_set、hash_map、hash_multiset和hash_multimap，但是设计思想是一致的，只是在一些接口上有些许差别。

本篇主要内容：

1.基于hashtable实现的set和map；

2.基于hashtable实现的multiset和multimap。

注：基于hashtable实现的set和map对外接口在hashtable几乎以及实现，因此只需要调用即可，实现细节参考hashtable。本篇基本只是代码注释和简介，会比较枯燥。

前言

hashtable是实现set和map的另一种底层机制，准确来说，在C++11之后，是实现unordered_set、unordered_map、unordered_multiset和unordered_multimap这四种无序关联式容器的底层机制。

但是由于书中使用的C++编译器是C++11之前的版本，因此这里的解析在C++11标准之前，下面介绍的hashtable与正式标准存在一些差别，比如hash function的差别、C++增加了重映射策略等等。

尽管如此，这里剖析的hashtable在关键设计思想上与新标准一致，比如均使用开链法（链地址法）处理冲突，即使用bucket vector和linked list实现哈希表。

本篇主要内容有：

1.STL中使用链地址法实现hash表；

2.hashtable的迭代器为正向迭代器，递增的实现方式；

3.hashtable的构造与内存管理（插入和重整）；

4.hashtable的复制和清除操作。

前言

在了解STL的RB-tree（红黑树）数据结构之后，实现set和map就非常简单，因为set和map均以红黑树作为底层实现（因此set和map中的元素实际上均是一个有序的序列），其对外接口均是调用底层实现的接口。本篇主要内容：

1.set和map的特性以及如何基于红黑树实现容器；

2.multiset和multimap如何基于红黑树实现。

注：本篇基本上是对set、map、multiset、multimap源代码的注释，实现技巧在红黑树中已经说明。

因此比较枯燥。

前言

本篇主要介绍STL中的RB-tree(红黑树)结构，主要内容包括：

1.在了解红黑树之前，需要对于二叉搜索树和AVL树进行初步认识，红黑树作为一种二叉搜索树，其本身就是为了提高查找效率(O(logn))，此外还需要熟悉AVL树的左旋和右旋操作；

2.红黑树的性质，以及当插入时如何通过一些调整措施保证红黑树的性质不被破坏；

3.在STL中对于红黑树的实现，以及常见操作。

前言

本篇主要是介绍SGI STL中提供的单链表容器——slist，主要内容如下：

1.分析slist（单链表）与list（双向循环链表）的不同，引入slist的主要原因是占用空间更小，虽然操作上受限；

2.slist的迭代器和节点设计架构采用了继承的方式，这种设计与后面关联式容器中的RB-Tree（红黑树）类似；

3.slist常见的对外接口。

前言

本篇首先介绍STL中优先级队列（priority queue）的底层实现组件——heap，主要内容有：

1.堆的概念以及实现方式（一个容器vector和一组操作算法），STL中实现的是大顶堆；

2.堆的操作方式：push_heap、pop_heap、sort_heap以及make_heap；

3.补充介绍堆排序算法，时间复杂度为O(logn)。

接着介绍STL中的priority_queue（优先级队列），由于是在底层容器的基础上加上heap方法，因此优先级队列是一种适配器。

前言

本篇主要是介绍STL中stack和queue，主要内容有：

1.stack和queue分别是先进后出和先进先出的数据结构；

2.stack和queue均以deque作为底层容器，对外通过限制操作提供接口（设计模式中的适配器模式）；

3.可以将list作为二者的底层容器。

前言

这篇博客是对STL中的序列式容器deque的实现讲解。主要包括：

1.deque对比vector来说是双端可以进行操作的线性表，采用多段定长连续空间组成；

2.deque的关键任务：借助map中控器完成多段连续空间的管理、借助专属的迭代器对外提供随机访问接口；

3.deque的构造与内存管理，主要涉及到map的调整和新的连续存储空间的分配会回收；

4.常见的一些deque操作实现原理，比如insert：

前言

本篇内容是《STL源码剖析》中对于list容器的读书笔记和个人理解。主要内容是：

1.list容器在概念上对应于线性表的链式存储结构，实现上是双向循环链表；

2.list的构造与内存管理，重点是如何插入一个元素；

3.list中的一些关键操作实现，包括splice、merge、reverse、sort等以及底层实现transfer。