首页 > 编程语言 >C++语言学习10

C++语言学习10

时间:2023-09-06 21:12:25浏览次数:46  
标签:10 deque const 语言 iterator 容器 C++ key 迭代

一、deque 双端队列容器
#include
是下标顺序容器,它允许在首尾两端快速的插入、删除数据
deque的元素不是全部相邻存储的:采用单独分配的固定大小数组的序列存储数据,以及额外的登记表(中控数组),
该表中记录了所有序列的地址,这表示通过下标访问元素时必须经过两次指针解引用,vector只需要一次

deque支持随机访问,效率依然是O(1)
deque的存储也可以按需自动扩展、收缩,并且deque的扩展比vector更优,因为不设计到原内存复制,销毁环节
    1、vector扩容,先申请一块更大的新内存,把原内存数据拷贝,释放原内存
    2、deque扩容,只需要申请一块新的固定大小的序列,记录到中控数组即可
deque比vector多push_front\pop_front操作,并且效率也能O(1)
vector比deque多个reserve预分配内存,因为deque不需要预分配内存来节约时间
deque的优点:
    1、与vector相比,头部的插入和删除时,不需要搬运后序的元素,效率特别高(O(1));
    在扩容时,也不需要移动、释放原内存,只需要操作中控数组即可
    2、与list相比,底层依然是连续空间,空间利用率更高,支持随机访问O(1)
deque的缺点:
    1、没有vector和list那么极致,随机访问的速度要比vector慢,因为vector
    是真正的连续空间;中间位置的插入和删除没有list快,list根本不需要扩容
    2、不适合遍历,因为在遍历时deque的迭代器需要频繁的检查是否移动到了某个
    序列的末尾,并且需要解两次引用,效率低
    3、因此当需要线性容器时,大多数情况下优先考虑vector、list、deque的应用不多(stack\queue)

二、stack 栈容器(适配器)

底层由deque实现的
不支持运算符,没有迭代器,只有无参构造、拷贝构造
empty、push、pop、top、size

三、queue 队列容器(适配器)

底层由deque实现的
不支持运算符,没有迭代器,只有无参构造、拷贝构造
empty、push、pop、front、back、size

四、prioroty_queue 优先队列容器(适配器)
#include
底层采用vector实现,当数据入队时,会对数据进行调整成堆结构,默认
是大顶堆,元素越大,优先级越高,越先出队,不允许相同
注意:存储的元素必须支持 < 运算符
注意:只能查看top。所以,可以使用top和pop查看各个元素

如何调整优先队列的优先级:(小顶堆)
1、元素取反存入,取出去反
2、类类型数据重载 < 运算符,调整 < 运算符的比较过程
3、固定语法
    priority_queue<类型,vector<类型>,greater<类型> >   队列名;
    //升序
    priority_queue<类型,vector<类型>,less<类型> >   队列名;
    //降序

五、关联性容器(有序)
关联性容器可以实现快速查找(O(logn))的容器
线性容器中array、vector、list、deque都可以使用全局的find进行顺序查找(O(n)),
必须支持operator==比较

底层实现:红黑树

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

默认下是按照 operator< 运算符进行比较,为什么不是使用 operatior== 来比较
    1、因为二叉排序树的规则:左小于根、根小于右,如果相等插入失败, ==无法判断大小
    2、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<添加的位置,是否添加成功>
    class pair{
        iterator first;
        bool second;
    }

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

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速度也不慢,但是
比set多一个value来进行描述。
redis内存数据库中使用键值对存储数据

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

构造函数:
    map();
    map( const map& m );
    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 就变得有意义了

通过迭代器删除元素需要注意的问题:
1、对于关联性容器(set\multiset\map\nultimap ),删除当前iterator会仅仅使得
当前iterator失效,其余位置没有变化,因此在erase时只需要递增iterator即可依次删除,
因为底层是红黑树,某个节点删除不会影响其他节点的位置
    map.erase(it++);

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

3、list两种方式都可以

十、bitset 位集合容器
#include
是一种封装了各种位操作的类类型数据结构
!=, ==, &=, ^=, |=, ~, <<=, >>=, []

成员函数:
bool any();
功能:有任意一位是1,返回真

size_type count();
功能:统计二进制位是1的位数有几位

flip 所有二进制位取反\指定的二进制位取反
none 全部位没有一个是1,返回真
reset 全部二进制位置0\指定二进制位置0
set  全部二进制位置1\指定二进制位置val=1
size 获取位数
test 访问指定的二进制位的值
to_string 把所有二进制位转string类型
to_ulong  把所有二进制位转unsigned long类型

C++不常用,但是对于嵌入式软件编程会比较方便去设置二进制位

