C++容器:list

C++中的list是一个双向链表,也是一种序列容器,它可以在任何位置高效地插入和删除元素,支持正向迭代和反向迭代。在list中,每个元素保存在一个结点中,相邻的结点使用指针连接起来(前一个结点的后向指针指向后一个结点,后一个结点的前向指针指向前一个结点)。因此,要想找到位于第i个位置的元素,需要从第一个元素开始,顺着指针依次找下去,导致该操作的时间复杂度为O(n)。

C++容器:array

array是一个固定大小的序列容器,和vector相似,它使用连续的空间来保存元素。不同的是,它只能在定义的时候指定大小,而不能通过其它方式修改大小。除了保存的数据元素外,array中不保存任何数据(vector需要指针来保存其分配的空间的地址等信息)。

C++容器:vector

C++中的vector是一种像数组一样的序列容器,它使用连续的存储空间来保存元素。当需要保存的元素增多时,容器通过分配更多的空间来保存更多的元素。通常来说,vector不会在每次增加元素时都去重新分配内存,而是预先在尾部预留出一部分空间来容纳新放入的元素。对于随机访问以及在尾部增加或删除元素的操作,其效率是很高的。