網站首頁 編程語言 正文
目錄
list基本介紹和使用
list模擬實現
list的迭代器：
理解：
const_iterator問題：
list迭代器失效問題：
list的反向迭代器
理解：?
reverse_iterator.h
反向迭代器的operator*實現：
operator->()?
vector和list的比較
list基本介紹和使用
list - 帶頭雙向循環鏈表。
對比vector，因為list是由一個個結點連接而成的，致使list
1. 不支持元素的隨機訪問，即沒有operator[]，因為效率低。訪問元素front back
2. 沒有capacity的概念，內存允許的情況下，可以無限申請節點并擴展
3. 支持push_front pop_front，使得list可以作為queue的適配容器
4. 最大的優勢是在任意位置插入刪除都可以在O(1)時間完成
學習成員函數 見https://cplusplus.com/reference/list/list/
list模擬實現
#ifndef STL_LIST_H
#define STL_LIST_H
#include <cstddef> // size_t
#include <cassert>
#include <iostream>
#include "reverse_iterator.h"
//using namespace std;
namespace yzl
{
template<class T>
struct list_node // list內部使用的結點類型
{
public:
T _data;
list_node<T>* _next;
list_node<T>* _prev;
public:
list_node(const T& data = T()) // 結點的默認構造函數
: _data(data), _next(nullptr), _prev(nullptr)
{ }
// ~list_node() = default;
// // 拷貝構造，其實沒必要
// list_node(const list_node<T>& node)
// : _data(node._data), _next(node._next), _prev(node._prev) // 淺拷貝
// { }
// // 賦值運算符重載，也沒必要
// list_node<T>& operator=(const list_node<T>& node) // 淺拷貝
// {
// _data = node._data;
// _prev = node._prev;
// _next = node._next;
// return *this;
// }
};
// 說真的，只是對結點指針的一個封裝罷了，構造函數也是通過一個結點指針即可構造出一個迭代器。
// 對于迭代器的操作，其實也就是++ -- 然后解引用。目前的操作就是這些，之后再有再補充吧。
template<class T, class Ref, class Ptr> // T& T* or const T& const T*
class __list_iterator // 成員就是一個結點指針
{
public:
typedef list_node<T> Node; // 這是一個結構體，結點。Node就是一個結點結構體。
typedef __list_iterator<T, Ref, Ptr> iterator;
typedef std::bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef ptrdiff_t difference_type;
public:
Node* _node; // 這個迭代器類型有一個數據成員，是結點指針。
public:
__list_iterator(Node* node)
:_node(node)
{ }
// 這個類型的實例化對象本身不支持解引用操作，operator*賦予了它解引用之后的操作。
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
// return &(_node->_data);
}
bool operator!=(const iterator& it)
{
return _node != it._node;
}
bool operator==(const iterator& it)
{
return _node == it._node;
}
// 思考一下迭代器++，普通迭代器和const迭代器其實都可以++
iterator& operator++() // 前置
{
_node = _node->_next;
return *this;
}
iterator operator++(int) // 后置
{
iterator tmp = *this;
this->_node = this->_node->_next;
return tmp;
}
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
iterator operator--(int)
{
iterator tmp(*this);
this->_node = this->_node->_prev;
return tmp;
}
};
// list<int> ls;
template<class T>
class list
{
private:
typedef list_node<T> Node;
Node* _head; // list_node<int>* _head;
public:
// 說真的，關于list的迭代器，你只需要實現begin end這一系列的即可，還要讓它的返回值支持++ 解引用操作，這就夠了，說真的。
typedef __list_iterator<T, T&, T*> iterator; // 這個結構體別名為迭代器，本身是不支持解引用操作的。
//typedef const __list_iterator<T> const_iterator; // 你這里const修飾的是迭代器類型，他有結點指針數據成員，const使得結點指針不能改變。
// 但是根本上，const迭代器是指不能修改*迭代器所指的值。而不是迭代器本身。
typedef __list_iterator<T, const T&, const T*> const_iterator;
// typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;
// typedef __list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;
typedef __reverse_iterator<__list_iterator<T, T&, T*>, T&, T*> reverse_iterator;
typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
const_iterator cbegin() const
{
return const_iterator(_head->_next);
}
const_iterator cend() const
{
return const_iterator(_head);
}
reverse_iterator rbegin()
{
return reverse_iterator(end());
}
reverse_iterator rend()
{
return reverse_iterator(begin());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin());
}
const_reverse_iterator crbegin() const
{
return const_reverse_iterator(end());
}
const_reverse_iterator crend() const
{
return const_reverse_iterator(begin());
}
public:
list() { // list的默認構造函數
_head = new Node; // 調用list_node<T>的默認構造函數，頭節點里面的data是隨機數
_head->_next = _head;
_head->_prev = _head;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
template<class InputIterator>
list(InputIterator first, InputIterator last)
{
empty_init();
while(first != last)
{
push_back(*first);
++first;
}
}
// 拷貝構造函數現代寫法
list(const list<T>& ls)
{
empty_init();
list<T> tmp(ls.begin(), ls.cend());
this->swap(tmp);
}
// list(const list<T>& ls)
// :_head(new Node)
// {
// _head->_next = _head;
// _head->_prev = _head;
// for(auto&i:ls)
// {
// Node* newnode = new Node(i);
// Node* tail = _head->_prev;
// tail->_next = newnode;
// newnode->_prev = tail;
// newnode->_next = _head;
// _head->_prev = newnode;
// }
// }
// ls1 = ls2
list<T>& operator=(list<T> ls)
{
this->swap(ls);
return *this;
}
public:
void push_back(const T& val)
{
Node* newnode = new Node(val);
Node* tail = _head->_prev;
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
void push_front(const T& val)
{
Node* newnode = new Node(val);
Node* first = _head->_next;
_head->_next = newnode;
newnode->_prev = _head;
newnode->_next = first;
first->_prev = newnode;
}
iterator insert (iterator position, const T& val)
{
Node* cur = position._node;
Node* prev = cur->_prev;
Node* newnode = new Node(val);
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
iterator erase(iterator position)
{
assert(position._node != _head);
Node* cur = position._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
void pop_back()
{
assert(size() > 0);
Node* tail = _head->_prev;
Node* newtail = tail->_prev;
newtail->_next = _head;
_head->_prev = newtail;
delete tail;
}
void pop_front()
{
assert(size() > 0);
Node* front = _head->_next;
Node* newfront = _head->_next->_next;
_head->_next = newfront;
newfront->_prev = _head;
delete front;
}
void show() const
{
Node* tmp = _head->_next;
while(tmp != _head)
{
std::cout<<tmp->_data<<" ";
tmp = tmp->_next;
}
std::cout << std::endl;
}
void swap(list<T>& ls)
{
std::swap(_head, ls._head);
}
size_t size() const
{
size_t ret = 0;
Node* tmp = _head->_next;
while(tmp != _head)
{
++ret;
tmp = tmp->_next;
}
return ret;
}
bool empty() const
{
return _head->_next == _head;
}
T& front()
{
assert(size() > 0);
return _head->_next->_data;
}
const T& front() const
{
assert(size() > 0);
return _head->_next->_data;
}
T& back()
{
assert(size() > 0);
return _head->_prev->_data;
}
const T& back() const
{
assert(size() > 0);
return _head->_prev->_data;
}
void clear() // const不能使用
{
// auto it = begin();
// while(it != end())
// {
// it = it = erase(it);
// }
Node* it = cbegin()._node;
while(it != cend()._node)
{
Node* prev = it->_prev;
Node* next = it->_next;
prev->_next = next;
next->_prev = prev;
delete it;
it = next;
}
}
};
}
#endif //STL_LIST_Hlist_node 是結點類，存儲data next prev ，很清楚。
而list，只有一個數據成員，就是一個頭節點指針? list_node<T>* _head;
先不談list的迭代器。push_back, pop_back, push_front pop_front size front back等都是帶頭雙向循環鏈表的基本套路。
list的迭代器：
理解：
我們知道，vector的迭代器是原生指針，這是因為vector底層存儲的緣故，原生指針完全符合迭代器的要求。
那么，list是一個雙向帶頭循環鏈表，由一個個結點組成，結點指針顯然不能滿足迭代器的要求， 因為解引用后是結點實例化對象list_node<T>，而不是數據data。結點指針++也不是下一個結點，因為結點的存儲不連續。
不過，基于C++的特性：封裝和運算符重載，我們可以把結點指針進行封裝，再使用運算符重載重新定義其解引用和++的操作，使其符合迭代器的要求。于是，有了__list_iterator
template<class T, class Ref, class Ptr> // T& T* or const T& const T*
class __list_iterator // 成員就是一個結點指針
{
public:
typedef list_node<T> Node; // 這是一個結構體，結點。Node就是一個結點結構體。
typedef __list_iterator<T, Ref, Ptr> iterator;
public:
Node* _node; // 這個迭代器類型有一個數據成員，是結點指針。
public:
__list_iterator(Node* node)
:_node(node)
{ }
// 這個類型的實例化對象本身不支持解引用操作，operator*賦予了它解引用之后的操作。
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
// return &(_node->_data);
}
bool operator!=(const iterator& it)
{
return _node != it._node;
}
bool operator==(const iterator& it)
{
return _node == it._node;
}
// 思考一下迭代器++，普通迭代器和const迭代器其實都可以++
iterator& operator++() // 前置
{
_node = _node->_next;
return *this;
}
iterator operator++(int) // 后置
{
iterator tmp = *this;
this->_node = this->_node->_next;
return tmp;
}
iterator& operator--()
{
_node = _node->_prev;
return *this;
}
iterator operator--(int)
{
iterator tmp(*this);
this->_node = this->_node->_prev;
return tmp;
}
};其實非常簡單，這個迭代器類型就是對結點指針的一個封裝。和list一樣，它只有一個數據成員，即Node*? ?(typedef?list_node<T> Node)?
然后進行一些運算符重載，比如operator* operator++ operator==，這里也是C++的基礎知識，因為結點指針不能直接做迭代器，所以將其封裝，但是封裝好的類__list_iterator對象本身并不支持解引用 ++ 操作，C++的運算符重載特性使得可以定義這個類對象的某些操作。? 之后就可以使其像迭代器一樣使用，即__list_iterator的對象是list的一個迭代器。
typedef __list_iterator<T, T&, T*> iterator; // 這個結構體別名為迭代器，本身是不支持解引用操作的。
typedef __list_iterator<T, const T&, const T*> const_iterator;
在list內進行如上typedef即可。?
const_iterator問題：
//typedef const __list_iterator<T> const_iterator; // 你這里const修飾的是迭代器類型，他有結點指針數據成員，const使得結點指針不能改變。
如何區分list的iterator 和 const_iterator是一個問題，首先我們需要明確const_iterator需要什么特殊性質：解引用后的值是const的，且是引用性質的。迭代器本身可以++ --。如上代碼是最初我想的一個錯誤的實現，挺愚蠢的。const_iterator 并不是 const __list_iterator，這里的const __list_iterator使得這個迭代器存儲的Node*不能改變，也就是迭代器不能++ --。這是錯誤的。
根本上我們需要控制的是迭代器__list_iterator類對象operator*? operator->的返回值，普通迭代器返回普通引用，const迭代器返回const &，這里通過模板參數即可實現。
通過在list中實例化時模板參數不同，從而確定operator*的返回值。
template<class T, class Ref, class Ptr> // T& T* or const T& const T*
class __list_iterator // 成員就是一個結點指針
typedef __list_iterator<T, T&, T*> iterator; // 這個結構體別名為迭代器，本身是不支持解引用操作的。
typedef __list_iterator<T, const T&, const T*> const_iterator;
基于模板的知識我們知道，模板的參數不同，則實際上是完全不同的兩個類。上方的iterator 和 const_iterator大部分都是一樣的，只有operator* 和 operator->的返回值不同，他們都可以完成operator++ opeator--操作。
list迭代器失效問題：
迭代器失效即迭代器所指向的節點的無效，即該節 點被刪除了。因為list的底層結構為帶頭結點的雙向循環鏈表，因此在list中進行插入時是不會導致list的迭代 器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節點的迭代器，其他迭代器不會受到影響。
void TestListIterator1()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
// erase()函數執行后，it所指向的節點已被刪除，因此it無效，在下一次使用it時，必須先給
其賦值
l.erase(it);
++it;
}
}
// 改正
void TestListIterator()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0]));
auto it = l.begin();
while (it != l.end())
{
l.erase(it++); // it = l.erase(it);
}
}list的反向迭代器
STL的反向迭代器實際上運用的是適配器設計模式。
理解：?
首先，還是要明白反向迭代器的操作，再來說如何實現它更方便。
反向迭代器，無非就是++是往前，--是往后。同樣支持解引用操作 和 == != 判斷。
那么，感覺正向和反向迭代器的操作并沒有太大變化，無非++ -- 的方向不同。故我們可以基于正向迭代器的操作，進行封裝，然后設計出反向迭代器。? （這里在學完stack queue priority_queue之后再學會更好理解一點）
reverse_iterator.h
namespace yzl
{
template <class Iterator, class Ref, class Ptr> // 沒必要傳T
class __reverse_iterator
{
// 反向迭代器
public:
typedef __reverse_iterator<Iterator, Ref, Ptr> reverse_iterator;
public:
__reverse_iterator(const Iterator& _it) // 用一個正向迭代器去構造反向迭代器
:it(_it)
{}
Ref operator*() // 反向迭代器的解引用操作和正向的一樣
{
// Iterator tmp = --it;
// ++it;
// return *tmp;
auto tmp = it;
--tmp;
return *tmp;
}
Ptr operator->()
{
return &(this->operator*());
}
reverse_iterator& operator++() // 前置++，迭代器向后一步即可。
{
--it; // 調用構造函數中傳來的迭代器的operator--()
return *this;
}
reverse_iterator operator++(int)
{
reverse_iterator ret = *this;
--it;
return ret;
}
reverse_iterator& operator--()
{
++it;
return *this;
}
reverse_iterator operator--(int)
{
auto ret = *this;
++it;
return ret;
}
bool operator==(const reverse_iterator& rit)
{
return it == rit.it;
}
bool operator!=(const reverse_iterator& rit)
{
return it != rit.it;
}
private:
Iterator it;
};
}模板參數Iterator就是傳來的正向迭代器，只有一個數據成員，即一個正向迭代器it，因為正向迭代器已經支持了* -> ++ -- == !=操作，所以上述實現都是基于這個基礎來完成的。
因為我們僅憑傳來的一個正向迭代器無法直接得出其保存的元素類型，即T的類型（不考慮類型萃?。?。所以增加了兩個類型參數Ref Ptr，用于指明operator* operator->的返回值
這個不僅適用于list，vector也同樣適用。因為vector的正向迭代器（原生指針）支持那些操作。所以直接利用適配器設計模式進行封裝即可得到反向迭代器。
typedef __reverse_iterator<__list_iterator<T, T&, T*>, T&, T*> reverse_iterator;
typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;在list內進行如上typedef并非必要操作，而是這樣在下面rbegin rend處更方便...
反向迭代器的operator*實現：
Ref operator*() // 反向迭代器的解引用操作和正向的一樣
{
// Iterator tmp = --it;
// ++it;
// return *tmp;
auto tmp = it;
--tmp;
return *tmp;
}這里的operator*并不是直接獲取此正向迭代器所指元素，而是其前一個元素。這樣做不是必須的。
如上圖，這樣做僅僅為了讓begin 和 rend對應上，end和rbegin對應上。
如果operator*是直接返回正向迭代器所值元素，則rbegin指向7，rend指向1前面的那個位置。
同理，在list中，則rbegin()指向最后一個元素，rend指向頭節點。
operator->()?
我們知道，迭代器是一個類似指針的東西，->運算符一般是用于自定義類型對象指針使用->直接獲取其某個數據成員。比如Date* p = &d1;? ?cout << p->year << endl; 那么迭代器重載->是為什么呢？
迭代器指向元素類型不確定，比如int，或者一個Date。這要看容器存儲的什么元素類型。迭代器重載->就是為了當迭代器指向自定義類型時使用->可以直接獲取其數據成員比如：
std::list<Date> ls;
ls.push_back(Date(2001,1,1));
ls.push_back(Date(2002,1,1));
std::list<date>::iterator it = ls.begin();
cout << it->year << endl;這里應該輸出2001，這里it->year就調用了迭代器的operator-> 返回值是元素指針即Date*。
那么 it->的返回值是一個Date*，又是如何直接和year連接起來呢？實際上這里省略了一個->應該是it->->year;
void test11()
{
yzl::list<Date> ls;
ls.push_back(Date(2001,1,1));
ls.push_back(Date(2002,2,2));
yzl::list<Date>::reverse_iterator rit = ls.rbegin();
cout<<rit.operator->()->year<<endl;
cout<<rit->year<<endl;
}結果2002
vector和list的比較
?偷的
原文鏈接：https://blog.csdn.net/i777777777777777/article/details/127283890
相關推薦
- 2022-09-17 Makefile構建Golang項目示例詳解_Golang
- 2022-02-27 selectByPrimaryKey()按主鍵查詢結果為null
- 2022-06-20 關于go-micro與其它gRPC框架之間的通信問題及解決方法_Golang
- 2022-10-16 QT網絡通信TCP客戶端實現詳解_C 語言
- 2022-07-10 詳解HashMap并發修改異常
- 2022-03-23 詳解C#異步多線程使用中的常見問題_C#教程
- 2022-06-22 關于Metalama使用Fabric操作項目或命名空間的問題_實用技巧
- 2022-04-01 關于使用pyqt彈出消息提示框的問題_python
- 最近更新
-
- 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加速