05 | 容器汇编 II：需要函数对象的容器

Dec 6, 2019

05 | 容器汇编 II：需要函数对象的容器-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

05 | 容器汇编 II：需要函数对象的容器

2019-12-06 吴咏炜来自北京

《现代C++编程实战》

课程介绍



讲述：吴咏炜

时长11:40大小8.00M



你好，我是吴咏炜。
上一讲我们学习了 C++ 的序列容器和两个容器适配器，今天我们继续讲完剩下的标准容器（[1]）。
函数对象及其特化在讲容器之前，我们需要首先来讨论一下两个重要的函数对象，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);
  }
};
这当然是一个极其简单的例子。更复杂的类型，如指针或者 string 的特化，都会更复杂。要点是，对于每个类，类的作者都可以提供 hash 的特化，使得对于不同的对象值，函数调用运算符都能得到尽可能均匀分布的不同数值。
我们用下面这个例子来加深一下理解：
#include <algorithm>   // std::sort
#include <functional>  // std::less/greater/hash
#include <iostream>    // std::cout/endl
#include <string>      // std::string
#include <vector>      // std::vector
#include "output_container.h"
using namespace std;
int main()
{
  // 初始数组
  vector<int> v{13, 6, 4, 11, 29};
  cout << v << endl;
  // 从小到大排序
  sort(v.begin(), v.end());
  cout << v << endl;
  // 从大到小排序
  sort(v.begin(), v.end(),
       greater<int>());
  cout << v << endl;
  cout << hex;
  auto hp = hash<int*>();
  cout << "hash(nullptr)  = "
       << hp(nullptr) << endl;
  cout << "hash(v.data()) = "
       << hp(v.data()) << endl;
  cout << "v.data()       = "
       << static_cast<void*>(v.data())
       << endl;
  auto hs = hash<string>();
  cout << "hash(\"hello\")  = "
       << hs(string("hello")) << endl;
  cout << "hash(\"hellp\")  = "
       << hs(string("hellp")) << endl;
}
在 MSVC 下的某次运行结果如下所示：
{ 13, 6, 4, 11, 29 }
{ 4, 6, 11, 13, 29 }
{ 29, 13, 11, 6, 4 }
hash(nullptr) = a8c7f832281a39c5
hash(v.data()) = 7a0bdfd7df0923d2
v.data() = 000001EFFB10EAE0
hash("hello") = a430d84680aabd0b
hash("hellp") = a430e54680aad322
可以看到，在这个实现里，空指针的哈希值是一个非零的数值，指针的哈希值也和指针的数值不一样。要注意不同的实现处理的方式会不一样。事实上，我的测试结果是 GCC、Clang 和 MSVC 对常见类型的哈希方式都各有不同。
在上面的例子里，我们同时可以看到，这两个函数对象的值不重要。我们甚至可以认为，每个 less（或 greater 或 hash）对象都是等价的。关键在于其类型。以 sort 为例，第三个参数的类型确定了其排序行为。
对于容器也是如此，函数对象的类型确定了容器的行为。
priority_queuepriority_queue 也是一个容器适配器。上一讲没有和其他容器适配器一起讲的原因就在于它用到了比较函数对象（默认是 less）。它和 stack 相似，支持 push、pop、top 等有限的操作，但容器内的顺序既不是后进先出，也不是先进先出，而是（部分）排序的结果。在使用缺省的 less 作为其 Compare 模板参数时，最大的数值会出现在容器的“顶部”。如果需要最小的数值出现在容器顶部，则可以传递 greater 作为其 Compare 模板参数。
下面的代码可以演示其功能：
#include <functional>  // std::greater
#include <iostream>    // std::cout/endl
#include <memory>      // std::pair
#include <queue>       // std::priority_queue
#include <vector>      // std::vector
#include "output_container.h"
using namespace std;
int main()
{
  priority_queue<
    pair<int, int>,
    vector<pair<int, int>>,
    greater<pair<int, int>>>
    q;
  q.push({1, 1});
  q.push({2, 2});
  q.push({0, 3});
  q.push({9, 4});
  while (!q.empty()) {
    cout << q.top() << endl;
    q.pop();
  }
}
输出为：
(0, 3)
(1, 1)
(2, 2)
(9, 4)
关联容器关联容器有 set（集合）、map（映射）、multiset（多重集）和 multimap（多重映射）。跳出 C++ 的语境，map（映射）的更常见的名字是关联数组和字典 [3]，而在 JSON 里直接被称为对象（object）。在 C++ 外这些容器常常是无序的；在 C++ 里关联容器则被认为是有序的。
我们可以通过以下的 xeus-cling 交互来体会一下。
#include <functional>
#include <map>
#include <set>
#include <string>
using namespace std;
set<int> s{1, 1, 1, 2, 3, 4};
s
{ 1, 2, 3, 4 }
multiset<int, greater<int>> ms{1, 1, 1, 2, 3, 4};
ms
{ 4, 3, 2, 1, 1, 1 }
map<string, int> mp{
  {"one", 1},
  {"two", 2},
  {"three", 3},
  {"four", 4}
};
mp
{ "four" => 4, "one" => 1, "three" => 3, "two" => 2 }
mp.insert({"four", 4});
mp
{ "four" => 4, "one" => 1, "three" => 3, "two" => 2 }
mp.find("four") == mp.end()
false
mp.find("five") == mp.end()
(bool) true
mp["five"] = 5;
mp
{ "five" => 5, "four" => 4, "one" => 1, "three" => 3, "two" => 2 }
multimap<string, int> mmp{
  {"one", 1},
  {"two", 2},
  {"three", 3},
  {"four", 4}
};
mmp
{ "four" => 4, "one" => 1, "three" => 3, "two" => 2 }
mmp.insert({"four", -4});
mmp
{ "four" => 4, "four" => -4, "one" => 1, "three" => 3, "two" => 2 }
可以看到，关联容器是一种有序的容器。名字带“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）
mp.find("four")->second
4
mp.lower_bound("four")->second
4
(--mp.upper_bound("four"))->second
4
mmp.lower_bound("four")->second
4
(--mmp.upper_bound("four"))->second
-4
如果你需要在 multimap 里精确查找满足某个键的区间的话，建议使用 equal_range，可以一次性取得上下界（半开半闭）。如下所示：
#include <tuple>
multimap<string, int>::iterator
  lower, upper;
