从零开始手写STL库:Deque
从零开始手写STL库–Deque部分
Github链接:miniSTL
Deque是什么
std::deque(双端队列)是一种在内存中连续存储元素的数据结构,它支持在两端添加和删除元素,属于顺序容器。
底层构造和std::vector是一样的,都是数组,可以理解为多了pop_front/push_front功能的vector。
Deque需要包含什么函数
1) 基础成员函数
构造函数:初始化Deque
析构函数:释放内存,当运行结束后要摧毁这个Deque防止内存泄漏
2) 核心功能
push_back/push_front:从队尾/头插入元素
pop_back/pop_front:从队尾/头删除元素
get:获取某个位置的元素
size:获取队列长度
clear:清空队列
3) 其他功能
迭代器、还有连续储存类型的容器必须有的resize函数,用来处理内存不足的情况
基础成员函数的编写
Deque的成员
一个双向队列应当包含Vector所有的成员:数组、容量、长度,额外的要有头尾指针
private:
T* elements;
size_t capacity;
size_t frontIndex;
size_t backIndex;
size_t size;
那么构造函数和析构函数也就可以写了
Deque() : elements(nullptr), capacity(0), frontIndex(0), backIndex(0), size(0) {}
~Deque() {
clear();
delete[] elements;
}
核心功能函数的编写
1、push_back/push_front:从队尾/头插入元素
和vector中的写法基本一样,详见从零开始手写STL库:Vector
void push_back(const T& value) {
if (size == capacity) {
resize();
}
elements[backIndex] = value;
backIndex = (backIndex + 1) % capacity;
++size;
}
void push_front(const T& value) {
if (size == capacity) {
resize();
}
frontIndex = (frontIndex - 1 + capacity) % capacity;
elements[frontIndex] = value;
++size;
}
但是这里有两行
backIndex = (backIndex + 1) % capacity;
frontIndex = (frontIndex - 1 + capacity) % capacity;
这样写的意义,实际上是把这个数组的首位相接了,如果从队头pop,那么只需要让头指针后移一位即可,不需要整个数组前移
而真正用于构建队列的元素就只有夹在头尾指针之间的数,大大缩短了操作时间
2、pop_back/pop_front:从队尾/头删除元素
移动头尾节点即可
void pop_front() {
if (size == 0) {
throw std::out_of_range("Deque is empty");
}
frontIndex = (frontIndex + 1) % capacity;
--size;
}
void pop_back() {
if (size == 0) {
throw std::out_of_range("Deque is empty");
}
backIndex = (backIndex - 1 + capacity) % capacity;
--size;
}
3、get:获取某个位置的元素
对符号[]
重载来完成这个函数的功能
T& operator[](int index) {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of range");
}
return elements[(frontIndex + index) % capacity];
}
这里需要提一下,STL库中Deque有两种访问方式,一种是使用符号[]
,另一种是使用at()
区别在于遇到Index越界的情况
at()
会抛出异常,告诉我们下标越界了,而[]
不会,它会导致未定义行为
所以at()
更安全,但是效率比[]
低一些,需要看代码运行的具体任务进行取舍
4、size:获取队列长度
size_t getSize() const {
return size;
}
5、clear:清空队列
void clear() {
while (size > 0) {
pop_front();
}
}
其他函数
核心就是resize函数
void resize() {
size_t newCapacity = (capacity == 0) ? 1 : capacity * 2;
T* newElements = new T[newCapacity];
size_t index = frontIndex;
for (size_t i = 0; i < size; ++i) {
newElements[i] = elements[index];
index = (index + 1) % capacity;
}
delete[] elements;
elements = newElements;
capacity = newCapacity;
frontIndex = 0;
backIndex = size;
}
实际上和Vector中的分配方式基本一样,但是这里需要注意,resize后头尾指针会和真实的数组头尾对齐,这样会稍微规范一些
总结
Deque作为双向队列,底层实现与Vector几乎无异,但是Vector实际上是用一整块连续的内存,而Deque是使用分散的几个内存块,这使得Deque能够更加方便地去进行队头队尾的插入和删除。在需要对数据的中间和两头进行插入和删除时,Deque会是更好的选择
原文地址:https://blog.csdn.net/weixin_48013375/article/details/140695755
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!