当前位置：网站首页>List Simulation Implementation
List Simulation Implementation
2022-07-27 04:09:00 【Korean suspense】
list Simulation Implementation
1. Constructors and push_back Realization
There's nothing to talk about ,list It is the sequence table leading the two-way cycle
The sequence table creates a structure , There are two pointers plus data
and push_back It's easier , Create a node and insert it
#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. Iterator implementation
Iterators are the same , Because and string Iterator implementations like this are somewhat different
But the same is to achieve !+ ++ * These are not difficult
But what I write below is not a complete iterator , It will be improved later
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;
}
}
Here's another interesting
iterator begin()
{
return iterator(_head->_next);
//return _head->_next;
}
The commented code below can also be accessed , Because the annotated code will be implicitly converted into iterators , So there's no mistake
If it doesn't work, remember to write us list.h The header file is included in , Otherwise, it will report an error cout Or something like that
Running results 
3.list Iterator access structure writing
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));
// Iterators simulate pointer behavior
// 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;
}
What is not commented now is written by yourself , Inside it-> obtain it.operator() yes AA* You should add one -> Can be accessed , The reason why it can be accessed here is that the compiler has optimized and omitted one ->, Or two ->-> It's too ugly
5. Realization const iterator
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; // No modification allowed
cout << *it << " ";
++it;
}
cout << endl;
}
function 
You can see that this is not const Iterator, but why can you still change the content
Because iterators simulate the behavior of pointers , So let's look at the following two functions
const T& operator*()
{
return _node->_data;
}
const T* operator->()
{
//return &(operator*());
return &_node->_data;
}
You can't assign values after changing , But there is another problem with this change. Ordinary members can't change the content , Maybe most people do it , Is to assign another code and change it to const iterator , But this method works , But it's not good, and the reusability is too poor , The solution here may be to use templates
terms of settlement
The method is very simple. Provide two templates , A template is used for ordinary iterators , One is for const iterator
Send pictures of the changes first , Send the full code again 
Code
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; // No modification allowed
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 and earse Realization
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);
}
Same here insert and erase Achieved so push_back You can use it directly insert Instead of
But
Note that there insert There will be no iterator failure , Why? ？
Because each node is independent enough , There is no wild pointer , There is no problem that the meaning of iterators has changed , But why is the return value given above? Because it is the same as the Library , Get the position of the newly added character
erase There will be iterator problems , Delete even digits , Classic wild pointer failure , Because the node pointed to by the iterator has been released
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);
// Delete all even numbers
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 And destructors
~list()
{
clear();
delete _head;
_head = nullptr;
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
The more interesting thing here is clear,clear It stops at the sentry post , It won't be released , The destructor just calls clear Just give the sentry position to GA again
8. Copy construction and assignment
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) -- Modern writing
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 Simulate all the code
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) -- Modern writing
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; // No modification allowed
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));
// Iterators simulate pointer behavior
// 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);
// Delete all even numbers
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;
}
}
边栏推荐
- 面试题 16.05. 阶乘尾数
- 物联网智能家居项目---智能卧室
- H. 265 web player easyplayer's method of opening video to the public
- jmeter接口测试（登录、注册）
- 想要获得 Apache 官方域名邮箱吗？专访 Apache Linkis 五位新晋 Committer告诉你怎么做
- 搜索旋转排序数组
- Day 28 of leetcode
- flinkSQLclient创建的job，flink重启就没了，有什么办法吗？
- Nonlinear optimal tracking control based on wind energy conversion system (realized by matlab code)
- The fifth strong network cup national network security challenge Title reappearance (with title attachment, detailed explanation)
猜你喜欢
随机推荐
C＃怎么实现给Word每一页设置不同文字水印
Threads and processes
H. 265 web player easyplayer's method of opening video to the public
First pass of routing strategy
【SemiDrive源码分析】【驱动BringUp】41 - LCM 驱动 backlight 背光控制原理分析
Detailed analysis of trajectory generation tool in psins toolbox
Redis database, which can be understood by zero foundation Xiaobai, is easy to learn and use!
A. YES or YES?
C ＃ using sqlsugar updatable system to report invalid numbers, how to solve it? Ask for guidance!
What is the principle difference between lateinit and lazy in kotlin
An online duplicate of a hidden bug
【OBS】circlebuf
0726~ resume sorting interview summary
Is it safe for tongdaxin to open an account
面试题 16.05. 阶乘尾数
356页14万字高端商业办公综合楼弱电智能化系统2022版
There is no problem reading from flick CDC to mysql8 and mysql5. What should I do?
JS array de duplication (including simple array de duplication and object array de duplication)
The job created by flinksqlclient will disappear after the restart of Flink. Is there any way?
2022年危险化学品经营单位主要负责人复训题库及答案