《Effective STL》读书笔记（三）：关联容器

理解相等（equality）和等价（equivalence）的区别

相等的概念是基于operator==的，但是相等不意味着两个对象完全相等，取决于operator==的具体实现。

等价关系是以“在已排序的区间中对象值的相对顺序”为基础的。对于两个对象x和y，如果按照关联容器c的排列顺序，每个都不在另一个的前面，那么这两个对象的值在c中就是等价的。针对一个set来说，它的默认比较函数是less，在默认情况下less只是简单的调用了Widget的operator<，所以对于两个对象w1, w2如果满足!(w1 < w2) && !(w2 < w1)，那么它俩就是等价的。

一般情况下，一个关联容器的比较函数不是operator<或less，而是用户定义的判别式，每个标准关联容器都通过key_comp成员函数使排序判别式可被外部使用。如果下面的表达式为true，则按照关联容器c的排列方式，两个对象x和y就具有等价的值：

!c.key_comp()(x, y) && !c.key_comp()(y, x)
1

上面的式子看起来有点难以理解，实际上c.key_comp()返回一个函数（或函数对象），知道这个之后就可以读懂了。

这里有一个坑，关联容器插入数据需要排序，排序时调用的是容器的比较函数（比较函数默认是less，我们也可以指定），但是在进行查找时，需要判断两个对象是否有相等值，默认情况下比较函数是equal_to，但是STL中的一般惯例是直接调用operator==。假如有一个可以忽略字符串字符大小写的，类似于set的容器set2CF：

set2CF<string, CIStringCompare, equal_to<string> > s;  // CIStringCompare指明了字符串的排序方式, equal_to用来决定两个对象是否有相同值

s.insert("Persephone");
s.insert("persephone");  // 因为排序忽略大小写，所以这次插入被忽略

if (s.find("persephone") != s.end())  // 判断是否可以成功
    //......
1
2
3
4
5
6
7

这个find函数可能调用的是相等判断，因为我们并没有指定一个忽略字符大小写的相等判断方法，代码中的判断式在这种情况下为false。

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

假定有一个包含string*指针的set

set<string*> ssp;
ssp.insert(new string("Anteater"));
ssp.insert(new string("Wombat"));
ssp.insert(new string("Lemur"));
ssp.insert(new string("Penguin"));
1
2
3
4
5

如果想要打印这个集合的可能首先想到的方法是

for (auto i = ssp.begin(); i != ssp.end(); ++i)
    cout << *i << endl;
1
2

但是实际上面的话只能打印出这四个指针的地址，但是如果改用**i打印的话，是可以打印出字符串了，但是set并没有把字符串进行排序，而是按照指针的地址进行排序的

set<string*> ssp;
// 等价于
set<string*, less<string*> > ssp;
// 等价于
set<string*, less<string*>, allocator<string*> > ssp;  // 但是allocator和这里讨论的问题无关
1
2
3
4
5

如果我们想要按照指向的字符串的值进行排序，那么我们就需要指定排序方式

struct StringPtrLess:
	public binary_function<const string*,
						const string*,
						bool> {
     bool operator() (const string *ps1, const string *ps2) const {
         return *ps1 < *ps2;
     }
}
1
2
3
4
5
6
7
8

然后把StringPtrLess作为ssp的比较类型

typedef set<string*, StringPtrLess> StringPtrSet;
StringPtrSet ssp;
1
2

接下来就可以以正确的方式打印出字符串了

for (StringPtrSet::const_iterator i = ssp.begin(); i != ssp.end(); ++i)
    cout << **i << endl;
1
2

如果要进一步写一个通用的解除指针引用的函数子类的话

// 传入T*类型变量，返回constet T&
struct Dereference {
    templage<typename T>
    const T& operator ()(const T* ptr) const {
        return *ptr;
    }
}
1
2
3
4
5
6
7

这样就可以调用算法库中的函数方便的代替循环来进行输出

transform(ssp.begin(), ssp.end(), ostream_iterator<string>(cout, "\n"), Dereference);
1

