文章目錄：
- STL-List-原始碼
- 1. 對私有成員的資料型別進行宣告
- 2. 初始化，寫入建構式，申請一個頭節點，
- 3.尾插
- 4. 構造迭代器
- 5. 插入一個節點到_P位置
- 6. 判空
- 7. 取鏈表的第一個節點
- 8. 取鏈表的尾節點(需- -)
- 9. 三種建構式
- 10. 洗掉節點
- 11. 最終刨析代碼
STL-List-原始碼
List原始碼可查看—>[List原始碼]
1. 對私有成員的資料型別進行宣告
原始碼中私有成員如下：
刨析后如下：
#include<iostream>
using namespace std;
namespace code
{
template <class _Ty>
class list
{
public:
//型別的萃取
typedef size_t size_type;//大小的型別
typedef _Ty value_type;//值型別
typedef _Ty* pointer_type;//指標型別
typedef _Ty& reference_type;//參考型別
typedef const _Ty* const_pointer_type;//常指標型別
typedef const _Ty& const_reference_type;//常參考型別
public:
struct _Node;
typedef struct _Node* _Nodeptr;
private:
_Nodeptr _Head;
size_type _Size;
};
}
void main()
{
code::list<int>mylist;
}
2. 初始化，寫入建構式，申請一個頭節點，
相關原始碼如下：
刨析如下：
#include<iostream>
using namespace std;
namespace code
{
template <class _Ty>
class list
{
public:
//型別的萃取
typedef size_t size_type;//大小的型別
typedef _Ty value_type;//值型別
typedef _Ty* pointer_type;//指標型別
typedef _Ty& reference_type;//參考型別
typedef const _Ty* const_pointer_type;//常指標型別
typedef const _Ty& const_reference_type;//常參考型別
public:
struct _Node;
typedef struct _Node* _Nodeptr;
struct _Node
{
_Nodeptr _Next;
_Nodeptr _Prev;
_Ty _value;
};
struct _Acc
{
typedef struct _Node* & _Nodepref;
typedef _Ty& _Vref;
static _Nodepref _Next(_Nodeptr _P)
{
return (_P->_Next);
}
static _Nodepref _Prev(_Nodeptr _P)
{
return (_P->_Prev);
}
static _Vref _Value(_Nodeptr _P)
{
return (_P->_Value);
}
};
//刨析寫法一：
//public:
// explicit list() :_Head(nullptr), _Size(0)
// {
// _Head = new _Node;
// _Head->_Next = _Head;
// _Head->_Prev = _Head;
// }
//刨析寫法二
//public:
// explicit list() :_Head(_Buynode()), _Size(0)
// {}
//protected:
// _Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
// {
// _Nodeptr _S = new _Node;
//申請完節點可以直接連接它的前驅和后繼
// _S->_Next = _Narg != 0 ? _Narg : _S;
// _S->_Prev = _Parg != 0 ? _Parg : _S;
// return _S;
// }
//原始碼寫法，封裝性更好，不會讓成員暴露
public:
explicit list() :_Head(_Buynode()), _Size(0)
{}
protected:
_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
{
_Nodeptr _S = new _Node;
_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;
return _S;
}
private:
_Nodeptr _Head;
size_type _Size;
};
}
void main()
{
code::list<int>mylist;
}
如上三種寫法的效果是一樣的，但原始碼的寫法不會將成員暴露出來，相對更好
測驗效果如下：
3.尾插
相關原始碼如下：
刨析后資料結構寫法如下：
public:
void push_back(const _Ty& _X)
{
_Nodeptr _S = new _Node;
_S->_Value = _X;
_S->_Prev = _Head->_Prev;
_S->_Next = _Head;
_Head->_Prev = _S;
_S->_Prev->_Next = _S;
++_Size;
}
優化后如下：
//尾插
public:
void push_back(const _Ty& _X)
{
_Nodeptr _S = _Buynode(_Head, _Acc::_Prev(_Head));
_Acc::_Value(_S) = _X;
_Acc::_Next(_Acc::_Prev(_S)) = _S;
_Acc::_Prev(_Acc::_Next(_S)) = _S;
++_Size;
}
4. 構造迭代器
給一個私有成員變數_Ptr(一個指標)，寫出迭代器的默認建構式
public:
//構造一個迭代器
class iterator
{
public:
iterator()
{}
iterator(_Nodeptr _P) :_Ptr(_P)
{}
private:
_Nodeptr _Ptr;
};
寫一個begin()構造器，回傳第一個真實節點；一個end()構造器，回傳頭節點
public:
//begin()迭代器 回傳第一個真實節點
iterator begin()
{
return iterator(_Acc::_Next(_Head));
}
//end()迭代器 回傳頭節點
iterator end()
{
return iterator(_Head);
}
多載++，–，*，!=，==
原始碼如下：
刨析后寫法如下：
public:
//構造一個迭代器
class iterator
{
public:
iterator()
{}
iterator(_Nodeptr _P) :_Ptr(_P)
{}
public:
//不等號多載
bool operator!=(const iterator& _it)
{
return _Ptr != _it._Ptr;
}
//等號多載
bool operator==(const iterator& _it)
{
return _Ptr == _it._Ptr;
}
//*的多載
_Ty& operator*()
{
return _Acc::_Value(_Ptr);
}
//前置++的多載
iterator& operator++()
{
_Ptr = _Acc::_Next(_Ptr);
return *this;
}
//后置++的多載
iterator operator++(int)
{
iterator tem(_Ptr);
++*this;
return tem;
}
//前置--的多載
iterator& operator--()
{
_Ptr = _Acc::_Prev(_Ptr);
return *this;
}
//后置--的多載
iterator operator--(int)
{
iterator tmp(_Ptr);
--*this;
return tmp;
}
private:
_Nodeptr _Ptr;
};
列印測驗：
void main()
{
code::list<int>mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
code::list<int>::iterator it = mylist.begin();
while (it != mylist.end())
{
cout << *it << "->";
++it;
}
cout << "end" << endl;
}
測驗效果如下：
5. 插入一個節點到_P位置
寫入一個插入函式insert
原始碼如下：
刨析后代碼如下：
//資料結構寫法
//public:
// //指定一個位置進行插入
// iterator insert(iterator _P, const _Ty& _X = _Ty())
// {
// _Nodeptr _S = new _Node;
// _Acc::_Value(_S) = _X;
//
// _Nodeptr _N = _P._Mynode();
// _S->_Next = _N;
// _S->_Prev = _N->_Prev;
// _S->_Prev->_Next = _S;
// _S->_Next->_Prev = _S;
// ++_Size;
// return iterator(_S);
// }
public:
iterator insert(iterator _P, const _Ty& _X = _Ty())
{
//_S指向_P位置
_Nodeptr _S = _P._Mynode();
//新節點連向它的后繼和前驅，_P連接新節點
_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
//_S指向新節點
_S = _Acc::_Prev(_S);
//_S的前驅的后繼指向_S
_Acc::_Next(_Acc::_Prev(_S)) = _S;
_Acc::_Value(_S) = _X;
++_Size;
return (iterator(_S));
}
此時頭插尾插可以優化為：
//尾插
void push_back(const _Ty& _X)
{
insert(end(), _X);
}
//頭插
void push_front(const _Ty& _X)
{
insert(begin(), _X);
}
6. 判空
回傳_Size的大小判斷是否為0
7. 取鏈表的第一個節點
此處有兩個方法一個針對普通物件，一個針對常物件
8. 取鏈表的尾節點(需- -)
end()取的是最后一個節點的下一個位置(_Head)
9. 三種建構式
（1）默認建構式（2）初始化為n個x（3）初始化一個區間
原始碼如下：
刨析如下：
//默認建構式
explicit list():_Head(_Buynode()),_Size(0)
{}
//初始化為n個x
list(size_type _N, const _Ty& _V = _Ty())
:_Head(_Buynode()), _Size(0)
{
insert(begin(), _N, _V);
}
//初始化一個區間
list(const _Ty *_F, const _Ty *_L)
:_Head(_Buynode()), _Size(0)
{
insert(begin(), _F, _L);
}
10. 洗掉節點
//洗掉節點
iterator erase(iterator _P)
{
_Nodeptr _S = (_P++)._Mynode();
_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
_Deletenode(_S);
--_Size;
return (_P);
}
//洗掉一個區間
iterator erase(iterator _F, iterator _L)
{
while (_F != _L)
erase(_F++);
return (_F);
}
//清除函式
void clear()
{
erase(begin(), end());
}
protected:
void _Deletenode(_Nodeptr _S)
{
delete _S;
}
11. 最終刨析代碼
#include<iostream>
using namespace std;
namespace code
{
template <class _Ty>
class list
{
public:
//型別的萃取
typedef size_t size_type;//大小的型別
typedef _Ty value_type;//值型別
typedef _Ty* pointer_type;//指標型別
typedef _Ty& reference_type;//參考型別
typedef const _Ty* const_pointer_type;//常指標型別
typedef const _Ty& const_reference_type;//常參考型別
public:
struct _Node;
typedef struct _Node* _Nodeptr;
struct _Node
{
_Nodeptr _Next;
_Nodeptr _Prev;
_Ty _Value;
};
struct _Acc
{
typedef struct _Node* & _Nodepref;
typedef _Ty& _Vref;
static _Nodepref _Next(_Nodeptr _P)
{
return (_P->_Next);
}
static _Nodepref _Prev(_Nodeptr _P)
{
return (_P->_Prev);
}
static _Vref _Value(_Nodeptr _P)
{
return (_P->_Value);
}
};
public:
//構造一個迭代器
class iterator
{
public:
iterator()
{}
iterator(_Nodeptr _P) :_Ptr(_P)
{}
public:
//不等號多載
bool operator!=(const iterator& _it)
{
return _Ptr != _it._Ptr;
}
//等號多載
bool operator==(const iterator& _it)
{
return _Ptr == _it._Ptr;
}
//*的多載
_Ty& operator*()
{
return _Acc::_Value(_Ptr);
}
//前置++的多載
iterator& operator++()
{
_Ptr = _Acc::_Next(_Ptr);
return *this;
}
//后置++的多載
iterator operator++(int)
{
iterator tem(_Ptr);
++*this;
return tem;
}
//前置--的多載
iterator& operator--()
{
_Ptr = _Acc::_Prev(_Ptr);
return *this;
}
//后置--的多載
iterator operator--(int)
{
iterator tmp(_Ptr);
--*this;
return tmp;
}
//回傳Ptr指標
_Nodeptr _Mynode()
{
return _Ptr;
}
private:
_Nodeptr _Ptr;
};
//刨析寫法一：
//public:
// explicit list() :_Head(nullptr), _Size(0)
// {
// _Head = new _Node;
// _Head->_Next = _Head;
// _Head->_Prev = _Head;
// }
//刨析寫法二
//public:
// explicit list() :_Head(_Buynode()), _Size(0)
// {}
//protected:
// _Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
// {
// _Nodeptr _S = new _Node;
// _S->_Next = _Narg != 0 ? _Narg : _S;
// _S->_Prev = _Parg != 0 ? _Parg : _S;
// return _S;
// }
//原始碼寫法，封裝性更好，不會讓資料暴露
public:
//建構式
explicit list() :_Head(_Buynode()), _Size(0)
{}
list(size_type _N, const _Ty& _V = _Ty()):_Head(_Buynode()), _Size(0)
{
insert(begin(), _N, _V);
}
list(const _Ty *_F, const _Ty *_L)
:_Head(_Buynode()), _Size(0)
{
insert(begin(), _F, _L);
}
//解構式
~list()
{
//erase(begin(), end());
clear();
_Deletenode(_Head);
_Head = 0, _Size = 0;
}
// public:
//void push_back(const _Ty& _X)
//{
// _Nodeptr _S = new _Node;
// _S->_Value = _X;
// _S->_Prev = _Head->_Prev;
// _S->_Next = _Head;
// _Head->_Prev = _S;
// _S->_Prev->_Next = _S;
// ++_Size;
//}
public:
//begin()迭代器 回傳第一個真實節點
iterator begin()
{
return iterator(_Acc::_Next(_Head));
}
//end()迭代器 回傳頭節點
iterator end()
{
return iterator(_Head);
}
尾插
// public:
//void push_back(const _Ty& _X)
//{
// _Nodeptr _S = _Buynode(_Head, _Acc::_Prev(_Head));
// _Acc::_Value(_S) = _X;
// _Acc::_Next(_Acc::_Prev(_S)) = _S;
// _Acc::_Prev(_Acc::_Next(_S)) = _S;
// ++_Size;
//}
//尾插
void push_back(const _Ty& _X)
{
insert(end(), _X);
}
//頭插
void push_front(const _Ty& _X)
{
insert(begin(), _X);
}
//資料結構寫法
//public:
// //指定一個位置進行插入
// iterator insert(iterator _P, const _Ty& _X = _Ty())
// {
// _Nodeptr _S = new _Node;
// _Acc::_Value(_S) = _X;
//
// _Nodeptr _N = _P._Mynode();
// _S->_Next = _N;
// _S->_Prev = _N->_Prev;
// _S->_Prev->_Next = _S;
// _S->_Next->_Prev = _S;
// ++_Size;
// return iterator(_S);
// }
public:
iterator insert(iterator _P, const _Ty& _X = _Ty())
{
//_S指向_P位置
_Nodeptr _S = _P._Mynode();
//新節點連向它的后繼和前驅，_P連接新節點
_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
//_S指向新節點
_S = _Acc::_Prev(_S);
//_S的前驅的后繼指向_S
_Acc::_Next(_Acc::_Prev(_S)) = _S;
_Acc::_Value(_S) = _X;
++_Size;
return (iterator(_S));
}
//洗掉節點
iterator erase(iterator _P)
{
_Nodeptr _S = (_P++)._Mynode();
_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
_Deletenode(_S);
--_Size;
return (_P);
}
void insert(iterator _P, size_type _M, const _Ty& _X)
{
for (; 0 < _M; --_M)
insert(_P, _X);
}
void insert(iterator _P, const _Ty *_F, const _Ty *_L)
{
for (; _F != _L; ++_F)
insert(_P, *_F);
}
//洗掉一個區間
iterator erase(iterator _F, iterator _L)
{
while (_F != _L)
erase(_F++);
return (_F);
}
//清除函式
void clear()
{
erase(begin(), end());
}
//申請節點
protected:
_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
{
_Nodeptr _S = new _Node;
_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;
return _S;
}
void _Deletenode(_Nodeptr _S)
{
delete _S;
}
private:
_Nodeptr _Head;
size_type _Size;
};
}
void main()
{
code::list<int>mylist;
mylist.push_back(1);
mylist.push_back(2);
mylist.push_back(3);
//code::list<int>::iterator pos = mylist.begin();
///*mylist.erase(pos);*/
mylist.clear();
code::list<int>::iterator it = mylist.begin();
while (it != mylist.end())
{
cout << *it << "->";
++it;
}
cout << "end" << endl;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/280259.html
標籤：區塊鏈
下一篇：MySQL下載與安裝