C++ 中 STL Vector 和 STL List 的区别

Jinku Hu 2023年10月12日
C++ 中 STL Vector 和 STL List 的区别

本文解释并演示了 C++ 中 STL vectorlist 容器之间的主要区别。

确定何时使用 C++ 中的 std::vectorstd::list 容器

C++ STL 容器通常共享类似的接口来操作元素。尽管如此,还是应该探索这些数据结构的内部差异,为给定的问题选择最优化的容器。std::vector 函数通常被称为动态数组。它在内部自动管理动态内存并保持连续存储的元素类似于 C 类型数组。后一个特性使得在恒定时间内访问元素成为可能。

另一方面,std::list 命令实现了一种数据结构,其中元素作为双向链表进行管理。我们按原样表述前一句是因为 C++ 标准通常不会强制执行确切的实现为双向链表。尽管如此,它还是指定了标准库实现者需要满足的某些特征。

std::list 命令作为模板类提供,存储类似于 std::vector 的任何类型的对象。我们可以使用 push_backpush_front 成员函数将新元素存储到 std::list 对象中,它们都具有恒定的时间复杂度。至于 std::vector,我们只有 push_back,它具有平均常数复杂度。请注意,这些函数用于在给定对象的开头/结尾添加元素。

下面的示例代码演示了上述函数在每种容器类型上的基本用法。

#include <algorithm>
#include <iostream>
#include <list>

using std::cout;
using std::endl;
using std::list;
using std::vector;

int main() {
  vector<int> v = {1, 2, 13, 84};
  list<int> l = {1, 2, 13, 84};

  v.push_back(25);
  v.push_back(13);

  l.push_back(25);
  l.push_front(13);

  return EXIT_SUCCESS;
}

相反,如果我们想在给定位置插入一个新元素,我们需要利用 insert 成员函数。现在,此操作是 std::liststd::vector 之间的主要区别之一。通常,insert 操作对向量对象的开销比对列表对象的开销更大。

由于向量内容是连续存储的,每个新插入的元素都会迫使后面的元素向右移动,这取决于向量本身的大小。因此,如果我们需要在对象开头的中间进行多次插入,我们应该避免使用 vector 容器。如果是后者,我们宁愿使用 list 容器,因为一旦位置已知,在列表中的任何位置插入新元素需要恒定的时间。

我们在下一个代码示例中演示了插入时间差异,其中两个容器都用任意 100000 整数初始化,然后我们对每个对象的单个插入操作进行计时。请注意,我们为两个容器选择了一个相对中间的位置(39999),使用 std::search 函数检索。因此,在 listvector 中插入一个新元素需要数百个因素。

由于元素删除操作与插入操作类似,与 vector 相比,它在 list 对象上的效率更高。不利的一面是,除了第一个和最后一个元素之外,list 元素没有固定时间访问操作。

#include <sys/time.h>

#include <algorithm>
#include <iostream>
#include <list>
#include <random>

using std::cout;
using std::endl;
using std::list;
using std::vector;

float time_diff(struct timeval *start, struct timeval *end) {
  return (end->tv_sec - start->tv_sec) + 1e-6 * (end->tv_usec - start->tv_usec);
}

const int MIN = 1;
const int MAX = 100;
const int CAPASITY = 100000;

int main() {
  struct timeval start {};
  struct timeval end {};

  std::random_device rd;
  std::mt19937 eng(rd());
  std::uniform_int_distribution<int> distr(MIN, MAX);

  vector<int> vec1;
  list<int> list1;

  vec1.reserve(CAPASITY);
  for (int i = 0; i < CAPASITY; ++i) {
    if (i % 39999 == 0) {
      vec1.push_back(111);
      continue;
    }
    vec1.push_back(distr(eng));
  }

  for (int i = 0; i < CAPASITY; ++i) {
    if (i % 39999 == 0) {
      list1.push_back(111);
      continue;
    }
    list1.push_back(distr(eng));
  }

  auto iter = std::find(vec1.begin(), vec1.end(), 111);
  gettimeofday(&start, nullptr);
  vec1.insert(iter, 1111);
  gettimeofday(&end, nullptr);
  printf("insert vector: %0.8f sec\n", time_diff(&start, &end));

  auto iter2 = std::find(list1.begin(), list1.end(), 111);
  gettimeofday(&start, nullptr);
  list1.insert(iter2, 1111);
  gettimeofday(&end, nullptr);
  printf("insert list  : %0.8f sec\n", time_diff(&start, &end));

  return EXIT_SUCCESS;
}

输出:

insert vector: 0.00053000 sec
insert list  : 0.00000100 sec
作者: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

DelftStack.com 创始人。Jinku 在机器人和汽车行业工作了8多年。他在自动测试、远程测试及从耐久性测试中创建报告时磨练了自己的编程技能。他拥有电气/电子工程背景,但他也扩展了自己的兴趣到嵌入式电子、嵌入式编程以及前端和后端编程。

LinkedIn Facebook

相关文章 - C++ List

相关文章 - C++ Vector