电子商务网站建设参考文献书籍,江苏网站关键词优化优化,代注册公司要多少钱,网站群建设目标阅读导航 前言一、deque简介1. 概念2. 特点 二、deque使用1. 基本操作#xff08;增、删、查、改#xff09;2. 底层结构 三、deque的缺陷四、 为什么选择deque作为stack和queue的底层默认容器总结温馨提示 前言
文章绑定了VS平台下std::deque的源码#xff0c;大家可以下载… 阅读导航 前言一、deque简介1. 概念2. 特点 二、deque使用1. 基本操作增、删、查、改2. 底层结构 三、deque的缺陷四、 为什么选择deque作为stack和queue的底层默认容器总结温馨提示 前言
文章绑定了VS平台下std::deque的源码大家可以下载了解一下
前面我们讲了C语言的基础知识也了解了一些数据结构并且讲了有关C的命名空间的一些知识点以及关于C的缺省参数、函数重载引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ 以及学习了几个STL的结构也相信大家都掌握的不错接下来博主将会带领大家继续学习有关C比较重要的知识点—— dequeSTL。下面话不多说坐稳扶好咱们要开车了
一、deque简介
1. 概念
官方文档介绍
在C中deque双端队列是一种容器。deque是缩写形式表示double-ended queue即双向队列。deque是C标准库提供的一种方便、高效的双向队列容器提供了在两端进行插入和删除操作的能力同时支持随机访问。
2. 特点 双向访问deque允许在队列的两端进行插入和删除操作。这意味着你可以在队列的头部和尾部同时执行插入和删除操作而不仅仅限制在一端。 动态大小deque的大小是动态调整的它可以根据需要自动增加或减少。这使得deque能够灵活地应对不同的数据量和操作需求。 高效插入和删除与vector相比在deque的头部和尾部进行插入和删除操作的时间复杂度是常数时间O(1)。这意味着deque对于频繁的插入和删除操作非常高效。 随机访问与vector类似deque也支持随机访问。你可以使用索引来访问deque中的元素这使得deque在需要快速访问元素的情况下非常有用。 存储连续性deque在内部使用一系列分段的固定大小数组来存储元素。每个分段都具有连续的内存但这些分段之间不要求连续。这种内部结构使得deque能够提供高效的双向访问和动态大小调整。
二、deque使用
1. 基本操作增、删、查、改 插入元素 push_back(value): 在deque的尾部插入一个元素。push_front(value): 在deque的头部插入一个元素。 删除元素 pop_back(): 删除deque的尾部元素。pop_front(): 删除deque的头部元素。 访问元素 front(): 返回deque的头部元素的引用。back(): 返回deque的尾部元素的引用。 判断容器是否为空 empty(): 如果deque为空则返回true否则返回false。 获取容器的大小 size(): 返回deque中元素的个数。 清空容器 clear(): 删除deque中的所有元素使其变为空。 随机访问元素 at(index): 返回位于指定索引位置的元素的引用索引从0开始。operator[](index): 返回位于指定索引位置的元素的引用。
下面是一些使用deque的基本代码
#include iostream
#include dequeint main() {std::dequeint myDeque;// 插入元素myDeque.push_back(10);myDeque.push_front(5);// 访问元素std::cout Front element: myDeque.front() std::endl;std::cout Back element: myDeque.back() std::endl;// 删除元素myDeque.pop_back();myDeque.pop_front();// 判断容器是否为空if (myDeque.empty()) {std::cout Deque is empty std::endl;} else {std::cout Deque is not empty std::endl;}// 获取容器的大小std::cout Deque size: myDeque.size() std::endl;// 清空容器myDeque.clear();return 0;
}2. 底层结构
deque双端队列的底层结构通常由多个固定大小的缓冲区组成每个缓冲区是一个连续的存储块。这些缓冲区通过一个指向前一个缓冲区和一个指向后一个缓冲区的指针进行连接形成了一个双向链表。
deque的内部缓冲区以分块的形式存储元素。每个缓冲区有一个固定的大小它通常是2的幂次方例如512、1024等。缓冲区中的元素被存储在数组中以保持元素的连续性。
deque的双向链表由一个或多个缓冲区组成每个缓冲区都包含一个指向前一个缓冲区和一个指向后一个缓冲区的指针。第一个缓冲区的指向前一个缓冲区的指针为空指针最后一个缓冲区的指向后一个缓冲区的指针也为空指针。
当需要在deque的头部或尾部插入或删除元素时只涉及到相关缓冲区的操作而不会涉及其他缓冲区。这种设计使得deque的插入和删除操作时间复杂度为常数级别O(1)。 ⭕部分源代码(详细代码在文件里)
namespace program_queue
{
template class ContainerAllocator
struct DequeueProgramRequest_
{typedef DequeueProgramRequest_ContainerAllocator Type;DequeueProgramRequest_(): token(0), id(0) {}DequeueProgramRequest_(const ContainerAllocator _alloc): token(0), id(0) {(void)_alloc;}typedef uint64_t _token_type;_token_type token;typedef uint64_t _id_type;_id_type id;typedef boost::shared_ptr ::program_queue::DequeueProgramRequest_ContainerAllocator Ptr;typedef boost::shared_ptr ::program_queue::DequeueProgramRequest_ContainerAllocator const ConstPtr;}; // struct DequeueProgramRequest_
...............................三、deque的缺陷
⭕deque双端队列在大多数情况下是非常高效且灵活的数据结构但它也有一些缺点需要注意。 相对于vectordeque的内存占用更高deque的底层实现通常由多个固定大小的缓冲区组成。这导致deque在存储元素时可能需要更多的内存空间相对于vector而言。 不支持随机访问尽管deque支持常数时间的插入和删除操作但由于内部缓冲区是分块存储的因此对于deque而言随机访问的性能较差。在deque中进行随机访问需要根据元素的索引进行计算而不是直接通过指针操作。 迭代器的失效如果在deque中插入或删除元素会导致原始deque的迭代器失效。这意味着在操作之前获取的迭代器可能不再有效需要重新获取或使用新的迭代器。 对于大量元素的频繁插入和删除效率较低当大量元素需要在deque的中间位置插入或删除时由于涉及到内存的重分配和数据的移动deque的性能可能受到影响。 可能不利于缓存由于deque的底层实现包含多个不相邻的缓冲区这可能导致在连续访问元素时对CPU缓存的使用效率不高。
四、 为什么选择deque作为stack和queue的底层默认容器 高效的插入和删除操作deque支持在队列的前端和后端进行高效的插入和删除操作。这对于实现stack的后进先出LIFO语义和queue的先进先出FIFO语义非常重要。 避免元素移动相对于vector来说deque的插入和删除操作不会引起元素的移动。而对于vector当在前端插入或删除元素时需要将整个元素序列进行移动当在队列的末端插入或删除元素时除了移动元素还要考虑重新分配内存空间。这使得deque在插入和删除操作时更加高效。 动态大小调整deque支持动态大小调整可以根据需要自动增长或缩小存储空间。虽然这也是vector的特性但由于deque的内部实现不需要进行元素的移动所以在动态调整大小时deque的性能更好。 同时提供栈和队列功能由于deque既支持在队列的前端和后端进行插入和删除操作也提供了随机访问的能力因此可以同时满足栈和队列的需求。
⭕尽管deque有一些缺点但这些缺点相对于deque在栈和队列操作中的优势来说是可以接受的。总体而言deque作为stack和queue的底层默认容器是一个平衡性能和功能的选择。但是也可以根据具体需要选择其他容器来实现stack和queue例如vector或list这取决于具体的使用场景和需求。
总结
首先我们了解了deque的基本概念和特点包括多个固定大小的缓冲区、双向链表连接以及高效的插入和删除操作。接着我们深入探讨了deque的使用方法包括基本操作和底层结构。其中我们了解了如何进行增、删、查、改操作以及deque由多个缓冲区组成的底层实现结构。此外我们也提及了deque的一些缺陷如内存占用较高、随机访问效率较低等。最后我们解释了为何选择deque作为stack和queue的底层默认容器包括高效的插入和删除操作、避免元素移动、动态大小调整等优势。然而根据具体需求我们也可以选择其他容器来实现相同的功能。
⭕总的来说deque作为一种高效且灵活的数据结构在栈和队列的实现中发挥着重要作用。通过了解deque的特点和使用方法读者可以更好地理解和应用这一数据结构并在实际开发中做出明智的选择。无论是作为stack还是queue的底层容器deque在提供高效操作的同时也带来了一些缺陷因此需要根据具体的场景和需求来选择合适的数据结构。
温馨提示
感谢您对博主文章的关注与支持在阅读本篇文章的同时我们想提醒您留下您宝贵的意见和反馈。如果您喜欢这篇文章可以点赞、评论和分享给您的同学这将对我提供巨大的鼓励和支持。另外我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新不要错过任何精彩内容
再次感谢您的支持和关注。我们期待与您建立更紧密的互动共同探索C、算法和编程的奥秘。祝您生活愉快排便顺畅
