vector和list的区别

1. vector

• 基于动态数组： std::vector 基于可以动态扩展的数组实现，这意味着它在内存中 连续存储 元素。
• 随机访问：提供快速的随机访问能力，可以 通过索引快速访问 任何元素。
• 内存分配：通常在内存分配上更紧凑，因为元素紧密排列，没有额外的空间用于链接或指针。
• 时间复杂度：
  • 元素访问： O(1) ，即常数时间复杂度。
  • 插入和删除：在 vector 的末尾是 O(1) ，但如果需要在中间插入或删除元素，则可能需要 O(n) ，因为可能需要移动后续所有元素。
• 内存管理：使用连续内存分配，可以利用缓存的优势，提高访问速度。

1. list

• 基于双向链表： std::list 是基于 双向链表 的容器，每个元素通过节点链接到前一个和后一个元素。
• 非连续存储： 元素在内存中不是连续存储的 ，每个元素包含指向前一个和后一个元素的指针。
• 时间复杂度：
  • 元素访问： O(n) ，需要从头开始遍历到所需位置。
  • 插入和删除：非常快速，特别是当需要在列表中间插入或删除元素时，操作是 O(1) ，前提是已经拥有指向待插入或删除元素的迭代器。
• 内存管理：由于元素间通过指针链接，内存分配可能更分散，但插入和删除操作不需要移动其他元素。

1. 使用场景

• std::vector ：
  • 当你需要快速随机访问元素时。
  • 当你需要在末尾快速添加或删除元素时。
  • 当你关心内存使用效率时。
• std::list ：
  • 当你需要在列表中间高效地插入或删除元素时。
  • 当你不需要随机访问元素时。
  • 当你需要一个灵活的容器，可以动态地添加和删除元素而不会引起大量的内存复制或移动。