跳到主要内容

C++ List 容器

什么是List容器？​

List容器是C++ STL(标准模板库)中提供的一种序列式容器，它实现了一个双向链表(doubly linked list)。与vector等基于数组的容器不同，list容器中的元素在内存中并不是连续存储的，而是通过指针相互连接形成链表结构。

备注

List容器的每个元素都包含一个值和两个指针，这两个指针分别指向前一个元素和后一个元素。

List的特点​

List容器与其他STL容器相比具有以下特点：

  1. 高效的插入和删除操作：在list的任何位置插入或删除元素都是常数时间O(1)的操作。
  2. 不支持随机访问：不能像数组那样通过下标直接访问元素，必须通过迭代器逐个遍历。
  3. 占用空间较大：由于需要存储前后指针，所以比vector等容器占用更多内存。
  4. 不支持元素排序的随机访问算法：如std::sort，但提供了自己的排序方法sort()。

如何使用List容器​

包含必要的头文件​

cpp
#include <list>
#include <iostream>

创建List容器​

cpp
// 创建一个空的整型list
std::list<int> myList;

// 创建具有5个元素的list，每个元素都初始化为100
std::list<int> myList2(5, 100);

// 使用初始化列表创建list
std::list<int> myList3 = {1, 2, 3, 4, 5};

// 使用另一个list初始化
std::list<int> myList4(myList3);

基本操作​

添加元素​

cpp
std::list<int> myList;

// 在末尾添加元素
myList.push_back(10);
myList.push_back(20);

// 在开头添加元素
myList.push_front(5);

// 在指定位置插入元素
auto it = myList.begin();
++it; // 移动到第二个元素
myList.insert(it, 15);

执行上述代码后，myList的内容为：5, 15, 10, 20

删除元素​

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

// 删除第一个元素
myList.pop_front();

// 删除最后一个元素
myList.pop_back();

// 删除特定值的元素
myList.remove(3);

// 使用条件删除元素
myList.remove_if([](int n){ return n % 2 == 0; }); // 删除所有偶数

执行上述代码后，myList的内容为：5（只剩下5）

访问元素​

cpp
std::list<int> myList = {10, 20, 30, 40, 50};

// 访问第一个元素
int first = myList.front();

// 访问最后一个元素
int last = myList.back();

// 通过迭代器访问元素
for (auto it = myList.begin(); it != myList.end(); ++it) {
    std::cout << *it << " ";
}

输出：

10 20 30 40 50

其他常用操作​

cpp
std::list<int> myList = {3, 7, 9, 2, 5, 8, 1, 6, 4};

// 获取list大小
size_t size = myList.size();
std::cout << "List size: " << size << std::endl;

// 检查list是否为空
bool isEmpty = myList.empty();
std::cout << "Is list empty? " << (isEmpty ? "Yes" : "No") << std::endl;

// 清空list
myList.clear();

// 为list重新分配元素
myList.assign(5, 10); // 5个值为10的元素

输出：

List size: 9
Is list empty? No

List的特殊操作​

List容器提供了一些其他容器没有的特殊操作：

排序​

cpp
std::list<int> myList = {5, 2, 9, 1, 7, 3};

// 升序排序
myList.sort();

std::cout << "Sorted list: ";
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
std::cout << std::endl;

// 使用自定义比较函数降序排序
myList.sort([](int a, int b) { return a > b; });

std::cout << "Reverse sorted list: ";
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
std::cout << std::endl;

输出：

Sorted list: 1 2 3 5 7 9
Reverse sorted list: 9 7 5 3 2 1

合并两个有序list​

cpp
std::list<int> list1 = {1, 3, 5, 7};
std::list<int> list2 = {2, 4, 6, 8};

// 合并两个有序list（两个list必须已排序）
list1.merge(list2);

std::cout << "Merged list: ";
for (const auto& elem : list1) {
    std::cout << elem << " ";
}
std::cout << std::endl;

// list2现在为空
std::cout << "Size of list2 after merge: " << list2.size() << std::endl;

输出：

Merged list: 1 2 3 4 5 6 7 8
Size of list2 after merge: 0

反转list​

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

// 反转list
myList.reverse();

std::cout << "Reversed list: ";
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
std::cout << std::endl;

输出：

Reversed list: 5 4 3 2 1

删除重复元素​

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

// 删除连续的重复元素（list必须已排序）
myList.unique();

std::cout << "After removing duplicates: ";
for (const auto& elem : myList) {
    std::cout << elem << " ";
}
std::cout << std::endl;

输出：

After removing duplicates: 1 2 3 4 5

实际应用场景​

场景1：任务队列管理​

在需要频繁在两端插入和删除元素的情况下，list是一个很好的选择：

cpp
#include <list>
#include <iostream>
#include <string>

class TaskManager {
private:
    std::list<std::string> taskQueue;

public:
    void addUrgentTask(const std::string& task) {
        taskQueue.push_front(task);
        std::cout << "Added urgent task: " << task << std::endl;
    }

    void addRegularTask(const std::string& task) {
        taskQueue.push_back(task);
        std::cout << "Added regular task: " << task << std::endl;
    }

    void executeNextTask() {
        if (!taskQueue.empty()) {
            std::cout << "Executing task: " << taskQueue.front() << std::endl;
            taskQueue.pop_front();
        } else {
            std::cout << "No tasks to execute." << std::endl;
        }
    }

