【Effective STL（3）】关联容器

19 了解相等和等价的区别

• find算法和set::insert是判断两个值是否相同的函数代表，它们以不同的方式完成，find的相同基于operator==，set::insert对相同的定义是等价，通常基于operator<
• 相等基于operator==，在类中重载时，即使两个类不完全相同也可以相等
• 等价基于一个有序区间中对象值的相对位置，标准关联容器保持有序，所以每个容器必须定义一个保持有序的比较函数（默认是less），如果一个元素不在另一个之前（关于某个排序标准），则这两个元素是等价的（按照这个标准）。如果用相等决定两个对象是否有相同的值，除了排序的比较函数还需要一个用于判断两个值是否相等的比较函数（习惯用operator==）
• 一般关联容器的比较函数不是operator<或less，而是用户定义的判断式，标准关联容器通过key_comp成员函数访问排序判断式，key_comp默认是一个 std::less 对象，类似操作符 operator<，返回容器中用来比较主键的比较对象的一份拷贝

!c.key_comp()(x, y) && !c.key_comp()(y, x) // 为true则xy等价

• 为了更理解相等和等价的区别，考虑一个忽略大小写的set<string>，item35实现了忽略大小写比较的ciStringCompare函数，这里写一个仿函数类，类的operator()调用ciStringCompare

struct CIStringCompare : public binary_function<string, string, bool>
{ // 这个基类信息见item40
    bool operator()(const string& lhs, const string& rhs) const
    {
        return ciStringCompare(lhs, rhs);
    }
}

• 利用这个函数对象建立一个忽略大小写的set<string>

set<string, CIStringCompare> ciss; // case-insensitive string set
ciss.insert("Persephone"); // 添加到set中
ciss.insert("persephone"); // 未添加到set中

• 用set的find成员函数搜索字符串“persephone”会成功，但用find算法会失败，因为前者基于等价，后者基于相等，“persephone”和"Persephone"在此定义中等价但不相等

if (ciss.find("persephone") != ciss.end())... // true
if (find(ciss.begin(), ciss.end(), "persephone") != ciss.end())... // false

20 为指针的关联容器指定比较类型

• 假定有一个string*指针的set，把一些动物的名字插入进set

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

• 接着希望用下列代码使字符串按字母顺序出现

