当前位置：网站首页>list模拟实现
list模拟实现
2022-07-27 02:47:00 【韩悬子】
list模拟实现
1.构造函数和push_back实现
也没什么好讲，list是带头双向循环的顺序表
顺序表也就创个结构体，结构体里面有二个指针加个data
而push_back也就更简单了，创个节点然后插入就好了
#pragma once
namespace ls
{
template <class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _date;
ListNode(const T& val = T())
:_next(nullptr)
, _prev(nullptr)
, _data(val)
{
}
};
template<class T>
class list
{
typedef ListNode<T>* Node;
public:
list()
{
_head = new Node;
_head->_next = _head;
_head->prev = _head;
}
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
//head tail newnode
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
private:
Node* _head;
};
}
2.迭代器实现
迭代器也一样，因为和string之类的迭代器实现有些不同
不过一样是要实现!+ ++ * 这些也没难度
不过下面我写的不是完全的迭代器，等下会完善的
namespace ls
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val= T())
:_next(nullptr)
,_prev(nullptr)
,_data(val)
{
}
};
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
//return &(operator*());
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T> iterator;
iterator begin()
{
return iterator(_head->_next);
//return _head->_next;
}
iterator end()
{
return iterator(_head);
}
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
// _head tail newnode
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
private:
Node* _head;
};
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
这里还有个好玩的
iterator begin()
{
return iterator(_head->_next);
//return _head->_next;
}
下面被注释的代码其实也能访问，因为被注释的代码会被隐式转换成迭代器，所以不会报错
如果运行不了的记得把我们写的list.h包含在头文件，要不然会报错没有cout之类的错误
运行结果
3.list迭代器访问结构体写法
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{
}
int _a1;
int _a2;
};
void test_list2()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
lt.push_back(AA(4, 4));
// 迭代器模拟的是指针行为
// int* it *it
// AA* it *it it->
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << (*it)._a1 << "-"<< (*it)._a2 <<" ";
cout << it->_a1 << "-" << it->_a2 << " ";
++it;
}
cout << endl;
}
现在没被注释写的是自己写的，这里面的it->得到it.operator()是AA*应该在加一个->才能访问的了，而这里能访问是编译器做了优化省略了一个->，要不然二个->->就太难看了
5.实现const迭代器
iterator begin() const
{
return iterator(_head->_next);
}
iterator end() const
{
return iterator(_head);
}
void print_list(const list<int>& lt)
{
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
*it = 10; // 不允许修改
cout << *it << " ";
++it;
}
cout << endl;
}
运行
可以看到这不是const迭代器但是为什么还是可以改内容
因为迭代器是模拟的是指针的行为，所以要看下面二个函数
const T& operator*()
{
return _node->_data;
}
const T* operator->()
{
//return &(operator*());
return &_node->_data;
}
改了过后就不能赋值了，但是这么改又有一个问题普通成员也不能改内容了，可能大部分的人做法，是再赋值一份代码改为const迭代器，但是这种办法能行，但是很不好可复用性太差，而解决这里的办法可能用模板
解决办法
办法很简单提供二个模板，一个模板是用来普通迭代器，一个是用来const迭代器
先发改动地方的图片，再发全代码
代码
namespace ls
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val= T())
:_next(nullptr)
,_prev(nullptr)
,_data(val)
{
}
};
//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T, const T&, const T*> const_iterator;
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
//return &(operator*());
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
//return _head->_next;
}
iterator end()
{
return iterator(_head);
}
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
void push_back(const T& x)
{
Node* tail = _head->_prev;
Node* newnode = new Node(x);
// _head tail newnode
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
}
private:
Node* _head;
};
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//*it = 10; // 不允许修改
cout << *it << " ";
++it;
}
cout << endl;
}
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
print_list(lt);
}
}
6.insert和earse实现
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
_head tail newnode
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
//prev newNode cur
newNode->_next = cur;
newNode->_prev = prev;
prev->_next = newNode;
cur->_prev = newNode;
return iterator(newNode);
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// prev next
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
这里一样把insert和erase实现了那么push_back之类的就可以直接用insert来代替了
不过要
注意这里insert不会出现迭代器失效，为什么？
因为每个节点足够独立，不存在野指针，也不出现迭代器意义变了的问题，但是为什么上面还是给了返回值因为和库相同，得到新加入的字符的位置
erase会出现迭代器问题,删除偶数位，经典野指针失效，因为迭代器指向的节点已经被释放了
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
// 删除所有的偶数
auto it1 = lt.begin();
while (it1 != lt.end())
{
if (*it1 % 2 == 0)
{
it1 = lt.erase(it1);
}
else
{
++it1;
}
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
7.clear和析构函数
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
这里的比较有意思的是clear，clear是到哨兵位就停了，就不释放了，而析构就只要调用clear再把哨兵位给嘎了就行了
8.拷贝构造和赋值
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;
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
// lt2(lt1) -- 现代写法
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
// lt2 = lt1
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
9.list模拟实现全部代码
namespace ls
{
template <class T>
struct list_node
{
list_node<T>* _next;
list_node<T>* _prev;
T _data;
list_node(const T& val= T())
:_next(nullptr)
,_prev(nullptr)
,_data(val)
{
}
};
//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T, const T&, const T*> const_iterator;
template<class T, class Ref, class Ptr>
struct __list_iterator
{
typedef list_node<T> Node;
typedef __list_iterator<T, Ref, Ptr> self;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
//return &(operator*());
return &_node->_data;
}
self& operator++()
{
_node = _node->_next;
return *this;
}
self operator++(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
self& operator--()
{
_node = _node->_prev;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const self& it)
{
return _node != it._node;
}
bool operator==(const self& it)
{
return _node == it._node;
}
};
template <class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head);
}
iterator begin()
{
return iterator(_head->_next);
//return _head->_next;
}
iterator end()
{
return iterator(_head);
}
list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
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;
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
// lt2(lt1) -- 现代写法
list(const list<T>& lt)
{
empty_init();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
// lt2 = lt1
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
//Node* tail = _head->_prev;
//Node* newnode = new Node(x);
_head tail newnode
//tail->_next = newnode;
//newnode->_prev = tail;
//newnode->_next = _head;
//_head->_prev = newnode;
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* newNode = new Node(x);
Node* cur = pos._node;
Node* prev = cur->_prev;
//prev newNode cur
newNode->_next = cur;
newNode->_prev = prev;
prev->_next = newNode;
cur->_prev = newNode;
return iterator(newNode);
}
iterator erase(iterator pos)
{
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
// prev next
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);
}
private:
Node* _head;
};
void print_list(const list<int>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
//*it = 10; // 不允许修改
cout << *it << " ";
++it;
}
cout << endl;
}
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
print_list(lt);
}
struct AA
{
AA(int a1 = 0, int a2 = 0)
:_a1(a1)
, _a2(a2)
{
}
int _a1;
int _a2;
};
void test_list2()
{
list<AA> lt;
lt.push_back(AA(1, 1));
lt.push_back(AA(2, 2));
lt.push_back(AA(3, 3));
lt.push_back(AA(4, 4));
// 迭代器模拟的是指针行为
// int* it *it
// AA* it *it it->
list<AA>::iterator it = lt.begin();
while (it != lt.end())
{
//cout << (*it)._a1 << "-"<< (*it)._a2 <<" ";
cout << it->_a1 << "-" << it->_a2 << " ";
++it;
}
cout << endl;
}
void test_list3()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.pop_front();
lt.pop_front();
lt.pop_back();
lt.pop_back();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list5()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
// 删除所有的偶数
auto it1 = lt.begin();
while (it1 != lt.end())
{
if (*it1 % 2 == 0)
{
it1 = lt.erase(it1);
}
else
{
++it1;
}
}
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
void test_list6()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
lt.push_back(6);
list<int> lt1(lt);
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
list<int> lt2;
lt2.push_back(10);
lt2.push_back(20);
lt1 = lt2;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}
}
边栏推荐
- [untitled]
- VR全景制作在家装行业是谈单利器？这是为什么呢？
- Abstract intelligent extraction [based on Bert technology]
- Case when in MySQL returns multiple field processing schemes
- 【OBS】circlebuf
- 分析一下CSDN大佬写的CAS,可重入锁, 非公平锁
- Plato farm has a new way of playing, and the arbitrage eplato has secured super high returns
- 0726~ resume sorting interview summary
- Connman introduction
- 04. Detailed steps for installing the simulated browser chromedriver in Google browser
猜你喜欢
Implementation of API short message gateway based on golang
Application, addition and deletion of B-tree
288 page 180000 word intelligent campus overall design directory
Connman introduction
Smart pointer shared_ ptr、unique_ ptr、weak_ ptr
Process analysis of object creation
![Machine learning [Matplotlib]](/img/d1/31ec2f96ca96465c6863798c7db179.jpg)
Machine learning [Matplotlib]
Plato farm brings a new experience to community users through the LAAS protocol elephant swap
《MySQL》认识MySQL与计算机基础知识
"Gonna be right" digital collection is now on sale! Feel the spiritual resonance of artists
随机推荐
Restful Fast Request 2022.2.2发布,支持批量导出文档
回归测试：意义、挑战、最佳实践和工具
路由策略第一关
222. 完全二叉树的节点个数
Interview question: the difference between three instantiated objects in string class
The problem that prevented the installation of umi4 for one day has been solved
这个FlinkCDC会监控数据库中所有的表？还是指定的表呢？我看后台日志，他是监控了所有表，如果监控
安装umi4阻碍一天的问题解决了
04. Detailed steps for installing the simulated browser chromedriver in Google browser
C. Cypher
Restful fast request 2022.2.2 release, supporting batch export of documents
Plato Farm有望通过Elephant Swap，进一步向外拓展生态
Abstract intelligent extraction [based on Bert technology]
VR全景人淘金“小心机”（上）
Detailed analysis of trajectory generation tool in psins toolbox
Is it safe for tongdaxin to open an account
次轮Okaleido Tiger即将登录Binance NFT,引发社区热议
LeetCode 第二十八天
Chapter 5 决策树和随机森林实践
PSINS工具箱中轨迹生成工具详细解析