C++ 数据结构与算法

数组

常量数组

int arr[10] //长度为10， 但不能求值 arr[10]

特点: 内存是连续的，带来了一些优点和缺点：

优点:

1. 下标访问 O(1) arr[n] 与查找注意区分，查找复杂度是 O(n)
2. 末尾位置增加删除元素的时间复杂度是O(1) 指针-- 即可
3. 访问前后相邻的元素非常容易

缺点:

1. 非末尾元素插入时间复杂度 O(n)
2. 无序数组查找时间复杂度是 O(n)
3. 有序数组可以用二分查找，时间复杂度是O(logn)

数组扩容的消耗比较大

---

程序运行后生成一个进程，内存分为 .data, heap, stack, 堆上内存可以自己分配，stack 自动分配释放，.data 的内存整个程序的声明周期都不会被释放。因此要自己控制内存扩容就只能定义在堆上。

msvc以 1.5 倍扩容（即 floor(1.5*capability)），而 linux 是两倍

面试题：C++vector的动态扩容，为何是1.5倍或者是2倍_vector扩容1.5倍,2倍区别-CSDN博客

• vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度，相对于增长指定大小的O(n)时间复杂度更好。
• 为了防止申请内存的浪费，现在使用较多的有2倍与1.5倍的增长方式，而1.5倍的增长方式可以更好的实现对内存的重复利用。