vector和list区别在于底层实现机理不同,因而特性和适用场景也有所不同。
vector:一维数组
特点:元素在内存连续存放,动态数组,在堆中分配内存,元素连续存放,有保留内存,如果减少大
小后内存也不会释放。
优点:和数组类似开辟一段连续的空间,并且支持随机访问,所以它的查找效率高其时间复杂度
O(1)。
缺点:由于开辟一段连续的空间,所以插入删除会需要对数据进行移动比较麻烦,时间复杂度
O(n),另外当空间不足时还需要进行扩容。
list:双向链表
特点:元素在堆中存放,每个元素都是存放在一块内存中,它的内存空间可以是不连续的,通过指针
来进行数据的访问。
优点:底层实现是循环双链表,当对大量数据进行插入删除时,其时间复杂度O(1)。
缺点:底层没有连续的空间,只能通过指针来访问,所以查找数据需要遍历其时间复杂度O(n),
没有提供[]操作符的重载。
应用场景
vector拥有一段连续的内存空间,因此支持随机访问,如果需要高效的随即访问,而不在乎插入和删
除的效率,使用vector。
list拥有一段不连续的内存空间,如果需要高效的插入和删除,而不关心随机访问,则应使用list。