C++STL库的 deque、stack、queue、list、set/multiset、map/multimap

deque 容器

        Vector 容器是单向开口的连续内存空间, deque 则是一种双向开口的连续线性空 间。所谓的双向开口,意思是可以在头尾两端分别做元素的插入和删除操作,当然, vector 容器也可以在头尾两端插入元素,但是在其头部操作效率奇差,无法被接受。
        Deque 容器和 vector 容器最大的差异,一在于 deque 允许使用常数项时间对头端 进行元素的插入和删除操作。二在于 deque 没有容量的概念,因为它是动态的以 分段连续空间组合而成,随时可以增加一段新的空间并链接起来,换句话说,像 vector 那样, 旧空间不足而重新配置一块更大空间,然后复制元素,再释放旧空间” 这样的事情在 deque 身上是不会发生的。也因此 deque 没有必须要提供所谓的空间保留(reserve) 功能 .
        虽然 deque 容器也提供了 Random Access Iterator, 但是它的迭代器并不是普通的指针,其复杂度和 vector 不是一个量级,这当然影响各个运算的层面。因此,除非 有必要,我们应该尽可能的使用 vector ,而不是 deque 。对 deque 进行的排序操作,为了最高效率,可将 deque 先完整的复制到一个 vector 中,对 vector 容器进行排序,再复制回 deque.

deque 容器实现原理

        Deque 容器是连续的空间,至少逻辑上看来如此,连续现行空间总是令我们联想 到 array vector,array 无法成长, vector 虽可成长,却只能向尾端成长,而且其 成长其实是一个假象,事实上(1) 申请更大空间 (2) 原数据复制新空间 (3) 释放原空间 三步骤,如果不是 vector 每次配置新的空间时都留有余裕,其成长假象所带来 的代价是非常昂贵的。
        Deque 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间,便配置一段连续定量的空间,串接在 deque 的头端或者尾端。
        Deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象,并提供随 机存取的接口,避开了重新配置空间,复制,释放的轮回,代价就是复杂的迭代器架构。
        既然 deque 是分段连续内存空间,那么就必须有中央控制,维持整体连续的假象, 数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque 代码的实现远比 vector 或 list 都多得多。         Deque 采取一块所谓的 map( 注意,不是 STL map 容器 ) 作为主控,这里所谓map 是一小块连续的内存空间,其中每一个元素 ( 此处成为一个结点 ) 都是一个指针, 指向另一段连续性内存空间,称作缓冲区。缓冲区才是 deque 的存储空间的主体。

deque 构造函数

