引言

关联容器是基于节点的结构，STL关联容器中包含了set、multiset、map、multimap。底层都通过红黑树来实现的，查询效率极高。但并非所有的场景都适合它们，只有正确的遵守它们的游戏规则，才可让它们发挥出最大的效力。

关联容器

关联容器中可以分为:标准STL以红黑树为底层的容器、非标准STL以散列表为底层的hash容器。相对于查询而言，hash容器具有着独到的优势，但深入探讨这些问题之前，需要先厘清一个重要的基础论题: 相等与等价的区别?

相等与等价

相等的概念，在STL的体现就是operator==()的应用。即简单的两个值的相等判别，如:

1
2
3

int a = 0;
int b = 0;
...

而等价这个概念则相对于相等就会更加的复杂一些，从下例分析:

class CIStringClass {...} // 不区分大小的类
set <string, CIStringClass> tmp;

tmp.insert("Hello");
tmp.insert("hello");

这里创建了一个不区分大小的类，那么依此创建的一个set，就会认为： “Hello”与”hello”是等价的。而set最后插入的结果就是，仅会接受第一个的插入，而第二个就会被忽略。

修改set键

修改set键值?为什么不说修改关联容器键？
因为set iterator::operator*最后返回的是一个T&，map返回的是一个const T&。
当然，改变键会这导致一个问题，即代码的平台移植性被破坏了。
若是你不需要什么平台移植性，仅仅需要修改键，那么你也就应遵守以下的守则:

找到你需要修改的键
为这个键做一份拷贝
修改这个拷贝
删除原有的这个元素
插入这个已修改好的拷贝

包含对象指针的容器指定比较类型

你有这样一个vector容器，它的内部存储的是string*对象。
如果你想要获取对象，那么你可以通过iterator遍历去获取，但是你最后得到的是一个string*对象。
而这并不会阻碍我们去获取这个最后的对象，我们仍可以使用**string,解引后获取最终内容。但由于指针排列的顺序不会按照字符串的值进行排序的，因此我们最终可能会得到到下一个不确定的正确的顺序值。
显然并不是，我们需要提供一个类，就可以解决这个问题了。

map的插入方式

map在插入方式上，我们可以有两种选择： insert插入或operator[]插入。
这两种方式需要对应不同的情况:
针对于新值创建插入时，我们就使用insert
针对现值，更新的插入，我们就应使用operator[]
那么对于新值使用operator[]插入，会有哪些影响呢?
它会额外付出一些代价:

使用构造函数创建一个临时对象
使用析构函数析构掉它
使用拷贝构造函数进行赋值
因此，针对不同的场景，需要将其区分清楚，使用时才不会有困惑。

关联容器并非查询首选

思考容器查询会经历么样的步骤?
应该有如下三个步骤:

大量的数据插入
数据查询
数据的重组
一、三是一个极为耗时的操作，关联容器的插入也需要大量的时间
但是对于查询二，它们的效率则是极高的。
vector 作为一个序列容器，若是排序完成，拥有随机迭代器的它，查询效率也不会低于关联容器。
当然，关键的前提是排序完成。如果没有排序完成，那么查询效率而言，还是关联容器高。

数据相等时返回false

若是set中同时插入两个10，它会以10(A)与10(B)的方式进行比较，那么由于比较结果不一致，因此set容器中就存在了这样两个相同的元素。
因此，在处理相同元素时，应返回false，避免容器被破坏。

结语

关联容器使用是一个相对技巧与复杂较高的过程，需要结合不同的场景去选择最适合的容器去应用。

Rabbet

Effective_STL 阅读笔记(三)

引言