// 希望看到“Anteater”，“Lemur”，“Penguin”，"Wombat"
for (set<string*>::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
    cout << *i << endl;

• 然而结果只能看见四个十六进制数，因为set元素为指针，*i是一个string的指针。马上会想出把*i改为**i，但这样也不能保证输出按字母顺序出现，因为set中保存的是指针，以指针值排序而非string值
• 为了解决这个问题，首先应要知道set<string*> ssp是下列代码的简写

set<string*, less<string*>, allocator<string*>> ssp;

• 因此要string*指针以字符串值顺序存储在set中，不能用默认的仿函数类less<string*>，必须改为自己的比较仿函数类，它的对象带有string*指针并按指向的字符串值排序

struct StringPtrLess : public binary_function<const string*, const string*, bool>
{ // 这个基类信息见item40
    bool operator()(const string *ps1, const string *ps2) const
    {
        return *ps1 < *ps2;
    }
};

• 然后用StringPtrLess作为比较类型，循环就可以得到按字母顺序排序的输出了

typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp;
for (StringPtrSet::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
    cout << **i << endl;

• 可以改为使用算法，写一个函数给for_each联用

void print(const string *ps)
{
    cout << *ps << endl;
}
for_each(ssp.begin(), ssp.end(), print); // 对ssp的每个元素上调用print

• 或者用泛型的解引用仿函数类，然后让它和transform与ostream_iterator联用

struct Dereference {
    template <typename T>
    const T& operator()(const T *ptr) const
    {
        return *ptr;
    }
};
// 通过解引用“转换”ssp中的每个元素，把结果写入cout
transform(ssp.begin(), ssp.end(), ostream_iterator<string>(cout, "\n"), Dereference());

• 需要一个仿函数类而不是一个简单的比较函数的原因是，set不要一个函数，它要的是能在内部用实例化建立函数的一种类型
• 建立指针的关联容器得指定容器的比较类型，大多数时候，比较类型只是解引用指针并比较所指向的对象，因此手头最好有一个这样的仿函数模板

struct DereferenceLess {
    template <typename PtrType>
    bool operator()(PtrType pT1, PtrType pT2) const
    {
        return *pT1 < *pT2;
    }
};

set<string*, DereferenceLess> ssp; // 行为就像set<string*, StringPtrLess>

• 对于智能指针或迭代器的关联容器，也得指定比较类型。指针的解决方案也可以用于类似指针的对象，正如DereferenceLess适合作为T*的关联容器的比较类型一样，它也可以作为T对象的迭代器和智能指针容器的比较类型

21 永远让比较函数对相等的值返回false

• 建立一个set，比较类型用less_equal，然后插入两次10

set<int, less_equal<int> > s; // s以“<=”排序
s.insert(10);
s.insert(10);

• 对于后一个insert调用，set必须先要判断出10是否已经位于其中，为了区分，将前一个10称为10A，后一个称为10B。set遍历内部数据结构以查找适合插入10B的位置，最终使用比较函数检查10B是否与10A等价，这里比较函数为less_equal，而less_equal意思就是operator<=。于是，set将计算这个表达式

!(10A <= 10B) && !(10B <= 10A)

• 这个表达式结果显然是false，于是set认为10A与10B不等价，然后将10B插入到10A旁边，于是set有了两个10，因此用less_equal作为比较类型破坏了容器，同理任何对相等的值返回true的比较函数都会做同样的事情

// 对item20的StringPtrLess中的operator()结果取反实现StringPtrGreater
struct StringPtrGreater : public binary_function<const string*, const string*, bool> {
    bool operator()(const string *ps1, const string *ps2) const
    {
        return !(*ps1 < *ps2);
    }
};
// 这里取反返回的是>=而不是>，因此这是一个无效的比较函数
// 需要改为 return *ps2 < *ps1;

• 不仅仅对于map和set如此，对于multiset和multimap也是同理。将开头的代码改为multiset

multiset<int, less_equal<int>> s; // s仍然以“<=”排序
s.insert(10);
s.insert(10);

• s有两个10，对它做一个equal_range，希望得到一对指出包含这两个拷贝的范围的迭代器，而equal_range指示等价而非相等的值的范围，比较函数认为10A和10B是不等价的，所以不会同时出现在equal_range指示的范围内。因此，除非比较函数总是为相等的值返回false，否则将会打破所有的标准关联型容器

22 避免原地修改set和multiset的键

• 对于于map和multimap，试图改变容器里的一个键值的程序将不能编译，因为map<K, V>或multimap<K, V>元素的类型是pair<const K, V>
• 原地修改键对map和multimap来说是不可能的（除非用const_cast去掉const属性，但没有人会这样做），但对set和multiset却是可能的，因为set<T>或multiset<T>的元素类型是T而非const T
• 首先要理解为什么set里的类型不是const

// 一个雇员类
class Employee {
public:
    ...
    const string& name() const; // 获取雇员名
    void setName(const string& name); // 设置雇员名
    const string& getTitle() const; // 获取雇员头衔
    void setTitle(string& title); // 设置雇员头衔
    int idNumber() const; // 获取雇员ID号
    ...
};
// 以ID号来排序
struct IDNumberLess : public binary_function<Employee, Employee, bool> {
    bool operator()(const Employees lhs, const Employee& rhs) const
    {
        return lhs.idNumber() < rhs.idNumber();
    }
};
// 建立雇员类的set
typedef set<Employee, IDNumberLess> EmpIDSet;
EmpIDSet se; // se按ID号排序
// ID是主键不能修改，但对雇员的头衔做修改是合法的
// 而这种行为的合法则决定了set元素不能是const
Employee selectedID; // 容纳被选择雇员的ID号
...
EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end())
{
    i->setTitle("Corporate Deity"); // 给雇员新头衔
}

• 上面的原因对于map来说其实也是适用的，但标准委员会认为map/multimap键应该是const而set/multiset的值不是
• 即使set和multiset的元素不是const，仍然有很多阻止修改方式，比如让用于set<T>::iterator的operator*返回一个const T&，不过这样的实现不一定合法，根据不同编译器有不同的表现结果，既然标准模棱两可，试图修改set或multiset中元素的代码就不可移植
• 如果不关心移植性，要改变set或multiset中元素的值，编译器可以通过，那就保持这样，但要确定不要改变元素的键部分，即影响容器有序性的元素部分。如果在乎移植性，就认为set和multiset中的元素在没有const_cast的情况下不能被修改

EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()) {
    i->setTitle("Corporate Deity"); // 有些编译器不能通过，因为*i是const
}
// 为了编译通过使用const_cast
if (i != se.end()) {
   const_cast<Employee&>(*i).setTitle("Corporate Deity");
}
// static_cast不可行，因为修改的只是临时对象
if (i != se.end()) {
    static_cast<Employee>(*i).setTitle("Corporate Deity");
}
// 等价于
if (i != se.end()){
    Employee tempCopy(*i); // 把*i拷贝到tempCopy
    tempCopy.setTitle("Corporate Deity"); // 修改tempCopy
}

