1.vector数据结构

vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。

因此能高效的进行随机存取，时间复杂度为o(1);

但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。

另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。

2.list数据结构

list是由双向链表实现的，因此内存空间是不连续的。

只能通过指针访问数据，所以list的随机存取非常没有效率，时间复杂度为o(n);

但由于链表的特点，能高效地进行插入和删除。

3.vector和list的区别

我们看一个简单的vector和list使用示例：

#include
      
       #include
       
        #include
        
         using namespace std;int main(){    vector
         
           v;    list
          
            l;    for(int i=0;i<8;i++) 往v和l中分别添加元素    {        v.push_back(i);        l.push_back(i);    }    cout<<"v[2]="<
           
            <
           
          
         
        
       
      

vector拥有一段连续的内存空间，能很好的支持随机存取，

因此vector<int>::iterator支持“+”，“+=”，“<”等操作符。

list的内存空间可以是不连续，它不支持随机访问，

因此list<int>::iterator则不支持“+”、“+=”、“<”等

vector<int>::iterator和list<int>::iterator都重载了“++”运算符。

总之，如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector;

如果需要大量的插入和删除，而不关心随机存取，则应使用list。

 

分类: