首页 > 其他分享 >STL模版 -- day02

STL模版 -- day02

时间:2023-09-04 19:22:52浏览次数:59  
标签:deque set const iterator STL day02 -- vector key

一、deque 双端队列容器
  • 头文件 #include < deque >

  • 是下标顺序容器,它允许在首尾两端快速地插入、删除数据

  • deque的元素不是全部相邻存储的:采用单独分配的固定大小数组的序列存储数据,以及额外的登记表(中控数组),该表中记录了所有序列的地址,这表示通过下标访问元素时必须经过两次指针解引用,vector只需要一次

  • deque支持随机访问,效率依然是O(1)

  • deque的存储也可以按需自动扩展、收缩,并且deque的扩展比vector更优,因为不设计到原内存复制、销毁环节

    • vector扩容,先申请一块更大的新内存,把原内存数据拷贝,释放原内存

    • deque扩容,只需要申请一块新的固定大小的序列,记录到中控数组即可

  • deque比vector多push_front\pop_front操作,并且效率也能O(1)

  • vector比deque多个reserve预分配内存,因为deque不需要预分配内存来节约时间

  • deque的优点:

    • 与vector相比,头部插入、删除时,不需要搬运后序元素,效率特别高(O(1));在扩容时,也不需要移动、释放原内存,只需操作中控数组即可

    • 与list相比,底层依然是连续空间,空间利用率更高,支持随机访问O(1)

  • deque的缺点:

    • 没有vector和list那么极致,随机访问的速度比vector慢(vector是真正的连续空间);中间位置的插入、删除没有list快,list根本不需要扩容

    • 不适合遍历,因为在遍历时deque的迭代器需要频繁地检查是否移动到了某个序列的末尾,并且需要解两次引用,效率低

    • 因此当需要线性容器时,大多数情况下优先考虑vector、list,deque的应用不多(stack\queue)

二、stack 栈容器(适配器)
  • 头文件 #include < stack >

  • 底层由deque实现的

  • 不支持运算符,没有迭代器,只有无参构造、拷贝构造

  • empty、push、pop、top、size

三、queue 队列容器(适配器)
  • 头文件 #include < queue >

  • 底层由deque实现的

  • 不支持运算符,没有迭代器,只有无参构造、拷贝构造

  • empty\push\pop\front\back\size

四、priority_queue 优先队列容器(适配器)
  • 头文件 #include < queue >

  • 底层采用vector实现,当数据入队时,会对数据进行调整成堆结构,默认是大顶堆,元素越大,优先级越高,越先出队

  • 注意:存储的元素必须支持 < 运算符,如果是类类型数据必须重载<运算符

  • 注意:只能查看top

  • 如何调整优先队列的优先级:(小顶堆)

    • 元素取反存入、取出取反

    • 类类型数据重载 < 运算符,调整<运算符的比较过程

    • 固定语法

      • priority_queue<类型,vector<类型>,greater<类型> > 队列名;

        • // 升序
      • priority_queue<类型,vector<类型>,less<类型> > 队列名;

        • // 降序
五、关联性容器(有序)
  • 关联性容器可以实现快速查找(O(logn))的容器
  • 线性容器中array、vector、list、deque都可以使用全局find进行顺序查找(O(n)),必须支持operator==比较
  • 底层实现 红黑树