deque<T> deqT; // 默认构造形式
deque(beg, end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。
deque(n, elem); // 构造函数将 n elem 拷贝给本身。
deque( const deque &deq); // 拷贝构造函数。

deque 赋值操作

assign(beg, end); // [beg, end) 区间中的数据拷贝赋值给本身。
assign(n, elem); // n elem 拷贝赋值给本身。
deque& operator =( const deque &deq); // 重载等号操作符
swap(deq); // deq 与本身的元素互换

deque 大小操作

deque.size(); // 返回容器中元素的个数
deque.empty(); // 判断容器是否为空
deque.resize(num); // 重新指定容器的长度为 num, 若容器变长,则以默认值填充新位 置。如果容器变短,则末尾超出容器长度的元素被删除。
deque.resize(num, elem); // 重新指定容器的长度为 num, 若容器变长,则以 elem 填充新位置 , 如果容器变短,则末尾超出容器长度的元素被删除。

deque 双端插入和删除操作

push_back(elem); // 在容器尾部添加一个数据
push_front(elem); // 在容器头部插入一个数据
pop_back(); // 删除容器最后一个数据
pop_front(); // 删除容器第一个数据

deque 数据存取

at(idx); // 返回索引 idx 所指的数据,如果 idx 越界,抛出 out_of_range
operator []; // 返回索引 idx 所指的数据,如果 idx 越界,不抛出异常,直接出错。
front(); // 返回第一个数据。
back(); // 返回最后一个数据

deque 插入操作

insert(pos,elem); // pos 位置插入一个 elem 元素的拷贝,返回新数据的位置。
insert(pos,n,elem); // pos 位置插入 n elem 数据,无返回值。
insert(pos,beg,end); // pos 位置插入 [beg,end) 区间的数据,无返回值。

deque 删除操作

clear(); // 移除容器的所有数据
erase(beg,end); // 删除 [beg,end) 区间的数据,返回下一个数据的位置。
erase(pos); // 删除 pos 位置的数据,返回下一个数据的位置。

stack 容器

容器基本概念

        stack 是一种先进后出 (First In Last Out,FILO) 的数据结构,它只有一个出口,形式 如图所示。stack 容器允许新增元素,移除元素,取得栈顶元素,但是除了最顶端 外,没有任何其他方法可以存取 stack 的其他元素。换言之, stack 不允许有遍历 行为。
有元素推入栈的操作称为 :push, 将元素推出 stack 的操作称为 pop

stack 没有迭代器

        Stack 所有元素的进出都必须符合 先进后出 的条件,只有 stack 顶端的元素,才有机会被外界取用。Stack 不提供遍历功能,也不提供迭代器。

stack 构造函数

stack<T> stkT; //stack 采用模板类实现, stack 对象的默认构造形式:
stack( const stack &stk); // 拷贝构造函数

stack 赋值操作

stack& operator =( const stack &stk); // 重载等号操作符

stack 数据存取操作

push(elem); // 向栈顶添加元素
pop(); // 从栈顶移除第一个元素
top(); // 返回栈顶元素

stack 大小操作

empty(); // 判断堆栈是否为空
size(); // 返回堆栈的大小

queue 容器

容器基本概念
        Queue 是一种先进先出 (First In First Out,FIFO) 的数据结构,它有两个出口, queue 容器允许从一端新增元素,从另一端移除元素。
queue 没有迭代器
        Queue 所有元素的进出都必须符合 先进先出 的条件,只有 queue 的顶端元素,才 有机会被外界取用。Queue 不提供遍历功能,也不提供迭代器。

queue 构造函数

queue<T> queT; //queue 采用模板类实现, queue 对象的默认构造形式:
queue( const queue &que); // 拷贝构造函数

queue 存取、插入和删除操作

push(elem); // 往队尾添加元素
pop(); // 从队头移除第一个元素
back(); // 返回最后一个元素
front(); // 返回第一个元素

queue 赋值操作

queue& operator =( const queue &que); // 重载等号操作符

queue 大小操作

empty(); // 判断队列是否为空
size(); // 返回队列的大小

list 容器

list 容器基本概念

        链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通 过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点) 组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素 的数据域,另一个是存储下一个结点地址的指针域。
        相较于 vector 的连续线性空间, list 就显得负责许多,它的好处是每次插入或者删除一个元素,就是配置或者释放一个元素的空间。因此,list 对于空间的运用有绝对的精准,一点也不浪费。而且,对于任何位置的元素插入或元素的移除,list 永远是常数时间。
         List 和 vector 是两个最常被使用的容器。
List 容器是一个双向链表。
        采用动态存储分配,不会造成内存浪费和溢出
        链表执行插入和删除操作十分方便,修改指针即可,不需要移动大量元素
        链表灵活,但是空间和时间额外耗费较大
list 容器的迭代器
        List 容器不能像 vector 一样以普通指针作为迭代器,因为其节点不能保证在同一 块连续的内存空间上。List 迭代器必须有能力指向 list 的节点,并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list 正确的递增,递减、取值、成员 取用” 是指,递增时指向下一个节点,递减时指向上一个节点,取值时取的是节点 的数据值,成员取用时取的是节点的成员。
        由于 list 是一个双向链表,迭代器必须能够具备前移、后移的能力,所以 list 容器 提供的是 Bidirectional Iterators.
        List 有一个重要的性质,插入操作和删除操作都不会造成原有 list 迭代器的失效。
        这在 vector 是不成立的,因为 vector 的插入操作可能造成记忆体重新配置,导致 原有的迭代器全部失效,甚至 List 元素的删除,也只有被删除的那个元素的迭代 器失效,其他迭代器不受任何影响。
