c++,可以大概讲一下关于vector、map的作用吗?

发布网友 发布时间：2022-04-12 13:39

我来回答

共1个回答

热心网友 时间：2022-04-12 15:09

1. Vector 动态数组

（1）vector有自动扩容操作，每次扩容伴随着“配置新空间 / 移动旧数据 / 释放旧空间”的操作，因此有一定时间成本。 
（2）vector提供了reserve接口，如果能够对元素个数有大概了解，可以一开始就分配合适的空间。 
（3）vector的内存空间是连续的，对插入元素的操作而言，在vector尾部插入才是合适的选择。维护的是一个连续线性空间，所以vector支持随机存取。 
（4）vector动态增加大小时，并不是在原空间之后持续新空间（无法保证原空间之后尚有可供配置的空间），而是以原大小的2倍另外配置一块较大的空间，接着将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。

2、vector与array的区别

vector与array非常相似。两者的唯一区别在于空间运用的灵活性。array是静态空间，一旦配置了就不能改变；vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助。

所采用的数据结构非常简单：线性连续空间。为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充，这便是容量的观念。增加新元素时，如果容量不足，则扩充至2倍（若原大小为0，则配置为1），2倍容量仍不足，就扩充至足够大的容量。

2.list特性

（1）相较于vector的连续线性空间，list就显得复杂许多。 
（2）它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。 
（3）对于任何位置的元素插入或元素移除，list永远是常数时间。 
（4）list不仅是一个双向链表，而且还是一个环状双向链表。它只需要一个指针便可完整表现整个链表。 
（5）插入操作和接合操作都不会造成原有的list迭代器失效，这在vector是不成立的。因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。 
（6）list不再能够像vector那样以普通指针作为迭代器，因为其节点不保证在储存空间中连续。list提供的是Bidirectional Iterators。

slist

slist与list的区别：

（1）STL list是双向链表，而slist是单向链表。 



（2）STL list的迭代器是双向的Bidirectional Iterator，而slist的迭代器是单向的Forward Iterator。 



（3）单向链表所耗用的空间更小，某些操作更快。 



（4）两者有一个共同特点：插入（insert）、删除（erase）、接合（splice）等操作不会造成原油迭代器的失效。（指向被移除元素的那个迭代器，在移除操作后肯定会失效）。 



（5）因为单链表只能往前迭代，所以很多操作都没有提供，即使提供了，也是非常低效的操作，需要从头结点开始遍历。



除了slist起点处附近的区域之外，在其他位置上采用insert或erase操作函数，都属不智之举，这便是slist相较于list的大缺点。 



（6）slist迭代器是单向的Forward Iterator，因此除了迭代器的基本操作之外，只实现了operator++操作。

deque

1、deque与vector的区别

（1）vector是单向开口的连续线性空间，用户只能在vector尾部进行插入删除操作（也允许在某个pos处插入，但由于vector的底层实现是数组，过多非队尾位置的插入会有性能上的消耗）。而deque是一种双向开口的连续线性空间，允许在头尾两端分别做插入和删除操作。

（2）deque允许在常数时间内对起头端进行元素的插入或移除操作。

（3）deque没有所谓容量概念。它是动态地用分段连续的空间组合而成，随时可以增加一段新的空间并连接起来。没有必要提供所谓的空间保留（reserve）功能。

（4）deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回，代价则是复杂的迭代器架构。

（5）既是分段连续线性空间，就必须有*控制，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐。deque的实现代码分量远比vector或list都多得多。所以，我们应尽可能选择vector而非deque。

2、deque的中控器

deque采用一块所谓的map（注意，不是STL的map容器）作为主控。这里所谓map是一小块连续空间，其中每个元素（此处称为一个节点，node）都是指针，指向另一段（较大的）连续线性空间，称为缓冲区。缓冲区才是deque的储存空间主体。SGI STL 允许我们指定缓冲区大小，默认值0表示将使用512 bytes 缓冲区。

总结：

（1）map是块连续空间，其内的每个元素都是一个指针，指向一块缓冲区。 



（2）进一步发现，map其实是一个T**,也就是说它是一个指针，所指之物又是一个指针，指向型别为T的一块空间。

3、deque的迭代器

deque是分段连续空间。维持其”整体连续”假象的任务，落在了迭代器的operator++和operator–两个运算子身上。

deque的迭代器应该具备什么结构： 
（1）它必须能够指出分段连续空间（亦即缓冲区）在哪里 
（2）它必须能够判断自己是否已经处于其所在缓冲区的边缘，如果是，一旦前进或后退就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map）。

