STL源码剖析--读书笔记（4）

迷南。 2021-11-02 07:14 353阅读 0赞

# 写在前面的话 #

前一篇博文介绍了**序列式容器**，接下来介绍**关联式容器**。

# 概览 #

所谓关联式容器，即每个元素都有一个键值（key）和一个实值（value）。当元素被插入到关联式容器中时，容器的内部结构便按照其键值大小，以某种特定规则将这个元素放置于适当位置。关联式容器没有头尾（只有最大元素和最小元素），所以不会有push\_back(), push\_front(), pop\_back(), pop\_front(), begin(), end()这些操作行为。  
　　STL中的关联式容器分为set和map两大类，以及这两大类的衍生体multiset和multimap。这些容器的底层实现机制都是红黑树。红黑树也是一个独立的容器，但是并不开放给外界使用。此外，SGI STL还提供了一个不在标准规格之列的关联式容器：hashtable,以及以hashtable为底层机制的hash\_set,hash\_map,hash\_multiset,hash\_multimap。

# set #

（1）set里面元素的键值就是实值，实值就是键值，所有元素都会根据元素的键值自动被排序，并且set不允许两个元素有相同的键值。  
　　（2）我们不能通过set的迭代器改变set的元素值，因为set的元素值就是其键值，关系到set元素的排列规则，如果任意改变set的元素值，会破坏set组织。因此，set::iterator 被定义为const\_iterator，杜绝写入操作。  
　　（3）set拥有与list相同的某些性质：当用户对它进行元素新增或删除操作时，操作之前的所有迭代器（除了被删除元素的迭代器）在操作之后都依然有效。  
　　（4）set是以红黑树为底层机制，因为红黑树是一种平衡二叉搜索树，自动排序效果不错。而且对于set所开放的各种接口操作，红黑树也都提供了，所以几乎所有的set操作行为，都只是调用红黑树的操作行为而已。

# map #

（1）map的所有元素都是pair，同时拥有实值（value）和键值（key）。pair的第一元素被视为键值，第二元素被视为实值。它的所有元素都会根据元素的键值自动被排序，并且map不允许两个元素拥有相同的键值。  
　　（2）我们不能通过map的迭代器改变map里元素的键值，因为键值关系到map元素的排列规则，任意改变map元素键值将会严重破坏map组织，但是可以改变元素的实值，因为map元素的实值并不影响map元素的排列规则。  
　　（3）map拥有与list相同的某些性质：当用户对它进行元素新增或删除操作时，操作之前的所有迭代器（除了被删除元素的迭代器）在操作之后都依然有效。  
　　（4）map也是以红黑树为底层机制，因为红黑树是一种平衡二叉搜索树，自动排序效果不错。而且对于map所开放的各种接口操作，红黑树也都提供了，所以几乎所有的map操作行为，都只是调用红黑树的操作行为而已。

# multiset和multimap #

（1）multiset的特性以及用法和set完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制红黑树的insert\_equal()而非insert\_unique()。  
　　（2）multimap的特性以及用法和map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制红黑树的insert\_equal()而非insert\_unique()。

# hash\_set #

（1）hash\_set以hashtable为底层机制，由于hash\_set所提供的操作接口，hashtable都提供了，所以几乎所有的hash\_set操作行为都只是转调用hashtable的操作行为而已。  
　　（2）红黑树有自动排序功能，而hashtable没有，反映到表层就是，set的元素有自动排序功能而hash\_set没有。  
　　（3）hash\_set跟set一样，元素的键值就是实值，实值就是键值。

# hash\_map #

（1）hash\_map也是以hashtable为底层机制，由于hash\_map所提供的操作接口，hashtable都提供了，所以几乎所有的hash\_map操作行为都只是转调用hashtable的操作行为而已。  
　　（2）红黑树有自动排序功能，而hashtable没有，反映到表层就是，map的元素有自动排序功能而hash\_map没有。  
　　（3）hash\_map跟map一样，每一个元素同时拥有一个实值和一个键值。

# hash\_multiset和hash\_multimap #

（1）hash\_multiset的特性与multiset完全相同，唯一差别就在于它的底层机制是hashtable。因此，hash\_multiset的元素不会自动排序。  
　　（2）hash\_multiset和hash\_set实现上的唯一差别在于，前者的元素插入操作采用底层机制hashtable的insert\_equal(),后者则是采用insert\_unique()。  
　　（3）hash\_multimap的特性与multimap完全相同，唯一差别就在于它的底层机制是hashtable。因此，hash\_multimap的元素不会自动排序。  
　　（4）hash\_multimap和hash\_map实现上的唯一差别在于，前者的元素插入操作采用底层机制hashtable的insert\_equal(),后者则是采用insert\_unique()。