如何实现随机访问？

数组的特点:

• 是线性表

• 非线性表举例

• 连续的内存空间
• 相同类型的数据

连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。

实现根据下标随机访问数组元素的方法:

当计算机需要随机访问数组中的某个元素时，它会首先通过下面的寻址公式，计算出该元素存储的内存地址：

• 随机访问的复杂度是 O(1)

a[i]_address = base_address + i * data_type_size

低效的“插入”和“删除”

插入操作

如果要保持有序:

• O(n)

没有顺序要求:

• 可以将原第 k 个元素放到最后
• O(1)

删除操作

• 平均 O(n)

优化:

• 先标记为删除
• 存储空间不足时才移动

警惕数组的访问越界问题

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

数组越界在 C 语言中是一种未决行为，并没有规定数组访问越界时编译器应该如何处理。因为，访问数组的本质就是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，那么程序就可能不会报任何错误。

容器能否完全替代数组？

对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。