• 要安全地改变set、multiset、map或multimap里的元素，按五个简单的步骤去做
  • 定位想要改变的容器元素
  • 拷贝一份要被修改的元素
  • 修改副本，使它有你想要在容器里的值
  • 调用erase删除容器中的元素
  • 把新值插入容器。如果新元素在容器的排序顺序中的位置正好相同或相邻于删除的元素，使用insert
    的“提示”形式（第一步获得的迭代器作为提示）把插入的效率从对数时间改进到分摊的常数时间

typedef set<Employee, IDNumberLess> EmpIDSet;
EmpIDSet se;
Employee selectedID;
...
EmpIDSet::iterator i = se.find(selectedID); // 第一步：找到要改变的元素
if (i!=se.end())
{
    Employee e(*i); // 第二步：拷贝元素
    se.erase(i++); // 第三步：删除元素，自增保持迭代器有效
    e.setTitle("Corporate Deity"); // 第四步：修改副本
    se.insert(i, e); // 第五步：插入新值，提示它的位置和原先元素的一样
}

23 考虑用有序vector代替关联容器

• 标准关联容器的典型实现是平衡二叉查找树，平衡二叉查找树是对插入、删除和查找的混合操作优
  化的数据结构，因此它的设计目标是优化这些混合操作
• 很多应用中的数据结构没有那么混乱，它们有三个不同的阶段
  • 建立。通过插入很多元素建立一个新的数据结构。在这个阶段，几乎所有的操作都是插入和删除，几
    乎没有查找
  • 查找。在数据结构中查找指定的信息片。在这个阶段，几乎所有的操作都是查找，几乎没有插入和删除
  • 重组。通过删除所有现有数据或在原地插入新数据修改内容。这个阶段的行为等价于阶段1，一旦这个阶段完成，程序返回阶段2
• 对于使用上述数据结构的应用来说，vector可能比关联容器性能高（时间和空间上都是）。但必须是有序vector，因为有序容器才能使用查找算法binary_search、lower_bound、equal_range等
• vector二分查找比二叉树的二分查找性能好的原因是，平衡二叉树的每个类对象要附加左右孩子和父节点三个指针，而vector没有这种开销。假如数据结构足够大，分为多个内存页面，类的大小为12个字节，指针为4个字节，一个内存页面为4096（4K）字节，用vector可以保存4096/12=341个对象，而关联容器只能保存一半
• 当然，有序vector的最大缺点是必须保持有序，插入和删除开销大，新元素插入时，大于新元素的所有元素都必须向上移一位，删除同理。因此数据结构使用查找而几乎不用插入和删除时，有序vector代替关联容器才有意义
• 使用有序vector代替set的代码框架，其中最难的是选择搜索算法，见item45

vector<Widget> vw;
... // 建立阶段
sort(vw.begin(), vw.end()); // 结束建立阶段，模拟multiset时用stable_sort，见item31
Widget w; // 用于查找的值的对象
... // 开始查找阶段
if (binary_search(vw.begin(), vw.end(), w))... // 通过binary_search查找
vector<Widget>::iterator i = lower_bound(vw.begin(), vw.end(), w); // 通过lower_bound查找
if (i != vw.end() && !(w < *i))...
pair<vector<Widget>::iterator, vector<Widget>::iterator> range =
    equal_range(vw.begin(), vw.end(), w); // 通过equal_range查找
if (range.first != range.second)...
... // 结束查找阶段，开始重组阶段
sort(vw.begin(), vw.end()); // 开始新的查找阶段...

• map中的元素类型是pair<const K, V>，要用vector模拟map或者multimap时必须去掉const，因为对vector排序时，元素值会通过赋值移动
• map和multimap排序只作用于元素的key，而pair的operator<作用于pair的两个组件，所以排序vector时要给pair自定义比较函数，排序的比较函数的参数是两个pair。另外还需要第二个比较函数用于查找，查找只用到key，需要传给查找的比较函数一个key和一个pair，因为不知道key还是pair是作为第一个实参传递的，所以需要写两个函数

