【C++】vector和list的区别

1. vector

• vector和数据类似，拥有一段连续的内存空间，而且起始地点稳固
  
• vector能高效的举行随机存取，时间复杂度为o(1)
  
• 由于vector内存空间是连续的，以是在举行插入和删除使用时，会造成内存块的拷贝，时间复杂度为o(n)
  
• 当数组中内存空间不敷时，会重新申请一块内存空间并举行内存拷贝
  

2. list

• list是由双向链表实现的，因此内存空间不是连续的
  
• 只能通过指针访问数据，以是list的随机存取服从非常低，时间复杂度为o(n)
  
• 但是由于链表的特点，插入和删除比力高效
  

3. vector和list的区别

• vector拥有一段连续的内存空间，能很好的支持随机存取
  
• list的内存空间是不连续的，不支持随机访问
  

4. 代码

1. #include<iostream>
2. #include<vector>
3. #include<list>
4. using namespace std;
6. int main()
7. {
8.     vector<int> v;
9.     list<int> l;
10.    
11.         //往v和l中分别添加元素
12.     for(int i=0; i<8; i++)
13.     {
14.         v.push_back(i);
15.         l.push_back(i);
16.     }
17.    
18.     cout << "v[2]=" << v[2] << endl;
19.     //cout << "l[2]=" << l[2] << endl;  //编译错误,list没有重载`[]`
20.    
21.     cout << (v.begin()<v.end()) << endl;
22.     //cout << (l.begin() < l.end()) << endl; /编译错误,list::iterator没有重载 `<` 和 `>`
23.    
24.     cout << *(v.begin()+1) << endl;
25.     //cout << *(l.begin()+1) << endl; //编译错误,list::iterator没有重载`+`
26.    
27.     vector<int>::iterator itv = v.begin();
28.     list<int>::iterator itl = l.begin();
29.     itv = itv + 2;
30.     //itl = itl + 2; //编译错误,list::iterator没有重载+
31.    
32.     itv++;
33.     itl++;        //list::iterator中重载了++，只能使用++进行迭代访问。
34.    
35.     cout << *itv << endl;
36.     cout << *itl << endl;
37.    
38.     getchar();
39.     return 0;
40. }

复制代码

5. 总结

• 如果须要高效的存取，不在乎插入和删除的服从，使用vector
  
• 如果须要大量的插入和删除，不须要随机存取，则使用list