    void displayAllTasks() {
        if (taskQueue.empty()) {
            std::cout << "No tasks in the queue." << std::endl;
            return;
        }

        std::cout << "Current tasks in the queue:" << std::endl;
        int index = 1;
        for (const auto& task : taskQueue) {
            std::cout << index++ << ". " << task << std::endl;
        }
    }
};

int main() {
    TaskManager manager;
    
    manager.addRegularTask("Send email");
    manager.addRegularTask("Update database");
    manager.addUrgentTask("Fix critical bug");
    
    manager.displayAllTasks();
    
    manager.executeNextTask();
    manager.executeNextTask();
    
    manager.displayAllTasks();
    
    return 0;
}

输出：

Added regular task: Send email
Added regular task: Update database
Added urgent task: Fix critical bug
Current tasks in the queue:
1. Fix critical bug
2. Send email
3. Update database
Executing task: Fix critical bug
Executing task: Send email
Current tasks in the queue:
1. Update database

场景2：多项式表示​

list可以用来表示和操作多项式：

cpp
#include <list>
#include <iostream>
#include <utility> // for std::pair

class Polynomial {
private:
    // 每个元素是一个(指数,系数)对
    std::list<std::pair<int, int>> terms;

public:
    // 添加一项到多项式
    void addTerm(int coefficient, int exponent) {
        if (coefficient == 0) return; // 系数为0不添加
        
        auto it = terms.begin();
        // 找到合适的位置插入（按指数降序）
        while (it != terms.end() && it->first > exponent) {
            ++it;
        }
        
        // 如果指数已存在，则合并系数
        if (it != terms.end() && it->first == exponent) {
            it->second += coefficient;
            // 如果合并后系数为0，则移除该项
            if (it->second == 0) {
                terms.erase(it);
            }
        } else {
            terms.insert(it, std::make_pair(exponent, coefficient));
        }
    }

    // 显示多项式
    void display() const {
        if (terms.empty()) {
            std::cout << "0" << std::endl;
            return;
        }

        bool isFirst = true;
        for (const auto& term : terms) {
            if (term.second > 0 && !isFirst) {
                std::cout << " + ";
            } else if (term.second < 0 && !isFirst) {
                std::cout << " - ";
            } else if (term.second < 0) {
                std::cout << "-";
            }

            int absCoeff = std::abs(term.second);
            if (absCoeff != 1 || term.first == 0) {
                std::cout << absCoeff;
            }
            
            if (term.first > 0) {
                std::cout << "x";
                if (term.first > 1) {
                    std::cout << "^" << term.first;
                }
            }
            
            isFirst = false;
        }
        std::cout << std::endl;
    }
};

int main() {
    Polynomial poly;
    
    poly.addTerm(3, 4); // 3x^4
    poly.addTerm(-2, 2); // -2x^2
    poly.addTerm(1, 1); // x
    poly.addTerm(5, 0); // 5
    
    std::cout << "Polynomial: ";
    poly.display();
    
    // 修改多项式
    poly.addTerm(2, 2); // 将抵消之前的-2x^2
    poly.addTerm(7, 4); // 将与3x^4合并为10x^4
    
    std::cout << "Modified polynomial: ";
    poly.display();
    
    return 0;
}

输出：

Polynomial: 3x^4 - 2x^2 + x + 5
Modified polynomial: 10x^4 + x + 5

List容器的性能特点​

为了更好地理解何时应该选择list容器，以下是list与vector性能比较的表格：

操作listvector
随机访问元素O(n)O(1)
在开头插入/删除O(1)O(n)
在结尾插入/删除O(1)平均O(1)
在中间插入/删除O(1)O(n)
内存开销较高较低
提示

选择list还是vector取决于你的应用程序需求：

  • 如果需要频繁插入和删除元素，特别是在容器中间，选择list
  • 如果需要随机访问元素或者内存连续性，选择vector

总结​

C++ STL的list容器提供了双向链表的实现，它支持高效的插入和删除操作，但不支持随机访问。list在需要频繁插入、删除且不需要随机访问的场景中表现出色。

关键特性回顾：

  1. 实现了双向链表数据结构
  2. 支持常数时间的插入和删除操作
  3. 提供了特殊的操作，如sort()、merge()、unique()等
  4. 对迭代器的支持稳定（插入和删除操作不会导致已存在的迭代器失效，除非指向被删除的元素）
  5. 内存占用比vector等容器更高

练习题​

  1. 创建一个list，将1到10的整数添加到list中，然后删除所有奇数。
  2. 创建两个已排序的list，然后将它们合并成一个仍然有序的list。
  3. 创建一个包含重复元素的list，并使用unique()函数删除重复元素。
  4. 编写一个函数，接受一个list并将其反转，但不使用list的reverse()方法。
  5. 实现一个简单的音乐播放列表，使用list来存储歌曲，并支持添加、删除和播放操作。

延伸阅读​

  • C++ STL的其他容器（如deque、vector、forward_list）
  • list与其他容器的性能比较与适用场景分析
  • C++中更高级的list操作，如splice()和自定义分配器

通过理解和掌握list容器，你将能够更有效地解决需要频繁插入和删除操作的编程问题，并为你的C++工具箱增添一个强大的数据结构。