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

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

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

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

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

    作者回复: 基本正确。

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

     1
     2
  • Encoded Star
    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.为什么容器没有继承一个公用的基类
    答:不同容器内部实现方式不同(包括存储方式),虽然外部接口都是相同的方法调用,但是接口内部实现机制都是不同的,如果非要使用基类,那基类也只能定义虚函数,还不如现在,在实现的时候就做了统一接口,还少一层构造
    展开
    
     1
  • 皓首不倦
    2019-12-09
    老师您好
    第一个问题个人觉得提供出头尾迭代器目的主要是提供给STL算法库用,STL算法库实现是只认迭代器的,这样的设计可以避免算法实现和具体容器类型的强耦合
    第二个问题个人觉得是因为各种容器API和功能上差异比价大,难以做一层比较通用的抽象,但是像map和unordered_map这样功能比较相近的容器我觉的还是可以做一层抽象的,像Java中TreeMap和HashMap就同时实现了Map接口,做了一层抽象,其实我也一直没有弄懂C++为什么没有向Java一样对功能相近的容器做一层接口的抽象层,老师能帮我解答下吗?

    作者回复: 一,正确。

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

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

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

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

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

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

    
     1
  • robonix
    2019-12-21
    老师,
    template <class T> struct hash;
    这一句的作用是什么呀?

    作者回复: 声明一个模板 hash,其有一个类型参数。编译器知道了 hash 是一个类模板之后,下面才能进行特化。

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

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

    
    
  • 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);
        }
    };

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

     1
    
  • 传说中的成大大
    2019-12-06
    第一问 大概是因为可以通过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 讲应该还好吧,烧脑的东西不多。再往下可能会又比较干些,尤其到了模板元编程的部分。

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

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

    
    
我们在线,来聊聊吧