【c++】列表的增删改查

常见的列表容器及其特点

C++ 标准库提供了多种容器，用于不同的需求和使用场景。以下是一些常见的列表容器及其特点：

1. std::vector 特点：动态数组，元素存储在连续的内存块中。 访问时间：随机访问时间为常数时间 (O(1))。 插入/删除时间：末尾插入/删除为常数时间 (O(1))；中间插入/删除为线性时间 (O(n))。
2. std::list 特点：双向链表，每个元素包含指向前一个和后一个元素的指针。 访问时间：随机访问时间为线性时间 (O(n))。 插入/删除时间：在任意位置插入/删除为常数时间 (O(1))。
3. std::forward_list 特点：单向链表，每个元素只包含指向下一个元素的指针。 访问时间：随机访问时间为线性时间 (O(n))。 插入/删除时间：在头部插入/删除为常数时间 (O(1))；在中间或末尾插入/删除需要遍历链表。
4. std::deque 特点：双端队列，支持高效地在两端进行插入和删除操作。 访问时间：随机访问时间为常数时间 (O(1))。 插入/删除时间：在两端插入/删除为常数时间 (O(1))，在中间插入/删除为线性时间 (O(n))。
5. std::array 特点：固定大小的数组，元素存储在连续的内存块中。 访问时间：随机访问时间为常数时间 (O(1))。 插入/删除时间：不支持动态插入/删除操作，因为大小是固定的。
6. std::string 特点：专门用于存储字符序列的动态数组。 访问时间：随机访问时间为常数时间 (O(1))。 插入/删除时间：类似于 std::vector，末尾插入/删除为常数时间 (O(1))，中间插入/删除为线性时间 (O(n))。 总结

   连续存储：std::vector, std::array, std::string（随机访问高效，插入/删除中间元素较慢）。

   链表存储：std::list, std::forward_list（随机访问较慢，插入/删除任意位置高效）。

   双端队列：std::deque（随机访问高效，两端插入/删除高效）。

   选择合适的容器需要根据具体的应用场景和操作需求来决定。例如，如果需要频繁的随机访问，可以考虑使用 std::vector 或

   std::array；如果需要高效地在中间插入和删除元素，可以考虑使用 std::list

std::vector 和 std::list

std::vector 和 std::list 是 C++ 标准库中常用的两个容器，它们在内存布局和访问方式上有显著的区别，这导致了它们在不同操作上的性能差异。

• 内存布局

  std::vector：使用连续的内存块来存储元素。这意味着所有元素都在一个连续的内存区域中。

  std::list：使用双向链表存储元素。每个元素存储在独立的内存块中，并且每个元素都有指向前一个和后一个元素的指针。

  • 访问效率

    std::vector：

    由于元素存储在连续的内存块中，std::vector 支持常数时间 (O(1)) 随机访问。例如，访问第 i 个元素可以通过 v[i] 或 *(v.data() + i) 快速实现。 连续的内存布局还利于 CPU 缓存优化。当访问 std::vector 中的元素时，CPU 可以更有效地预取数据，从而减少缓存未命中的次数，提高访问速度。

    std::list：

    std::list 不支持随机访问，因为它是通过链表结构存储的。要访问第 i 个元素，需要从头开始遍历链表，访问时间是线性时间(O(n))。 链表中的元素分散在内存的不同位置，导致访问时可能会频繁发生缓存未命中，因为每次访问下一个元素时，都需要读取新的内存地址。

    • 插入和删除效率

      std::vector：

      在末尾插入或删除元素是常数时间 (O(1)) 操作。 在中间插入或删除元素需要移动后续元素，因此是线性时间 (O(n)) 操作。

      std::list：

      在任何位置插入或删除元素都是常数时间 (O(1)) 操作，只需调整指针即可。

      总结

      访问效率：std::vector 的访问效率远高于 std::list，因为它支持常数时间的随机访问，并且其连续内存布局更有利于 CPU

      缓存。 插入和删除效率：std::list 对于在中间任意位置的插入和删除操作更加高效，因为不需要移动其他元素。

      因此，如果你的应用场景主要涉及频繁的随机访问，那么 std::vector

      是更好的选择。如果主要涉及频繁的插入和删除操作，特别是在中间位置，那么 std::list

      可能会表现得更好。选择合适的容器需要根据具体的使用场景和操作类型来决定。

      列表容器的增删改查操作

      #include 
      #include 
      int main() {
          std::list myList;
          // 增加元素 (在列表末尾添加元素)
          myList.push_back(10);
          myList.push_back(20);
          myList.push_back(30);
          // 在列表头部添加元素
          myList.push_front(5);
          std::cout 
              std::cout 
              std::cout 
              if (*it == 10) {
                  *it = 15;
              }
          }
          std::cout 
              std::cout 
              std::cout 
              std::cout