其他容器

deque

---

deque介绍

• 双端数组，可对头端进行插入删除操作 deque和vector区别:
• vector对头部插入删除效率低，数据量越大，效率越低
• deque相对而言，对头部的插入删除速度比vector快
• vector访问元素的速度比deque快，这和两者内部实现有关

工作原理 deque内部有一个中控器，维护每段缓冲区的内容，缓冲区存放真实数据 中控器维护的是每个缓冲区的地址，使得使用deque时像是一片连续内存空间

Note

deque图解

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

0x01

0x02

0x03

节点

中控器

ele

ele

ele

ele

ele

ele

ele

ele

ele

ele

ele

ele

指向原始笔记的链接

deque构造函数

• deque<T>deqT; //默认构造
• deque(beg, end); //左闭右开[beg, end)之间的元素赋值给本身
• deque(n, elem); //n个elem拷贝给自身
• deque(const deque *deq); //拷贝构造

deque赋值操作

• deque& operator=(const deque& deq);
• assign(beg, end);
• assign(n, elem);

deque大小操作

• empty();
• size();
• resize(num);
• resize(num, elem);

deque插入和删除

头尾操作

• push_back(elem); //尾部插入元素
• pop_back(); //删除最后的元素
• push_front(elem); //开头插入元素
• pop_front(); //移除开头元素 中间操作
• int insert(const_iterator pos, ele); //ele从pos位置插入(从0开始)，返回新的数据位置
• insert(iterator pos, int count, ele); //ele从pos位置插入count次(从0开始)
• insert(const_iterator pos, const_iterator beg, const_iterator end); //在pos位置插入[beg, end)区间的数据
• erase(iterator pos); //删除pos位元素(从0开始)
• erase(iterator start, iterator end); //删除pos位元素[beg, end)
• clear(); //全清
• remove(elem); //删除与elem值匹配的元素

deque数据存取

• at(int idx);
• operator[];
• front();
• back();

deque排序

利用算法实现

• sort(beg, end, T);

stack

---

stack基本概念

stack是一种先进后出(First In Last Out,FILO)的数据结构,他只有一个出口 栈只有顶端元素才能被外界使用，因此栈不允许遍历

• 可以判断元素是否为空isEmpty()
• 可以返回元素个数size()
• 加入元素(入栈)push()
• 输出元素(出栈)pop()

Note

stack图解

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

ele

栈底

ele

ele

栈顶

top()

pop()

push()

ele

指向原始笔记的链接

生活中的例子：弹夹

stack常用接口

stack构造函数

• stack<T>s;
• stack(const stack& stk);

stack赋值

• stack& operator=(const stack& stk);

stack数据存取

• push(elem);
• pop();
• top();

stack大小操作

• bool empty();
• int size();

queue

---

queue基本概念

queue是一种先进先出(First In First Out,FIFO)的数据结构,他只有一个出口 队列只有队头队尾才能被外界使用，不允许遍历

• 可以判断元素是否为空isEmpty()
• 可以返回元素个数size()
• 加入元素(入队)push()
• 输出元素(出队)pop()

Note

queue图解

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

ele

ele

ele

ele

ele

push()

pop()

指向原始笔记的链接

queue常用接口

queue构造函数

• queue<T>que;
• queue(const queue& que);

queue赋值

• queue& operator=(const queue& que);

queue数据存取

• push(elem);
• pop();
• back();
• front();

queue大小操作

• bool empty();
• int size();

其他

---

• array stl中的模板静态数组，在栈上分配内存，和普通数组功能基本一致。 在部分场景中，模板数组比常规数组更能提高开发效率。
• unordered_multimap 允许重复键值，操作跟unordered_multimap相差不大
• unordered_set和unordered_multiset 操作跟set相差不大
• priority_queue 优先队列，元素都做了加权处理