常考的面试问题:
    1、vector与list的区别
        顺序结构、链式结构的区别
        容器区别:支持运算符、算法、迭代器等
    2、指针与迭代器的区别
        1、迭代器实际是为了遍历、操作容器而进行了封装的类模版,重载了指针操作的相关运算符,
        使用起来像指针一样,更像智能指针
        2、迭代器使用后会释放失效,不能继续直接使用,正常使用指针是可以继续使用
        3、指针可以指向函数,迭代器只能指向容器
        4、指针是迭代器的一种,只能用于某些特定类型的容器;迭代器是指针的一种泛化类型,
        可以用于任意类型的容器,所以,指针满足迭代器的一切要求。

        迭代器的设计模式:提供一种方法,不需要暴露其容器中的内部数据类型情况下,也能够正常操作、遍历该容器的每个
        元素,这种设计模式在STL中广泛使用。

    3、STL中哪些容器底层采用红黑树,为什么
        set\multiset\map\multimap
        (1)、数据需要频繁查找,也需要进行插入、删除操作,普通链式结构、顺序结构性能不高
        (2)、选择二分查找
        (3)、基于以上两点的话,就可以选择有序二叉树、不够均匀、接近单支状、效率低
        (4)、所以可以选择平衡二叉树AVL,查找效率高,创建、插入、删除效率低
        (5)、红黑树,伪平衡、查找速度很接近AVL、创建、插入、删除效率比AVL树高的多,综合性能最优

标签:10,deque,const,语言,iterator,容器,C++,key,迭代
From: https://www.cnblogs.com/c-learnmore/p/17683376.html

相关文章

  • C++的向上转型
    在C/C++中经常会发生数据类型的转换,例如将int类型的数据赋值给float类型的变量时,编译器会先把int类型的数据转换为float类型再赋值;反过来,float类型的数据在经过类型转换后也可以赋值给int类型的变量。数据类型转换的前提是,编译器知道如何对数据进行取舍。例如:inta=......
  • 米联客-S02(Artix-7-XC7A35T/100T)开发平台硬件手册
    1产品概述    MLK-S02(XC7A35T/100T)是米联客S系列开发平台的一款高性价比开发板。其核心模块集成电源管理:1V核心电源,最大输出8A。其开发平台为一体开发板,将主芯片直接焊接于开发板上,其开发板设计尺寸紧凑、资源丰富。其应用领域包含高速通信、机器视觉、伺服系统、视频采集......
  • CF1036F
    题目链接description\(10^5\)次询问每次给定\(n\leq10^{18}\),求2到\(n\)内质因子分解结果为\(p_{a_1}^{b_1}p_{a_2}^{b_2}...\),且\(\gcd(b1,b2...)=1\)的数的个数。solution显然答案为\(\sum\limits_{i=1}\mu(i)\lfloor\sqrt[i]{n}-1\rfloor\)。直接用cmath......
  • C++ 算法竞赛、02 周赛篇 | AcWing 第2场周赛
    AcWing第2场周赛竞赛-AcWing3626三元一次方程AcWing3626.三元一次方程-AcWing两层循环#include<iostream>usingnamespacestd;voidfind(intn){for(intx=0;x<=1000/3;x++){for(inty=0;y<=1000/5;y++){int......
  • R语言逻辑回归Logistic选股因素模型交易策略及沪深300指数实证|附代码数据
    全文链接:http://tecdat.cn/?p=32071原文出处:拓端数据部落公众号最近我们被客户要求撰写关于交易策略的研究报告,包括一些图形和统计输出。随着中国的证券市场规模的不断壮大、市场创新不断深化、信息披露不断完善、市场监管不断强化,随着现代投资组合理论的发展和计算机技术的进......
  • 10 个 效果不错的值得收藏的 css 代码片段
    10个css代码片段以下这10个常用的css代码片段值得收藏,都可以用于平常的业务代码当中。1.点点点加载中效果这是一个兼容性不错的用户体验很棒的点点点加载效果,实现思路如下:使用自定义的标签元素dot。将dot元素设置为内联元素(display:inline-block),并设置溢出隐藏(over......
  • 如何让 Llama2、通义千问开源大语言模型快速跑在函数计算上?
    :::info本文是“在Serverless平台上构建AIGC应用”系列文章的第一篇文章。:::前言随着ChatGPT以及StableDiffusion,Midjourney这些新生代AIGC应用的兴起,围绕AIGC应用的相关开发变得越来越广泛,有呈井喷之势,从长远看这波应用的爆发不仅仅是停留在形式之上,更是在各个领域产生......
  • C语言---函数
    与指针相关的运算符指针是一个值为内存地址的变量(或数据对象)地址运算符:&一般注解:后面跟一个变量名时,&给出该变量的地址。示例:&nurse表示变量nurse的地址间接(或解引用)运算符:*一般注解:后跟一个指针名或地址时,*给出存储在指针指向地址上的值。示例:nurse=22;ptr=&nurse;//指向......
  • C++运算符优先级
    所有(可能)运算符共分为18级。第1级运算符含义::作用域解析运算符第2级运算符含义()函数调用()值构造,即type(expr)[]数组下标->间接成员运算符.直接成员运算符const_cast专用的类型转换dynamic_cast专用的类型转换re......
  • 【C语言进阶】指针数组 —— 数组指针
    (文章目录)......