数据结构中常见容器原理分析

舒尹

摘 要：当今的网络世界中，数据日益增多，对数据的处理成为了至关重要的一环。各种各样的数据结构为数据处理提供了方便，而容器是其中用来缓存数据的重要工具，容器实现了对重复问题的固定解决方案。本文从数据结构入手介绍了线性表，散列表和树几种常用的数据结构。再对容器的概念做了详细说明，又对比了list，map等各式容器，最终给出了在不同情景下选择不同容器的建议。

关键词：数据结构;容器;散列表;map

中图分类号：R446 文献标识码：A 文章编号：1671-2064（2019）02-0036-02

1 数据结构

存储在计算机中的数据之间存在一定的联系，这种联系体现在数据之间所具备的逻辑关系，同时对应着数据在计算机中的存储结构。以上所述的数据间的联系就被称为数据结构。它包含：数据的逻辑结构和存储（物理）结构。

逻辑结构描述了数据元素间的逻辑关系，大致分为：线性结构和非线性结构[1]。线性结构是指数据元素之间存在一对一的关系，非线性结构则包含了一对多，多对多等关系。

数据的存储结构是逻辑结构在计算机中的具体表示（又称映像），其有顺序存储结构和链式存储结构两种类型。数据的逻辑结构独立于计算机，与数据的存储方式无关。而存储结构是在计算机内存中对逻辑结构的实现，是计算机用于处理数据的逻辑。

此外，数据操作也是数据结构的研究对象，不同的逻辑结构对应有不同的操作，这是由于数据的操作是定义在逻辑结构之上的。常用的操作主要有：访问元素，更新元素，插入元素，删除元素和排序元素等等。

数据结构的概念兴于上世纪七十年代，是随程序的结构设计而一起提出的。在设计程序时，先确定了数据结构后，往往算法也就随之确定了。或是反过来由特定的算法来确定合适的数据结构。前种情况中，数据结構是程序设计的关键，而不是算法，这种想法也包括了面向对象的程序设计思想。

下面介绍一些基本的数据结构：

线性表是数据结构中最基础的结构，它按存储结构的不同分为顺序表和链表两类[2]。

顺序表和链表都是顺序存放的数据元素的有限序列。不同的是，两者的线性逻辑结构是以不同存储结构来实现的。

顺序表中的数据元素存放在一组连续的内存中。而链表中的数据存储在内存上不连续的节点中，而每个节点都存在表示逻辑关系的标志，这种标志叫作指针[3]。由两者的存储特点可以看出：顺序表可以很方便地进行数据检索，而链表更加适应于数据的插入和删除，因为在插入或删除元素时，实质上是在操作元素的指针。

树结构是一种非线性结构，它是数据元素（在树中称为节点）按分支关系组织起来的结构，一棵树只有一个根节点，根节点没有前驱节点，其余每个节点有且只有一个前驱节点。大部分节点可以有一个或多个后继节点，而我们将没有后继节点的节点称为叶子节点。

散列表是一种映射结构。它可以根据键码（key）直接找到对应的值，从而进行访问[4]。这种以键一值的方式存储数据的结构，十分适用于数据的查找。用于查找的映射关系称为散列函数，用于存放值的顺序表称为散列表。其实，完全可以用字典来说明这种结构。比如，当我们用音节或偏旁去查找“中”字时，实际就是用一种键值映射去完成查找。“中”的字形或读音就是key，查阅的过程就是在索引，而最终查询到的页数以及“中”字的具体解释就是对应的值。

2 容器

容器仍是来源于数据结构的，某个特定容器的底层原理可能是由某种相关的数据结构实现的。由此可见，容器就是由数据结构提炼而来的产物，一个容器就是一种数据结构的实例。容器可以存储对象，而它自身仍是一个可被操作的对象，它被认为是一类对象的集合。简单来讲，容器就是存放对象的对象。但是，它自身包含处理其他对象的一类方法，实现了对重复问题的固定解决方案。

容器的一大优点是它可以自动扩展。可以自行管理和分配内存空间的容器能解决这样的问题，设置对象时，我们不需要预先知道对象占用内存的大小，只需要创建一个合适的容器对象，调用对应的操作方法，容器会自行考虑完成其中的处理细节。也就是说，当你发出指令时，容器会自动申请内存，并采用最优化的算法去执行指令。

在说到容器时，更容易想到的是生活中各种实体。比如装水的杯子，放杂物的收纳盒等等。一个旅行箱中可以放置许多衣物，衣物视作对象，那么旅行箱也可视作对象。更极端一点，大旅行箱中放一个小旅行箱的情况即容器之中存放容器的情况也是存在的。

在书写程序时，不同的场景下选择不同的容器对数据进行缓存，很大程度上影响着程序运行的时间和性能。按容器中元素的组织方式，可把容器分为顺序容器和关联容器两大类。

顺序容器是一种线性表，它将相同类型的元素以严格的顺序关系进行组织。顺序容器中的元素有固定的位置，这个位置不因元素的改变而改变，除非用插入或删除的操作来改变这个位置。在操作元素时，操作的逻辑顺序直接成为元素的存储顺序，即两者之间是相互对应的。