六、set 集合容器
  • 头文件 #include < set >

  • 集合容器,底层采用红黑树实现,特点元素不能重复,会自动对数据进行排序,它存储的元素必须支持 < 运算符,只能使用迭代器遍历

  • 默认下是按照 operater< 运算符进行比较

  • 为什么不是使用 operator== 来比较?

    • 二叉排序树的规则:左小于根、根小于右,如果相等插入失败,==无法判断大小

    • a == b 可以使用 !(a<b || b<a) 替代

  • 构造函数:只有无参、拷贝构造

  • 支持的运算符:与list一致,不支持随机访问

  • 常用成员函数:

    iterator insert( iterator i, const TYPE& val );
    //功能:向set中添加val,i位置意义不大
    void insert( input_iterator start, input_iterator end );
    //功能:想set添加一组[start,end)数据
    pair<iterator,bool> insert( const TYPE& val );
    //功能:向set中添加val
    //返回值:返回键值对pair<添加的位置,是否添加成功>
    
    size_type count( const key_type& key );
    //功能:查看key在set中有几个,要么0要么1
    
    iterator find( const key_type& key );
    //功能:查找set中key的元素的位置,并返回该位置的迭代器
    //如果找不到key,返回end()位置的迭代器
    
    pair<iterator, iterator> equal_range(const key_type& key );
    //功能:查看key在set中的范围,并返回该范围组成的键值对,在set中意义不大
    
    void erase( iterator pos );
    void erase( iterator start, iterator end );
    size_type erase( const key_type& key );
    //功能:删除值为key的元素,成功返回1 失败返回0
    
    key_compare key_comp() const;
    //功能:返回一个用于比较set中元素的函数对象,该对象属于set
    set<int>::key_compare cmp = s.key_comp();
    cmp(int,int);//第一个"小",则为真
    
    value_compare value_comp() const;
    //    在set中等同于 key_comp
    
    iterator lower_bound( const key_type& key );
    //功能:返回一个大于或等于key的最小的元素的迭代器
    iterator upper_bound( const key_type& key );
    //功能:返回一个大于key的最小的元素的迭代器
    
七、multiset 多重集合容器
  • 头文件 #include < set >

  • 元素可以重复,也会对元素自动进行排序,元素必须支持<运算符,只能用迭代器遍历

  • size_type count( const key_type& key );
    //功能:计算有几个key
    pair<iterator, iterator> equal_range(const key_type& key);
    //功能:返回值为key的元素的范围
    
八、map 映射容器
  • 头文件 #include

  • 有序键值对容器,是由key/value组成的元素(键值对、字典)pair,要求key不能重复,一个key只能对应一个值,会根据key进行排序,因此key必须支持 < 运算符

  • 一般map中存储一些经常需要查找的数据,因为map的查找速度极快,set速度也不慢,但是map比set多一个value来进行描述,redis内存数据库中使用键值对存储数据

  • key和value一一对应,可以根据key来访问value,底层采用红黑树根据key来进行组织、管理,查找效率很高

  • //构造函数:
    map( iterator start, iterator end );
    //功能:使用一组数据(pair类型)构造
    map( iterator start, iterator end,const key_compare& cmp );
    //功能:使用一组数据(pair类型)构造,并提供key的比较函数
    map( const key_compare& cmp );
    //功能:提供key的比较函数构造
    //支持的运算符:
            //[] 支持通过key作为下标访问元素的value
            //既可以用于访问,当key不存在时,也可以用于插入数据<key,value>,如果key存在,则修改value
                m[key] = value; //  添加、修改
                m[key]; //  key不存在,添加key-value value使用无参构造或者默认值0
                m[key]; //  key存在,访问对应的value
            //成员函数 at(key) 也可以用于访问、修改key的value,但是当key不存在时会抛出异常out_of_range
    //常用成员函数:
    iterator insert( iterator i, const TYPE& pair );
    void insert( input_iterator start, input_iterator end );
    pair<iterator,bool> insert( const TYPE& pair );
    
九、multimap 多重映射容器
  • 头文件 #include

  • 使用方式与map几乎类似

  • 不同的是它的key可以对应多个不同的value,因此不能支持[]运算符

  • 一些成员函数:count、equal_range 就变得有意义

  • 通过迭代器删除元素需要注意的问题:

    • 对于关联性容器(set\multiset\map\multimap),删除当前iterator会仅仅使得当前iterator失效,其余位置没有变化,因此在erase时只需要递增iterator即可依次删除,因为底层是红黑树,某个节点删除不会影响其它节点的位置

      • map.erase(it++);
    • 对于线性容器(vector\deque\stack\queue\priority_queue),删除当前iterator后,后序所有的iterator失去原来意义,因为使用的是连续内存,删除一个,后面所有元素都重新移动,iterator不能递增删除,只能通过重新接收erase的返回值,获取新的当前iterator继续删除

      • it = vector.erase(it);
    • list 两种方式都可以

