網站首頁 編程語言 正文
list 概述
相比于 vector 的連續線性空間，list 采用的是零散的空間，它的好處是每次插入或刪除一個元素，就配置或釋放一個元素空間。
list 是支持常數時間從容器任何位置插入和移除元素容器，但不支持快速隨機訪問。list 通常實現為雙向鏈表，與 forward_list 相比，list 的迭代器可以向前移動，但也因此需要在節點中多開辟一個指針變量，在空間上效率稍低。
接口總覽
namespace qgw {
/// @brief list 中每個節點
/// @tparam T 節點存儲的數據的類型
template <class T>
struct _list_node {
_list_node(const T& data = val()); // 節點類的構造函數
_list_node<T>* _prev; // 指向前一節點
_list_node<T>* _next; // 指向后一節點
T _data; // 存儲節點數據
};
/// @brief list 的迭代器
/// @tparam T list 數據的類型
/// @tparam Ref 數據的引用類型
/// @tparam Ptr 數據的指針類型
template <class T, class Ref, class Ptr>
struct _list_iterator {
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, Ref, Ptr> self;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef _list_node<T> list_node;
// 構造函數
_list_iterator(list_node* node = nullptr);
// 各種運算符重載
bool operator==(const self& x) const;
bool operator!=(const self& x) const;
reference operator*() const;
pointer operator->() const;
self& operator++();
self operator++(int);
self& operator--();
self operator++(int);
list_node* _node; // 指向對應的 list 節點
};
template <class T>
class list {
public:
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef _list_node<T> list_node;
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
public:
// 默認成員函數
list();
list(const list<T>& other);
list<T>& operator=(const list<T>& other);
~list();
// 元素訪問
reference front();
reference back();
// 迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
// 容量
bool empty() const;
size_t size() const;
// 修改器
void clear();
iterator insert(iterator pos, const T& val);
void push_front(const T& val);
void push_back(const T& val);
iterator erase(iterator pos);
void pop_front();
void pop_back();
void swap(list& other);
// 操作
void splice(iterator pos, list& other);
void splice(iterator pos, list& other, iterator it);
void splice(iterator pos, list& other, iterator first, iterator last);
void merge(list& other);
void remove(const T& value);
void reverse();
void unique();
private:
list_node* _node; // 指向鏈表頭節點
};
}
list 的節點
list 的節點我們設計成一個 _list_node 類，里面有三個成員變量，分別為前后指針和數據。
它的構造函數將數據初始化為給定數據，再將前后指針初始化為空即可。
/// @brief 節點類的構造函數
/// @param data 用來構造節點的初值
_list_node(const T& data = T())
: _data(data) {
_prev = nullptr;
_next = nullptr;
}默認成員函數
默認構造函數
SGI list 不僅是一個雙向鏈表，還是一個帶頭的循環鏈表。
/// @brief 構造一個空鏈表
list() {
_node = new list_node; // 創建一個頭節點
_node->_prev = _node; // 前面指向自己
_node->_next = _node; // 后面指向自己
}析構函數
list 的析構函數，先調用 clear 釋放數據資源，再 delete 掉頭節點即可。
/// @brief 釋放資源
~list() {
clear();
delete _node;
_node = nullptr;
}
拷貝構造函數
用另一容器創建新對象。
先申請一個頭節點，然后遍歷 other 容器，將 other 中的數據逐一尾插到 *this 中。
/// @brief 用給定容器初始化
/// @param other 用來初始化的容器
list(const list<T>& other) {
_node = new list_node;
_node->_next = _node;
_node->_prev = _node;
for (const auto& e : other) {
push_back(e);
}
}
復制賦值函數
先創建給定容器的拷貝 tmp，然后交換 *this 和 tmp，最后返回 *this。
/// @brief 替換容器內容
/// @param other 用作數據源的另一容器
/// @return *this
list<T>& operator=(const list<T>& other) {
// tmp 出了作用域就銷毀了
list<T> tmp(other);
swap(tmp);
// 返回引用可以連續賦值
return *this;
}
list 的迭代器
list 的節點在內存中不是連續存儲的，因此不能使用原生指針作為 list 的迭代器。list 的迭代器必須有能力指向 list 的節點，并能夠正確的遞增、遞減、取值、成員存取等操作。正確的操作是指：遞增時指向下一節點，遞減時指向上一節點，取值時取的是節點的數據值，成員取用的是節點的成員。
由于 STL list 是一個雙向鏈表（double linked-list），迭代器必須具備前移、后移的能力，所以 list 提供的是 Bidirectional Iterators。
構造函數
list 的迭代器中成員變量只有一個節點指針，將其指向給定節點即可。
/// @brief list 迭代器的構造函數
/// @param node 用來構造的節點
_list_iterator(list_node* node = nullptr) {
_node = node;
}
operator==
判斷兩迭代器指向的節點是否為同一個，直接比較迭代器中節點的指針即可。切記不能比較指針中的值，因為不同節點的值可能相同。
/// @brief 判斷兩迭代器指向的節點是否相同
/// @param x 用來比較的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const {
return _node == x._node;
}
operator!=
!= 的比較方法和 == 一樣。
/// @brief 判斷兩迭代器指向的節點是否不同
/// @param x 用來比較的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const {
return _node != x._node;
}
operator*
迭代器是模仿指針的，讓我們可以像使用指針一樣。因此可以對迭代器進行解引用操作，該操作得到的是迭代器中節點指針指向的數據，并且返回引用，因為有可能修改該數據。
/// @brief 獲取指向節點中的數據值
/// @return 返回指向節點數據的引用
reference operator*() const {
return _node->_data;
}
operator->
-> 運算符的重載稍顯復雜，讓我們先看下面這個場景。
也就是 list 中存儲的是自定義類型，自定義類型中又有多個成員變量，我們想取出指定的成員變量，當然這里用 . 也可以做到。
// 有一個學生類，里面有姓名和學號兩個成員
struct Stu {
string name;
string id;
};
list<Stu> s;
Stu s1 = { "qgw", "001" };
Stu s2 = { "wlr", "002" };
s.push_back(s1);
s.push_back(s2);
list<Stu>::iterator ptr = s.begin();
// 輸出第一個學生的姓名和學號
cout << (*ptr).name << endl;
cout << s.begin()->id << endl;
/// @brief 獲取節點中數據的地址
/// @return 返回節點指向的數據的地址
pointer operator->() const {
return &(operator*());
}
看到這你可能會疑惑，operator-> 返回的是節點的數據的地址，也是說上面 s.begin()-> 得到的是一個地址，那這條語句是怎么執行的？
實際上這里確實應該有兩個箭頭像這樣 s.begin()->->id，但這種方式的可讀性太差了，所以編譯器對此做了優化，在編譯為我們添加一個箭頭。
operator++
operator++ 運算符的作用十分清晰，就是讓迭代器指向鏈表中下一節點。
前置實現的思路是：通過迭代器中的節點指針找到下一節點，然后賦值給迭代器中的節點指針。
后置實現的思路是：先保存當前位置迭代器，然后調用前置 ++，最后返回臨時變量。
需要注意的是：前置 ++ 返回的是前進后迭代器的引用，后置 ++ 返回的是一個臨時變量。
/// @brief 前置++
/// @return 返回前進一步后的迭代器
self& operator++() {
_node = _node->_next;
return *this;
}
/// @brief 后置++
/// @param 無作用，只是為了與前置 ++ 進行區分，形成重載
/// @return 返回當前的迭代器
self operator++(int) {
self tmp = *this;
// 直接調用前置 ++
++(*this);
return tmp;
}
operator--
前置實現的思路是：通過迭代器中的節點指針找到前一節點，然后賦值給迭代器中的節點指針。
后置實現的思路是：先保存當前位置迭代器，然后調用前置 --，最后返回臨時變量。
/// @brief 前置 --
/// @return 返回后退一步后的迭代器
self& operator--() {
_node = _node->_prev;
return *this;
}
/// @brief 后置 --
/// @param 無作用，只是為了與前置 -- 進行區分，形成重載
/// @return 返回當前的迭代器
self operator--(int) {
self tmp = *this;
--(*this);
return tmp;
}
元素訪問
front
front 獲取第一個元素的引用，直接用 begin 獲取指向第一個元素的迭代器，再解引用即可。
/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front() {
return *begin();
}
back
end 獲取最后一個元素的引用，先用 end 獲取最后一個元素下一位置的迭代器，再回退一步，然后解引用就可以了。
/// @brief 返回容器中最后一個元素的引用
/// @return 最后元素的引用
reference back() {
return *(--end());
}
迭代器
在 begin 和 end 實現之前，我們先來看下 list 的示意圖，下圖為有 3 個元素的鏈表：
begin
begin 獲取的是首元素的迭代器，根據上圖，begin 的實現也就非常清晰了，直接返回頭節點的下一位置即可。
/// @brief 返回指向 list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {
// 根據節點指針構造迭代器
return iterator(_node->_next);
}
// const 版本供 const 容器使用
const_iterator begin() const {
return const_iterator(_node->_next);
}
end
end 獲取的是最后一個元素下一個位置的迭代器，根據上圖就是 _node 所指向的節點。
/// @brief 返回指向 list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() {
// 調用 iterator 構造函數
return iterator(_node);
}
const_iterator end() const {
return const_iterator(_node);
}
容量
empty
begin 和 end 指向相同，說明鏈表此時只有一個頭節點，鏈表為空。
/// @brief 檢查容器是否無元素
/// @return 若容器為空則為 true，否則為 false
bool empty() const {
return begin() == end();
}
size
size 函數的作用是返回容器中元素的數量。
在 C++ 11 前，該函數的復雜度可能是常數的，也可能是線性的。從 C++ 11 起該函數的復雜度為常數。
下面代碼的時間復雜度是線性的，要想改成常數也很簡單，只需要在 list 中開辟一個成員變量記錄個數即可。
/// @brief 返回容器中的元素數
/// @return 容器中的元素數量
size_t size() const {
size_t sz = 0;
auto it = begin();
while (it != end()) {
++it;
++sz;
}
return sz;
}
修改器
insert
下圖為：只有 0、1 兩個元素的鏈表，在 1 之前插入元素值為 2 的節點的示意圖。
插入的思路比較清晰：
1.插入節點的 _next 指向 pos 位置的節點
2.插入節點的 _prev 指向 pos 前一位置的節點
3.pos 前一位置的節點的 _next 指向插入的節點
4.pos 位置節點的 _prev 指向插入的節點
/// @brief 插入元素到容器中的指定位置
/// @param pos 將內容插入到 pos 之前
/// @param val 要插入的元素值
/// @return 指向被 插入 val 的迭代器
iterator insert(iterator pos, const T& val) {
list_node* tmp = new list_node(val); // 創建要插入的節點
tmp->_next = pos._node; // (1)
tmp->_prev = pos._node->_prev; // (2)
(pos._node->_prev)->_next = tmp; // (3)
pos._node->_prev = tmp; // (4)
return tmp;
}
push_front
push_front 的作用是在第一個元素之前插入一個節點，直接調用 insert 在 begin 之前插入就行。
/// @brief 添加給定元素 val 到容器起始
/// @param val 要添加的元素值
void push_front(const T& val) {
insert(begin(), val);
}
push_back
push_back 的作用是在容器的最后添加一個節點，直接調用 insert 在 end 之前插入就行。
/// @brief 添加給定元素 val 到容器尾
/// @param val 要添加的元素值
void push_back(const T& val) {
insert(end(), val);
}
erase
下圖為：有三個元素 0、1、2 的鏈表，刪除 pos 指向節點（值為 1）的示意圖。
刪除的思路也很清晰：
1.將 pos 前一節點的 _next 指針指向 pos 的下一節點
2.將 pos 下一節點的 _prev 指針指向 pos 的前一節點
3.delete 釋放掉 pos 所指向的節點
/// @brief 從容器擦除指定的元素
/// @param pos 指向要移除的元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase(iterator pos) {
list_node* nextNode = pos._node->_next; // 記錄 pos 指向節點的下一節點
list_node* prevNode = pos._node->_prev; // 記錄 pos 指向節點的前一節點
prevNode->_next = nextNode; // (1)
nextNode->_prev = prevNode; // (2)
delete (pos._node);
return (iterator)nextNode;
}
pop_front
pop_front 移除容器第一個元素，也就是 begin 指向的節點。
/// @brief 移除容器首元素
void pop_front() {
erase(begin());
}
pop_back
pop_back 移除容器最后一個節點，也就是 end 指向的前一個節點。
/// @brief 移除容器的末元素
void pop_back() {
erase(--end());
}
clear
clear 用于清空容器所有數據，不清理頭節點。
采用遍歷的方式調用 erase 刪除每一個節點。
/// @brief 從容器擦除所有元素
void clear() {
iterator it = begin();
while (it != end()) {
it = erase(it);
}
}
swap
swap 用來交換兩個 list 容器，不用 list 中每個元素的值，直接交換 _node 指針即可。
/// @brief 將內容與 other 的交換
/// @param other 要與之交換內容的容器
void swap(list& other) {
std::swap(_node, other._node);
}
操作
splice
在實現該函數之前，先來看下 list 內部的一個函數 transfer。
list 內部提供一個遷移操作（transfer）：將某連續范圍的元素遷移都某個特定位置之前。
這個函數比上面所寫的要復雜的多，要對著圖仔細思考。
/// @brief 將 [first, last) 范圍的所有元素移動到 pos 之前
/// @param pos 將內容移動到 pos 之前
/// @param first 范圍起始位置
/// @param last 范圍結束位置
void transfer(iterator pos, iterator first, iterator last) {
if (pos != last) {
last._node->_prev->_next = pos._node; // (1)
first._node->_prev->_next = last._node; // (2)
pos._node->_prev->_next = first._node; // (3)
list_node* tmp = pos._node->_prev; // (4)
pos._node->_prev = last._node->_prev; // (5)
last._node->_prev = first._node->_prev; // (6)
first._node->_prev = tmp; // (7)
}
}有了上面的函數，splice 的實現也就非常簡單了，下面共有三個重載實現：
根據要轉移的元素選擇調用不同的函數。
/// @brief 將 other 接合于 pos 所指位置之前，兩者不能是同一 list
/// @param pos 將內容插入到它之前
/// @param other 要從它轉移內容的另一容器
void splice(iterator pos, list& other) {
if (!other.empty()) {
transfer(pos, other.begin(), other.end());
}
}
/// @brief 將 it 所指元素接合到 pos 所指位置之前
/// @param pos 將內容插入到它之前
/// @param other 要從它轉移內容的另一容器
/// @param it 從 other 轉移到 *this 的元素
void splice(iterator pos, list& other, iterator it) {
// 取得一個 [i, j) 的范圍，使得能調用 transfer
iterator j = it;
++j;
// 檢查是否有必要執行
// pos == it 時說明 pos 和 it 指向的是同一節點
// pos == j 時說明，it 剛好在 pos 之前
if (pos == it || pos == j) {
return;
}
transfer(pos, it, j);
}
/// @brief 將 [first, last) 內的所有元素接合于 pos 所指位置之前
/// @param pos 將內容插入到它之前
/// @param first 起始位置
/// @param last 結束位置
void splice(iterator pos, list& other, iterator first, iterator last) {
if (first != last) {
transfer(pos, first, last);
}
}
merge
merge 函數和歸并排序中的合并操作類似，該函數的作用是：合并兩個已遞增排序的鏈表。
/// @brief 合并兩個遞增鏈表，合并到 *this 上
/// @param other 要合并的另一容器
void merge(list& other) {
iterator first1 = begin();
iterator end1 = end();
iterator first2 = other.begin();
iterator end2 = other.end();
while (first1 != end1 && first2 != end2) {
if (*first2 < *first1) {
iterator next = first2;
transfer(first1, first2, ++next);
first2 = next;
} else {
++first1;
}
}
if (first2 != end2) {
// 將 other 鏈表剩余元素合并到 *this 中
transfer(first1, first2, end2);
}
}
remove
remove 用來刪除 list 中值等于 val 的元素，直接遍歷鏈表，找到就刪除。
/// @brief 移除等于 val 元素
/// @param val 要移除的元素的值
void remove(const T& val) {
iterator first = begin();
iterator last = end();
while (first != last) {
iterator next = first;
++next;
if (*first == val) {
erase(first);
}
first = next;
}
}
reverse
reverse 的作用是逆轉容器中的元素順序。
該函數的思路簡單，從第 2 個元素開始，以次頭插到鏈表頭部。
/// @brief 將 *this 的內容逆置
void reverse() {
// 空鏈表或只有一個元素直接返回
if (_node->_next == _node || _node->_next->_next == _node) {
return;
}
iterator first = begin();
++first;
while (first != end()) {
iterator old = first; // 第一次循環時指向第 2 個元素
++first; // 第一次循環時指向第 3 個元素
transfer(begin(), old, first);
}
}
unique
unique 用來移除數值相同的連續元素，只保留一個。
該函數利用的是雙指針的思想，first 和 next 分別指向前后兩個元素，相同就刪除后一個。
/// @brief 移除數值相同的連續元素
void unique() {
iterator first = begin();
iterator last = end();
if (first == last) {
return;
}
iterator next = first;
while (++next != last) {
// 此時 next 指向 first 下一個節點
if (*first == *next) {
// 連續的相同，就刪除后一個
erase(next);
} else {
// 不相同 first 向 end 移動
first = next;
}
// 使 next 再次指向 first
// 這樣再進 while 時，++next 又使 next 指向 first 下一個
next = first;
}
}
原文鏈接：https://blog.csdn.net/qq_40080842/article/details/128634865
相關推薦
- 2022-03-14 關于log4j日志擴展---自定義PatternLayout（log4j自定義日志級別）
- 2022-08-04 Docker?Desktop更改鏡像存儲位置的實現_docker
- 2022-02-07 ifconfig顯示沒有網卡，nmtui運行提示NetworkManaer 未運行
- 2022-09-09 詳解C語言中動態內存管理及柔性數組的使用_C 語言
- 2022-08-20 python3?最常用的三種裝飾器語法匯總_python
- 2022-08-05 RedisConfig 配置文件
- 2022-04-25 turtle的基礎使用之python?turtle遞歸繪圖_python
- 2023-03-05 Go語言學習之golang-jwt/jwt的教程分享_Golang
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速