现代C++实战30讲
吴咏炜
前 Intel 资深软件架构师
立即订阅
3598 人已学习
课程目录
已更新 10 讲 / 共 30 讲
0/4登录后,你可以任选4讲全文学习。
课前必读 (2讲)
开篇词 | C++这么难,为什么我们还要用C++?
免费
课前必读 | 有关术语发音及环境要求
基础篇 (8讲)
01 | 堆、栈、RAII:C++里该如何管理资源?
02 | 自己动手,实现C++的智能指针
03 | 右值和移动究竟解决了什么问题?
04 | 容器汇编 I:比较简单的若干容器
05 | 容器汇编 II:需要函数对象的容器
06 | 异常:用还是不用,这是个问题
07 | 迭代器和好用的新for循环
08 | 易用性改进 I:自动类型推断和初始化
现代C++实战30讲
登录|注册

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

吴咏炜 2019-12-06
你好,我是吴咏炜。
上一讲我们学习了 C++ 的序列容器和两个容器适配器,今天我们继续讲完剩下的标准容器([1])。

函数对象及其特化

在讲容器之前,我们需要首先来讨论一下两个重要的函数对象,lesshash
我们先看一下 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],类似于:
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《现代C++实战30讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(15)

  • qinsi
    既然关联容器的key需要满足strict weak ordering,那么sort的比较函数是不是也需要满足?比如sort(v.begin(), v.end(), less_equal<int>());是否可行?

    作者回复: 是,也必须满足。标准里明确这么要求了。

    如果你传了 less_equal 这样的条件,结果可能是正确,也可能是错误,也可能是程序崩溃。具体发生什么,取决于排序算法的实现。出了问题,就是调用者的锅,不是 sort 的 bug。

    以冒泡排序为例,我试了一下,如果是用检验有没有交换来决定是否退出排序,那么,在元素有重复的情况下使用 less_equal 来排序,会导致死循环。

    2019-12-07
    2
  • lyfei
    老师你好,那为什么unodered_map会使用到operator==的呢?
    我感觉他不是应该把数据转到hash值,然后保存起来,也感觉没有比较的过程,哪个地方体现了==这个运算符呀?

    作者回复: 不是。哈希是哈希,哈希可能有冲突的,相同哈希值也要看键是相同还是不同,来决定是覆盖还是加一项。去看一下数据结构里面的哈希。

    2019-12-08
    1
    1
  • 中年男子
    1、begin、end是迭代器,主要用于对不同类型的容器提供统一的遍历容器的辅助

    2不同容器内存分配方式不同,实现不同,基类方法无法做到统一,非要用继承只能定义虚函数
    多用组合、少用继承(抖个机灵)

    作者回复: 哈哈,是这样的。

    2019-12-06
    1
  • 啦啦啦
    想问一下,priority_queue这种,如果通过指针持有某个对象,然后传入比较函数,那么如果更新指针指向对象的值,priority_queue是否会更新?如果不会,有方法能够使它更新吗?

    作者回复: 不会也不可以。这些容器适配器不提供遍历的迭代器就是不允许像你描述这样的任意访问。(迭代器就是广义指针。)

    2019-12-10
  • 皓首不倦
    老师您好
    第一个问题个人觉得提供出头尾迭代器目的主要是提供给STL算法库用,STL算法库实现是只认迭代器的,这样的设计可以避免算法实现和具体容器类型的强耦合
    第二个问题个人觉得是因为各种容器API和功能上差异比价大,难以做一层比较通用的抽象,但是像map和unordered_map这样功能比较相近的容器我觉的还是可以做一层抽象的,像Java中TreeMap和HashMap就同时实现了Map接口,做了一层抽象,其实我也一直没有弄懂C++为什么没有向Java一样对功能相近的容器做一层接口的抽象层,老师能帮我解答下吗?

    作者回复: 一,正确。

    二,问题还在于C++的值语义。如果你用一个 AbstractMap来访问map和unordered_map,你只能用引用或指针,并不方便。而且,map和unordered_map的模板参数还不一样,通用的话反而成了阉割版……

    2019-12-09
    1
  • lyfei
    老师你好,我在使用无序容器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);
        }
    };

    2019-12-07
    3
  • 1. 首先是为了遍历容器方便,其次为了保证std接口的一致性
    2. 我认为是没有必要的,因为,如果用类的继承一般会产生虚函数,这也就导致多存储一个虚函数表,在内存上产生了不必要的浪费。

    作者回复: 基本正确。

    2 实际上还是因为这儿继承真的没啥用。有了泛型,继承基本是种浪费。而且,继承用基类的指针或引用才有用,而C++里的容器类一般都是当值类型来用的。

    2019-12-07
  • 老师,我又有问题了!
    、、、
    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());
    }
    };
    、、、
    这段代码会不会出现问题呢?因为h(v.real())和h(v.imag())的范围都是size_t,他两个和的取值应该超出了size_t的取值范围,因此是否需要进行处理一下呢?

    作者回复: 超出范围,在此处我们是不在乎的——我们不需要一个正确的数值。哈希值本来就是有冲撞的。

    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++ 里到处是半开半闭区间。右界一直是会超出有效范围的。

    2019-12-07
    1
  • 传说中的成大大
    第一问 大概是因为可以通过begin()方法的返回值迭代到end() 就像数组或者链表 等等都可以从头遍历到尾 这也是为啥子 有些线性容器 删除以后返回的是下一个元素的迭代器 而map set这种容器无法通过迭代器进行迭代 所以调用erase函数返回void
    第二问 大概是因为各个容器的存储方式不太一样吧 所以导致操作不一样 像priority_queue 和queue他们的操作方式就不一样 queue插入或者删除元素只需要移动指针或者下标就行 但是priority_queue 优先级队列 又称为堆 增加删除操作都涉及到一个堆化过程 维持 最小或者最大值在堆顶

    作者回复: 一、前面正确。关于map错了。可以迭代,并且现在erase已经返回迭代器了(C++98时不行)。

    二、跟这个关系不大。OO语言里也是推荐继承接口而不是实现的。

    2019-12-06
  • 方阳
    1.方便算法遍历容器
    2.容器内部也有一些继承和复合,容器是独立的组件,没必要继承公用基类。

    作者回复: 好,基本正确。

    2019-12-06
  • 罗乾林
    1、为algorithm服务
    2、继承必然要用虚函数,性能有损失

    作者回复: 1 是激发大家思考,现在多想想就行了。

    2 这也算是个点。我再等等其他回答。😊

    2019-12-06
  • 李义盛
    2.继承是强耦合。 继承导致关系混乱。

    作者回复: 算是一个点。真要继承,不会更好用,因为容器的接口差异往往很小,这儿多一个,那儿少一个,要多少接口才能表达啊。

    2019-12-06
  • 总统老唐
    又更新一课,之前还有同学说更新慢,现在看,是更新太快了,因为都是干货,每一课都要花大力气学

    作者回复: 我还真希望更新慢点呢,但编辑不肯啊……写文字、造例子都挺花力气的。

    第 4、5 讲应该还好吧,烧脑的东西不多。再往下可能会又比较干些,尤其到了模板元编程的部分。

    2019-12-06
  • hello world
    1. 因为统一要为迭代器服务
    2. 等大佬们!

    作者回复: 同学动作很快,但有点调皮啊。😄

    2019-12-06
收起评论
15
返回
顶部