c++ STL系列——（三）list

时间：2024-02-17 11:21:24

目录

引言

list的特点

list的用法

list与其他容器的比较

结论

引言

在C++ STL中，list 是一个非常灵活且功能强大的双向链表容器，它允许存储任意类型的元素，并提供了丰富的操作函数，包括插入、删除、排序、查找以及对容器的遍历等功能。list 的特性和用法使得它在各种情况下都能发挥重要作用，并与其他容器有着明显的区别与优势。本文将详细介绍list的特点、用法以及其与其他容器的比较。

list的特点

list是一个双向链表，其内部每个节点都包含了元素的值、指向前驱节点的指针和指向后继节点的指针。这种结构使得list具有许多独特的特点：

  • 双向链表结构： list 内部以双向链表的形式存储元素，这意味着每个元素都包含了指向前一个元素和后一个元素的指针。这种结构使得在 list 中进行插入和删除操作非常高效，时间复杂度为 O(1)。

  • 灵活性： list 提供了一种灵活的存储方式，允许在任意位置插入和删除元素，而不像 vector 那样需要进行内存的重新分配。这使得 list 特别适用于频繁的插入和删除操作。

  • 操作函数： list 提供了丰富的操作函数，包括在指定位置插入元素（insert）、删除元素（erase）、排序（sort）、翻转（reverse）等。这些操作函数使得可以方便地对 list 进行各种操作，满足不同的需求。

  • 无随机访问： 与 vector 和 deque 不同，list 不支持随机访问，即不能通过下标直接访问元素。这是因为在双向链表中，要访问某个元素需要从头或者从尾开始逐个遍历，时间复杂度为 O(n)。

  • 与其他容器比较： 相对于 vector，list 在插入和删除操作上更加高效，但在随机访问和存储空间上略逊一筹；与 deque 相比，list 在任意位置的插入和删除操作更为高效，但在访问元素时稍慢一些。

list的用法

创建和初始化

创建一个空的list可以使用默认构造函数，也可以使用初始化列表：

std::list<int> mylist; // 创建一个空的int类型的list
std::list<std::string> mystrings = {"hello", "world"}; // 使用初始化列表创建list

插入和删除元素

list提供了多种方法来插入和删除元素，例如push_back()、push_front()、insert()、erase()等。下面是一些示例：

std::list<int> mylist = {1, 2, 3, 4, 5};

// 在末尾添加元素
mylist.push_back(6);

// 在开头添加元素
mylist.push_front(0);

// 在指定位置插入元素
auto it = mylist.begin();
++it;
mylist.insert(it, 9);

// 删除末尾元素
mylist.pop_back();

// 删除开头元素
mylist.pop_front();

// 删除指定位置的元素
auto it2 = mylist.begin();
++it2;
mylist.erase(it2);

访问和修改元素

由于list不支持随机访问，因此必须使用迭代器进行遍历和访问元素。要修改元素的值，可以使用迭代器的解引用操作符：

std::list<int> mylist = {1, 2, 3, 4, 5};

// 遍历list并输出元素
for (auto it = mylist.begin(); it != mylist.end(); ++it) {
    std::cout << *it << " ";
}

// 修改指定位置的元素
auto it = mylist.begin();
++it;
*it = 9;

排序和查找

list提供了内置函数来排序和查找元素，例如sort()、find()、count()等：

std::list<int> mylist = {5, 3, 2, 4, 1};

// 对元素进行排序
mylist.sort();

// 查找元素并返回迭代器
auto it = std::find(mylist.begin(), mylist.end(), 3);

// 统计元素出现的次数
int count = std::count(mylist.begin(), mylist.end(), 5);

list与其他容器的比较

在C++ STL中，除了list之外还有许多其他容器，例如数组容器vector、关联容器map和set等。虽然list具有自己独特的特点，但在一些方面，它也存在一些劣势：

  • 不支持随机访问：由于list是一个链表，因此无法通过下标或指针进行随机访问，这可能会导致一些性能问题。
  • 占用更多的内存：由于每个节点都需要存储元素值以及指向前驱节点和后继节点的指针，因此list通常会占用比其他容器更多的内存空间。
  • 缓存不友好：由于list的元素在内存中不是连续存储的，因此在遍历时可能会出现缓存未命中的情况，从而影响性能。

然而，list在动态调整容量、快速元素插入和删除等方面具有明显优势，这使得它在某些场景下仍然是一个非常有用的容器。

结论

总之，list是C++ STL中一个非常重要和有用的容器，可以用于存储任意类型的元素，并提供了多种操作函数，如插入、删除、排序、查找和遍历等。虽然list在一些方面具有劣势，但在一些场景下它仍然是一个非常有用的容器。如果你需要一种动态调整容量、快速插入和删除元素的容器，那么list可能是一个不错的选择。

相关文章