logo资料库

C++ 顺序容器基础知识总结.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.53M 资料格式：pdf 举报 版权申诉
第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
资料共10页，剩余部分请下载后查看
    C++ 顺序容器基础知识总结 正文 0.前言 回到顶部 本文简单地总结了STL的顺序容器的知识点。文中并不涉及具体的实现技巧，对于细节的东 西也没有提及。一来不同的标准库有着不同的实现，二来关于具体实现《STL源码剖析》已 经展示得全面细致。所以本文仅仅是对容器基础知识的归纳。至于容器提供的接口与使用实 例，建议查取官方文档。文章难免有错漏，希望指出。 1.容器概论 回到顶部 容器，置物之所也。像桶可装水，碗可盛汤，C++的容器，可以存储对象。容器有多种， 用来处理不同的元素操作诉求。按照元素存储到容器中以及访问方式的差异，容器分为顺序 容器与关联容器。顺序容器也称为序列式容器。序列式容器按元素插入的顺序存储元素，这 些元素可以进行排序，但未必是有序的。C++本身内置了一个序列式容器array（数组）， STL另外提供了vector,list,forward_list,deque,stack,queue,priority­queue，string 等等序列式容器。所有的容器都是基于模板实现的，因为容器必须保证能装得下各种各样的 类型。其中，stack，queue都是基于deque来实现的，priority­queue基于heap来实 现，从技术上来说它们属于容器适配器（adapter）。其中array与forward_list是 C++11添加的新容器类型。 回到顶部 2.std::array 2.1.底层数据结构 array的底层数据结构是固定数组。与C­style的数组类似，它的大小在定义后就不能被改 变。由于array具有固定的大小，它不支持添加和删除元素或改变容器大小等其他容器拥有 的操作。在定义一个array容器的时候必须指定大小： Defined in header  template<     class T,     std::size_t N > struct array; 2.2.内存分配策略
    在内存分配策略上，array也与C­style数组类似。编译器在哪里为array分配内存，取决于 array定义的位置和方式。 若作为函数的局部对象，则将从栈上获得内存，与之对比是的vector，vector 底层数据结构是动态数组，从自由存储区上分配内存： 若使用new操作符分配内存，则是在自由存储区上分配内存。 若作为全局变量或局部静态变量，则是在全局/静态存储区上分配的内存。 例如，在函数定义的array局部对象在栈上分配内存，与此对比的是vector，它底层数据结 构为动态数组，因此在自由存储区上分配内存： #include  #include  #include    using namespace std;   int main() {     int stack_var;     array a;     vector b(5);       cout << "stack area: 0x" << hex << (uintptr_t)&stack_var << endl;     cout << "a[3] address: 0x" << hex << (uintptr_t)&a[3] << endl;     cout << "b[3] address: 0x" << hex << (uintptr_t)&b[3] << endl;       getchar();     return 0; } 结果： 2.3.array的优势在哪 array比数组更安全。它提供了opeartor[]与at()成员函数，后者将进行数组越 界检查。 与其他容器相似，array也有自己的迭代器，因此array能够更好地与标准算法 库结合起来。 通过array::swap函数，可以实现线性时间内的两个数组内容的交换。
    另外，不像C­style数组，array容器类型的名称不会自动转换为指针。对于C++程序员来 说，array要比C­style数组更好用。 回到顶部 3.forward_list 3.1.底层数据结构 forward_list的底层数据结构为单向链表。如C++标准所讲，forward_list容器支持前向 遍历元素序列，允许常数时间内在任意位置的插入或删除操作并进行自动的内存管理。与 list的主要区别是forward_list没有反方向的迭代器，不过也正因如此，forward_list的每 个节点都节省了迭代器大小的开销，在元素众多的时候，将比list消耗少得多的内存。 受单向链表这种特殊结构的影响，forward_list在很多地方表现得和其他容器不同： 3.2.forward_list特殊之一：forward_list不提供返回 其大小的操作。 在所有已知的STL容器中，forward_list是唯一一个不提供size()的容器。不提供的原因 在于计算一个forward_list的长度需要线性的时间，库用户有时无法忍受这样的时间开销。 其他容器提供的size()操作皆可以在常数时间内完成（在C++98时，list也是线性时间）。 为了节省内存，forward_list甚至不跟踪序列的长度，要想获得某个forward_list对象的长 度，用户需要通过distance()来计算。这带来了一些不便，但使得用户远离了size()带来的 高消耗。每个容器类型都有三个与大小相关的操作：max_size(),empty(),size(),而 forward_list只提供了前两个。 int main() {     forward_list flist;     for (int i = 0; i < 10; i++)     {         flist.push_front(i);     }     std::cout << std::distance(flist.begin(), flist.end()); //输出10      getchar(); } 3.3.forward_list特殊之二：forward_list是唯一一个 在给定位置之后插入新元素的容器。 为此，forward_list提供了如下的插入接口： 接口 描述 insert_after 在给定位置之后插入新元素
    emplace_after erase_after splice_after 在给定位置之后构造新元素 删除给定位置之后的元素 将另一个forward_list的元素移动到本 forward_list的指定位置之后 其他所有STL容器都是在指定位置之前插入元素（除了std::array，它不允许插入）。 forward_list的这种特殊处理，还是出于效率的考虑。对于单链表我们应该很熟悉，为了在 某个指定节点之前插入插入节点，我们必须改变插入位置的前一个节点的指向。换句话说， 为了在指定节点之前插入新元素，我们必须要先获得插入位置前一个位置的节点，为了获取 前面这个节点，需要线性的操作时间。 而如果我们是在指定位置之后插入新元素，则无需线性时间的查找操作，这样可实现常数时 间的插入： 同样的，处于性能的考虑，forward_list没有提供在尾部进行操作的接口，包括 push_back(),pop_back()和emplace_back(),这些操作对单列表来说都至少要花费 O(n)来完成。 3.4.迭代器失效问题 指向被删除元素的迭代器，在删除之后失效。 4.list 回到顶部
    4.1.底层数据结构 list同样是一个模板类，它底层数据结构为双向循环链表。因此，它支持任意位置常数时间 的插入/删除操作，不支持快速随机访问。 4.2.迭代器类型 list的迭代器具备前移、后移的能力，所以list提供的是Bidirectional iterator(双向迭代 器)。由于采用的是双向迭代器，自然也很方便在指定元素之前插入新节点，所以list很正常 地提供了insert()操作与push_back()/pop_back()操作。在C++11中，list新增了三个 接口，以支持在指定位置构造对象后插入容器中: 接口（C++11新增） 描述 emplace 在指定位置之前插入新构造的元素 emplace_front 在链表头插入新构造的元素 emplace_back 在链表尾插入新构造的元素 4.3.内存分配策略 list的空间配置策略，自然是像我们普通双向链表那样，有多少元素申请多少内存。它不像 vactor那样需要预留空间供新元素的分配，也不会因找不到连续的空间而引起整个容器的 内存迁移。 4.4.迭代器失效问题 list 有一个重要性质：插入操作（insert）与接合操作（splice）都不会造成原有的list迭代 器失效。这在vector是不成立的，因为vactor的插入可能引起空间的重新配置，导致原来 的迭代器全部失效。list的迭代器失效，只会出现在删除的时候，指向删除元素的那个迭代 器在删除后失效。 通常来说，forward_list在使用灵活度上比不上list，因为它只能单向迭代元素，且提供的 接口没有list多。然而，在内存的使用上，它是比list占优势的。当对内存的要求占首要位置 时，应该选择forward_list。 回到顶部 5.vector 5.1.底层数据结构 vector的底层数据结构是动态数组，因此，vector的数据安排以及操作方式与std::array 十很相似，它们间的唯一差别在于对空间的运用灵活性上。array为静态数组，有着静态数 组最大的缺点：每次只能分配一定大小的存储空间，当有新元素插入时，要经历 “找到更大 的内存空间”­>“把数据复制到新空间” ­>“销毁旧空间” 三部曲， 对于std::array而言，这
    种空间管理的任务压在使用它的用户身上，用户必须把握好数据的数量，尽量在第一次分配 时就给数据分配合理的空间（这有时很难做到），以防止“三部曲”带来的代价，而数据溢出 也是静态数组使用者需要注意的问题。而vector用户不需要亲自处理空间运用问题。 vector是动态空间，随着新元素的插入，旧存储空间不够用时，vector内部机制会自行扩 充空间以容纳新元素，当然，这种空间扩充大部分情况下（几乎是）也逃脱不了“三部曲”， 只是不需要用户自己处理，而且vector处理得更加安全高效。vector的实现技术关键就在 于对其大小的控制以及重新配置时数据移动效率。 5.2.迭代器类型 对于C_style数组，我们使用普通指针就可以对数组进行各种操作。vector维护的是一个连 续线性空间，与数组一样，所以无论其元素型别为何，普通指针都可以作为vector的迭代 器而满足所有必要的条件。vector所需要的迭代器操作，包括operator*,operator­ >,operator++,operator­­,operator+=,operator­=等，普通指针都具有。因此，普通 指针即可满足vector对迭代器的需求。所以，vector提供了Random Access  Iterators。 5.3.内存分配策略 标准库的实现者使用了这样的内存分配策略：以最小的代价连续存储元素。为了使vector 容器实现快速的内存分配，其实际分配的容量要比当前所需的空间多一些(预留空间)， vector容器预留了这些额外的存储区用于存放添加的新元素，于是不必为每个新元素进行 一次内存分配。当继续向容器中加入元素导致备用空间被用光（超过了容量 capacity）， 此时再加入元素时vector的内存管理机制便会扩充容量至两倍，如果两倍容量仍不足，就 扩张至足够大的容量。容量扩张必须经历“重新配置、元素移动、释放原空间”这个浩大的工 程。按照《STL源码剖析》中提供的vector源码，vector的内存配置原则为： 如果vector原大小为0，则配置1，也即一个元素的大小。 如果原大小不为0，则配置原大小的两倍。 当然，vector的每种实现都可以自由地选择自己的内存分配策略，分配多少内存取决于其 实现方式，不同的库采用不同的分配策略。 5.4.迭代器失效问题 1. vector管理的是连续的内存空间，在容器中插入（或删除）元素时，插入（或删 除）点后面的所有元素都需要向后（或向前）移动一个位置，指向发生移动的元素的 迭代器都失效。这里以插入操作示例：
    1. 随着元素的插入，原来分配的连续内存空间已经不够且无法在原地拓展新的内存 空间，整个容器会被copy到另外一块内存上，此时指向原来容器元素的所有迭代器 通通失效。 1. 删除元素后，指向被删除元素的迭代器失效，这是显而易见的。 回到顶部 6.deque 6.1.底层数据结构 vector是单向开口的线性连续空间，deque则是一种双向开口的连续数据空间。所谓的双 向开口，意思是可以在头尾两端分别做元素的插入和删除操作。当然vector也可以在头尾 两端进行操作，但是其头部操作效果奇差，所以标准库没有为vector提供push_front或 pop_front操作。与vector类似，deque支持元素的快速随机访问。deque的示意图如 下：
    现在问题来了：如果deque以数组来实现，如何做到在头部的常数时间插入？如果是采用 链表来实现，又如何做到快速随机访问？deque的内部数据结构到底如何？想必你已经猜 到了，要实现如上需求，需要由一段一段的连续空间链接起来的数据结构才能满足。 6.2.内存分配策略 接着上面讲。deque由一段一段的连续空间所链接而成，一旦需要在deque的前端或尾端 增加新空间，便配置一段定量的连续空间，并将该空间串接在deque的头部或尾部。 deque复杂的迭代器架构，构建出了所有分段连续空间”整体连续“的假象。 既然deque是由一段一段定长的连续空间所构成，就需要有结构来管理这些连续空间。 deque采用一块map（非STL中的map）作为主控，map是一块小的连续空间，其中每个 元素都是指针，指向一块较大的线性连续空间，称为缓冲区。而缓冲区才是存储deque元 素的空间主体。示例图： map本身也是一块固定大小的连续空间，当缓冲区数量增多，map容不下更多的指针时， deque会寻找一块新的空间来作为map。 6.3.deque的迭代器 为了使得这些分段的连续空间看起来像是一个整体，deque的迭代器必须有这样的能力： 它必须能够指出分段连续空间在哪里，判断自己所指的位置是否位于某一个缓冲区的边缘， 如果位于边缘，则执行operator­­ 或operator++时要能够自动跳到下一个缓冲区。因 此，尽管deque的迭代器也是Ramdon Access Iterator 迭代器，但它的实现要比 vector的复杂太多。SGI版本的STL deque实现思路可以看侯捷的《STL源码剖析》。 6.4.迭代器失效问题 在deque容器首部或者尾部插入元素不会使得任何迭代器失效。 在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料