Rebirth: I am a C++ cake maker (use of list and simulation implementation)

Use and simulation implementation of list

• Preface
• 1. Use of list
• • 1.1Construction of list
  • 1.2list iterator
  • 1.3list capacity
  • 1.4 View the beginning and end of the list
  • 1.5 List addition, deletion, checking and modification
• 2. Simulation implementation of list
• • 2.1Construction of list
  • 2.2list iterator (emphasis)
  • 2.3List capacity
  • 2.4 View the beginning and end of the list
  • 2.5 List addition, deletion, checking and modification
• Summarize

Foreword

In the last chapter, we learned about the use and simulation implementation of vector, which gave us knowledge about iterator failure. Today we are going to learn about list. The iterator of list is a big difficulty that needs to be explained in detail.

The use of .list

Note: The list in STL is a two-way leading linked list!

Construction of 1.1list

Function name	Function introduction
list (size_type n, const value_type & amp; val = value_type())	The constructed list contains n elements with the value val
list()	Construct an empty list
list (const list & amp; x)	Copy constructor
list (InputIterator first, InputIterator last)	Construct a list with elements in the range [first, last)

#include <iostream>
#include <list>

using namespace std;

void test_list1()
{<!-- -->
list<int> l;
list<int> l1(10, 1);
list<int> l2(l1);
list<int> l3(l1.begin(), l1.end());

for (auto ch : l)
{<!-- -->
cout << ch << " ";
}
cout << endl;

for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

for (auto ch : l2)
{<!-- -->
cout << ch << " ";
}
cout << endl;

for (auto ch : l3)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}
int main()
{<!-- -->
test_list1();
return 0;
}

1.2list iterator

Now we can temporarily treat the iterator of the list as a pointer: pointing to a node. We will carefully study its underlying logic when simulating the implementation.

Function name	Function introduction
begin + end	Returns the iterator of the first element + returns the iterator of the next position of the last element
rbegin + rend	Returns the first The reverse_iterator of the element, which is the end position, returns the reverse_iterator of the next position of the last element, which is the begin position

#include <iostream>
#include <list>

using namespace std;

