笔 记 归 档

第一部分 数组

一、什么是数组


是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。

二、数组相比于容器的优劣


1)优势
  • 支持随机访问,根据下标访问的时间复杂度为 $O(1)$。
  • 相比容器,数组性能更高。
2)劣势
  • 低效的「插入」和「删除」

    在插入和删除某个数据时,会有数据的移动操作。

    插入操作时间复杂度为 $O(n)$。移动数据采取的技巧是,将插入数据移动到数组最后。

    删除操作时间复杂度为 $O(n)$。为了减少移动操作,可以直接记录哪个数据被删除,

    当数组中每隔更多的空间时,进行一次整体的数据删除。大大减少了数据搬移带来的时间损耗。

  • 数组的访问越界问题

    当访问的存储空间已经越界时,可能程序仍然能够运行,这样会造成未知的 bug。

    一般会用容器来替代。

Note:对于数组以及 c++ vector 容器的选择问题,对于业务开发,用容器即可。但是对于性能要求特别高的地方,或者追求简洁的表达方式。可以直接操作数组。但是要求自己分配申请内存和删除

继续阅读“笔 记 归 档”