C++ STL List 的基本用法和实现原理 |21xrx.com

C++ STL List 的基本用法和实现原理

2023-07-04 21:42:30 深夜i -- --

C++ STL List 基本用法实现原理

C++ STL List 是一种基于双向链表实现的容器，允许在其任何位置插入、删除元素，而且具有常数时间复杂度。这使得 List 成为了一个非常实用的容器，特别是当涉及到大量插入和删除操作时。

基本用法

List 对象的声明方式与 vector 一样。以下是一些常用的 List 操作：

1. push_back() 和 push_front()

- push_back() 函数在列表末尾添加元素。

- push_front() 函数在列表前面添加元素。

2. pop_back() 和 pop_front()

- pop_back() 函数从列表末尾删除元素。

- pop_front() 函数从列表前面删除元素。

3. insert() 和 erase()

- insert() 函数把元素插入到列表中的任何位置。

- erase() 函数删除列表中任何位置的元素。

4. clear() 和 size()

- clear() 函数删除所有元素。

- size() 函数返回列表中元素的总数。

代码示例：


#include <iostream>
#include <list>
using namespace std;
int main() {
  // 声明一个 List 容器
  list<int> mylist;
  // 在列表末尾添加元素
  mylist.push_back(1);
  mylist.push_back(2);
  mylist.push_back(3);
  // 在列表前面添加元素
  mylist.push_front(0);
  // 通过迭代器遍历列表
  for (list<int>::iterator it = mylist.begin(); it != mylist.end(); it++)
    cout << *it << " ";
  cout << endl;
  // 通过迭代器在列表任意位置插入元素
  list<int>::iterator it = mylist.begin();
  it++;
  mylist.insert(it, 4);
  it = mylist.begin();
  it++;
  it++;
  mylist.insert(it, 5);
  // 通过迭代器遍历列表
  for (list<int>::iterator it = mylist.begin(); it != mylist.end(); it++)
    cout << *it << " ";
  cout << endl;
  // 通过迭代器在列表中删除元素
  list<int>::iterator it1 = mylist.begin();
  advance(it1, 2);
  mylist.erase(it1);
  it1 = mylist.begin();
  advance(it1, 3);
  mylist.erase(it1);
  // 通过迭代器遍历列表
  for (list<int>::iterator it = mylist.begin(); it != mylist.end(); it++)
    cout << *it << " ";
  cout << endl;
  // 删除所有元素
  mylist.clear();
  cout << "Size of List = " << mylist.size() << endl;
  return 0;
}

实现原理

List 的实现基于双向链表数据结构，其核心思想是每个节点包含两个指针：一个指向前一个节点，一个指向后一个节点。由此可以快速地在链表的任何位置插入、删除元素。与 vector 不同，List 没有连续的内存空间，因此它不能像 vector 一样随机访问列表中的元素。然而，List 具有相对较小的常量因子和比 vector 更好的空间利用率，这时它们最有效的使用情况。

在 List 中插入和删除元素需要执行以下步骤：

- 分配新的节点空间。

- 将新节点链接到列表中。

- 更新前向和后向链接。

在 List 中查找元素需要遍历整个列表，直到找到期望的节点，时间复杂度为 $O(n)$。由于 List 中每个节点都含有指向前面和后面节点的指针，访问和删除下一个元素的操作也只需常数时间。

总结

C++ STL List 是一个非常有用的容器，特别是在涉及到插入和删除操作的情况下。它基于双向链表实现，可以在不存在任何内存复制的情况下对列表中的元素进行插入和删除操作。然而，由于其遍历元素的操作的时间复杂度为 $O(n)$，因此在查找操作需要进行时不适合使用。

上一篇: idea打包java可执行jar包

下一篇: Node.js心跳机制简介

评论区

()

相似文章