void test_list2()
{<!-- -->
list<int> l1(10, 1);
list<int>::iterator it = l1.begin();
while (it != l1.end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;
}
int main()
{<!-- -->
test_list2();
return 0;
}

Capacity of 1.3list

Function name	Function introduction
empty	Check whether the list is empty, return true, otherwise return false
size	Return the number of valid nodes in the list

#include <iostream>
#include <list>

using namespace std;

void test_list3()
{<!-- -->
list<int> l1(10, 1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

cout << l1.size() << endl;

while (!l1.empty())
{<!-- -->
l1.pop_back();
}
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

}

int main()
{<!-- -->
test_list3();
return 0;
}

View the first and last of the 1.4 list

Function name	Function introduction
front	Returns a reference to the value in the first node of the list
back	Returns a reference to the value in the last node of the list

#include <iostream>
#include <list>

using namespace std;

void test_list4()
{<!-- -->
list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);

cout << l1.front() << endl;
cout << l1.back() << endl;
}

int main()
{<!-- -->
test_list4();
return 0;
}

Add, delete, and modify 1.5list

Function name	Function introduction
pop_back	Tail deletion
pop_front	Head deletion
push_back	Tail plug
push_front	Head plug
intsert	in list Insert the element with value val in position position
erase	Delete the element in list position position
swap	Exchange the elements in the two lists
clear	Clear the valid elements in the list

#include <iostream>
#include <list>

using namespace std;

void test_list5()
{<!-- -->
list<int> l1;
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);
l1.push_front(2);
l1.push_front(1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.pop_back();
l1.pop_front();
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.insert(l1.end(),5);
l1.insert(l1.begin(),1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

list<int>::iterator it = l1.begin();
l1.erase(it);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

list<int> l2(10, 1);
l1.swap(l2);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;
for (auto ch : l2)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.clear();
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
}

int main()
{<!-- -->
test_list5();
return 0;
}

Simulation implementation of 2.list

Construction of 2.1list

#include <iostream>

using namespace std;

namespace Std
{<!-- -->
    //Content within the node
template<class T>
struct __list_node
{<!-- -->
__list_node(const T & t =T())
:_prev(nullptr)
,_next(nullptr)
,_date(t)
{<!-- -->}
T_date;
__list_node<T>* _prev;
__list_node<T>* _next;
};

    //The member variables of the List class are the nodes of the sentinel position
template <class T>
class List
{<!-- -->
public:
typedef __list_node<T> Node;
void empty_init()
{<!-- -->
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
List()
{<!-- -->
empty_init();
}

private:
Node* _head;
};

void test_list1()
{<!-- -->
List<int> l;
}
}

using namespace Std;

int main()
{<!-- -->
Std::test_list1();
return 0;
}

In this constructor, we can find that the construction method of list is different from the previous string and vector: we have defined two classes. In the List class, the members are defined as nodes one by one, so we also need to define a class to illustrate the nodes. What’s stored in it.

2.2list iterator (emphasis)

Before writing a list iterator, we need to first understand what types of iterators there are. Generally, iterators are classified in two ways: one is classified according to function, and the other is classified according to the nature of the iterator.

Function Category:
1. Forward iterator
2. Reverse iterator

Property classification:
1. One-way iterator: only supports + + iterators, such as: singly linked list
2. Bidirectional iterator: iterator that supports + + and –, such as: list (bidirectional headed linked list)
3. Random access iterator: not only supports + + and – but also + and – iterators, such as: vector, string, deque

And before we write it, we have to think about it: Can the iterator of list just be typedefed like the previous string and vector? If it can’t be done then why? Is there any underlying difference between list, vector, and string?

#include <iostream>

using namespace std;

namespace Std
{<!-- -->
template<class T>
struct __list_node
{<!-- -->
__list_node(const T & t =T())
:_prev(nullptr)
,_next(nullptr)
,_date(t)
{<!-- -->}
T_date;
__list_node<T>* _prev;
__list_node<T>* _next;
};

template<class T>
struct __list_iterator
{<!-- -->
typedef __list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{<!-- -->}

        //Overloaded operator
self & amp; operator + + ()const
{<!-- -->
_node = _node->_next;
return *this;
}

self & amp; operator--()const
{<!-- -->
_node = _node->_prev;
return *this;
}

bool operator!=(const self & amp; it)
{<!-- -->
return _node != it._node;
}

bool operator==(const self & amp; it)
{<!-- -->
return _node == it._node;
}

T & operator*()
{<!-- -->
return _node->_date;
}
};

template <class T>
class List
{<!-- -->
public:
typedef __list_node<T> Node;
typedef __list_iterator<T> iterator;
void empty_init()
{<!-- -->
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
List()
{<!-- -->
empty_init();
}

iterator begin()
{<!-- -->
return _head->_next;//Implicit type conversion
}

iterator end()
{<!-- -->
return _head;//Implicit type conversion
}

void push_back(const T & val)
{<!-- -->
Node* tail = _head->_prev;
Node* newnode = new Node(val);

tail->_next = newnode;
newnode->_prev = tail;

newnode->_next = _head;
_head->_prev = newnode;
}

private:
Node* _head;
};

void test_list2()
{<!-- -->
List<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);

List<int>::iterator it = l.begin();
while (it != l.end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;
}
}

using namespace Std;

int main()
{<!-- -->
Std::test_list2();
return 0;
}

After thinking about the above questions and reading the code, do you have any ideas? Why do we need to redefine a class and overload various operators?
The answer is: The difference between list, vector, and string is that list is a node that is opened one by one. They are not continuous in the heap, while vector and string are continuous spaces. So they can use the iterator as a pointer, and operators such as + + do not need to be overloaded by us, but not for lists. We need to define an iterator class ourselves to use.

But if we look closely at the iterator class, we will find a problem?
When we want to use an iterator to print data, but if the data is modified by const, we will find that the code cannot run successfully, so we also need to write a const iterator class.

//iterator class
template<class T>
struct __list_iterator
{<!-- -->
typedef __list_node<T> Node;
typedef __list_iterator<T> self;
Node* _node;

__list_iterator(Node* node)
:_node(node)
{<!-- -->}

self & amp; operator + + ()const
{<!-- -->
_node = _node->_next;
return *this;
}

self & amp; operator--()const
{<!-- -->
_node = _node->_prev;
return *this;
}

bool operator!=(const self & amp; it)
{<!-- -->
return _node != it._node;
}

bool operator==(const self & amp; it)
{<!-- -->
return _node == it._node;
}

T & operator*()
{<!-- -->
return _node->_date;
}

T* operator->()
{<!-- -->
return &_node->_date;
}
};

//const iterator class
template<class T>
struct __list_const_iterator
{<!-- -->
typedef __list_node<T> Node;
typedef __list_const_iterator<T> self;
Node* _node;

__list_const_iterator(Node* node)
:_node(node)
{<!-- -->}

self & amp; operator + + ()const
{<!-- -->
_node = _node->_next;
return *this;
}

self & amp; operator--()const
{<!-- -->
_node = _node->_prev;
return *this;
}

bool operator!=(const self & amp; it)
{<!-- -->
return _node != it._node;
}

bool operator==(const self & amp; it)
{<!-- -->
return _node == it._node;
}

const T & operator*()
{<!-- -->
return _node->_date;
}

const T* operator->()
{<!-- -->
return &_node->_date;
}
};

After comparing the two codes, we found that the difference between the const iterator class and the iterator class is only the difference in the return values of the two overloaded operators * and ->. At this time, because the iterator modified by const can only Reading cannot be written and these are the only two operators we can write to. So we can combine these two classes into one by modifying the parameters of the template. This is also the method used in STL

 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)
{<!-- -->}

self & amp; operator + + ()const
{<!-- -->
_node = _node->_next;
return *this;
}

self & amp; operator--()const
{<!-- -->
_node = _node->_prev;
return *this;
}

bool operator!=(const self & amp; it)
{<!-- -->
return _node != it._node;
}

bool operator==(const self & amp; it)
{<!-- -->
return _node == it._node;
}

Ref operator*()const
{<!-- -->
return _node->_date;
}

Ptr operator->()const
{<!-- -->
return &_node->_date;
}
};

template <class T>
class List
{<!-- -->
public:
typedef __list_node<T> Node;
typedef __list_iterator<T,T & amp;,T*> iterator;
typedef __list_iterator<T,const T & amp;,const T*> const_iterator;
void empty_init()
{<!-- -->
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
List()
{<!-- -->
empty_init();
}

iterator begin()
{<!-- -->
return _head->_next;//Implicit type conversion
}

iterator end()
{<!-- -->
return _head;//Implicit type conversion
}

void push_back(const T & val)
{<!-- -->
Node* tail = _head->_prev;
Node* newnode = new Node(val);

tail->_next = newnode;
newnode->_prev = tail;

newnode->_next = _head;
_head->_prev = newnode;
}

private:
Node* _head;
};

Capacity of 2.3list

The interface for list is too simple in terms of capacity. One is empty and the other is large. Just add a _size to the member variable, and + + _size when inserting and –_size when deleting.

View the first and last of 2.4 list

 T & front()
{<!-- -->
return _head->_next->_date;
}

T & back()
{<!-- -->
return _head->_prev->_date;
}

Add, delete, and modify 2.5list

 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)
{<!-- -->}


self & operator + + ()
{<!-- -->
_node = _node->_next;
return *this;
}

self & operator--()
{<!-- -->
_node = _node->_prev;
return *this;
}
self operator + + (int)
{<!-- -->
self tmp = this;
_node = _node->_next;
return *tmp;
}

self operator--(int)
{<!-- -->
self tmp = this;
_node = _node->_prev;
return *tmp;
}

bool operator!=(const self & amp; it)
{<!-- -->
return _node != it._node;
}

bool operator==(const self & amp; it)
{<!-- -->
return _node == it._node;
}

Ref operator*()
{<!-- -->
return _node->_date;
}

Ptr operator->()
{<!-- -->
return &_node->_date;
}
};

template <class T>
class List
{<!-- -->
public:
typedef __list_node<T> Node;
typedef __list_iterator<T,T & amp;,T*> iterator;
typedef __list_iterator<T,const T & amp;,const T*> const_iterator;
void empty_init()
{<!-- -->
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
List()
{<!-- -->
empty_init();
}

~List()
{<!-- -->
iterator it = begin();
while (it != end())
{<!-- -->
it = erase(it);
}
delete _head;
}

List(const List & l)
{<!-- -->
for (auto ch : l)
{<!-- -->
push_back(ch);
}
}

void Swap(List & tmp)
{<!-- -->
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}

List & amp; operator=(List & amp; tmp)
{<!-- -->
Swap(tmp);
return *this;
}

iterator begin()
{<!-- -->
return _head->_next;//Implicit type conversion
}

iterator end()
{<!-- -->
return _head;//Implicit type conversion
}

size_t size()
{<!-- -->
return _size;
}

T & front()
{<!-- -->
return _head->_next->_date;
}

T & back()
{<!-- -->
return _head->_prev->_date;
}

void push_back(const T & val)
{<!-- -->
/*Node* tail = _head->_prev;
Node* newnode = new Node(val);

tail->_next = newnode;
newnode->_prev = tail;

newnode->_next = _head;
_head->_prev = newnode;

+ + _size;*/
insert(end(), val);
}
void push_front(const T & val)
{<!-- -->
insert(begin(), val);
}

void pop_back()
{<!-- -->
erase(--end());
}

void pop_front()
{<!-- -->
erase(begin());
}

void insert(iterator pos, const T & val)
{<!-- -->
Node* newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;

newnode->_next = cur;
cur->_prev = newnode;

newnode->_prev = prev;
prev->_next = newnode;

+ + _size;
}

iterator erase(iterator pos)
{<!-- -->
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;

delete cur;

prev->_next = next;
next->_prev = prev;

--_size;

return iterator(next);
}

void clear()
{<!-- -->
iterator it = begin();
while (it != end())
{<!-- -->
it = erase(it);
}
}

private:
Node* _head;
size_t _size;
};

void test_list4()
{<!-- -->
List<int> l1;
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);
l1.push_front(2);
l1.push_front(1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.pop_back();
l1.pop_front();
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.insert(l1.end(), 5);
l1.insert(l1.begin(), 1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

List<int>::iterator it = l1.begin();
l1.erase(it);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;


l1.clear();
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
}
}

After writing the erase and iterator, the copy construction and destruction of the list can also be written. Then the overloading of the = operator can also be written in modern writing.

Summary

After simulating and implementing the list, we can find that we are familiar with using lists, but when simulating the implementation, we met the iterator of the list for the first time. This first encounter made us suffer a lot, but after understanding it After looking at the underlying logic, we can find that this is also very easy to understand. We will also write this way when facing binary trees in the future, so today’s list is over. See you next time, stack and deque~

#include <iostream>

using namespace std;

namespace Std
{<!-- -->
template<class T>
struct __list_node
{<!-- -->
__list_node(const T & t =T())
:_prev(nullptr)
,_next(nullptr)
,_date(t)
{<!-- -->}
T_date;
__list_node<T>* _prev;
__list_node<T>* _next;
};

//template<class T>
//struct __list_iterator
//{<!-- -->
// typedef __list_node<T> Node;
// typedef __list_iterator<T> self;
// Node* _node;

// __list_iterator(Node* node)
// :_node(node)
// {}

// self & amp; operator + + ()const
// {<!-- -->
// _node = _node->_next;
// return *this;
// }

// self & amp; operator--()const
// {<!-- -->
// _node = _node->_prev;
// return *this;
// }

// bool operator!=(const self & amp; it)
// {<!-- -->
// return _node != it._node;
// }

// bool operator==(const self & amp; it)
// {<!-- -->
// return _node == it._node;
// }

// T & operator*()
// {<!-- -->
// return _node->_date;
// }

// T* operator->()
// {<!-- -->
// return &_node->_date;
// }
//};

/*template<class T>
struct __list_const_iterator
{
typedef __list_node<T> Node;
typedef __list_const_iterator<T> self;
Node* _node;

__list_const_iterator(Node* node)
:_node(node)
{}

self & operator + + ()
{
_node = _node->_next;
return *this;
}

self & operator--()
{
_node = _node->_prev;
return *this;
}

bool operator!=(const self & amp; it)
{
return _node != it._node;
}

bool operator==(const self & amp; it)
{
return _node == it._node;
}

const T & operator*()
{
return _node->_date;
}

const T* operator->()
{
return &_node->_date;
}
};*/

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)
{<!-- -->}


self & operator + + ()
{<!-- -->
_node = _node->_next;
return *this;
}

self & operator--()
{<!-- -->
_node = _node->_prev;
return *this;
}
self operator + + (int)
{<!-- -->
self tmp = this;
_node = _node->_next;
return *tmp;
}

self operator--(int)
{<!-- -->
self tmp = this;
_node = _node->_prev;
return *tmp;
}

bool operator!=(const self & amp; it)
{<!-- -->
return _node != it._node;
}

bool operator==(const self & amp; it)
{<!-- -->
return _node == it._node;
}

Ref operator*()
{<!-- -->
return _node->_date;
}

Ptr operator->()
{<!-- -->
return &_node->_date;
}
};

template <class T>
class List
{<!-- -->
public:
typedef __list_node<T> Node;
typedef __list_iterator<T,T & amp;,T*> iterator;
typedef __list_iterator<T,const T & amp;,const T*> const_iterator;
void empty_init()
{<!-- -->
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
List()
{<!-- -->
empty_init();
}

~List()
{<!-- -->
iterator it = begin();
while (it != end())
{<!-- -->
it = erase(it);
}
delete _head;
}

List(const List & l)
{<!-- -->
for (auto ch : l)
{<!-- -->
push_back(ch);
}
}

void Swap(List & tmp)
{<!-- -->
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}

List & amp; operator=(List & amp; tmp)
{<!-- -->
Swap(tmp);
return *this;
}

iterator begin()
{<!-- -->
return _head->_next;//Implicit type conversion
}

iterator end()
{<!-- -->
return _head;//Implicit type conversion
}

size_t size()
{<!-- -->
return _size;
}

T & front()
{<!-- -->
return _head->_next->_date;
}

T & back()
{<!-- -->
return _head->_prev->_date;
}

void push_back(const T & val)
{<!-- -->
/*Node* tail = _head->_prev;
Node* newnode = new Node(val);

tail->_next = newnode;
newnode->_prev = tail;

newnode->_next = _head;
_head->_prev = newnode;

+ + _size;*/
insert(end(), val);
}
void push_front(const T & val)
{<!-- -->
insert(begin(), val);
}

void pop_back()
{<!-- -->
erase(--end());
}

void pop_front()
{<!-- -->
erase(begin());
}

void insert(iterator pos, const T & val)
{<!-- -->
Node* newnode = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_prev;

newnode->_next = cur;
cur->_prev = newnode;

newnode->_prev = prev;
prev->_next = newnode;

+ + _size;
}

iterator erase(iterator pos)
{<!-- -->
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;

delete cur;

prev->_next = next;
next->_prev = prev;

--_size;

return iterator(next);
}

void clear()
{<!-- -->
iterator it = begin();
while (it != end())
{<!-- -->
it = erase(it);
}
}

private:
Node* _head;
size_t _size;
};

void test_list1()
{<!-- -->
List<int> l;
}

void test_list2()
{<!-- -->
List<int> l;
l.push_back(1);
l.push_back(2);
l.push_back(3);
l.push_back(4);
l.push_back(5);

List<int>::iterator it = l.begin();
while (it != l.end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;
}


void test_list3()
{<!-- -->
List<string> l;
l.push_back("xxx");
l.push_back("xxx");
l.push_back("xxx");
l.push_back("xxx");
l.push_back("xxx");
l.push_back("xxx");

for (auto ch : l)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}

void test_list4()
{<!-- -->
List<int> l1;
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);
l1.push_front(2);
l1.push_front(1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.pop_back();
l1.pop_front();
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

l1.insert(l1.end(), 5);
l1.insert(l1.begin(), 1);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

List<int>::iterator it = l1.begin();
l1.erase(it);
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
cout << endl;


l1.clear();
for (auto ch : l1)
{<!-- -->
cout << ch << " ";
}
}
}



using namespace Std;

int main()
{<!-- -->
Std::test_list4();
return 0;
}