typedef pair<string, int> Data;
class DataCompare { // 用于比较的类
public:
    bool operator()(const Data& lhs, const Data& rhs) const // 用于排序的比较函数
    {
        return keyLess(lhs.first, rhs.first);
    }
    bool operator()(const Data& Ihs, const Data::first_type& k) const // 用于查找的比较函数（形式1）
    {
        return keyLess(lhs.first, k);
    }
    bool operator()(const Data::first_type& k, const Data& rhs) const // 用于查找的比较函数（形式2）
    {
        return keyLessfk, rhs.first);
    }
private:
    bool keyLess(const Data::first_type& k1, const Data::first_type& k2) const // 真正的比较函数
    {
        return k1 < k2;
    }
};

vector<Data> vd; // 代替map<string, int>
... // 建立阶段
sort(vd.begin(), vd.end(), DataCompare()); // 结束建立阶段，模拟multimap时用stable_sort
string s; // 用于查找的值的对象
... // 开始查找阶段
if (binary_search(vd.begin(), vd.end(), s, DataCompare()))... // 通过binary_search查找
vector<Data>::iterator i = lower_bound(vd.begin(), vd.end(), s, DataCompare()); // 通过lower_bound查找
if (i != vd.end() && !DataCompare()(s, *i))...
pair<vector<Data>::iterator, vector<Data>::iterator> range =
    equal_range(vd.begin(), vd.end(), s, DataCompare()); // 通过equal_range查找
if (range.first != range.second)...
... // 结束查找阶段，开始重组阶段
sort(vd.begin(), vd.end(), DataCompare()); // 开始新的查找阶段...

24 当关乎效率时应该在map::operator[]和map-insert之间仔细选择

• map::operator[]被设计为简化“添加或更新”功能，对于m[k] = v，检查键k，如果k已经在map里，关联值被更新成v，否则就添加上，以v作为对应值。原理是operator[]返回一个与k关联的值对象的引用，然后v赋值给所引用对象，如果k不在map里，operator[]就没有可以引用的值对象，于是值类型的默认构造函数重新建立一个，operator[]返回新建立对象的引用

map<int, Widget> m;
m[1] = 1.50;
// 等价于
typedef map<int, Widget> IntWidgetMap;
pair<IntWidgetMap::iterator, bool> result = m.insert(IntWidgetMap::value_type(1, Widget())); 
result.first->second = 1.50;

• 由上述代码可知，用想要的值构造Widget比默认构造Widget再赋值显然更高效。用insert替换operator[]，节省了三次函数调用：默认构造Widget对象，销毁临时对象和一个赋值操作

m.insert(IntWidgetMap::value_type(1, 1.50));

• 添加时insert比operator[]更高效，当等价的键已经在map里再更新时正好相反。insert需要IntWidgetMap::value_type类型实参（即pair<int, Widget>），调用insert时必须构造和析构一个该类型对象，耗费了一对构造函数和析构函数，因为pair<int, Widget>本身包含了一个Widget对象，还会造成一个Widget的构造和析构，operator[]没有使用pair对象，所以没有构造和析构pair和Widget

m[k] = v; // 使用operator[]
m.insert(IntWidgetMap::value_type(k, v)).first->second = v; // 使用insert

• 可以自己实现一个对于添加和更新都适用的函数

template<typename MapType, typename KeyArgType, typename ValueArgtype>
typename MapType::iterator efficientAddOrUpdate
    (MapType& m, const KeyArgType& k, const ValueArgtype& v)
{
    typename MapType::iterator Ib = m.lower_bound(k);
    if(Ib != m.end() && !(m.key_comp()(k, Ib->first)))
    {
        Ib->second = v;
        return Ib;
    }
    else
    {
        typedef typename MapType::value_type MVT;
        return m.insert(Ib, MVT(k, v)); // 把pair(k, v)添加到m并返回指向新map元素的迭代器
    }
}

efficientAddOrUpdate(m, 10, 1.5);
// 如果m已经包含键是10的元素，推断出ValueArgType是double
// 函数体直接把1.5作为double赋给与10相关的那个Widget

25 熟悉非标准散列容器

• 兼容STL的散列关联容器可以从多个来源获得，而且它们的名字通常是：hash_set、hash_multiset、hash_map和hash_multimap。但因为没有遵循一个标准实现，为了避开这些名字，在C++标准委员会的议案中，散列容器的名字是unordered_set、unordered_multiset、unordered_map和unordered_multimap，C++11中引入了这些容器