采用这种解引用的方式，我们可以修改上面的StringPtrLess

struct DereferenceLess {
    template<typename PtrType>
    bool operator()(PtrType pT1, PtrType pT2) const {
        return *pT1 < pT2;
    }
}
1
2
3
4
5
6

然后在声明set的时候就可以使用下面的这种方法

set<string*, DereferenceLess> ssp;  // 与set行为相同
1

让比较函数在等值情况下返回false

有这样一个例子，按照下面的方式创建一个set

set<int, less_equal<int> > s;  // 使用 <= 来排序
s.insert(10);  // 插入一个10
1
2

在现在这种情况下，再尝试插入一个10

s.insert(10);
1

这一次插入的时候，集合会进行比较在确定10是否已经存在在集合中。对于关联容器来说，“相同”的定义是等价，最后要检查第一次插入的10和将要插入的10是否等价。此时就会调用我们传入的比较函数operator<=。

集合采用下面的方式来判断等价性

!(10 <= 10) && !(10 <= 10);
// =>
!(true) && !(true);
// =>
false && false;
1
2
3
4
5

然后集合就得到了结论这两个10不等价！

所以对于关联容器排序的比较函数，必须为容器中存放的对象定义一个“严格的弱序化”，对于传递给sort这类的算法的比较也有同样的限制。

切勿直接修改set或multiset中的键

所有关联容器元素的排列都是有一定顺序的，这些容器的正确行为也依赖于元素的正确排列。如果把关联容器的一个元素的值改变了，那么新插入的值就可能不在正确的位置上。

对于map和multimap来说，如果有程序试图改变容器中的键，那么他就不能通过编译：

map<int, string> m;
m.begin()->first = 10;   // map键不能被修改

multimap<int, string> mm;
mm.begin()->first = 20;		// multimap键同样不能修改
1
2
3
4
5

这是因为map和multimap的元素类型是pair，所以键的值就不能被修改。（但是可以通过强制类型转换去除const语义。）

但是对于set和multiset来说，容器中元素的类型是T，而不是const T。所以可以随时改变set或multiset中的元素而不需要强制类型转换。

先解释一下为什么set/multiset的元素不是const的，假设现在有一个雇员类，每个对象除了唯一标识身份的ID之外还有很多其他信息，在逻辑上，改变除ID外的其他信息是合理的。

那么为什么同样的逻辑不能用于map和multimap的键呢，这就是标准委员会的想法了。

在有的STL实现里面可能认为改变set和multiset内的元素是不合法的，这时候我们可以通过强制类型转换来达到目的。

EmpIDSet se;
Employee selectedID:

EmpIDSet::iterator i = se.find(selectedID);
if (i != se.end()) {
    i -> setTitle("Corporate Deity");		// 某些STL实现下编译不通过
}

// 改用强制类型转换
if (i != se.end()) {
    const_cast<Employee&>(*i).setTitle("Corporate Deity");  // 去除掉*i的const属性
}

