【3-22 list 详解STL C++ 】-EW帮帮网

先看代码，常用的就是代码中有的那些

#include <bits/stdc++.h>
using namespace std;
int main() {
	list<int> mylist;
	for(int i=0;i<5;i++){
		mylist.push_back(i);
		//TODO
	}
	for(const auto&i:mylist)
		cout<<i<<'\n';
		
	//fanzhuan
	reverse(mylist.begin(),mylist.end());
	cout<<" 	//fanzhuan\n ";
		for(const auto&i:mylist){
			cout<<i<<'\n';	
		//TODO
	}
	mylist.insert(++mylist.begin(),9);
	cout<<" 	//插入\n ";
		for(const auto&i:mylist){
			cout<<i<<'\n';	
		//TODO
	}	
	mylist.erase(++ mylist.begin(),--mylist.end());
	//删除了一个区间的数
	
	cout<<"size"<<mylist.size()<<'\n';
			for(const auto&i:mylist){
				cout<<i<<'\n';	
			//TODO
		}	
	return 0;
	
	
}

List的核心操作：如push_back, push_front, pop_back, pop_front等。
迭代器使用：如何遍历list，不同迭代器的区别（正向、反向）。
容量与大小管理：size(), empty(), clear()等方法，以及与vector在内存管理上的对比。
元素访问：通过迭代器和下标访问的效率差异，at()方法的使用。
插入与删除操作：在特定位置插入或删除元素的效率，erase方法的不同用法。
自定义类型支持：如何存储对象，需要重载哪些运算符。
性能比较：list在插入删除时的优势，以及随机访问的劣势。
实际应用案例：比如实现栈、队列，或者作为链表结构的使用场景。

一、核心成员函数详解（修正拼写错误后）

函数名称	功能说明	示例代码	注意事项
`push_back()`	在链表尾部插入元素	`lst.push_back(10);`	时间 O(1)
`push_front()`	在链表头部插入元素	`lst.push_front(20);`	时间 O(1)
`pop_back()`	移除链表尾部元素	`lst.pop_back();`	空容器调用会崩溃
`pop_front()`	移除链表头部元素	`lst.pop_front();`	同上
`size()`	返回链表元素个数	`int n = lst.size();`	O(1)
`empty()`	检查链表是否为空	`if (lst.empty()) {...}`	O(1)
`clear()`	清空所有元素	`lst.clear();`	O(n)
`front()`	获取第一个元素的引用	`int x = lst.front();`	空容器调用崩溃
`back()`	获取最后一个元素的引用	`int y = lst.back();`	同上
`begin()`	返回首元素的迭代器	`auto it = lst.begin();`
`end()`	返回尾元素后继的迭代器	`auto rit = lst.rbegin();`
`insert(pos, val)`	在位置 `pos` 前插入元素	`lst.insert(lst.begin()+1, 30);`	时间 O(n)
`erase(pos)`	删除位置 `pos` 的元素	`lst.erase(lst.begin()+1);`	同上

二、常用扩展函数（图片未提及）

函数名称	功能说明	示例代码
`emplace_back(val)`	在尾部直接构造元素（比 `push_back` 更高效）	`lst.emplace_back(100);`
`splice(pos, other)`	将另一个链表的元素插入到当前位置	`lst.splice(it, other_lst);`
`merge(other)`	合并两个有序链表（保持有序性）	`auto merged = merge(&a, &b);`
`remove(val)`	删除所有等于 `val` 的元素	`lst.remove(5);`
`reverse()`	反转链表顺序	`lst.reverse();`
`assign(range)`	用区间内的元素覆盖当前链表	`lst.assign(arr.begin(), arr.end());`

三、安全操作示例

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lst;

    // 安全插入
    lst.push_back(1);
    lst.push_front(2);

    // 避免空容器操作
    if (!lst.empty()) {
        cout << "首元素: " << lst.front() << endl; // 输出 2
        cout << "末元素: " << lst.back() << endl;   // 输出 1
    }

    // 使用迭代器安全删除
    if (lst.size() > 0) {
        auto it = lst.begin();
        lst.erase(it); // 删除第一个元素
    }

    return 0;
}

四、list vs vector 对比分析

特性	`list`（双向链表）	`vector`（动态数组）
内存分配	分散的内存块（指针开销大）	连续内存块（紧凑存储）
插入/删除效率	头部 O(1)，中间 O(1)（已知位置）	头部 O(n)，中间 O(n)
随机访问	O(n)（需遍历）	O(1)（直接索引）
内存占用	较高（每个节点存储指针）	较低（仅存储数据）
迭代器失效性	仅被删除元素的迭代器失效	所有迭代器可能失效（扩容时）
适用场景	频繁插入/删除元素	频繁随机访问元素

1. 实现LRU缓存（基于list和unordered_map）

#include <list>
#include <unordered_map>
using namespace std;

template<typename K, typename V>
class LRUCache {
private:
    list<pair<K, V>> cache; // 按访问顺序排列
    unordered_map<K, typename list<pair<K, V>>::iterator> pos_map;
    size_t capacity;

public:
    LRUCache(size_t cap) : capacity(cap) {}