十、bitset 位集合容器
  • 头文件 #include < bitset >

  • 是一种封装了各种位操作的类类型数据结构

  • !=, ==, &=, ^=, |=, ~, <<=, >>=, []

  • 成员函数:

  • any(); //有任意一位是1,返回真
    count(); //统计二进制位是1的位数有几位
    flip(); //所有二进制位取反\指定的二进制位取反
    none(); //全部位没有一个是1,返回真
    reset(); //全部二进制位置0\指定二进制位置0
    set(); //全部二进制位置1\指定二进制位置val=1
    size(); //获取位数
    test(); //访问指定的二进制位的值
    to_string(); //把所有二进制位转stirng类型
    to_ulong(); //把所有二进制位转unsigned long类型,C++不常用,但是对于嵌入式软件编程会比较方便去设置二进制位
    
  • 常考面试题:

    • vector与list的区别?

    • 指针与迭代器的区别?

    • STL中哪些容器底层采用红黑树?为什么?

标签:deque,set,const,iterator,STL,day02,--,vector,key
From: https://www.cnblogs.com/bigflyny/p/17677890.html

相关文章

  • Redis持久化
    1.描述redis的持久化是为了避免进程突然退出导致数据永久丢失,需要将redis中的数据以某种形式从内存保存到硬盘中。当redis再次重启时,通过这些redis持久化文件对进程结束之前的数据进行数据恢复。redis持久化的方式有RDB持久化和AOF持久化两种。RDB持久化是通过将数据保存到硬盘,A......
  • vim配置和插件
    Linux干活三板斧,shell、vim和git 下面主要内容包括:1、vim安装及基本设置2、插件安装及设置3、快捷键设置     2vim安装及基本设置   下面内容包括:1、vim安装2、查看对python支持3、基本设置    2.1vim安装    sudoapt-getinstal......
  • 地址线等长
    规则设置地址线组规则地址线组的线差控制在+-200mil。上一节说明了如何创建xSignal。在上一节的基础上,我们设置该规则。快捷键打开规则管理器:DR。HighSpeed->MatchedLengths->MatchedLengths_ADDR_PP1设置公差为400mil。另外的,我们要保证3W规则,这里设置Clearace......
  • 学习Markdown
    学习Markdown---Typora初体验标题语法:#+空格+标题+回车。几级标题就有几个#号。三级标题四级标题五级标题六级标题#######七级标题。。。我没有字体斜体语法:\[*内容*\]加粗语法:\[**内容**\]斜体加粗语法:\[***内容***\]删除线语法:\[两条波浪线内容两条波浪线......
  • 467B - Fedor and New Game
    B.FedorandNewGamehttps://codeforces.com/problemset/problem/467/B"""思路:1.暴力方法:通过循环二进制之后的,逐个位与fedor进行判断,通过取余,如果最后不同的超过3个就计+12.解决方法:通过异或^进行判断,然后转成二进制,统计1的数量,就是不同的数量,然后相加"""#利用异或......
  • 快速入门
    快速入门NW.js基于Chromium 和 Node.js.NW.js利用Web技术结合Node.js及其模块进行桌面应用开发.获取NW.js您可以从官网获取最新版本的文件,或通过源代码构建.【注意】 :推荐选择SDK构建方式开发应用,这样就可以使用开发工具进行调试,参考[构建方式](Advanced/Buil......
  • Python 遍历字典的若干方法
    哈喽大家好,我是咸鱼我们知道字典是Python中最重要且最有用的内置数据结构之一,它们无处不在,是语言本身的基本组成部分我们可以使用字典来解决许多编程问题,那么今天我们就来看看如何在Python中遍历字典全文内容:https://realpython.com/iterate-through-dictionary-python/p......
  • 常见问题
    常见问题Linux系统终端中不能使用console.log打印信息在命令行设置 --enable-logging=stderr参数,更多信息参考chromium文档varcrypto=require('crypto')获取对象错误Chromium有个名为 crypto的全局对象,该对象无法被重写.所以不要使用 crypto作为变量名,更改成......
  • 动手实践-XA模式代码
             ......
  • 【抽奖】重磅!Cloud Ace 荣获三项 2023 年 Google Cloud 年度合作伙伴大奖
    【CloudAce是GoogleCloud全球战略合作伙伴,在亚太地区、欧洲、南北美洲和非洲拥有二十多个办公室。CloudAce在谷歌专业领域认证及专业知识目前排名全球第一位,并连续多次获得GoogleCloud各类奖项。作为谷歌云托管服务商,我们提供谷歌云、谷歌地图、谷歌办公套件、谷歌云认证......