list 容器的数据结构
list 容器不仅是一个双向链表,而且还是一个循环的双向链表。

list 构造函数

list<T> lstT; //list 采用采用模板类实现 , 对象的默认构造形式:
list(beg,end); // 构造函数将 [beg, end) 区间中的元素拷贝给本身。
list(n,elem); // 构造函数将 n elem 拷贝给本身。
list( const list &lst); // 拷贝构造函数。

list 数据元素插入和删除操作

push_back(elem); // 在容器尾部加入一个元素
pop_back(); // 删除容器中最后一个元素
push_front(elem); // 在容器开头插入一个元素
pop_front(); // 从容器开头移除第一个元素
insert(pos,elem); // pos 位置插 elem 元素的拷贝,返回新数据的位置。
insert(pos,n,elem); // pos 位置插入 n elem 数据,无返回值。
insert(pos,beg,end); // pos 位置插入 [beg,end) 区间的数据,无返回值。
clear(); // 移除容器的所有数据
erase(beg,end); // 删除 [beg,end) 区间的数据,返回下一个数据的位置。
erase(pos); // 删除 pos 位置的数据,返回下一个数据的位置。
remove(elem); // 删除容器中所有与 elem 值匹配的元素。

list 大小操作

size(); // 返回容器中元素的个数
empty(); // 判断容器是否为空
resize(num); // 重新指定容器的长度为 num
若容器变长,则以默认值填充新位置。
如果容器变短,则末尾超出容器长度的元素被删除。
resize(num, elem); // 重新指定容器的长度为 num
若容器变长,则以 elem 值填充新位置。
如果容器变短,则末尾超出容器长度的元素被删除。

list 赋值操作

assign(beg, end); // [beg, end) 区间中的数据拷贝赋值给本身。
assign(n, elem); // n elem 拷贝赋值给本身。
list& operator =( const list &lst); // 重载等号操作符
swap(lst); // lst 与本身的元素互换。
3.6.4.5 list 数据的存取
front(); // 返回第一个元素。
back(); // 返回最后一个元素。
3.6 .4 .6 list 反转排序
reverse(); // 反转链表,比如 lst 包含 1,3,5 元素,运行此方法后, lst 就包含 5,3,1 元素。
sort(); //list 排序

list 反转排序

reverse(); // 反转链表,比如 lst 包含 1,3,5 元素,运行此方法后, lst 就包含 5,3,1 元素。
sort(); //list 排序

set/multiset 容器

set/multiset 容器基本概念

        Set 的特性是。所有元素都会根据元素的键值自动被排序。 Set 的元素不像 map 那样可以同时拥有实值和键值,set 的元素即是键值又是实值。 Set 不允许两个元素 有相同的键值。
        我们可以通过 set 的迭代器改变 set 元素的值吗?不行,因为 set 元素值就是其键 值,关系到 set 元素的排序规则。如果任意改变 set 元素值,会严重破坏 set 组织。 换句话说,set iterator 是一种 const_iterator.
        set 拥有和 list 某些相同的性质,当对容器中的元素进行插入操作或者删除操作的 时候,操作之前所有的迭代器,在操作完成之后依然有效,被删除的那个元素的迭代器必然是一个例外。
        multiset 特性及用法和 set 完全相同,唯一的差别在于它允许键值重复。 set 和 multiset 的底层实现是红黑树,红黑树为平衡二叉树的一种。
树的简单知识:
二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。
二叉树示意图
        二叉搜索树,是指二叉树中的节点按照一定的规则进行排序,使得对二叉树中元素 访问更加高效。二叉搜索树的放置规则是:任何节点的元素值一定大于其左子树中 的每一个节点的元素值,并且小于其右子树的值。因此从根节点一直向左走,一直 到无路可走,即得到最小值,一直向右走,直至无路可走,可得到最大值。那么在 儿茶搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树:
        上面我们介绍了二叉搜索树,那么当一个二叉搜索树的左子树和右子树不平衡的时候,那么搜索依据上图表示,搜索 9 所花费的时间要比搜索 17 所花费的时间要多, 由于我们的输入或者经过我们插入或者删除操作,二叉树失去平衡,造成搜索效率降低。
        所以我们有了一个平衡二叉树的概念,所谓的平衡不是指的完全平衡。

