網(wǎng)站首頁 編程語言 正文
目錄
list基本介紹和使用
list模擬實(shí)現(xiàn)
list的迭代器：
理解：
const_iterator問題：
list迭代器失效問題：
list的反向迭代器
理解：?
reverse_iterator.h
反向迭代器的operator*實(shí)現(xiàn)：
operator->()?
vector和list的比較
list基本介紹和使用
list - 帶頭雙向循環(huán)鏈表。
對比vector，因?yàn)閘ist是由一個(gè)個(gè)結(jié)點(diǎn)連接而成的，致使list
1. 不支持元素的隨機(jī)訪問，即沒有operator[]，因?yàn)樾实汀ＴL問元素front back
2. 沒有capacity的概念，內(nèi)存允許的情況下，可以無限申請節(jié)點(diǎn)并擴(kuò)展
3. 支持push_front pop_front，使得list可以作為queue的適配容器
4. 最大的優(yōu)勢是在任意位置插入刪除都可以在O(1)時(shí)間完成
學(xué)習(xí)成員函數(shù) 見https://cplusplus.com/reference/list/list/
list模擬實(shí)現(xiàn)
#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內(nèi)部使用的結(jié)點(diǎn)類型
{
public:
T _data;
list_node<T>* _next;
list_node<T>* _prev;
public:
list_node(const T& data = T()) // 結(jié)點(diǎn)的默認(rèn)構(gòu)造函數(shù)
: _data(data), _next(nullptr), _prev(nullptr)
{ }
// ~list_node() = default;
// // 拷貝構(gòu)造，其實(shí)沒必要
// list_node(const list_node<T>& node)
// : _data(node._data), _next(node._next), _prev(node._prev) // 淺拷貝
// { }
// // 賦值運(yùn)算符重載，也沒必要
// list_node<T>& operator=(const list_node<T>& node) // 淺拷貝
// {
// _data = node._data;
// _prev = node._prev;
// _next = node._next;
// return *this;
// }
};
// 說真的，只是對結(jié)點(diǎn)指針的一個(gè)封裝罷了，構(gòu)造函數(shù)也是通過一個(gè)結(jié)點(diǎn)指針即可構(gòu)造出一個(gè)迭代器。
// 對于迭代器的操作，其實(shí)也就是++ -- 然后解引用。目前的操作就是這些，之后再有再補(bǔ)充吧。
template<class T, class Ref, class Ptr> // T& T* or const T& const T*
class __list_iterator // 成員就是一個(gè)結(jié)點(diǎn)指針
{
public:
typedef list_node<T> Node; // 這是一個(gè)結(jié)構(gòu)體，結(jié)點(diǎn)。Node就是一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體。
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; // 這個(gè)迭代器類型有一個(gè)數(shù)據(jù)成員，是結(jié)點(diǎn)指針。
public:
__list_iterator(Node* node)
:_node(node)
{ }
// 這個(gè)類型的實(shí)例化對象本身不支持解引用操作，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迭代器其實(shí)都可以++
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:
// 說真的，關(guān)于list的迭代器，你只需要實(shí)現(xiàn)begin end這一系列的即可，還要讓它的返回值支持++ 解引用操作，這就夠了，說真的。
typedef __list_iterator<T, T&, T*> iterator; // 這個(gè)結(jié)構(gòu)體別名為迭代器，本身是不支持解引用操作的。
//typedef const __list_iterator<T> const_iterator; // 你這里const修飾的是迭代器類型，他有結(jié)點(diǎn)指針數(shù)據(jù)成員，const使得結(jié)點(diǎn)指針不能改變。
// 但是根本上，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的默認(rèn)構(gòu)造函數(shù)
_head = new Node; // 調(diào)用list_node<T>的默認(rèn)構(gòu)造函數(shù)，頭節(jié)點(diǎn)里面的data是隨機(jī)數(shù)
_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;
}
}
// 拷貝構(gòu)造函數(shù)現(xiàn)代寫法
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 是結(jié)點(diǎn)類，存儲data next prev ，很清楚。
而list，只有一個(gè)數(shù)據(jù)成員，就是一個(gè)頭節(jié)點(diǎn)指針? list_node<T>* _head;
先不談list的迭代器。push_back, pop_back, push_front pop_front size front back等都是帶頭雙向循環(huán)鏈表的基本套路。
list的迭代器：
理解：
我們知道，vector的迭代器是原生指針，這是因?yàn)関ector底層存儲的緣故，原生指針完全符合迭代器的要求。
那么，list是一個(gè)雙向帶頭循環(huán)鏈表，由一個(gè)個(gè)結(jié)點(diǎn)組成，結(jié)點(diǎn)指針顯然不能滿足迭代器的要求， 因?yàn)榻庖煤笫墙Y(jié)點(diǎn)實(shí)例化對象list_node<T>，而不是數(shù)據(jù)data。結(jié)點(diǎn)指針++也不是下一個(gè)結(jié)點(diǎn)，因?yàn)榻Y(jié)點(diǎn)的存儲不連續(xù)。
不過，基于C++的特性：封裝和運(yùn)算符重載，我們可以把結(jié)點(diǎn)指針進(jìn)行封裝，再使用運(yùn)算符重載重新定義其解引用和++的操作，使其符合迭代器的要求。于是，有了__list_iterator
template<class T, class Ref, class Ptr> // T& T* or const T& const T*
class __list_iterator // 成員就是一個(gè)結(jié)點(diǎn)指針
{
public:
typedef list_node<T> Node; // 這是一個(gè)結(jié)構(gòu)體，結(jié)點(diǎn)。Node就是一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體。
typedef __list_iterator<T, Ref, Ptr> iterator;
public:
Node* _node; // 這個(gè)迭代器類型有一個(gè)數(shù)據(jù)成員，是結(jié)點(diǎn)指針。
public:
__list_iterator(Node* node)
:_node(node)
{ }
// 這個(gè)類型的實(shí)例化對象本身不支持解引用操作，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迭代器其實(shí)都可以++
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;
}
};其實(shí)非常簡單，這個(gè)迭代器類型就是對結(jié)點(diǎn)指針的一個(gè)封裝。和list一樣，它只有一個(gè)數(shù)據(jù)成員，即Node*? ?(typedef?list_node<T> Node)?
然后進(jìn)行一些運(yùn)算符重載，比如operator* operator++ operator==，這里也是C++的基礎(chǔ)知識，因?yàn)榻Y(jié)點(diǎn)指針不能直接做迭代器，所以將其封裝，但是封裝好的類__list_iterator對象本身并不支持解引用 ++ 操作，C++的運(yùn)算符重載特性使得可以定義這個(gè)類對象的某些操作。? 之后就可以使其像迭代器一樣使用，即__list_iterator的對象是list的一個(gè)迭代器。
typedef __list_iterator<T, T&, T*> iterator; // 這個(gè)結(jié)構(gòu)體別名為迭代器，本身是不支持解引用操作的。
typedef __list_iterator<T, const T&, const T*> const_iterator;
在list內(nèi)進(jìn)行如上typedef即可。?
const_iterator問題：
//typedef const __list_iterator<T> const_iterator; // 你這里const修飾的是迭代器類型，他有結(jié)點(diǎn)指針數(shù)據(jù)成員，const使得結(jié)點(diǎn)指針不能改變。
如何區(qū)分list的iterator 和 const_iterator是一個(gè)問題，首先我們需要明確const_iterator需要什么特殊性質(zhì)：解引用后的值是const的，且是引用性質(zhì)的。迭代器本身可以++ --。如上代碼是最初我想的一個(gè)錯(cuò)誤的實(shí)現(xiàn)，挺愚蠢的。const_iterator 并不是 const __list_iterator，這里的const __list_iterator使得這個(gè)迭代器存儲的Node*不能改變，也就是迭代器不能++ --。這是錯(cuò)誤的。
根本上我們需要控制的是迭代器__list_iterator類對象operator*? operator->的返回值，普通迭代器返回普通引用，const迭代器返回const &，這里通過模板參數(shù)即可實(shí)現(xiàn)。
通過在list中實(shí)例化時(shí)模板參數(shù)不同，從而確定operator*的返回值。
template<class T, class Ref, class Ptr> // T& T* or const T& const T*
class __list_iterator // 成員就是一個(gè)結(jié)點(diǎn)指針
typedef __list_iterator<T, T&, T*> iterator; // 這個(gè)結(jié)構(gòu)體別名為迭代器，本身是不支持解引用操作的。
typedef __list_iterator<T, const T&, const T*> const_iterator;
基于模板的知識我們知道，模板的參數(shù)不同，則實(shí)際上是完全不同的兩個(gè)類。上方的iterator 和 const_iterator大部分都是一樣的，只有operator* 和 operator->的返回值不同，他們都可以完成operator++ opeator--操作。
list迭代器失效問題：
迭代器失效即迭代器所指向的節(jié)點(diǎn)的無效，即該節(jié) 點(diǎn)被刪除了。因?yàn)閘ist的底層結(jié)構(gòu)為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，因此在list中進(jìn)行插入時(shí)是不會導(dǎo)致list的迭代 器失效的，只有在刪除時(shí)才會失效，并且失效的只是指向被刪除節(jié)點(diǎn)的迭代器，其他迭代器不會受到影響。
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()函數(shù)執(zhí)行后，it所指向的節(jié)點(diǎn)已被刪除，因此it無效，在下一次使用it時(shí)，必須先給
其賦值
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的反向迭代器實(shí)際上運(yùn)用的是適配器設(shè)計(jì)模式。
理解：?
首先，還是要明白反向迭代器的操作，再來說如何實(shí)現(xiàn)它更方便。
反向迭代器，無非就是++是往前，--是往后。同樣支持解引用操作 和 == != 判斷。
那么，感覺正向和反向迭代器的操作并沒有太大變化，無非++ -- 的方向不同。故我們可以基于正向迭代器的操作，進(jìn)行封裝，然后設(shè)計(jì)出反向迭代器。? （這里在學(xué)完stack queue priority_queue之后再學(xué)會更好理解一點(diǎn)）
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) // 用一個(gè)正向迭代器去構(gòu)造反向迭代器
: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; // 調(diào)用構(gòu)造函數(shù)中傳來的迭代器的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;
};
}模板參數(shù)Iterator就是傳來的正向迭代器，只有一個(gè)數(shù)據(jù)成員，即一個(gè)正向迭代器it，因?yàn)檎虻饕呀?jīng)支持了* -> ++ -- == !=操作，所以上述實(shí)現(xiàn)都是基于這個(gè)基礎(chǔ)來完成的。
因?yàn)槲覀儍H憑傳來的一個(gè)正向迭代器無法直接得出其保存的元素類型，即T的類型（不考慮類型萃取）。所以增加了兩個(gè)類型參數(shù)Ref Ptr，用于指明operator* operator->的返回值
這個(gè)不僅適用于list，vector也同樣適用。因?yàn)関ector的正向迭代器（原生指針）支持那些操作。所以直接利用適配器設(shè)計(jì)模式進(jìn)行封裝即可得到反向迭代器。
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內(nèi)進(jìn)行如上typedef并非必要操作，而是這樣在下面rbegin rend處更方便...
反向迭代器的operator*實(shí)現(xiàn)：
Ref operator*() // 反向迭代器的解引用操作和正向的一樣
{
// Iterator tmp = --it;
// ++it;
// return *tmp;
auto tmp = it;
--tmp;
return *tmp;
}這里的operator*并不是直接獲取此正向迭代器所指元素，而是其前一個(gè)元素。這樣做不是必須的。
如上圖，這樣做僅僅為了讓begin 和 rend對應(yīng)上，end和rbegin對應(yīng)上。
如果operator*是直接返回正向迭代器所值元素，則rbegin指向7，rend指向1前面的那個(gè)位置。
同理，在list中，則rbegin()指向最后一個(gè)元素，rend指向頭節(jié)點(diǎn)。
operator->()?
我們知道，迭代器是一個(gè)類似指針的東西，->運(yùn)算符一般是用于自定義類型對象指針使用->直接獲取其某個(gè)數(shù)據(jù)成員。比如Date* p = &d1;? ?cout << p->year << endl; 那么迭代器重載->是為什么呢？
迭代器指向元素類型不確定，比如int，或者一個(gè)Date。這要看容器存儲的什么元素類型。迭代器重載->就是為了當(dāng)?shù)髦赶蜃远x類型時(shí)使用->可以直接獲取其數(shù)據(jù)成員比如：
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;這里應(yīng)該輸出2001，這里it->year就調(diào)用了迭代器的operator-> 返回值是元素指針即Date*。
那么 it->的返回值是一個(gè)Date*，又是如何直接和year連接起來呢？實(shí)際上這里省略了一個(gè)->應(yīng)該是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;
}結(jié)果2002
vector和list的比較
?偷的
原文鏈接：https://blog.csdn.net/i777777777777777/article/details/127283890
相關(guān)推薦
- 2023-05-29 Python?input輸入超時(shí)選擇默認(rèn)值自動(dòng)跳過問題_python
- 2023-11-20 【ROS】用roslibpy庫在windows上用python 連接Ubuntu ROS
- 2022-10-06 Python?Numpy中數(shù)組的集合操作詳解_python
- 2022-02-14 centos7系統(tǒng)部署k8s集群詳細(xì)介紹_Linux
- 2024-07-15 SpringBoot使用Apache Poi導(dǎo)出word文檔
- 2022-09-13 python開發(fā)sdk模塊的方法_python
- 2022-06-28 C語言簡明清晰講解枚舉_C 語言
- 2022-04-09 node sass下載失敗解決方案
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速