[C++ 面试基础知识总结] 顺序容器[C++ 面试基础知识总结] 顺序容器

参考书籍：《c++ primer》

<a href="#c-%e9%9d%a2%e8%af%95%e5%9f%ba%e7%a1%80%e7%9f%a5%e8%af%86%e6%80%bb%e7%bb%93-%e9%a1%ba%e5%ba%8f%e5%ae%b9%e5%99%a8">c 面试基础知识总结 顺序容器</a>

<a href="#%e7%9b%ae%e5%bd%95">目录</a>

<a href="#%e9%a1%ba%e5%ba%8f%e5%ae%b9%e5%99%a8%e4%b8%8e%e9%80%89%e6%8b%a9">顺序容器与选择</a>

<a href="#%e8%bf%ad%e4%bb%a3%e5%99%a8">迭代器</a>

<a href="#%e5%ae%b9%e5%99%a8%e7%9a%84%e5%88%9d%e5%a7%8b%e5%8c%96%e5%92%8c%e8%b5%8b%e5%80%bc">容器的初始化和赋值</a>

<a href="#%e9%a1%ba%e5%ba%8f%e5%ae%b9%e5%99%a8%e6%93%8d%e4%bd%9c">顺序容器操作</a>

<a href="#%e6%b7%bb%e5%8a%a0%e5%85%83%e7%b4%a0">添加元素</a>

<a href="#%e8%ae%bf%e9%97%ae%e5%85%83%e7%b4%a0">访问元素</a>

<a href="#%e5%88%a0%e9%99%a4%e5%85%83%e7%b4%a0">删除元素</a>

<a href="#%e6%94%b9%e5%8f%98%e5%ae%b9%e5%99%a8%e5%a4%a7%e5%b0%8f">改变容器大小</a>

<a href="#%e8%bf%ad%e4%bb%a3%e5%99%a8%e5%a4%b1%e6%95%88">迭代器失效</a>

<a href="#vector%e5%af%b9%e8%b1%a1%e7%9a%84%e5%a2%9e%e9%95%bf">vector对象的增长</a>

<a href="#string-%e6%93%8d%e4%bd%9c">string 操作</a>

<a href="#%e6%94%b9%e5%8f%98string">改变string</a>

<a href="#%e6%90%9c%e7%b4%a2string">搜索string</a>

<a href="#%e6%95%b0%e5%80%bc%e8%bd%ac%e6%8d%a2">数值转换</a>

<a href="#%e5%ae%b9%e5%99%a8%e9%80%82%e9%85%8d%e5%99%a8">容器适配器</a>

<a href="#%e6%a0%88stack">栈stack</a>

<a href="#%e9%98%9f%e5%88%97queue">队列queue</a>

顺序容器类型：

vector 可变大小数组

deque 双端队列

list 双向链表

forward_list 单向链表

array 固定大小数组

string 专门用于保存字符的可变大小数组

选择容器的基本原则：

1.默认情况用vector

2.小元素多，空间额外开销重要的时候避免使用list或forward_list

3.要求随机访问元素时，用vector或deque

4.要求在容器中间插入或删除元素时，用list或forward_list

5.需要在头尾插入或删除元素，但不会在中间进行次操作时，用deque

复合使用：如果一个程序只有在读取输入时才需要在容器中间插入元素，随后需要随机访问元素，则可以在输入阶段使用list，一旦输入完成后，将list中的内容拷贝到一个vector中。

begin和end操作生成指向容器中第一个元素和尾元素之后位置的迭代器。除forward_list以外的顺序容器还支持按逆序寻址元素的迭代器<code>reverse_iterator</code>。采用rbegin和rend操作分别生成指向容器尾元素和收元素之前位置的迭代器。

创建一个容器为另一个容器的拷贝时，两个容器的类型和其存放的元素类型都必须匹配。用传递迭代器参数来拷贝一个范围时，就不要求容器类型是相同的了，容器中的元素类型也可以不同，只要是可以转换的即可。

array的大小也是类型的一部分，当定义一个array时，除了指定元素类型，还要指定容器大小。

进行赋值运算时，如果两个容器原来大小不等，则让两个容器的大小都与右边容器的原大小相等。

除array以外的顺序容器都支持assign，assign可以将右边运算对象的元素拷贝到左边运算对象中，也可以指定数目且具有相同给定值的元素替换容器中的原有元素。

注意：使用一个对象来初始化容器或将一个对象插入到容器时，实际上放入容器中的是对象值的一个拷贝，而不是对象本身。容器中的元素与提供值得对象之间没有任何关联！

访问容器中的元素的主要方法：解引迭代器，调用front,back函数，使用下标。

注意：如果容器为空，调用front,back函数会发生严重错误。在使用下标时需要保证给定下标在有效范围内，防止发生越界。在容器中访问成员函数返回的都是引用，如果容器是一个const对象，则返回值是const引用。如果容器不是const，则可以用返回值来改变元素的值。

注意：删除元素的函数都不会检查其参数，所以在删除元素之前，必须保证被删元素确实存在。

改变容器大小时，如果容器缩小，容器后部的元素会被删除，如果容器增大，会在容器后部添加新元素。

向容器中添加元素和从容器中删除元素的操作可能会使指向容器元素的指针，引用或迭代器失效。使用失效的指针，引用或迭代器是一种严重错误。当使用迭代器时，最好保证在每次改变容器的操作之后都正确地重新定位迭代器。

注意：end返回的迭代器很容易失效，不要保存end返回的迭代器。

在有些编程环境下运行最后一条语句，输出的v的容量也有可能是75，即系统自动为v重新分配的内存空间为原来的1.5倍。

string除了支持顺序容器的通用操作外，还支持一些其他的操作。

注意：substr和replace函数的开始位置不能超出string的长度，操作长度最大值为string长度与开始位置之差。

注意：搜索对大小写敏感！

除了顺序容器外，标准库还定义了3个顺序容器适配器:stack,queue和priority_queue。适配器可以接受一种已有的容器类型，使其行为看起来像一种不同的类型。所有适配器都要求容器具有添加，删除元素和访问尾元素的能力。所以array和<code>forward_list</code>无法用来构造适配器。

stack只需要实现添加，删除，访问尾元素操作，所以可以用vector，list，deque来构造，默认情况下stack是基于deque构造的。

栈的基本操作

queue需要实现添加尾元素，删除首元素，访问首尾元素操作，所以只能用list，deque来构造，默认情况下queue是基于deque构造的。

队列的基本操作

priority_queue与queue的区别在于<code>priority_queue</code>，需要实现的是队尾元素的添加删除和随机访问，所以只能用vector和deque进行构造，默认情况是用vector构造<code>priority_queue</code>。且<code>priority_queue</code>的元素是按优先级排序的（queue是按入队顺序），可用<code>q.top()</code>返回优先级最高的元素。