set 构造函数

set<T> st; //set 默认构造函数:
mulitset<T> mst; //multiset 默认构造函数 :
set( const set &st); // 拷贝构造函数

set 赋值操作

set& operator =( const set &st); // 重载等号操作符
swap(st); // 交换两个集合容器

set 大小操作

size(); // 返回容器中元素的数目
empty(); // 判断容器是否为空

set 插入和删除操作

insert(elem); // 在容器中插入元素。
clear(); // 清除所有元素
erase(pos); // 删除 pos 迭代器所指的元素,返回下一个元素的迭代器。
erase(beg, end); // 删除区间 [beg,end) 的所有元素 ,返回下一个元素的迭代器。
erase(elem); // 删除容器中值为 elem 的元素。

set 查找操作

find(key); // 查找键 key 是否存在 , 若存在,返回该键的元素的迭代器;若不存在,返 set.end();
count(key); // 查找键 key 的元素个数
lower_bound(keyElem); // 返回第一个 key>=keyElem 元素的迭代器。
upper_bound(keyElem); // 返回第一个 key>keyElem 元素的迭代器。
equal_range(keyElem); // 返回容器中 key keyElem 相等的上下限的两个迭代器。

set 的返回值 指定 set 排序规则:

// 插入操作返回值
// 插入操作返回值
void test01(){
        set< int > s;
        pair<set< int >::iterator, bool > ret = s.insert( 10 );
        if (ret.second){
                cout << " 插入成功 :" << *ret.first << endl;
        }
        else {
                cout << " 插入失败 :" << *ret.first << endl;
        }
        ret = s.insert( 10 );
        if (ret.second){
                cout << " 插入成功 :" << *ret.first << endl;
        }
        else {
                cout << " 插入失败 :" << *ret.first << endl;
        }
}
struct MyCompare02{
        bool operator ()( int v1, int v2){
                return v1 > v2;
        }
};
//set 从大到小
void test02(){
        srand(( unsigned int )time(NULL));
        //我们发现 set 容器的第二个模板参数可以设置排序规则,默认规则是 less<_Kt y>
        set< int , MyCompare02> s;
        for ( int i = 0 ; i < 10 ;i++){
                s.insert(rand() % 100 );
        }
        for (set< int , MyCompare02>::iterator it = s.begin(); it != s.end (); it ++){
                cout << *it << " " ;
        }
        cout << endl;
}
//set 容器中存放对象
class Person{
public :
        Person(string name, int age){
                this ->mName = name;
                this ->mAge = age;
        }
public :
        string mName;
        int mAge;
};
struct MyCompare03{
        bool operator ()( const Person& p1, const Person& p2){
                return p1.mAge > p2.mAge;
        }
};
void test03(){
        set<Person, MyCompare03> s;
        Person p1( "aaa" , 20 );
        Person p2( "bbb" , 30 );
        Person p3( "ccc" , 40 );
        Person p4( "ddd" , 50 );
        s.insert(p1);
        s.insert(p2);
        s.insert(p3);
        s.insert(p4);
        for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){
                cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
        }
}

对组(pair)

        对组(pair) 将一对值组合成一个值,这一对值可以具有不同的数据类型,两个值可 以分别用 pair 的两个公有属性 first second 访问。
类模板: template <class T1, class T2> struct pair.
如何创建对组 ?
// 第一种方法创建一个对组
pair<string, int > pair1(string( "name" ), 20 );
cout << pair1.first << endl; // 访问 pair 第一个值
cout << pair1.second << endl; // 访问 pair 第二个值
// 第二种
pair<string, int > pair2 = make_pair( "name" , 30 );
cout << pair2.first << endl;
cout << pair2.second << endl;
//pair= 赋值
pair<string, int > pair3 = pair2;
cout << pair3.first << endl;
cout << pair3.second << endl;

map/multimap 容器

