STL之list介绍-白红宇

STL之list介绍

阅读量：133 次

发布时间：2019-02-26

本文共 1714 字，大约阅读时间需要 5 分钟。

STL中的List容器是一种非常强大的序列容器，能够在常数时间内进行插入、删除和双向遍历操作。它基于双向链接列表实现，能够高效处理各种操作，尤其是在需要频繁插入、删除元素的场景中表现优异。

1. 概述

List容器的官方定义指出，它们是序列容器，支持在序列中的任意位置进行常数时间的插入和擦除操作，同时支持双向迭代。与其他常见的序列容器（如array、vector和deque）相比，List的性能在元素插入、删除以及迁移操作上有显著优势，特别是在需要频繁调整元素位置的算法中。

List是双向链接列表，每个元素都有一个指向前驱和后继的指针。这种结构允许List在O(1)时间内支持插入和删除操作，同时也支持双向迭代，既能从前往后，也能从后往前遍历元素。

值得注意的是，List和forward_list之间存在一个关键差异：forward_list是单向链接列表，只能从前往后迭代，而List可以双向迭代。尽管如此，List在性能上比其他序列容器更优，尤其是在插入、删除操作频繁的情况下。

然而，List也有一些缺点。与其他序列容器相比，List不支持直接通过位置访问元素。要访问某个位置的元素，通常需要从已知位置（如开头或结尾）开始遍历，直到目标位置，这在最坏情况下需要线性时间。此外，List需要额外的内存来存储链接信息，这在元素数量较多且每个元素较小的场景下可能成为内存使用的瓶颈。

2. 用法介绍

以下是List容器的两个简单示例，展示了其基本用法。

示例1：List的基本使用

#include 
   
    #include 
    
     using namespace std;int main() {    list
     
       lst;    int values[] = {10, 8, -1, 5};    // 将元素添加到列表末尾    for (int value : values) {        lst.push_back(value);    }    // 输出列表当前内容    cout << "List values: ";    while (!lst.empty()) {        cout << lst.front() << " ";        lst.pop_front();    }    cout << endl;    return 0;}

示例2：List的高级用法

#include 
   
    #include 
    
     #include 
     
      using namespace std;int main() {    list
      
        lst;    int i;    // 生成一个随机整数列表    for (i = 0; i < 10; ++i) {        lst.push_back(rand());    }    // 输出原始列表内容    cout << "Original list: ";    for (auto num : lst) {        cout << num << " ";    }    cout << endl;    // 创建并使用List的迭代器进行排序    auto p = lst.begin();    lst.sort();    // 输出排序后的列表内容    cout << "Sorted contents: ";    while (p != lst.end()) {        cout << *p << " ";        p++;    }    cout << endl;    return 0;}