std::tie(lower, upper) =
  mmp.equal_range("four");
(lower != upper)  // 检测区间非空
true
lower->second
4
(--upper)->second
-4
如果在声明关联容器时没有提供比较类型的参数，缺省使用 less 来进行排序。如果键的类型提供了比较算符 < 的重载，我们不需要做任何额外的工作。否则，我们就需要对键类型进行 less 的特化，或者提供一个其他的函数对象类型。
对于自定义类型，我推荐尽量使用标准的 less 实现，通过重载 <（及其他标准比较运算符）对该类型的对象进行排序。存储在关联容器中的键一般应满足严格弱序关系（strict weak ordering；[4]），即：
对于任何该类型的对象 x：!(x < x)（非自反）
对于任何该类型的对象 x 和 y：如果 x < y，则 !(y < x)（非对称）
对于任何该类型的对象 x、y 和 z：如果 x < y 并且 y < z，则 x < z（传递性）
对于任何该类型的对象 x、y 和 z：如果 x 和 y 不可比（!(x < y) 并且 !(y < x)）并且 y 和 z 不可比，则 x 和 z 不可比（不可比的传递性）
大部分情况下，类型是可以满足这些条件的，不过：
如果类型没有一般意义上的大小关系（如复数），我们一定要别扭地定义一个大小关系吗？
通过比较来进行查找、插入和删除，复杂度为对数 O(log(n))，有没有达到更好的性能的方法？
无序关联容器从 C++11 开始，每一个关联容器都有一个对应的无序关联容器，它们是：
unordered_set
unordered_map
unordered_multiset
unordered_multimap
这些容器和关联容器非常相似，主要的区别就在于它们是“无序”的。这些容器不要求提供一个排序的函数对象，而要求一个可以计算哈希值的函数对象。你当然可以在声明容器对象时手动提供这样一个函数对象类型，但更常见的情况是，我们使用标准的 hash 函数对象及其特化。
下面是一个示例（这次我们暂不使用 xeus-cling，因为它在输出复数时有限制，不能显示其数值）：
#include <complex>        // std::complex
#include <iostream>       // std::cout/endl
#include <unordered_map>  // std::unordered_map
#include <unordered_set>  // std::unordered_set
#include "output_container.h"
using namespace std;
namespace std {
template <typename T>
struct hash<complex<T>> {
  size_t
  operator()(const complex<T>& v) const
    noexcept
  {
    hash<T> h;
    return h(v.real()) + h(v.imag());
  }
};
}  // namespace std
int main()
{
  unordered_set<int> s{
    1, 1, 2, 3, 5, 8, 13, 21
  };
  cout << s << endl;
  unordered_map<complex<double>,
                double>
    umc{1.0, 1.0}, 1.4142},
        {3.0, 4.0}, 5.0};
  cout << umc << endl;
}
输出可能是（顺序不能保证）：
{ 21, 5, 8, 3, 13, 2, 1 }
{ (3,4) => 5, (1,1) => 1.4142 }
请注意我们在 std 名空间中添加了特化，这是少数用户可以向 std 名空间添加内容的情况之一。正常情况下，向 std 名空间添加声明或定义是禁止的，属于未定义行为。
从实际的工程角度，无序关联容器的主要优点在于其性能。关联容器和 priority_queue 的插入和删除操作，以及关联容器的查找操作，其复杂度都是 O(log(n))，而无序关联容器的实现使用哈希表 [5]，可以达到平均 O(1)！但这取决于我们是否使用了一个好的哈希函数：在哈希函数选择不当的情况下，无序关联容器的插入、删除、查找性能可能成为最差情况的 O(n)，那就比关联容器糟糕得多了。
array我们讲的最后一个容器是 C 数组的替代品。C 数组在 C++ 里继续存在，主要是为了保留和 C 的向后兼容性。C 数组本身和 C++ 的容器相差是非常大的：
C 数组没有 begin 和 end 成员函数（虽然可以使用全局的 begin 和 end 函数）
C 数组没有 size 成员函数（得用一些模板技巧来获取其长度）
C 数组作为参数有退化行为，传递给另外一个函数后那个函数不再能获得 C 数组的长度和结束位置
在 C 的年代，大家有时候会定义这样一个宏来获得数组的长度：
#define ARRAY_LEN(a) \
  (sizeof(a) / sizeof((a)[0]))
