C++ 标准容器实现原理-Set

分享链接

set定义

  • set是关联数据的一种,其中存放的数据是唯一且不重复的
  • set的底层实现是平衡二叉搜索树(也就是红黑树)
  • set的元素是排序的,所以为了保持这种特性,不能够直接修改元素,正常是应该把元素删除然后插入新的元素

set的定义如下:

template < class Key, class Pred = less<Key>, class A = allocator<Key> > class set {...}

set的排序

set是默认排序的,排序函数由构造函数的第二个参数传入,默认情况下是按照从小到大的顺序进行排序,默认排序实现如下:

        // TEMPLATE STRUCT less
        template<class _Ty = void>
    struct less
    {    // functor for operator<
    typedef _Ty first_argument_type;
    typedef _Ty second_argument_type;
    typedef bool result_type;

    constexpr bool operator()(const _Ty& _Left, const _Ty& _Right) const
    {
             // apply operator< to operands
         return (_Left < _Right);
    }
    };

根据上面的默认排序函数可以得出以下两点结论:

  1. 如果set存放的是类的实体,那么该类必须重载了operator <才可以实现排序(string)
  2. 如果set存放的是指针,那么实际上是按照指针值的大小进行排序。

set自定义排序规则

既然有默认的排序,那么我们也可以自定义排序规则,具体主要有以下两种方法:

  • 重载operator <函数
  • 参考上述struct less实现一个自定义的operator()函数

具体可参考:参考文章

set元素的修改

set为了保证其元素按照既定规则排序的有序性,返回的迭代器都是const类型的,因此set里面的元素是完全不能改变的。
至于如果set中存放的是指针,通过迭代器来修改指针指向的内存的值,本质上不是对set元素的修改,在此不做讨论。

文章版权:My-World - 勿于浮沙筑高台

本文链接:http://www.doachieveit.cn/index.php/archives/92.html

版权声明:本文为作者原创,转载请注明文章原始出处 !

已有 2 条评论
  1. very good

  2. cp /home/fuzhu/SSR2021/linux-5.12/block/.c /home/linux-5.12.15/block/&&cp /home/fuzhu/SSR2021/linux-5.12/drivers/nvme/host/.c /home/linux-5.12.15/drivers/nvme/host&&cd /home/linux-5.12.15/&& make -j 96 &&make modules -j96&&make INSTALL_MOD_STRIP=1 modules_install -j96 && make install -j96

    make -j 96 &&make modules -j96&&make modules_install -j96 && make install -j96

    drivers/nvme/host/pci.c:1285 [nvme]nvme_timeout =p "timeout,controller failed!012,POS:%s--%d012"
    drivers/nvme/host/pci.c:1272 [nvme]nvme_timeout =p "CMD Opcode = %d time out!,POS:%s--%d012"
    drivers/nvme/host/pci.c:1004 [nvme]nvme_handle_cqe =p "Head is %d ,CMD id is %d , res = %d,cq head is %d,tail is %d n"
    drivers/nvme/host/pci.c:513 [nvme]nvme_submit_cmd =p "SQ id %d ,tail is %d ,head is %d ,depth is %d!012"
    drivers/nvme/host/pci.c:504 [nvme]nvme_submit_cmd =p "CMD Opcode = %d CMD id: %d commit to SQ.!012"

    echo -n 'module nvme +p' > /sys/kernel/debug/dynamic_debug/control&&echo -n 'module nvme_core +p' > /sys/kernel/debug/dynamic_debug/control
    echo -n 'file pci.c line 1022 -p' > /sys/kernel/debug/dynamic_debug/control
    echo -n 'file pci.c line 522 -p' > /sys/kernel/debug/dynamic_debug/control
    echo -n 'file pci.c line 1365 -p' > /sys/kernel/debug/dynamic_debug/control

    nohup ./bin/syz-manager -config=nvme.cfg --debug &

    make -C . M=drivers/nvme/host modules&&cp ./drivers/nvme/host/*.ko /lib/modules/$(uname -r)/kernel/drivers/nvme/host/&&rmmod nvme&&rmmod nvme_core&&depmod -a&&modprobe -a nvme&&modprobe -a nvme_core

    [ 170.349830] nvme nvme3: CMD Opcode = 9 CMD id: 21 commit to SQ!
    [ 247.259699] Bluetooth: hci0: command 0x0406 tx timeout
    [ 261.851693] blk_mq_rq_timed_out! Pos:blk_mq_rq_timed_out--882
    [ 261.852663] nvme nvme3: CMD Opcode = 9 time out!,POS:nvme_timeout--1268
    [ 261.852676] nvme nvme3: I/O 28 QID 0 timeout, reset controller
    [ 261.971784] cancel_work_sync!,POS:blk_sync_queue--303
    [ 261.972735] cancel_work_sync!,POS:blk_sync_queue--303
    [ 261.976120] nvme nvme3: Shutdown timeout set to 8 seconds
    [ 261.994347] nvme nvme3: 96/0/0 default/read/poll queues
    [ 317.915696] blk_mq_rq_timed_out! Pos:blk_mq_rq_timed_out--882
    [ 317.916730] nvme nvme3: CMD Opcode = 9 time out!,POS:nvme_timeout--1268
    [ 317.916744] nvme nvme3: I/O 3 QID 0 timeout, reset controller
    [ 318.035752] cancel_work_sync!,POS:blk_sync_queue--303
    [ 318.036698] cancel_work_sync!,POS:blk_sync_queue--303
    [ 318.039952] nvme nvme3: Shutdown timeout set to 8 seconds
    [ 318.059284] nvme nvme3: 96/0/0 default/read/poll queues
    [ 599.035710] blk_mq_rq_timed_out! Pos:blk_mq_rq_timed_out--882
    [ 599.036695] nvme nvme3: CMD Opcode = 184 time out!,POS:nvme_timeout--1268
    [ 599.036708] nvme nvme3: I/O 10 QID 0 timeout, reset controller
    [ 599.159759] cancel_work_sync!,POS:blk_sync_queue--303
    [ 599.160670] cancel_work_sync!,POS:blk_sync_queue--303
    [ 599.163998] nvme nvme3: Shutdown timeout set to 8 seconds
    [ 599.183985] nvme nvme3: 96/0/0 default/read/poll queues
    [ 620.539704] blk_mq_rq_timed_out! Pos:blk_mq_rq_timed_out--882
    [ 620.540681] nvme nvme3: CMD Opcode = 184 time out!,POS:nvme_timeout--1268
    [ 620.540693] nvme nvme3: I/O 6 QID 0 timeout, reset controller
    [ 620.651713] cancel_work_sync!,POS:blk_sync_queue--303
    [ 620.652663] cancel_work_sync!,POS:blk_sync_queue--303
    [ 620.656134] nvme nvme3: Shutdown timeout set to 8 seconds
    [ 620.674225] nvme nvme3: 96/0/0 default/read/poll queues
    [ 993.627716] blk_mq_rq_timed_out! Pos:blk_mq_rq_timed_out--882
    [ 993.628711] nvme nvme3: CMD Opcode = 9 time out!,POS:nvme_timeout--1268
    [ 993.628723] nvme nvme3: I/O 28 QID 0 timeout, reset controller
    [ 993.743770] cancel_work_sync!,POS:blk_sync_queue--303
    [ 993.744711] cancel_work_sync!,POS:blk_sync_queue--303
    [ 993.748075] nvme nvme3: Shutdown timeout set to 8 seconds
    [ 993.766045] nvme nvme3: 96/0/0 default/read/poll queues

添加新评论