深入理解C++中的list容器：介绍、使用与实现-EW帮帮网

list<int> l1;          // 空list
list<int> l2(5, 10);   // 5个元素，每个初始化为10
list<int> l3(l2);      // 拷贝构造
list<int> l4(arr, arr + sizeof(arr)/sizeof(arr[0])); // 范围构造

`2.2 迭代器使用`

list支持双向迭代器，包括正向和反向迭代器：

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

// 正向遍历
for(auto it = myList.begin(); it != myList.end(); ++it) {
    cout << *it << " ";
}

// 反向遍历
for(auto rit = myList.rbegin(); rit != myList.rend(); ++rit) {
    cout << *rit << " ";
}

注意：begin()指向第一个元素，end()指向最后一个元素的下一个位置；rbegin()指向最后一个元素，rend()指向第一个元素的前一个位置。

`2.3 容量操作`

if(myList.empty()) {
    cout << "List is empty";
}
cout << "List size: " << myList.size();

`2.4 元素访问`

cout << "First element: " << myList.front();
cout << "Last element: " << myList.back();

`2.5 修改操作`

list提供了丰富的修改接口：

myList.push_front(0);    // 头部插入
myList.pop_front();      // 头部删除
myList.push_back(6);     // 尾部插入
myList.pop_back();       // 尾部删除

auto it = myList.begin();
advance(it, 2);          // 移动到第3个位置
myList.insert(it, 99);    // 在指定位置插入
myList.erase(it);        // 删除指定位置元素

myList.clear();          // 清空list

`2.6 迭代器失效问题`

list的迭代器在插入操作时不会失效，但在删除操作时，指向被删除元素的迭代器会失效： // 错误示例

auto it = myList.begin();
while(it != myList.end()) {
    myList.erase(it);  // it失效后再使用
    ++it;              // 未定义行为
}

正确写法1

while(it != myList.end()) {
    it = myList.erase(it);  // erase返回下一个有效迭代器
}

// 正确写法2
while(it != myList.end()) {
    myList.erase(it++);  // 使用后置++，在删除前移动迭代器
}

`3. list的模拟实现`

理解list的内部实现有助于更深入地使用它。下面简要介绍关键实现要点。

`3.1 节点结构`

template<class T>
struct ListNode {
    T _data;
    ListNode<T>* _prev;
    ListNode<T>* _next;
    
    ListNode(const T& val = T())
        : _data(val), _prev(nullptr), _next(nullptr) {}
};

`3.2 迭代器实现`

list的迭代器需要对原生指针进行封装，重载相关操作符：

template<class T>
class ListIterator {
public:
    typedef ListNode<T> Node;
    typedef ListIterator<T> Self;
    
    Node* _node;
    
    ListIterator(Node* node) : _node(node) {}
    
    T& operator*() { return _node->_data; }
    T* operator->() { return &_node->_data; }
    
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }
    
    Self operator++(int) {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }
    
    // 其他操作符重载...
};

`3.3 反向迭代器`

反向迭代器可以通过包装正向迭代器来实现：

template<class Iterator>
class ReverseListIterator {
    Iterator _it;
public:
    ReverseListIterator(Iterator it) : _it(it) {}
    
    auto& operator*() {
        Iterator tmp = _it;
        --tmp;
        return *tmp;
    }
    
    ReverseListIterator& operator++() {
        --_it;
        return *this;
    }
    
    // 其他操作符重载...
};

`4. list与vector的对比`

`特性`	`vector`	`list`
`底层结构`	`动态数组`	`双向链表`
`随机访问`	`O(1)`	`O(n)`
`插入/删除`	`尾部O(1)，其他位置O(n)`	`任意位置O(1)`
`空间利用率`	`高(连续内存)`	`低(内存碎片)`
`缓存友好性`	`高`	`低`
`迭代器失效`	`插入/删除可能导致全部失效`	`仅删除导致当前迭代器失效`
`适用场景`	`随机访问频繁，修改少`	`频繁插入删除，随机访问少`

总结

list是C++中一个非常重要的容器，特别适合需要频繁在任意位置插入和删除元素的场景。虽然它在随机访问方面不如vector高效，但在特定场景下能提供更好的性能。理解list的内部实现机制和迭代器失效规则，可以帮助开发者避免常见错误，编写出更健壮的代码。

在实际开发中，应根据具体需求选择合适的容器。如果需要频繁随机访问，vector是更好的选择；如果需要频繁在中间位置插入删除，list则更为合适。

深入理解C++中的list容器：介绍、使用与实现

前言

`1. list的基本介绍`

`2. list的基本使用`

`2.1 构造函数`