面试中经常会被问到的这个问题,所以顺道在这里去总结一下:
首先
list
1. list是由双向链表实现的,因此内存空间是不连续的。
2. 只能通过指针访问数据,所以list的随机存取非常没有效率,时间复杂度为o(n);
3. 但由于链表的特点,能高效地进行插入和删除。
vector
1. vector和数组类似,拥有一段连续的内存空间,并且起始地址不变。
因此能高效的进行随机存取,时间复杂度为o(1);
2. 但因为内存空间是连续的,所以在进行插入和删除操作时,会造成内存块的拷贝,时间复杂度为o(n)。
另外,当数组中内存空间不够时,会重新申请一块内存空间并进行内存拷贝。
区别为:
STL中,容器vector和list都可以用来存放一组类型相同的数据。不同于数组的一点是,他们都支持动态增长。不同点为:
(1) vector是顺序表,表示的是一块连续的内存,元素被顺序存储;list是双向连接表,在内存中不一定连续。
(2)当数值内存不够时,vector会重新申请一块足够大的连续内存,把原来的数据拷贝到新的内存里面;list因为不用考虑内存的连续,因此新增开销比vector小。
(3)list只能通过指针访问元素,随机访问元素的效 率特别低,在需要频繁随机存取元素时,使用vector更加合适。
(4)当向vector插入或者删除一个元素时,需要复制移动待插入元素右边的所有元素;因此在有频繁插入删除操作时,使用list更加合适。
总结:
需要高效的随机存取,而不在乎插入和删除的效率,使用vector;
如果需要大量的插入和删除,而不关心随机存取,则应使用list。