第三章. 关联容器

---

• 条款19.理解相等(equality)和等价(equivalence)的区别

标准关联容器需要保持有序，所以每个容器必须有一个定义了怎么保持东西有序的比较函数(默认是less)。
以set举例，set<string*> ssp 是 set<string*, less<string*>, allocator<string*> > ssp的简写。
第三个参数分配器不是这章讨论的问题。我们看第二个参数less<string*>,这是一个仿函数（通过重载类的()运算符，模仿函数的调用），是用于判断set中元素是否等价的比较函数。
等价不同于相等，是关联容器所引入的概念，即在排序顺序上，如果两个元素各自都不应该排在另一个的前面，则这两个元素是等价的。

在set类中，将比较函数typedef为key_compare.
判断是否等价的判别式为!c.key_compare()(x, y) && !c.key_compare()(y, x).
当keycompare()为less<>时，key_compare()(x,y)只有在x不小于y时返回false，key_compare()(y,x)只有在y不小于x时返回false.
所以只有x和y相等时该判别式为true，视该两元素等价，关联容器中不会保存两个等价的元素。

ps.set的第二个参数使用仿函数，是因为set模版第二个参数是数据类型，用于模板具现化，不接收函数指针。

---

• 条款20.为包含指针的关联容器指定比较类型

考虑下面这段代码，向一个set中放入指针对象

set<string*> ssp; 
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));

默认的比较函数会作用于指针值，即地址，将指针按地址大小排序，而不是根据指针所指向的内容进行排序
如果希望容器中根据指针所指向的内容排序，则需要为其指定特殊的比较函数

struct StringPtrLess:public binary_function<const string*, const string*, bool>
{
        bool operator()(const string *ps1, const string *ps2) const
        {
            return *ps1 < *ps2;
        }
};

ps.继承自binary_function<const string*, const string*, bool>的原因详见条款40（该基类也是less<>的基类）
创建关联容器时指定该比较函数

set<string*, StringPtrLess> ssp; 

然后这个容器内的元素就是按照指针所指向的元素进行排序了

ps.在输出时如果不想使用**iter，可以写一个输出函数print，使用foreach()，对每个元素调用print

void print(const string *ps)
{
    cout << *ps << endl;
}
for_each(ssp.begin(), ssp.end(), print);

---

• 条款21.总是让比较函数在等值情况下返回false

条款19中，less<>相当于"<",而less_equal<>相当于"<="，
如果比较函数key_compare指定为less_equal<>，则在判别式!c.key_compare()(x, y) && !c.key_compare()(y, x)中，
!c.key_compare()(x,y)在x==y时返回false,!c.key_compare()(y,x)在x==y时也返回false,则判断为x,y不等价，
set中就会插入值相等的x与y，这会破坏set的容器结构。

---

• 条款22.切勿直接修改set或multiset中的键

本条款中没有一并提及map和multimap，因为map<K,V>中元素类型为pair<const K, V>，对键的更改无法通过编译。
而set和multiset用于排序的键可由迭代器访问更改其值，这会破坏set中元素的有序性。
如果想要更改set中用于排序的键，应先通过迭代器将对象拷贝，再erase容器中的该元素，然后更改拷贝对象的键值，最将该拷贝insert入容器。

---

• 条款23.考虑用排序的vector替代关联容器

map中单个元素占用的内存比vector中多，因为map要额外维护指向两个子节点和指向父节点的三个指针。
所以元素很多时map要比vector多占用很多内存。
如果程序中使用的容器只在很短的阶段进行数据的插入和删除，而大多数的阶段是在进行查询和修改，使用vector性能会更好。
容器完成插入阶段后，进行排序。有序容器可以正确地使用查找算法——binary_search、lower_bound、equal_range等（参见条款34）。
而且一个有序vector的二分法查找(通过下标访问)比一个二叉树的二分法查找(通过指针迭代)提供了更好的性能。

---

• 条款24.当效率至关重要时，请在map::operator[]与map::insert之间谨慎做出选择

map::operator[]被设计为简化"添加或更新"功能。
map::operator[]会生成一个临时对象，只赋键值，insert入map中，无论是否已经有该键值了，insert都会返回pair<iterator, bool>对象，
这个返回值中的first变量会指向拥有该唯一键值的元素，然后将operator[]等号右侧的值赋给该变量.
当map中已经有该键值时，operator[]性能不如insert，因为在构造时并没有给新的元素赋值，而是在构造之后赋的值。
如果你要更新已存在的map元素，operator[]更好，但如果你要增加一个新元素，insert则有优势。

---

• 条款25.熟悉非标准的散列容器

散列容器，即基于哈希表(Hash Table)实现的容器。
本书作于2001年，当时C++标准委员会标准委员为了不过度地推迟标准的完成，将散列容器放在了标准的下一个版本中。
即C++11中，增加了散列容器unordered_set和unordered_map
散列容器中元素并不是有序的，所以并没有等价的概念，默认比较函数为equal_to。

---

如有错误，欢迎指正