// 下面两种强制类型转换方式是错误的
if (i != se.end()) {
    static_cast<Employee>(*i).setTitle("Corporate Deity");
}
if (i != se.end()) {
    ((Employee)(*i)).setTitle("Corporate Deity");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最后这两种强制类型转换是等价的，它们也可以通过编译，但是并达不到我们希望的效果，原因是强制类型转换后实际上产生了一个临时的匿名对象，setTitle实际作用在了临时对象上面，后两种方法等价于

if (i != se.end()) {
    Employee tempCopy(*i);
    tempCopy.setTitle("Corporate Deity");
}
1
2
3
4

如果想更改map/multimap的键值，那么可以采取先拷贝一份待修改的元素，然后删除容器中的元素，将拷贝修改后再插入原容器即可。

EmpIDSet se;
Employee selectedID;

EmpIDSet::iterator i = se.find(selectedID);  // 找到待修改的元素
if (i != se.end()) {
    Employee e(*i);		// 拷贝该元素
    e.setTitle("Corporate Deity");	// 修改拷贝
    se.erase(i++);		// 删除拷贝, 使用后缀自增确保迭代器不失效
    se.insert(i, e);	// 插入新元素, 通过提示位置将插入的效率从对数时间提高到常数时间
}
1
2
3
4
5
6
7
8
9
10

C++17中的关联容器中引入了extract成员函数
可以使用extract从容器中取下指定的元素，而不需要自己进行拷贝和删除的过程，STL帮我们从关联容器中删除了指定元素，然后返回被删除元素的引用，官方代码示例如下

#include 
#include 
#include 
#include 
 
void print(std::string_view comment, const auto& data)
{
    std::cout << comment;
    for (auto [k, v] : data)
        std::cout << ' ' << k << '(' << v << ')';
 
    std::cout << '\n';
}
 
int main()
{
    std::map<int, char> cont{{1, 'a'}, {2, 'b'}, {3, 'c'}};
 
    print("Start:", cont);
 
    // Extract node handle and change key
    auto nh = cont.extract(1);
    nh.key() = 4;
 
    print("After extract and before insert:", cont);
 
    // Insert node handle back
    cont.insert(std::move(nh));  // 使用move来提示将nh移动进cont中, 而不是被拷贝进cont中
 
    print("End:", cont);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

考虑使用排序的vector来替代关联容器

当我们真的需要一个快速查找的数据结构时，考虑一下哈希容器，如果容器的容量及哈希函数选择恰当的话，哈希容器可以提供近似常数时间的查找能力。

如果对数时间的查找能力已经足够，但是关联容器依然不是第一选择，排序的vector在很多情况下可以提供比关联容器更高的效率。

为什么排序的vector执行二分搜索的效率比二叉搜索树的效率更好呢？
先考虑大小的问题，二叉搜索树的节点不仅包含了存储的对象，而且还包含几个指针：指向做儿子的指针，指向右儿子的指针，通常还会有一个指向父节点的指针。
如果对于vector来说除了存储对象外的额外开销要少很多，在vector末尾可能会有一些预留的空间，但是这部分空间可以通过swap技巧去除。

数据结构的大小是如何影响性能的呢？
假如数据结构足够大，那么分割后将跨越多个内存页面。而且多余的存储也会占用更多的内存。
另外还和局部性原理相关，vector中的元素都是放在一起的，而关联容器的节点可能会分布在内存的任何地方，显然对vector进行二分查找可以产生更少的页面错误。

但是当对vector中元素进行增删改的时候，要维护vector的有序需要花费很大的代价，所以在容器内修改占比较多的情况下，使用vector可能就搞不定了，这时再考虑关联容器。

当数据结构的使用满足下面这三个阶段的时候，选用排序vector是合理的：

1. 设置阶段。创建一个新的数据结构，并插入大量元素，在这个阶段，几乎所有的操作都是插入和删除操作，很少或几乎没有查找操作
2. 查找阶段。在这个数据结构上进行查询操作，这个截断中，几乎所有的操作都是查找操作，很少或几乎没有插入和删除操作
3. 重组阶段。改变该数据结构的内容。在行为上与一阶段类似。当这个阶段结束后，应用程序又回到第2阶段。

效率重要时，谨慎选择map::operator[]和map::insert

当向映射表中添加元素的时候，优先选用insert；当更新已经在映射表中的元素的值的时候，要优先选用operator[]。

向映射表中添加元素使用operator[]的时候，会经历两个过程，先默认构造一个对象，然后立刻赋给它新的值，而使用insert可以直接用值构造出想要的对象，相比operator[]会节省三个函数调用：一个用于创建默认构造的临时对象，一个用于析构临时对象，一个是调用对象的赋值操作符。

更新元素的值的时候，如果使用insert，会额外产生一个operator[]不需要的pair对象，会有pair构造和析构的代价，这又会导致值对象的构造和析构动作，因为pair中包含一个值对象。