当前位置：首页 > article >正文

c++ 中的容器 vector、deque 和 list 的区别

article 2025/1/14 12:02:46

                    
                    表格汇总：
 
容器存储结构随机访问性能中间插入/删除性能两端插入/删除性能内存管理特点迭代器类型适用场景
vector连续存储的动态数组 
        
            O 
           
            ( 
           
            1 
           
            ) 
           
           O(1) 
          
       O(1) 
        
            O 
           
            ( 
           
            n 
           
            ) 
           
           O(n) 
          
       O(n)（需要移动元素）末尾： 
        
            O 
           
            ( 
           
            1 
           
            ) 
           
           O(1) 
          
       O(1)，头部： 
        
            O 
           
            ( 
           
            n 
           
            ) 
           
           O(n) 
          
       O(n)空间不足时重新分配并复制元素随机访问迭代器频繁随机访问，插入/删除在末尾
deque分段连续存储 
        
            O 
           
            ( 
           
            1 
           
            ) 
           
           O(1) 
          
       O(1)（稍逊于 vector） 
        
            O 
           
            ( 
           
            n 
           
            ) 
           
           O(n) 
          
       O(n)（优于 vector） 
        
            O 
           
            ( 
           
            1 
           
            ) 
           
           O(1) 
          
       O(1)以块为单位分配内存，空间扩展更稳定随机访问迭代器两端高效插入/删除，需一定随机访问
list双向链表，节点存储元素及前后指针 
        
            O 
           
            ( 
           
            n 
           
            ) 
           
           O(n) 
          
       O(n)（需遍历） 
        
            O 
           
            ( 
           
            1 
           
            ) 
           
           O(1) 
          
       O(1)（仅需修改指针） 
        
            O 
           
            ( 
           
            1 
           
            ) 
           
           O(1) 
          
       O(1)元素节点单独分配，可能碎片化双向迭代器频繁中间插入/删除，不依赖随机访问
 
存储结构： 
  vector： 
    是一个动态数组，元素在内存中是连续存储的。这使得它可以像数组一样支持快速的随机访问，通过下标访问元素的时间复杂度为  
          
              O 
             
              ( 
             
              1 
             
              ) 
             
             O(1) 
            
         O(1)。例如，对于一个 std::vector<int> v;，使用 v[2] 可以快速访问第三个元素（索引从 0 开始）。
 
deque（双端队列）： 
    数据在内存中是分段连续存储的，对用户而言逻辑上是连续的。它也支持随机访问，不过效率比 vector 稍低，但仍为  
          
              O 
             
              ( 
             
              1 
             
              ) 
             
             O(1) 
            
         O(1)。例如，对于 std::deque<int> d;，可以使用 d[3] 来访问第四个元素。
 
list（双向链表）： 
    是一个双向链表，每个元素存储在一个节点中，节点包含数据和指向前一个及后一个节点的指针。这导致它不能直接根据下标进行随机访问，访问元素需要从头部或尾部开始遍历，时间复杂度为  
          
              O 
             
              ( 
             
              n 
             
              ) 
             
             O(n) 
            
         O(n)，其中 n 是元素的个数。
 
插入和删除元素的性能： 
  vector： 
    在末尾插入和删除元素通常比较快，时间复杂度为  
          
              O 
             
              ( 
             
              1 
             
              ) 
             
             O(1) 
            
         O(1)，但当元素数量达到容器的容量时，插入元素会触发扩容操作，需要重新分配内存和复制元素，性能开销较大。在中间插入或删除元素时，需要移动其后的元素，时间复杂度为  
          
              O 
             
              ( 
             
              n 
             
              ) 
             
             O(n) 
            
         O(n)。例如，v.insert(v.begin() + 2, 5); 会将元素 5 插入到 v 的第三个位置，其后的元素会向后移动。
 
deque： 
    在两端插入和删除元素都非常快，时间复杂度为  
          
              O 
             
              ( 
             
              1 
             
              ) 
             
             O(1) 
            
         O(1)。在中间插入或删除元素时，性能比 vector 好，因为不需要移动大量元素，但仍然比 list 慢，时间复杂度为  
          
              O 
             
              ( 
             
              n 
             
              ) 
             
             O(n) 
            
         O(n)。例如，d.push_front(1); 和 d.push_back(2); 分别在 deque 的前端和后端插入元素。
 
list： 
    在任何位置插入和删除元素都很快，只要有指向该位置的迭代器，时间复杂度为  
          
              O 
             
              ( 
             
              1 
             
              ) 
             
             O(1) 
            
         O(1)，因为只需要修改前后节点的指针，不涉及元素的移动。例如，对于 std::list<int> l;，使用 l.insert(l.begin(), 3); 插入元素 3 时，只需调整指针。
 
内存管理： 
  vector： 
    当空间不足时，会分配一个更大的连续内存空间，将原元素复制过去，释放原空间。这可能导致性能开销和内存浪费（预留但未使用的空间）。例如，当 v 的元素数量超过其容量时，会重新分配更大的内存空间。
 
deque： 
    以块为单位分配内存，当需要更多空间时，会分配新的块，不需要像 vector 那样大规模复制元素，因此在空间扩展时相对更稳定。
 
list： 
    每个元素节点单独分配内存，插入元素时为新节点分配内存，不会出现 vector 那样的整体复制和重新分配问题，但可能导致内存碎片化，因为节点是分散存储的。
 
迭代器特性： 
  vector： 
    迭代器是随机访问迭代器，可以进行加、减操作，支持 operator[]。在插入或删除元素时，可能导致迭代器失效，特别是在扩容时，迭代器和指针、引用都可能失效。
 
deque： 
    迭代器是随机访问迭代器，但在中间插入或删除元素时，部分迭代器可能失效，因为存储是分段的。
 
list： 
    迭代器是双向迭代器，只能进行前后移动，不支持 operator[]。在插入或删除元素时，只有被操作元素的迭代器失效，其他迭代器不受影响。
 
适用场景： 
  vector： 
    适合需要频繁随机访问元素，并且元素的插入和删除操作主要在末尾进行的场景。例如，存储一组学生成绩，经常根据索引查询成绩，成绩的添加和删除多在末尾。
 
deque： 
    适用于需要在两端高效插入和删除元素，同时也需要一定程度随机访问能力的情况。例如，实现一个双端操作的队列，或者一个窗口滑动的数据结构。
 
list： 
    适用于需要频繁在容器中间插入和删除元素，对随机访问性能要求不高的情况。例如，实现一个文本编辑器中的文本行存储，频繁插入和删除行操作。

容器	存储结构	随机访问性能	中间插入/删除性能	两端插入/删除性能	内存管理特点	迭代器类型	适用场景
`vector`	连续存储的动态数组	$O (1)$	$O (n)$ （需要移动元素）	末尾： $O (1)$ ，头部： $O (n)$	空间不足时重新分配并复制元素	随机访问迭代器	频繁随机访问，插入/删除在末尾
`deque`	分段连续存储	$O (1)$ （稍逊于 `vector`）	$O (n)$ （优于 `vector`）	$O (1)$	以块为单位分配内存，空间扩展更稳定	随机访问迭代器	两端高效插入/删除，需一定随机访问
`list`	双向链表，节点存储元素及前后指针	$O (n)$ （需遍历）	$O (1)$ （仅需修改指针）	$O (1)$	元素节点单独分配，可能碎片化	双向迭代器	频繁中间插入/删除，不依赖随机访问