如果在一个函数内部对数组参数使用这个宏，结果肯定是错的。现在 GCC 会友好地发出警告：
void test(int a[8])
{
  cout << ARRAY_LEN(a) << endl;
}
warning: sizeof on array function parameter will return size of ‘int *’ instead of ‘int [8]’ [-Wsizeof-array-argument]
    cout << ARRAY_LEN(a) << endl;
C++17 直接提供了一个 size 方法，可以用于提供数组长度，并且在数组退化成指针的情况下会直接失败：
#include <iostream>  // std::cout/endl
#include <iterator>  // std::size
void test(int arr[])
{
  // 不能编译
  // std::cout << std::size(arr)
  //           << std::endl;
}
int main()
{
  int arr[] = {1, 2, 3, 4, 5};
  std::cout << "The array length is "
            << std::size(arr)
            << std::endl;
  test(arr);
}
此外，C 数组也没有良好的复制行为。你无法用 C 数组作为 map 或 unordered_map 的键类型。下面的代码演示了失败行为：
#include <map>  // std::map
typedef char mykey_t[8];
int main()
{
  std::map<mykey_t, int> mp;
  mykey_t mykey{"hello"};
  mp[mykey] = 5;
  // 轰，大段的编译错误
}
如果不用 C 数组的话，我们该用什么来替代呢？
我们有三个可以考虑的选项：
如果数组较大的话，应该考虑 vector。vector 有最大的灵活性和不错的性能。
对于字符串数组，当然应该考虑 string。
如果数组大小固定（C 的数组在 C++ 里本来就是大小固定的）并且较小的话，应该考虑 array。array 保留了 C 数组在栈上分配的特点，同时，提供了 begin、end、size 等通用成员函数。
array 可以避免 C 数组的种种怪异行径。上面的失败代码，如果使用 array 的话，稍作改动就可以通过编译：
#include <array>     // std::array
#include <iostream>  // std::cout/endl
#include <map>       // std::map
#include "output_container.h"
typedef std::array<char, 8> mykey_t;
int main()
{
  std::map<mykey_t, int> mp;
  mykey_t mykey{"hello"};
  mp[mykey] = 5;  // OK
  std::cout << mp << std::endl;
}
输出则是意料之中的：
{ hello => 5 }
内容小结本讲介绍了 C++ 的两个常用的函数对象，less 和 hash；然后介绍了用到这两个函数对象的容器适配器、关联容器和无序关联容器；最后，通过例子展示了为什么我们应当避免 C 数组而考虑使用 array。通过这两讲，我们已经完整地了解了 C++ 提供的标准容器。
课后思考请思考一下：
为什么大部分容器都提供了 begin、end 等方法？
为什么容器没有继承一个公用的基类？
欢迎留言和我交流你的看法。
参考资料[1] cppreference.com, “Containers library”. https://en.cppreference.com/w/cpp/container 
[1a] cppreference.com, “容器库”. https://zh.cppreference.com/w/cpp/container 
[2] cppreference.com, “Explicit (full) template specialization”. https://en.cppreference.com/w/cpp/language/template_specialization 
[2a] cppreference.com, “显式（全）模板特化”. https://zh.cppreference.com/w/cpp/language/template_specialization 
[3] Wikipedia, “Associative array”. https://en.wikipedia.org/wiki/Associative_array 
[3a] 维基百科, “关联数组”. https://zh.wikipedia.org/zh-cn/ 关联数组 
[4] Wikipedia, “Weak ordering”. https://en.wikipedia.org/wiki/Weak_ordering 
[5] Wikipedia, “Hash table”. https://en.wikipedia.org/wiki/Hash_table 
[5a] 维基百科, “哈希表”. https://zh.wikipedia.org/zh-cn/ 哈希表 

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 3

提建议

04 | 容器汇编 I：比较简单的若干容器

06 | 异常：用还是不用，这是个问题

 写留言

精选留言(24)

糖
2019-12-07
1. 首先是为了遍历容器方便，其次为了保证std接口的一致性 2. 我认为是没有必要的，因为，如果用类的继承一般会产生虚函数，这也就导致多存储一个虚函数表，在内存上产生了不必要的浪费。
作者回复: 基本正确。 2 实际上还是因为这儿继承真的没啥用。有了泛型，继承基本是种浪费。而且，继承用基类的指针或引用才有用，而C++里的容器类一般都是当值类型来用的。
共 3 条评论
19
EncodedStar
2019-12-21
《现代C++实战31讲》容器汇编二：需要函数对象的容器一、函数对象及其特化 1.俩个函数对象less 和 hash 2.less 二元函数，执行对任意类型的比较值，返回布尔类型，调用运算符 ( operator() )而且缺省行为是指定类型对象 < 的比较 3.sort 排序默认使用 less 从大到小使用 greater 4.hush 目的是把一个某种类型的值转化为一个无符号的整数 hush 值 (还没有用过hush) 二、priority_queue 1.不遵守一般 queue 规则，有序的队列，可以 less(顺排) 和 greater(逆排) 三、关联性容器 1.关联性容器有set(集合)、map(映射)、multiset(多重集)、multimap(多重映射)。C++外这些都是无序的，C++里这些都是有序的 2.关联性容器带 mult i的字段是允许重复键，不带是不允许 3.关联系容器没有 insert、emplace等成员函数，但都提供find(找到等价键值元素)、lower_bound(找到第一个不小于查询键值元素)、upper_bound(找到第一个不大于查询键值元素)等查询的函数。 4.在multimap 里精确查找满足某个区间使用 equal_range 四、无序关联容器 1.C++11开始每一个关联容器都有一个无序关联容器他们是unordred_set、unordered_map、unordered_multiset、unordered_multimap 2.有序的关联容器包括(priority_queue)的插入和删除操作以及关联性容器查找操作复杂度都是O(log(n)) 而无序可以平均达到O(1)(必须使用恰当) 五、array 1.C数组没有begin 和 end 成员函数(可以使用全局的) 2.C数组没有size成员函数 3.C数组作为参数传递时，不会获取C数组长度和结束位置课后思考 1.为什么大部分容器都提供了begin、end等方法答：不同容器内部实现方式不同，实现的遍历方式不同，都能提供begin、end的方法也是为了提供统一的调用方法 2.为什么容器没有继承一个公用的基类答：不同容器内部实现方式不同(包括存储方式)，虽然外部接口都是相同的方法调用，但是接口内部实现机制都是不同的，如果非要使用基类，那基类也只能定义虚函数，还不如现在，在实现的时候就做了统一接口，还少一层构造
展开
10
皓首不倦
2019-12-09
老师您好第一个问题个人觉得提供出头尾迭代器目的主要是提供给STL算法库用，STL算法库实现是只认迭代器的，这样的设计可以避免算法实现和具体容器类型的强耦合第二个问题个人觉得是因为各种容器API和功能上差异比价大，难以做一层比较通用的抽象，但是像map和unordered_map这样功能比较相近的容器我觉的还是可以做一层抽象的，像Java中TreeMap和HashMap就同时实现了Map接口，做了一层抽象，其实我也一直没有弄懂C++为什么没有向Java一样对功能相近的容器做一层接口的抽象层，老师能帮我解答下吗？
展开
作者回复: 一，正确。二，问题还在于C++的值语义。如果你用一个 AbstractMap来访问map和unordered_map，你只能用引用或指针，并不方便。而且，map和unordered_map的模板参数还不一样，通用的话反而成了阉割版……
共 2 条评论
9
qinsi
2019-12-07
既然关联容器的key需要满足strict weak ordering，那么sort的比较函数是不是也需要满足？比如sort(v.begin(), v.end(), less_equal<int>());是否可行？
作者回复: 是，也必须满足。标准里明确这么要求了。如果你传了 less_equal 这样的条件，结果可能是正确，也可能是错误，也可能是程序崩溃。具体发生什么，取决于排序算法的实现。出了问题，就是调用者的锅，不是 sort 的 bug。以冒泡排序为例，我试了一下，如果是用检验有没有交换来决定是否退出排序，那么，在元素有重复的情况下使用 less_equal 来排序，会导致死循环。
7
啦啦啦
2019-12-10
想问一下，priority_queue这种，如果通过指针持有某个对象，然后传入比较函数，那么如果更新指针指向对象的值，priority_queue是否会更新？如果不会，有方法能够使它更新吗？
作者回复: 不会也不可以。这些容器适配器不提供遍历的迭代器就是不允许像你描述这样的任意访问。（迭代器就是广义指针。）
4
lyfei
2019-12-08
老师你好，那为什么unodered_map会使用到operator==的呢？我感觉他不是应该把数据转到hash值，然后保存起来，也感觉没有比较的过程，哪个地方体现了==这个运算符呀？
作者回复: 不是。哈希是哈希，哈希可能有冲突的，相同哈希值也要看键是相同还是不同，来决定是覆盖还是加一项。去看一下数据结构里面的哈希。
共 2 条评论
3
贾陆华
2019-12-07
1. 看到一个注释笔误，是从大到小吧 // 从小到大排序 sort(v.begin(), v.end(), greater<int>()); cout << v << endl; 2. map.lower_bound(k)默认代表的意思是找到第一个x，x不小于k，map.upper_bound(k)默认是找到第一个x，x大于k，为什么不是x小于k，upper_bound字面意思不是上界吗？
展开
作者回复: 1. 哈，还真是的。典型的拷贝粘贴错误…… 2. 想一想，C++ 里到处是半开半闭区间。右界一直是会超出有效范围的。
共 2 条评论
2
中年男子
2019-12-06
1、begin、end是迭代器，主要用于对不同类型的容器提供统一的遍历容器的辅助 2不同容器内存分配方式不同，实现不同，基类方法无法做到统一，非要用继承只能定义虚函数多用组合、少用继承（抖个机灵）
作者回复: 哈哈，是这样的。
2
李义盛
2019-12-06
2.继承是强耦合。继承导致关系混乱。
作者回复: 算是一个点。真要继承，不会更好用，因为容器的接口差异往往很小，这儿多一个，那儿少一个，要多少接口才能表达啊。
2
Geek_24c4df
2020-05-23
看不懂下面用法 unordered_map<complex<double>, double> umc{{{1.0, 1.0}, 1.4142}, {{3.0, 4.0}, 5.0}}; 为什么键里面还要套一层大括号数据
作者回复: {1.0, 1.0} 可以用来构造一个复数（1 + i），{{1.0, 1.0}, 1.4142} 是 unordered_map 里的一项。
1
传说中的成大大
2019-12-06
第一问大概是因为可以通过begin()方法的返回值迭代到end() 就像数组或者链表等等都可以从头遍历到尾这也是为啥子有些线性容器删除以后返回的是下一个元素的迭代器而map set这种容器无法通过迭代器进行迭代所以调用erase函数返回void 第二问大概是因为各个容器的存储方式不太一样吧所以导致操作不一样像priority_queue 和queue他们的操作方式就不一样 queue插入或者删除元素只需要移动指针或者下标就行但是priority_queue 优先级队列又称为堆增加删除操作都涉及到一个堆化过程维持最小或者最大值在堆顶
展开
作者回复: 一、前面正确。关于map错了。可以迭代，并且现在erase已经返回迭代器了（C++98时不行）。二、跟这个关系不大。OO语言里也是推荐继承接口而不是实现的。
1
总统老唐
2019-12-06
又更新一课，之前还有同学说更新慢，现在看，是更新太快了，因为都是干货，每一课都要花大力气学
作者回复: 我还真希望更新慢点呢，但编辑不肯啊……写文字、造例子都挺花力气的。第 4、5 讲应该还好吧，烧脑的东西不多。再往下可能会又比较干些，尤其到了模板元编程的部分。
1
爱笑的布谷鸟
2022-09-01 来自上海
请问老师，为什么 weak_ptr 不能作为 unordered_x 容器的 key？
作者回复: weak_ptr里你要获取指针都得去lock一下，你该怎么去算哈希值和判断相等？不能算哈希值和判断相等，你以后怎么做查询？
shibo
2022-07-18
typedef char mykey_t[8]; 这些错了吧，应该是typedef char[8] mykey_t ?
作者回复: 你试试不就知道了？看来你C语法不过关啊？从 Java过来的？😝
水月
2022-03-09
老师，像HashTable这类容器，重载了Hash函数之后还需要给散列冲突也准备一个重载吗？
作者回复: 不太懂你的意思。我们这里首先没有重载，只有对 hash 类模板的特化。其次，在标准库的实现里，是用拉链方式来实现无序关联容器的，哈希值冲突的键会串成一个链表。用户需要避免这种情况，但如果真发生了，用户没有什么可做的——只能回到代码改进 hash 的特化了。
太阳
2021-09-22
第二段代码（hsah模板）g++编译报错
作者回复: 那段本来就是示意，不是让你运行的。失败的原因估计是因为 unary_function 没有定义。这是在 C++17 之前 STL 里定义的一个类模板。你可能没有 using namespace std;，也可能是标准开到了 17，编译器不让用这个了。整个把继承部分删掉试试。有其他问题请新提问题，不要使用回复（我收不到回复的通知）。
hello
2020-03-31
请问除了这两讲中讲到的容器，STL中还有其他容器存在吗？
作者回复: C++98 到 C++17 的所有容器都在这里了。还额外加了跟 string 的简单比较。
凉人。
2020-02-15
1 迭代器，分配器，适配器，算法，仿函数，容器。 begin和end应该算是迭代器部分 2 曾经想实现一个多态版的容器，后来发现很多接口不一致，行为也不一致，虽然Mycontainer实现list和vector的多态，但总感觉别扭
作者回复: 都很靠拢了。可以学完之后去看一下参考答案。
robonix
2019-12-21
老师， template <class T> struct hash; 这一句的作用是什么呀？
作者回复: 声明一个模板 hash，其有一个类型参数。编译器知道了 hash 是一个类模板之后，下面才能进行特化。
lyfei
2019-12-07
老师你好，我在使用无序容器unordered_map时，key是使用了我自定义的类型，所以需要对hash进行特化，但是我编译的时候出了问题： “/usr/include/c++/7/bits/stl_function.h:356:20: error: no match for ‘operator==’ (operand types are ‘const Test<int>’ and ‘const Test<int>’) { return __x == __y; }” 测试代码如下： <code> template <typename T> class Test; namespace std { template <typename T> struct hash<Test<T>> { size_t operator()(const Test<T>& v) const noexcept { hash<T> h; return h(v.a_t); } }; } // namespace std template <typename T> class Test { public: T a_t; }; int main() { Test<int> test; unordered_map<Test<int>, int> ump_test{{test, 1}}; return 1; } <code_end>
展开
作者回复: 正如错误信息提示的，你的类没有定义相等比较。把定义改成下面这样子就可以了（完整起见，我也加了 != 的定义）： template <typename T> class Test { public: T a_t; bool operator==(const Test& rhs) const { return a_t == rhs.a_t; } bool operator!=(const Test& rhs) const { return !operator==(rhs); } };
共 4 条评论

