线性表 - 数组

数组由于是紧凑连续存储，可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。

• 但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容， 要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)。
• 数组中间进行插入或删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

• 线性表 - 数组
• C++ 数组 array 和vector 间的联系和区别
  • 相同点
  • 不同点
• 数组与链表对比

C++ 数组 array 和vector 间的联系和区别

相同点

1. 都和数组类似，都可以使用标准数组的表示方法来访问每个元素；array和vector都针对下标运算符[]进行了重载
2. 三者的存储都是使用的连续内存，都可以进行随机访问；在array和vector的底层存储结构均使用数组。

不同点

技术	数组	array	vector
容量	定长容量，定义后的空间是固定的，不能进行改变	定长容量，定义后的空间是固定的，不能进行改变	变长容器，提供了可以动态插入和删除元素的机制，可以根据数据的 插入删除重新构建容器容量（1.5-2倍），即可以进行再加或减。
元素数量	定义的时候必须定义数组的元素个数	定义的时候必须定义数组的元素个数	不需要预先定义数量
数据访问	只能通过下标访问，更容易引发访问错误	提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，访问更加安全	提供了更好的数据访问机制，即可以使用front()和back()以及at()（at()可以避免a[-1]访问越界的问题）访问方式，访问更加安全
内容交换	只能通过遍历的方式，逐个元素交换的方式使用	两个容器对象的内容交换，即swap的机制	两个容器对象的内容交换，即swap的机制
容量获取	只能通过sizeof()/strlen()以及遍历计数来获取大小和是否为空	提供了size()和Empty()的获取机制	提供了size()和Empty()的获取机制
遍历机制	开箱即用的中台前端/设计解决方案	提供了更好的遍历机制，即有正向迭代器和反向迭代器两种	提供了更好的遍历机制，即有正向迭代器和反向迭代器两种
安全性	不安全的	比较安全的（有效的避免越界等问题）	比较安全的（有效的避免越界等问题）
内存使用	用new[ ]/malloc申请的空间，必须用对应的delete[ ]和free来释放内存	在声明周期完成后，会自动地释放其所占用的内存	在声明周期完成后，会自动地释放其所占用的内存
元素添加	数组一经定义就不允许添加新元素；若需要则要充许分配新的内存空间，再将员数组的元素赋值到新的内存空间。	数组一经定义就不允许添加新元素；若需要则要充许分配新的内存空间，再将员数组的元素赋值到新的内存空间。	vector有一系列的函数操作，非常方便使用

数组与链表对比

1. 数组由于是紧凑连续存储，可以随机访问， 通过索引快速找到对应元素，而且相对节约存储空间。

   • 但正因为连续存储， 内存空间必须一次性分配够， 所以说数组如果要扩容， 需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)。

   • 数组中间进行插入或删除，每次必须搬移后面的所有数据以保持连续， 时间复杂度 O(N)。

2. 链表因为元素不连续， 而是靠指针指向下一个元素的位置， 所以不存在数组的扩容问题。

   • 根据某个元素的前驱和后驱， 操作指针即可删除该元素或插入新元素， 时间复杂度 O(1)。

• 存储空间不连续，无法根据索引算出对应元素的地址，索引不能随机访问；
• 每个元素必须存储指向前后元素位置的指针， 会消耗相对更多的储存空间。