C++ | 3-需要函数对象的容器

函数对象及其特化

首先来讨论一下两个重要的函数对象，less 和 hash。

们先看一下 less，小于关系。在标准库里，通用的 less 大致是这样定义的：

template <class T>
struct less
: binary_function<T, T, bool>
{
    bool operator()(const T& x,
                    const T& y) const
    {
        return x < y;
    }
};

也就是说，less 是一个函数对象，并且是个二元函数，执行对任意类型的值的比较，返回 布尔类型。

作为函数对象，它定义了函数调用运算符（operator()），并且缺省行为是 对指定类型的对象进行 < 的比较操作。

这个缺省实现在大部分情况下已经够用，我们不太需要去碰它。在需要大小比较的场合，C++ 通常默认会使用 less，包括我们今天会讲到的若干 容器和排序算法 sort。如果我们需要产生相反的顺序的话，则可以使用 greater，大于关系。

计算哈希值的函数对象 hash 就不一样了。它的目的是把一个某种类型的值转换成一个无符 号整数哈希值，类型为 size_t。它没有一个可用的默认实现。对于常用的类型，系统提供 了需要的特化 [2]，类似于：

template <class T> struct hash;
template <>
struct hash<int>
: public unary_function<int, size_t> {
　　size_t operator()(int v) const
　　noexcept
　　{
　　　　return static_cast<size_t>(v);
　　}
}； 

 对于每个类，类的作者都可以提供 hash 的特化，使得对于不同的对象值，函数调用运算符都能得到尽可能均匀分布的不同数值。

priority_queue

priority_queue 也是一个容器适配器。它用到了比较函数对象（默认是 less）。它和 stack 相似，支持 push、pop、top 等 有限的操作，但容器内的顺序既不是后进先出，也不是先进先出，而是（部分）排序的结 果。在使用缺省的 less 作为其 Compare 模板参数时，最大的数值会出现在容器的“顶 部”。如果需要最小的数值出现在容器顶部，则可以传递 greater 作为其 Compare 模板 参数。

关联容器

关联容器有 set（集合）、map（映射）、multiset（多重集）和 multimap（多重映 射）。跳出 C++ 的语境，map（映射）的更常见的名字是关联数组和字典，而在 JSON 里直接被称为对象（object）。在 C++ 外这些容器常常是无序的；在 C++ 里关联容器则 被认为是有序的。

关联容器是一种有序的容器。名字带“multi”的允许键重复，不带的不允许键 重复。set 和 multiset 只能用来存放键，而 map 和 multimap 则存放一个个键值对。

与序列容器相比，关联容器没有前、后的概念及相关的成员函数，但同样提供 insert、 emplace 等成员函数。此外，关联容器都有 find、lower_bound、upper_bound 等查 找函数，结果是一个迭代器：

find(k) 可以找到任何一个等价于查找键 k 的元素（!(x < k || k < x)）

lower_bound(k) 找到第一个不小于查找键 k 的元素（!(x < k)）

upper_bound(k) 找到第一个大于查找键 k 的元素（k < x）

如果你需要在 multimap 里精确查找满足某个键的区间的话，建议使用 equal_range， 可以一次性取得上下界（半开半闭）。如下所示：

#include <tuple>
multimap<string, int>::iterator
    lower, upper;
std::tie(lower, upper) =
    mmp.equal_range("four");
(lower != upper) // 检测区间非空,true

无序关联容器

从 C++11 开始，每一个关联容器都有一个对应的无序关联容器，它们是：

unordered_set 

unordered_map

unordered_multiset

unordered_multimap

这些容器不要求提供 一个排序的函数对象，而要求一个可以计算哈希值的函数对象。

从实际的工程角度，无序关联容器的主要优点在于其性能。关联容器和 priority_queue 的插入和删除操作，以及关联容器的查找操作，其复杂度都是 O(log(n))，而无序关联容器 的实现使用哈希表 [5]，可以达到平均 O(1)！但这取决于我们是否使用了一个好的哈希函 数：在哈希函数选择不当的情况下，无序关联容器的插入、删除、查找性能可能成为最差情 况的 O(n)，那就比关联容器糟糕得多了。

array

C 数组没有 begin 和 end 成员函数（虽然可以使用全局的 begin 和 end 函数）

C 数组没有 size 成员函数（得用一些模板技巧来获取其长度）

C 数组作为参数有退化行为，传递给另外一个函数后那个函数不再能获得 C 数组的长度 和结束位置

C 数组也没有良好的复制行为。你无法用 C 数组作为 map 或 unordered_map 的 键类型。

三个可以考虑的选项：

如果数组较大的话，应该考虑 vector。vector 有最大的灵活性和不错的性能。

对于字符串数组，当然应该考虑 string。

如果数组大小固定（C 的数组在 C++ 里本来就是大小固定的）并且较小的话，应该考虑 array。array 保留了 C 数组在栈上分配的特点，同时，提供了 begin、end、size 等通用成员函数。 array 可以避免 C 数组的种种怪异行径。