map/multimap 基本概念

        Map 的特性是,所有元素都会根据元素的键值自动排序。 Map 所有的元素都是 pair,同时拥有实值和键值, pair 的第一元素被视为键值,第二元素被视为实值, map 不允许两个元素有相同的键值。
        我们可以通过 map 的迭代器改变 map 的键值吗?答案是不行,因为 map 的键值 关系到 map 元素的排列规则,任意改变 map 键值将会严重破坏 map 组织。如果 想要修改元素的实值,那么是可以的。
        Map 和 list 拥有相同的某些性质,当对它的容器元素进行新增操作或者删除操作 时,操作之前的所有迭代器,在操作完成之后依然有效,当然被删除的那个元素的迭代器必然是个例外。
        Multimap 和 map 的操作类似,唯一区别 multimap 键值可重复。
        Map 和 multimap 都是以红黑树为底层实现机制。

map 构造函数

map<T1, T2> mapTT; //map 默认构造函数 :
map( const map &mp); // 拷贝构造函数

map 赋值操作

map& operator =( const map &mp); // 重载等号操作符
swap(mp); // 交换两个集合容器

map 大小操作

size(); // 返回容器中元素的数目
empty(); // 判断容器是否为空

map 插入数据元素操作

map.insert(...); // 往容器插入元素,返回 pair<iterator,bool>
map< int , string> mapStu;
// 第一种 通过 pair 的方式插入对象
mapStu.insert(pair< int , string>( 3 , " 小张 " ));
// 第二种 通过 pair 的方式插入对象
mapStu.inset(make_pair(- 1 , " 校长 " ));
// 第三种 通过 value_type 的方式插入对象
mapStu.insert(map< int , string>:: value_type ( 1 , " 小李 " ));
// 第四种 通过数组的方式插入值
mapStu[ 3 ] = " 小刘 " ;
mapStu[ 5 ] = " 小王 " ;

map 删除操作

clear(); // 删除所有元素
erase(pos); // 删除 pos 迭代器所指的元素,返回下一个元素的迭代器。
erase(beg,end); // 删除区间 [beg,end) 的所有元素 ,返回下一个元素的迭代器。
erase(keyElem); // 删除容器中 key keyElem 的对组。

map 查找操作

find(key); // 查找键 key 是否存在 , 若存在,返回该键的元素的迭代器; / 若不存在,返 map.end();
count(keyElem); // 返回容器中 key keyElem 的对组个数。对 map 来说,要么是 0 要么是 1 。对 multimap 来说,值可能大于 1
lower_bound(keyElem); // 返回第一个 key>=keyElem 元素的迭代器。
upper_bound(keyElem); // 返回第一个 key>keyElem 元素的迭代器。
equal_range(keyElem); // 返回容器中 key keyElem 相等的上下限的两个迭代器。

