您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

C++ STL 源碼深度解析：slist 單向鏈表實現

編輯：C++ 入門

SGI STL slist 單向鏈表源碼解析

slist 是 SGI STL 提供的單向鏈表容器，不屬於 C++ 標準。相比雙向鏈表 list，slist 節點更小、插入刪除特定位置效率更高，但只能正向遍歷。

核心節點結構

struct _Slist_node_base { _Slist_node_base* _M_next; };
template <class _Tp>
struct _Slist_node : public _Slist_node_base { _Tp _M_data; };

關鍵基礎操作

插入：__slist_make_link 在指定節點後插入新節點，O(1)
查找前驅：__slist_previous 從頭遍歷找前驅，O(n)
拼接：__slist_splice_after 將一段鏈表移動到指定位置後，O(1)
反轉：__slist_reverse 就地反轉鏈表，O(n)

迭代器設計

前向迭代器 _Slist_iterator，支援 ++ 操作。before_begin() 返回頭節點前的虛擬位置，便於統一使用 insert_after/erase_after。

容器核心接口

// 插入操作統一用 insert_after
iterator insert_after(iterator __pos, const value_type& __x);
void insert_after(iterator __pos, size_type __n, const value_type& __x);
template <class _InIter>
void insert_after(iterator __pos, _InIter __first, _InIter __last);

// 刪除操作統一用 erase_after
iterator erase_after(iterator __pos);
iterator erase_after(iterator __before_first, iterator __last);

// 兼容性接口（內部調用前驅查找）
iterator insert(iterator __pos, const value_type& __x);
iterator erase(iterator __pos);