`
kongweile
  • 浏览: 517543 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

deque内部实现原理

 
阅读更多

deque的元素数据采用分块的线性结构进行存储,如图所示。deque分成若干线性存储块,称为deque块。块的大小一般为512个字节,元素的数据类型所占用的字节数,决定了每个deque块可容纳的元素个数。

所有的deque块使用一个Map块进行管理,每个Map数据项记录各个deque块的首地址Mapdeque的中心部件,将先于deque块,依照deque元素的个数计算出deque块数,作为Map块的数据项数,创建出Map块。以后,每创建一个deque块,都将deque块的首地址存入Map的相应数据项中。

Mapdeque块的结构之下,deque使用了两个迭代器M_startM_finish,对首个deque块和末deque块进行控制访问。迭代器iterator共有4个变量域,包括M_firstM_lastM_curM_nodeM_node存放当前deque块的Map数据项地址,M_firstM_last分别存放该deque块的首尾元素的地

址(M_last实际存放的是deque块的末尾字节的地址),M_cur则存放当前访问的deque双端队列的元素地址。

转:http://hi.baidu.com/hins_pan/blog/item/da4d0c35c8fbdc54241f143b.html

分享到:
评论

相关推荐

    Deque:使用C ++实现数据结构Deque的实现

    双端队列(Deque,全称Double Ended Queue)是一种线性数据结构,它...通过自定义实现,我们可以深入理解数据结构的工作原理,这在理解和优化代码性能方面非常有价值。同时,测试示例是验证正确性和性能的重要步骤。

    SGI STL deque相关代码

    本篇文章将深入探讨`deque`的实现原理、特性以及相关的编程实践。 `deque`,全称Double Ended Queue,其设计灵感来源于线性数据结构——数组和链表的结合体。与`vector`类似,`deque`内部也是通过动态分配内存来...

    源码解析jdk7.0集合:LinkedList的底层实现原理.pdf

    在深入分析JDK 7.0中LinkedList集合的底层实现原理前,我们首先需要了解LinkedList的基本概念。LinkedList,即双向链表,是一种通过双向指针相互连接的数据结构,每个节点包含数据域以及指向前驱和后继节点的指针。...

    vector和deque使用方法.doc

    在实验报告"vector和deque使用方法"中,我们将深入探讨这两种容器的用法、实现原理以及它们的优缺点。 **1. `vector`容器** `vector`是一种动态数组,它允许在任何位置插入和删除元素。在`vector`中,元素是连续...

    vc++中队列deque和queue的使用

    通常,`queue`会基于另一种容器(如`deque`或`list`)来实现其内部操作。默认情况下,`queue`使用`deque`作为底层容器。`queue`的主要操作包括: - `push()`:在队尾添加元素。 - `pop()`:移除并返回队头的元素。 -...

    STL(SGI)模板实现详解

    1. 容器:容器是一些可以存储数据的对象,如vector(动态数组)、list(双向链表)、deque(双端队列)、set(红黑树实现的集合)和map(关联数组)。它们提供了不同的数据结构和操作,以适应不同场景的需求。 2. ...

    java软件技术文档-深入java8的集合2:LinkedList的实现原理.pdf

    《深入Java8的集合2:LinkedList的实现原理》 LinkedList是Java编程语言...理解其内部结构和实现原理对于优化代码性能和解决并发问题至关重要。在实际开发中,根据具体需求选择适合的集合类型,是提高程序效率的关键。

    P189~196C++string学习笔记.docx

    这是因为 deque 容器内部实现的缘故。 deque 容器的构造函数有三种形式:默认构造形式、以区间构造形式和以元素个数构造形式。其中,构造函数将 [beg, end) 区间中的元素拷贝给本身,或者将 n 个 elem 拷贝给本身。...

    Java LinkedList的实现原理图文详解

    Java LinkedList 的实现原理图文详解 Java LinkedList 是一个通过双向链表实现的 List 和 Deque 接口,它允许插入所有元素,包括 null,并且它是线程不同步的。如果对双向链表这个数据结构很熟悉的话,学习 ...

    数据结构-用双端队列实现栈

    数据结构是计算机科学中的核心概念,它涉及到如何高效地存储和操作数据。在这个主题中,我们将探讨如何使用双端队列(deque...通过深入理解这些数据结构和容器的内部工作原理,开发者能够更好地设计和优化他们的代码。

    STL_C++stl实现_

    `map`内部实现为红黑树,提供O(log n)的时间复杂度进行插入、删除和查找操作。在这个压缩包中,`mapA`和`mapB`可能是两种不同实现或不同版本的`map`容器。 3. **deque**:双端队列(deque)是另一种容器,允许在两...

    java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf

    在 Java 中,LinkedList 的内部使用双端链表队列原理实现,而 ArrayList 的内部使用双端数组队列原理实现。 Java 实现自定义双端队列可以通过链表和数组两种方式实现,双端队列可以充当单端队列,也可以用于充当栈...

    C++开源项目:模拟实现小型STL

    本开源项目旨在模拟实现一个小型STL,帮助开发者更深入地理解STL的工作原理和设计思想。下面我们将详细探讨其中涉及的知识点。 1. **容器**:STL中的容器是用来存储数据的对象,如`vector`、`deque`、`list`、`set`...

    Custom-DeQue

    【Custom-DeQue】是一个基于C#编程...通过Custom-DeQue项目,开发者可以深入理解数据结构的实现原理,并将其应用到实际问题中。对于学习C#和数据结构的人来说,这是一个很好的实践案例,有助于提升编程能力和算法理解。

    C++标准模板库源代码

    通过研究这些源代码,你可以深入了解C++ STL的工作原理,学习如何高效地管理内存,理解各种数据结构的内部实现,以及如何利用这些工具解决实际问题。此外,你还可以看到C++模板机制的运用,这是C++中强大的泛型编程...

    stl容器.zip

    与vector相比,deque内部实现为多个块,因此随机访问性能稍逊,但在两端操作时更优。 - **list**:双向链表,元素在内存中不连续,支持高效的插入和删除操作,但随机访问性能较差。 2. **关联容器**: - **set**...

    队列,数据结构,c++实现,自创

    `std::queue`是C++标准库的一部分,它提供了对队列操作的基本接口,但内部实现可以是不同的容器,如`std::deque`或`std::list`。然而,为了更好地理解队列的工作原理,我们可以选择自创一个队列。 自创队列时,我们...

    数据结构与算法(C++实现).rar

    通过这个压缩包,学习者可以深入理解数据结构和算法的内部工作原理,通过C++代码实现加深对概念的理解。此外,还可以学习如何测试和调试这些代码,这对于提升编程技能和解决实际问题能力大有裨益。无论是初学者还是...

    演示Sequence容器vector

    本篇文章将专注于一种重要的Sequence容器——`vector`,并探讨其与其他Sequence容器如`list`和`deque`的使用、性能差异以及内部实现原理。 首先,`vector`是一种动态数组,它支持随机访问和连续存储。在构造`vector...

    list,queue 纯C语言 简洁实现

    总的来说,这份压缩包包含的"list"和"queue"源代码为学习者提供了一次宝贵的实践机会,可以深入理解链表和队列的内部工作原理,同时也可以在不同的C/C++编译环境下验证其兼容性和效率。无论是初学者还是经验丰富的...

Global site tag (gtag.js) - Google Analytics