所以在迭代器中需要定义：当前元素的指针，当前元素所在缓冲区的起始指针，当前元素所在缓冲区的尾指针，指向map中指向所在缓冲区地址的指针。

deque在效率上不如vector，因此有时候在对deque进行sort的时候，需要先将元素移到vector再进行sort，然后移回来。

4、deque的构造与内存管理

由于deque的设计思想就是由一块块的缓存区连接起来的，因此它的内存管理会比较复杂。插入的时候要考虑是否要跳转缓存区、是否要新建map节点（和vector一样，其实是重新分配一块空间给map，删除原来空间）、插入后元素是前面元素向前移动还是后面元素向后面移动（谁小移动谁）。而在删除元素的时候，考虑是将前面元素后移覆盖需要移除元素的地方还是后面元素前移覆盖（谁小移动谁）。移动完以后要析构冗余的元素，释放冗余的缓存区。

4.stack

stack是一种先进后出的数据结构，只有一个出口。允许新增元素、移除元素、取得最顶端元素。不允许有遍历行为。

在SGI STL的源码<stl_stack.h>的设计中，它是基于某种容器作为底部结构的，默认容器是deque容器，用户也可以自己指定容器的类型。

stack不提供走访功能，也不提供迭代器。

5.queue

queue是一种先进先出的数据结构。有两个出口，允许新增、移除元素、从最底端加入、取得最顶端元素。不允许遍历行为。

deque是双向队列，而queue是单向队列。

deque是双向开口的数据结构，若以deque为底部结构并封闭其底端出口和前端入口，便轻而易举的形成了一个queue。因此，SGI STL以deque作为缺省情况下的queue底部结构。

queue不提供遍历功能，也不提供迭代器。

map和multimap

map的特性： 
（1）所有元素都会根据元素的键值自动被排序。 
（2）map的所有元素都是pair，第一个值是键值，第二个是实值。 
（3）map不允许两个元素拥有相同的键值。 
（4）可以通过map的迭代器来改变元素的实值，但不可以改变键值，那样会违反元素的排列规则。 
（5）在客户端对map进行插入或删除操作后，之前的迭代器依然有效。当然，被删除的元素的迭代器是个例外。 
（6）它的底层机制是RB-tree。几乎所有的操作都只是转调用RB-tree的操作行为而已。

multimap和map几乎一样，唯一的区别是，multimap允许键值重复。因此map使用底层RB-tree的insert_unique()实现插入，而multimap插入采用的是RB-tree的insert_equal()而非insert_unique()。

hashtable

1、hashtable概述

hashtable可以提供对任意有名项的存取和删除操作，这种结构的用意在于提供常数时间的的基本操作，而不依赖于插入元素的随机性，是以统计为基础的。

散列函数（hash function）：负责将某一元素映射为一个”大小可接受之索引”。简而言之，就是将大数映射为小数。

使用hash function带来的问题：可能有不同元素映射到相同的位置（相同索引）。这便是碰撞或冲突问题。解决碰撞问题的方法：线性探测（linear probing），二次探测（quadratic probing），开链（separate chaining）等。stl hashtable采用的hash方式是开链法。

（1）线性探测：当hash function计算出某个元素的插入位置，而该位置空间不再可用时，怎么做?最简单的办法就是循序往下一一寻找，知道找到一个可用空间为止。

需要两个假设：a.表格足够大。b.每个元素都能够独立。

线性探测会造成主集团（primary clustering）问题：平均插入成本的成长幅度，远高于负载系数的成长幅度。

（2）二次探测：主要用来解决主集团问题。解决碰撞的方程式为F(i) = i^2。如果hash function计算出新元素的位置为H,而该位置实际上已被使用，那么就依次尝试H+1^2,H+2^2,H+3^2,H+4^2,….,H+i^2，而不像线性探测尝试的是H+1,H+2,H+3,H+4,….,H+i。

二次探测可以消除主集团，却可能造成次集团（secondary clustering）：两个元素经hash function计算出来的位置若相同，则插入时所探测的位置也相同，形成某种浪费。消除次集团的方法如复式散列。

（3）开链：这种做法是在每一个表格元素中维护一个list。hash function为我们分配某一个list，然后我们在哪个list身上执行元素的插入、搜寻、删除等操作。若list够短，速度还是够快。

使用开链法，表格的负载系数将大于1。SGI STL hashtable便采用的是开链法。

更多c++知识欢迎来我的博客：网页链接

追答