当前位置：首页 > news >正文

list的两种设计

news 2025/5/6 11:00:57

1. 内存布局对比

(1) MSVC 的实现

cpp

class _List_node {_List_node* _Next;  // 指向下一个节点_List_node* _Prev;  // 指向前一个节点_Value_type _Value; // 存储的数据
};

特点：
- 每个节点包含两个指针和一个数据成员。
- Debug 模式：可能添加迭代器校验字段（如 _Container_proxy）。

(2) GCC 的实现

cpp

struct _List_node {_List_node* _M_next;_List_node* _M_prev;_Tp _M_data;
};

特点：
- 与 MSVC 类似，但字段命名不同。
- 无 Debug 模式额外开销。

2. 迭代器设计

(1) 迭代器本质

std::list 的迭代器 不是指针，而是封装了节点指针的类（因为链表节点在内存中不连续）。
支持双向移动（++、--），但不支持随机访问（如 it + 5），因此是双向迭代器。

(2) MSVC 的迭代器

cpp

class _List_iterator {_List_node* _Ptr; // 指向当前节点// Debug 模式下可能包含校验信息
public:// 重载操作符（如 *、->、++ 等）
};

(3) GCC 的迭代器

cpp

struct _List_iterator {_List_node* _M_node;// 直接操作节点指针
};

1. `std::list` 的核心成员（MSVC vs GCC）

(1) MSVC 的实现

cpp

template<class _Ty, class _Alloc = allocator<_Ty>>
class list {
private:_Node _Myhead;          // 哨兵节点（双向链表的头尾环）size_t _Mysize;         // 当前元素数量_Alloc _Alnode;         // 节点分配器// Debug 模式下可能包含迭代器校验字段
};

关键成员：
- _Myhead：哨兵节点（不存储数据），其 _Next 指向首个真实节点，_Prev 指向末尾节点。
- _Mysize：缓存当前元素数量（使 size() 操作为 O(1)）。
- _Alnode：节点内存分配器（默认为 std::allocator）。

(2) GCC 的实现

cpp

template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class _List_base {
protected:_List_node_base _M_node; // 哨兵节点_Alloc _M_get_Node_allocator(); // 节点分配器
};template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class list : protected _List_base<_Tp, _Alloc> {size_t _M_size;         // 当前元素数量
};

关键成员：
- _M_node：哨兵节点（类似 MSVC 的 _Myhead）。
- _M_size：缓存元素数量（C++11 起标准要求 size() 为 O(1)）。

3. 哨兵节点（Sentinel Node）的作用

带头双向循环链表：
list 的内部实现是一个带哨兵节点的双向循环链表，其成员关系如下：
```
[哨兵] <-→ [节点1] <-→ [节点2] <-→ ... <-→ [哨兵]
```
优势：
- begin() = 哨兵的 _Next，end() = 哨兵自身。
- 插入/删除操作无需特殊处理头尾边界。