1. vector
vector
和数据类似,拥有一段连续的内存空间,并且起始地址不变vector
能高效的进行随机存取,时间复杂度为o(1)
因为vector
内存空间是连续的,所以在进行插入和删除操作时,会造成内存块的拷贝,时间复杂度为o(n)
当数组中内存空间不够时,会重新申请一块内存空间并进行内存拷贝
list
是由双向链表实现的,因此内存空间不是连续的只能通过指针访问数据,所以list 的随机存取效率非常低,时间复杂度为o(n)
但是由于链表的特点,插入和删除比较高效
list _9">3. vector和list 的区别
vector拥有一段连续的内存空间,能很好的支持随机存取 list 的内存空间是不连续的,不支持随机访问
4. 代码
# include <iostream>
# include <vector>
# include <list >
using namespace std; int main ( )
{ vector< int > v; list < int > l; for ( int i= 0 ; i< 8 ; i++ ) { v. push_back ( i) ; l. push_back ( i) ; } cout << "v[2]=" << v[ 2 ] << endl; cout << ( v. begin ( ) < v. end ( ) ) << endl; cout << * ( v. begin ( ) + 1 ) << endl; vector< int > :: iterator itv = v. begin ( ) ; list < int > :: iterator itl = l. begin ( ) ; itv = itv + 2 ; itv++ ; itl++ ; cout << * itv << endl; cout << * itl << endl; getchar ( ) ; return 0 ;
}
5. 总结
如果需要高效的存取,不在乎插入和删除的效率,使用vector
如果需要大量的插入和删除,不需要随机存取,则使用list