关联容器属于一种非线性的树结构。元素存入不会保留操作时的逻辑顺序，但关联容器可以根据元素的特点对元素进行排序。此外，关联容器的显著特点是它以键值形式进行存储，在这一点上，可以认为顺序容器只保留键或值的一种。

List的底层是由线性表实现的。比如在由链表实现的list中，数据是以节点的形式构成的，一个节点包括实际存储的数据，一个前驱和后驱指针。因为在物理内存中，其存储是不连续的，所以list不需要给它分配特定大小的内存，它可以任意的进行扩展。由于其结构特点，list进行数据的检索时需要对其进行顺序访问，那么当数据量很大时，随机检索的性能就变得很差了，越是在list中靠后的数据将要进行检索的时间就越长。虽然检索的性能不高，但链表结构的list适用于数据的插入和删除。在插入或删除节点时，指仅仅最多对三个元素有影响，提高了操作的效率。

Vector相当于一个数组，但又不只是一个数组。数组是静态的，数组的空间在分配之后一般不能改变，如果原有的空间满足不了需求，就只能重新申请更大的数组，然后把原数据拷贝到新的数组之中。而Vector是一个动态数组，它会自行分配内存空间，也就是说，Vector自行完成了上述在面对空间不够时，重新申请空间然后拷贝数据的过程。容器自动扩展的特点得以体现。但这并不意味着在数据量很大时，自行扩展的Vector效率就高，它的性能仍是很糟糕的，所以它通常会预留一部分空间，且预留空间是以一定比例增长的。另一方面，Vector中的数据是连续存储在内存中的，它可以方便的进行随机访问。同时由于Vector底层是由顺序表实现的，一般只能在Vector的尾部进行追加和删除。

Vector和list同为顺序容器，将两者进行对比是很有必要的;

Vector是一段连续存储数据，而链表实现的list是将所有的元素分开进行保存的，在使用时，用Vector进行随机检索的性能很好，在Vector尾部追加数据的性能也不错，除非需要重新申请内存。而链表list中元素可以不连续，使用指针使它适用于插入，删除元素而不适合进行查询。

所以，如果需要高效率的任意存取，就选择Vector，如果需要频繁的插入或删除元素而随机存取不那么重要时，就选择list。

另外还有一种介于两者之间的容器--deque，它兼顾了两者的优点，它的查询和插入/删除的性能是介于两者之间的，适用于即需要随机存取又有较频繁的插入，删除的情况。

Map和Set属于关联容器，都为非线性的树结构。

Set又称集合，为一组元素的集合，但储存的元素的值是唯一的，且元素是有一定的顺序的，同时也把集合中的一个元素叫做集合的实例。Map（映射）提供了”键-值“关系储存数据的方式。Map的每一个元素都由两部分组成，其中的键（key）在容器中不允许重复，且是经过排序的。

以下为更具体的说明：

Set，Map封装了一种二叉树的结构，它的插入删除效率一般较高，它们中的数据以节点存储，与链表相似，插入时只需将指针指向新的节点，而不需要移动和拷贝内存。另外，Set和Map的查找效率是较高的，它们采用的是二分查找的方式，当数据元素增加时，查找的效率并不会大幅的降低，要解释这个现象就需要理解其中具体的实现原理。简单来讲，查找的效率同以2为底的对数函数，即使数据量（自变量）增加的幅度很大，查找的时间（函数值）并不明显增加。

3 容器总结

在插入和删除元素时，关联容器是快于Vector而慢于list的。Vector是顺序结构而关联容器与list同为链式结构，但list是线性的。在改变元素时，关联容器涉及更多元素的改变，且还需对改变后的元素进行排序，这使其性能降低。

关联容器的查找比Vector慢，但比list快很多。Vector采用顺序结构，关联容器自然無法相比，但二分查找的方式又是大大优于list的，且数据越多，优越性越明显。

Map提供了一种重要的存储数据的方式，即以“键-值”关系进行存储。索引元素时，它用字符型的关键字进行索引，类似于数组中以下标的方式来索引元素，这是其他容器无法取代的。

在不同的情况下，要选择适合的容器。一般而言，list适用于大量插入和删除元素的情况，vector更适合用于大量数据的随机读取，map提供了“键—值”映射，十分适用于数据的查询。

4 结语

通过以上的探究，不难看出，容器的选择对编程的效率有着长远的影响。容器相当于处理一类事物的方法，方法选对后，后续的工作才会事半功倍。生活需面临的各种问题也是这样，以一个好的方法开始，往往结果才会以我们想要的方式出现。

参考文献

[1] 王立柱，王春枝.C/C++与数据结构[M].清华大学出版社，2016.

[2] 欧建圣.线性表在《数据结构》中重要性分析[J].武汉工程职业技术学院学报，2001，13（1）：64-66.

[3] 赵玉勇，刘凤亮.VB中用类模块实现栈和链表数据结构[J].中文信息，2002（5）：64-66.

[4] 马如林，蒋华，张庆霞.一种哈希表快速查找的改进方法[J].计算机工程与科学，2008，30（9）：66-68.