    void get(K key) {
        auto it = pos_map.find(key);
        if (it == pos_map.end()) return;
        // 将节点移到头部（最近使用）
        cache.splice(cache.begin(), cache, it->second);
    }

    void put(K key, V value) {
        auto it = pos_map.find(key);
        if (it != pos_map.end()) {
            // 更新值并移到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
        } else {
            if (cache.size() >= capacity) {
                // 删除末尾元素（最久未使用）
                auto last = cache.end();
                --last;
                pos_map.erase(last->first);
                cache.pop_back();
            }
            // 插入新节点到头部
            auto newNode = cache.emplace_front(key, value);
            pos_map[key] = newNode;
        }
    }
};

2. 双向链表反转

void reverse_list(list<int>& lst) {
    auto it1 = lst.begin();
    auto it2 = lst.end();
    while (it1 != it2) {
        swap(*it1, *it2);
        ++it1;
        --it2;
    }
}

二、核心内容架构

1. 双向链表节点的底层实现

• 节点结构体解析：

template<typename T>
struct Node {
    T data;          // 存储元素
    Node* prev;       // 前驱指针
    Node* next;       // 后继指针
    Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

• 内存分配策略：
• 节点池技术：预分配内存块减少动态分配开销
• 分配器模式：与vector不同的allocator实现（如__gnu_pbds::node_allocator）

2. 关键成员函数源码剖析

• 构造函数：

list() : head(nullptr), tail(nullptr), size(0) {} // 空链表初始化
list(initializer_list<T> il) { ... } // 包含初始化列表的构造

• 动态扩容机制：
• 无需扩容：链表结构支持O(1)时间复杂度的头尾插入/删除
• 迭代器失效性：只有被删除元素的迭代器会失效，其他迭代器保持有效

3. 高效操作实现原理

• push_back()：

void push_back(const T& val) {
    Node* newNode = allocator.allocate(1);
    allocator.construct(newNode, val);
    if (empty()) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    ++size;
}

• insert(pos, val)：
• 定位节点：双向链表支持O(n)时间复杂度定位
• 指针调整：四步操作（新节点创建→前后指针重新链接）

4. 与vector的对比实验

操作	list	vector
头部插入	O(1)	O(n)
中间插入	O(1)（已知位置）	O(n)
随机访问	O(n)	O(1)
内存占用	较高（指针开销）	较低（紧凑存储）
适用场景	频繁插入/删除	频繁随机访问

三、代码示例与调试

1. 实现链表反转（迭代器版）

void reverse_list(list<int>& lst) {
    auto it1 = lst.begin();
    auto it2 = lst.end();
    while (it1 != it2) {
        swap(*it1, *it2);
        ++it1;
        --it2;
    }
}

2. 模拟LRU缓存淘汰算法

#include <list>
#include <unordered_map>

template<typename K, typename V>
class LRUCache {
private:
    list<pair<K, V>> cache; // 按访问顺序排列
    unordered_map<K, typename list<pair<K, V>>::iterator> pos_map;
    size_t capacity;

public:
    LRUCache(size_t cap) : capacity(cap) {}

    void get(K key) {
        auto it = pos_map.find(key);
        if (it == pos_map.end()) return;
        // 将访问的节点移到链表头部
        cache.splice(cache.begin(), cache, it->second);
    }

    void put(K key, V value) {
        auto it = pos_map.find(key);
        if (it != pos_map.end()) {
            // 存在则更新值并移动到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
        } else {
            if (cache.size() >= capacity) {
                // 淘汰末尾元素
                auto last = cache.end();
                --last;
                pos_map.erase(last->first);
                cache.pop_back();
            }
            // 插入新节点到头部
            auto newNode = cache.emplace_front(key, value);
            pos_map[key] = newNode;
        }
    }
};

四、进阶知识点

1. 内存泄漏检测技巧

• 使用Valgrind工具检测链表节点泄漏：

valgrind --leak-check=yes ./a.out

2. 自定义内存池优化

template<typename T>
class FastList : public std::list<T> {
private:
    struct Pool {
        T* buffer;
        size_t capacity;
        Pool(size_t cap) : capacity(cap) {
            buffer = static_cast<T*>(malloc(cap * sizeof(T)));
        }
        ~Pool() { free(buffer); }
    };
    Pool pool(1024); // 预分配1024个节点

    // 重载allocator
    using allocator_type = typename std::list<T>::allocator_type;
    allocator_type alloc;

public:
    FastList() : std::list<T>(alloc), pool(1024) {
        this->allocator = alloc; // 绑定自定义分配器
    }
};

五、学习建议

配套书籍推荐：
• 《Effective STL》Item 10：选择合适的容器
• 《C++ Primer》第16章：链表容器详解

实验环境配置：

g++ -std=c++17 -Wall -Wextra list_exercise.cpp -o list_exercise

常见错误总结：
• 误用operator[]访问链表（仅vector支持随机访问）
• 忘记释放自定义分配的内存（内存泄漏）
• 在迭代器失效后继续操作（未理解链表结构特性）

【3-22 list 详解STL C++ 】