multimap 案例

        公司今天招聘了 5 个员工, 5 名员工进入公司之后,需要指派员工在那个部门工作 人员信息有: 姓名 年龄 电话 工资等组成 通过 Multimap 进行信息的插入 保存 显示 分部门显示员工信息 显示全部员工信息
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
// multimap 案例
// 公司今天招聘了 5 个员工,5 名员工进入公司之后,需要指派员工在那个部门工作
// 人员信息有: 姓名 年龄 电话 工资等组成
// 通过 Multimap 进行信息的插入 保存 显示
// 分部门显示员工信息 显示全部员工信息
#define SALE_DEPATMENT 1     // 销售部门
#define DEVELOP_DEPATMENT 2  // 研发部门
#define FINACIAL_DEPATMENT 3 // 财务部门
#define ALL_DEPATMENT 4      // 所有部门
// 员工类
class person
{
public:string name;   // 员工姓名int age;       // 员工年龄double salary; // 员工工资string tele;   // 员工电话
};
// 创建 5 个员工
void CreatePerson(vector<person> &vlist)
{string seed = "ABCDE";for (int i = 0; i < 5; i++){person p;p.name = "员工";p.name += seed[i];p.age = rand() % 30 + 20;p.salary = rand() % 20000 + 10000;p.tele = "010-8888888";vlist.push_back(p);}
}
// 5 名员工分配到不同的部门
void PersonByGroup(vector<person> &vlist, multimap<int, person> &plist)
{int operate = -1; // 用户的操作for (vector<person>::iterator it = vlist.begin(); it != vlist.end(); it++){cout << "当前员工信息:" << endl;
cout << "姓名:" << it->name << " 年龄:" << it->age << " 工
资:" << it->salary << " 电话:" << it->tele << endl;
cout << "请对该员工进行部门分配(1 销售部门, 2 研发部门, 3 财务
部门):" << endl;
scanf("%d", &operate);
while (true)
{if (operate == SALE_DEPATMENT){ // 将该员工加入到销售部门plist.insert(make_pair(SALE_DEPATMENT, *it));break;}else if (operate == DEVELOP_DEPATMENT){plist.insert(make_pair(DEVELOP_DEPATMENT, *it));break;}else if (operate == FINACIAL_DEPATMENT){plist.insert(make_pair(FINACIAL_DEPATMENT, *it));break;}else{
cout << "您的输入有误,请重新输入(1 销售部门, 2 研
发部门, 3 财务部门):" << endl;
scanf("%d", &operate);}
}}cout << "员工部门分配完毕!" << endl;cout << "********************************************************* **" << endl;
}
// 打印员工信息
void printList(multimap<int, person> &plist, int myoperate)
{if (myoperate == ALL_DEPATMENT){for (multimap<int, person>::iterator it = plist.begin(); it != plist.end(); it++){cout << "姓名:" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话:" << it->second.t ele << endl;}return;}multimap<int, person>::iterator it = plist.find(myoperate);int depatCount = plist.count(myoperate);int num = 0;if (it != plist.end()){while (it != plist.end() && num < depatCount){cout << "姓名:" << it->second.name << " 年龄:" << it->second.age << " 工资:" << it->second.salary << " 电话:" << it->second.t ele << endl;it++;num++;}}
}
// 根据用户操作显示不同部门的人员列表
void ShowPersonList(multimap<int, person> &plist, int myoperate)
{switch (myoperate){case SALE_DEPATMENT:printList(plist, SALE_DEPATMENT);break;case DEVELOP_DEPATMENT:printList(plist, DEVELOP_DEPATMENT);break;case FINACIAL_DEPATMENT:printList(plist, FINACIAL_DEPATMENT);break;case ALL_DEPATMENT:printList(plist, ALL_DEPATMENT);break;}
}
// 用户操作菜单
void PersonMenue(multimap<int, person> &plist)
{int flag = -1;int isexit = 0;while (true){
cout << "请输入您的操作((1 销售部门, 2 研发部门, 3 财务部门, 4
所有部门, 0 退出):" << endl;
scanf("%d", &flag);
switch (flag)
{
case SALE_DEPATMENT:ShowPersonList(plist, SALE_DEPATMENT);break;
case DEVELOP_DEPATMENT:ShowPersonList(plist, DEVELOP_DEPATMENT);break;
case FINACIAL_DEPATMENT:ShowPersonList(plist, FINACIAL_DEPATMENT);break;
case ALL_DEPATMENT:ShowPersonList(plist, ALL_DEPATMENT);break;
case 0:isexit = 1;break;
default:cout << "您的输入有误,请重新输入!" << endl;break;
}
if (isexit == 1)
{break;
}}
}
int main()
{vector<person> vlist;        // 创建的 5 个员工 未分组multimap<int, person> plist; // 保存分组后员工信息// 创建 5 个员工CreatePerson(vlist);// 5 名员工分配到不同的部门PersonByGroup(vlist, plist);// 根据用户输入显示不同部门员工信息列表 或者 显示全部员工的信息列表PersonMenue(plist);system("pause");return EXIT_SUCCESS;
}

STL 容器使用时机

        比如上一次的记录,上上次的记录,但却不会去删除记录,因为记录是事实的描述。
deque 的使用场景:比如排队购票系统,对排队者的存储可以采用 deque ,支持 头端的快速移除,尾端的快速添加。如果采用 vector ,则头端移除时,会移动大量 的数据,速度慢。
        vector 与 deque 的比较:
        一:vector.at() deque.at() 效率高,比如 vector.at(0) 是固定的, deque 的开始位 置 却是不固定的。
        二:如果有大量释放操作的话,vector 花的时间更少,这跟二者的内部实现有关。
        三:deque 支持头部的快速插入与快速移除,这是 deque 的优点。
list 的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
set 的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分 的顺序排列。
map 的使用场景:比如按 ID 号存储十万个用户,想要快速要通过 ID 查找对应的 用户。二叉树的查找效率,这时就体现出来了。如果是 vector 容器,最坏的情况 下可能要遍历完整个容器才能找到该用户。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/215722.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

三防平板|手持终端PDA|8寸/10寸工业三防平板电脑主板方案定制

近年来&#xff0c;随着科技的快速发展&#xff0c;三防平板成为了各行各业中不可或缺的工具。三防平板采用IP67级别的防护设计&#xff0c;通过了多项测试标准&#xff0c;如国标和美标&#xff0c;具备防水、防摔、防尘、防撞、防震、防跌落以及防盐雾等多重防护功能。因此&a…

ARM:作业3

按键中断代码编写 代码: key_it.h #ifndef __KEY_IT_H__ #define __KEY_IT_H__#include "stm32mp1xx_gpio.h" #include "stm32mp1xx_exti.h" #include "stm32mp1xx_rcc.h" #include "stm32mp1xx_gic.h"void key1_it_config(); voi…

vxe-table 右键菜单+权限控制(v3)

1.menu-config 是用于配置右键菜单的属性。通过 menu-config 属性&#xff0c;定义右键菜单的内容、显示方式和样式。 通过 menu-config 属性配置了右键菜单&#xff0c;其中的 options 属性定义了右键菜单的选项。用户在表格中右键点击时&#xff0c;将会弹出包含这些选项的自…

练练手之“四环”“磁铁”(svg)

文本是闲暇之余练习svg的运用的产物&#xff0c;记录以备有需。 <svg xmlns"http://www.w3.org/2000/svg" viewBox"0 0 500 500" width"500px" height"500px"><path d"M150,100 A50,50 0 1,1 150,99.999" stroke&q…

【数据结构(九)】顺序存储二叉树(2)

文章目录 1. 相关概念2. 顺序存储二叉树的遍历 1. 相关概念 从数据存储来看&#xff0c;数组存储方式和树的存储方式可以相互转换&#xff0c;即数组可以转换成树&#xff0c;树也可以转换成数组&#xff0c;看右面的示意图。 转换原则:     1.上图的二叉树的结点&#xff…

【深度学习】注意力机制(五)

本文介绍一些注意力机制的实现&#xff0c;包括CSRA/Spatial Shift/Triplet Attention/Coordinate Attention/ACmix。 【深度学习】注意力机制&#xff08;一&#xff09; 【深度学习】注意力机制&#xff08;二&#xff09; 【深度学习】注意力机制&#xff08;三&#xff…

python 实现 AIGC 大模型中的概率论:生日问题的基本推导

在上一节中&#xff0c;我们对生日问题进行了严谨的阐述&#xff1a;假设屋子里面每个人的生日相互独立&#xff0c;而且等可能的出现在一年 365 天中的任何一天&#xff0c;试问我们需要多少人才能让某两个人的生日在同一天的概率超过 50%。 处理抽象逻辑问题的一个入手点就是…

centos 7.9 二进制部署 kubernetes v1.27.7

文章目录 1. 预备条件2. 基础配置2.1 配置root远程登录2.2 配置主机名2.3 安装 ansible2.4 配置互信2.5 配置hosts文件2.6 关闭防firewalld火墙2.7 关闭 selinux2.8 关闭交换分区swap2.9 修改内核参数2.10 安装iptables2.11 开启ipvs2.12 配置limits参数2.13 配置 yum2.14 配置…

css实现姓名两端对齐

1.1 效果 1.2 主要代码 text-align-last: justify; 1.3 html完整代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0&quo…

【LeetCode刷题-树】-- 116.填充每个节点的下一个右侧节点指针

116.填充每个节点的下一个右侧节点指针 方法&#xff1a;层次遍历 /* // Definition for a Node. class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val _val;}public Node(int _val, Node _left, N…

MeterSphere实战(一)

MeterSphere是一位朋友讲到的测试平台&#xff0c;说这东西是开源的&#xff0c;因为我是做测试的&#xff0c;很乐意了解一些新鲜事物。在我看来&#xff0c;测试就是要专注一些领域&#xff0c;然后要啥都会一点点&#xff0c;接着融会贯通起来&#xff0c;这样就可以万变不离…

RCNN 学习

RCNN算法流程 RCNN算法流程可分为4个步骤 一张图像生成1K~2K个候选区域&#xff08;使用Selective Search方法&#xff09;对每个候选区域&#xff0c;使用深度网络图特征特征送入每一类的SVM分类器&#xff0c;判别是否属于该类使用回归期器细修正候选框位置 1.候选区域的生…

漏洞复现-泛微云桥 e-Bridge SQL注入(附漏洞检测脚本)

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…

C51单片机中reentrant关键字的使用,关于MULTIPLE CALL TO FUNCTION警告的问题

关于可重入关键字reentrant的使用&#xff1a; 现象&#xff1a; 在一个项目中警告信息如下&#xff0c;提示该函数多次调用&#xff0c;因为该函数在串口中断和主循环中都有被调用。 影响&#xff1a; 如果在使用该函数期间被中断打断&#xff0c;而中断也调用了该函数&a…

文件管理和操作工具Path Finder mac功能介绍

Path Finder mac是一款Mac平台上的文件管理和操作工具&#xff0c;提供了比Finder更丰富的功能和更直观的用户界面。它可以帮助用户更高效地浏览、复制、移动、删除和管理文件&#xff0c;以及进行各种高级操作。 Path Finder mac软件功能 - 文件浏览&#xff1a;可以快速浏览文…

node.js和npm的安装与环境配置(2023最新版)

目录 安装node.js测试是否安装成功测试npm环境配置更改环境变量新建系统变量 安装node.js 1、进入官网下载&#xff1a;node.js官网 我选择的是windows64位的&#xff0c;你可以根据自己的实际情况选择对应的版本。 2、下载完成&#xff0c;安装。 打开安装程序 接受协议 选…

学习-面试java基础-(集合)

String 为什么不可变&#xff1f; 1线程安全 2支持hash映射和缓存。因为String的hash值经常会使用到&#xff0c;比如作为 Map 的键&#xff0c;不可变的特性使得 hash 值也不会变&#xff0c;不需要重新计算。 3出于安全考虑。网络地址URL、文件路径path、密码通常情况下都是以…

降低检索系统搭建门槛,轻松实现 RAG 应用!Zilliz Cloud Pipelines 惊喜上线

Zilliz Cloud 正式上线 Pipelines&#xff01; Zilliz Cloud Pipelines 可以将文档、文本片段和图像等非结构化数据转换成可搜索的向量并存储在 Collection 中&#xff0c;帮助开发者简化工程开发&#xff0c;助力其实现多种场景的 RAG 应用&#xff0c;将复杂生产系统的搭建和…

【已解决】SpringBoot Maven 打包失败:class lombok.javac.apt.LombokProcessor 错误

文章目录 出错原因解决办法总结 最新项目部署的时候&#xff0c;出现了一个maven打包失败的问题&#xff0c;主要是lombok这个组件出的问题&#xff0c;具体的错误信息如下&#xff1a; 我的lombok版本如下&#xff1a; <dependency><groupId>org.projectlombok&l…

Editplus安装教程(附带汉化教程与获取注册码教程)

文章目录 前言一、Editplus简介1. 简介2. 特点和功能 二、Editplus5安装步骤1. 下载EditPlus52. 运行安装程序3. 接受许可协议4. 选择安装位置5. 选择组件6. 完成安装7. 启动EditPlus8. 注册EditPlus 三、Editplus4安装步骤1. 下载EditPlus42. 安装EditPlus43. 注册码获取 四、…