1, list introduction
list is a sequential container that can be inserted and deleted at any position within the constant range with an efficiency of O(1), and the container can iterate back and forth.
The bottom layer of the list is a two-way linked list structure. Each element in the two-way linked list is stored in independent nodes that are not related to each other. In the node, the pointer points to the previous element and the latter element. The details of the two-way linked list can be moved step by step Data structure (II): linked list.
2, Use of list
1. Constructor
There are four common constructors:
The code is as follows:
int main()
{
list<int> lt1;//Empty linked list
list<int> lt2(4, 100);//The linked list has four nodes with a value of 100
list<int> lt3(lt2);//lt3 is constructed by lt2 copy
list<int> lt4(lt2.begin(), lt2.end());//Constructing lt4 with iterator interval of lt2
return 0;
}
Commissioning is as follows:
2. Traversal
Because the addresses at the bottom of the linked list are not continuous, the traversal mode of subscript + [] is no longer supported. However, as mentioned earlier, the iterator is a unified traversal mode for all containers, so the iterator can still be used to traverse the linked list. Since the range for is replaced by an iterator by the compiler, the range for can also be traversed.
The code is as follows:
int main()
{
list<int> lt1;//Empty linked list
list<int> lt2(4, 100);//The linked list has four nodes with a value of 100
list<int> lt3(lt2);//lt3 is constructed by lt2 copy
list<int> lt4(lt2.begin(), lt2.end());//Constructing lt4 with iterator interval of lt2
//Iterator traversal
list<int>::iterator it1 = lt2.begin();
while (it1 != lt2.end())
{
cout << *it1 << " ";
it1++;
}
cout << endl;
//Range for traversal
for (auto& e : lt4)
cout << e << " ";
cout << endl;
return 0;
}
The operation results are as follows:
3. Data insertion and deletion
(1) Insertion and deletion of tail
The code is as follows:
//Function to print list contents
template<class T>
void print(const list<T>& lt)
{
list<int>::const_iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print(lt);//1 2 3 4 5
lt.pop_back();//Delete the trailing 5
print(lt);//1 2 3 4
return 0;
}
The operation results are as follows:
(2) Insertion and deletion of header
The previous two containers, string and vector, do not support header insertion and deletion because their underlying structure is an array. Data needs to be moved during header insertion and deletion, which consumes a lot of energy, so they do not support these two operations.
However, the bottom layer of the linked list is discontinuous, and the efficiency of inserting and deleting at any position is O(1). There is no need to worry about the consumption caused by moving data, so these two functions are provided.
The code is as follows:
int main()
{
list<int> lt;
lt.push_front(1);
lt.push_front(2);
lt.push_front(3);
lt.push_front(4);
lt.push_front(5);
print(lt);//5 4 3 2 1
lt.pop_front();//Delete the 1 in the header
print(lt);//5 4 3 2
return 0;
}
The operation results are as follows:
(3) Insert and delete anywhere
The code is as follows:
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print(lt);
auto pos = ++lt.begin();//pos points to 2 in lt
lt.insert(pos, -100);//Insert - 100 before pos position
print(lt);
lt.insert(pos, 3, 60);//Insert three 60's in front of pos
print(lt);
lt.erase(pos);//Delete pos location data
print(lt);
return 0;
}
The operation results are as follows:
4. Some simple operation functions
(1)clear
Clear the data in the linked list.
The code is as follows:
int main()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
print(lt);
lt.clear();//empty
print(lt);
return 0;
}
The operation results are as follows:
(2)swap
Note that the swap inside the list class is different from the global swap. The swap inside the list class is more efficient in execution, which can be seen in the following simulation implementation.
The code is as follows:
int main()
{
vector<int> v = { 1, 2, 3, 4, 5 };
list<int> lt1(v.begin(), v.end() - 3);
list<int> lt2(v.begin(), v.end());
cout << "lt1:";
print(lt1);
cout << "lt2:";
print(lt2);
lt1.swap(lt2);
cout << "lt1:";
print(lt1);
cout << "lt2:";
print(lt2);
return 0;
}
The operation results are as follows:
3, Simulation Implementation of list
1. Node structure
As mentioned earlier, the list in STL is implemented with double linked list, so it is not difficult to figure out the following structure.
The code is as follows:
template<class T>
struct _list_node//Using struct, the member defaults to public
{
T _val;
_list_node<T>* _prev;//Point to previous node
_list_node<T>* _next;//Point to the next node
};
Add default constructor to_ list_node structure.
The code is as follows:
template<class T>
struct _list_node
{
_list_node(const T& val = T())
:_val(val)
, _prev(nullptr)
, _next(nullptr)
{}
T _val;
_list_node<T>* _prev;
_list_node<T>* _next;
};
2. Iterator
The bottom layer of list is discontinuous nodes. The structure is very different from that of vector and string, so the iterator of list is also very different from that of vector and string. Iterator is a very important part in the simulation implementation of list.
(1) Preliminary implementation
1) Structure
First of all, the iterator here is still a pointer to the node, but in dereference, + += The behavior of C + + is different from that of native pointers and needs encapsulation. You can also see the advantages of C + + in the following encapsulation process.
The code is as follows:
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;//typedef to simplify the code
node* _pnode;
_list_iterator(node* pnode)
:_pnode(_pnode)
{}
};
2)opearator*
An iterator is a pointer to a node. If you dereference it directly, you get the address of the node, but you actually want to get the data (_val) in the node. Therefore, you need to overload the opearator here*
The code is as follows:
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
T& operator*()
{
return _pnode->_val;//Get the data (_val) in the node and return it
}
};
3)opearator!=
When an iterator is large, it is not the iterator itself that is compared, but the iterator itself_ Whether pnode is equal or not, so we need to overload operator here=
The code is as follows:
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
bool operator!=(const self& s)
{
return _pnode != s._pnode;
}
};
4)operator++
Nor can iterators + + let_ pnode + +, because the address at the bottom of the linked list is not continuous, direct + + may cause illegal access. What you actually want + + is to access the next node, which is realized by overloading. (this is the post + +)
The code is as follows:
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
self& operator++()
{
_pnode = _pnode->_next;
return _pnode;
}
};
5) Constructor
When the constructor is not written, the compiler automatically makes a shallow copy. Specifically here, the hope is that the generated iterator_ pnode is directly the same as the node pointer passed in, so you don't need to implement it yourself.
6) Destructor
If you want to write a destructor, you can only write_ pnode is released and null, but the iterator only accesses a node in the linked list. Whether this node is released or not can be handled by the whole linked list, so the destructor does not need to be written here.
7) Other operations
The following operation overload is relatively simple and will not be repeated here.
The code is as follows:
template<class T>
struct _list_iterator
{
typedef _list_node<T> node;
typedef _list_iterator<T> self;
node* _pnode;
self operator++(int)//Front++
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self operator--(int)//Front--
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
bool operator==(const self& s)
{
return _pnode == s._pnode;
}
};
(2) Question
The above iterator looks ok, but when encountering const type, it will appear that the iterator modifies the contents of const modified variables.
The code is as follows:
template<class T>
void func(const List<T>& lt)
{
List<T>::const_Iterator it = lt.begin();
while (it != lt.end())
{
*it += 2;//Although it is an iterator of const type, the compiler will not report an error if * it is modified here
cout << *it << " ";
it++;
}
cout << endl;
}
Therefore, there is a problem with the iterator implemented above. It cannot handle the problem of modifying the value of const type iterators, so it needs to be modified as follows.
(because the code is too repetitive and has been given above, only screenshots are shown here)
The screenshot is as follows:
It can be seen that the two codes and logic are almost the same, and the repeatability is too high, so such codes are very poor.
(3) Correction
There are three template parameters of the list in the STL library, the data type T, the reference Ref of T, and the pointer Ref of T. after adding the last two parameters, you can use a code to complete the functions of the ordinary iterator and const iterator.
(the code is similar to the above, except that the type of return value is modified)
The code is as follows:
// Data type T & T*
template<class T, class Ref, class Ptr>
struct _list_iterator
{
//Copy construction, assignment overload and destruct do not need to be written
//A node with data type T
typedef _list_node<T> node;
//Iterator with data type T
typedef _list_iterator<T, Ref, Ptr> self;
//Constructor
_list_iterator(node* pnode)
:_pnode(pnode)
{}
Ref operator*()
{
return _pnode->_val;
}
Ptr operator->()
{
return &_pnode->_val;//Address of return value
}
bool operator!=(const self& s) const
{
return _pnode != s._pnode;
}
bool operator==(const self& it) const
{
return _pnode == s._pnode;
}
//Front++
self& operator++()
{
_pnode = _pnode->_next;
return *this;
}
self& operator--()
{
_pnode = _pnode->_prev;
return *this;
}
//Post++
self operator++(int)
{
self tmp(*this);
_pnode = _pnode->_next;
return tmp;
}
self operator--(int)
{
self tmp(*this);
_pnode = _pnode->_prev;
return tmp;
}
//Member variable: pointer to a node
node* _pnode;
};
Type the two iterators in the list class at the same time.
The code is as follows:
template<class T>
class List
{
public:
//Normal iterator with data type T
typedef _list_iterator<T, T&, T*> Iterator;
//const iterator with data type T
typedef _list_iterator<T, const T&, const T*> const_Iterator;
private:
node* _head;
};
3. Implementation of member function
Note that the member variable in the linked list needs a head node. All nodes in the linked list can be accessed according to the prev, next pointer and iterative traversal of the head node.
The function of the header node is to mark the beginning of the linked list and use its prev and next pointers to access the whole linked list. It does not store data itself (even if it is saved, it will not be accessed).
The head of the linked list (the first node storing valid data) is the node pointed to by the next of the head node, and the tail (the previous node of the last node storing valid data) is the head node.
(1) Default constructor
When implementing the default constructor, pay attention to_ head->_ next,_ head->_ Prevs are initialized to_ Head itself, which will be much more convenient in the implementation of subsequent functions. If it is set to nullptr, the problem of null pointer access may need to be solved many times in subsequent processing.
The code is as follows:
template<class T>
class List
{
//A node with data type T
typedef _list_node<T> node;
public:
List()
{
//Note that although the value of the header node is not important, it cannot be given 0. The type that should be T is not necessarily int
//Here's T()
_head = new node(T());
//Both prev and next of the header node point to the header node
_head->_next = _head;
_head->_prev = _head;
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
(2) Copy construction
Copy construction is to form a head node, and then connect the nodes to the back of the head node in turn.
The code is as follows:
template<class T>
class List
{
//A node with data type T
typedef _list_node<T> node;
public:
List(const List<T>& lt)
{
//Generate a new header node
_head = new node(T());
_head->_next = _head;
_head->_prev = _head;
//Connect the following nodes in turn
for (const auto& e : lt)
push_back(e);//This function will be implemented later
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
(3) Assignment operator overload
Implementation method 1: first clear the current linked list, and then connect the data to the current linked list in turn.
The code is as follows:
template<class T>
class List
{
//A node with data type T
typedef _list_node<T> node;
public:
List<T>& operator=(const List<T>& lt)
{
if (this != <)
{
//Clear the linked list first
this->clear();
//Then connect the data to the header of * this in turn
for (const auto& e : lt)
push_back(e);
}
return *this;
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
Implementation method 2: generate a temporary copy when transferring parameters, and exchange the head node of the temporary copy with the head node of * this. Because all data in a linked list is connected behind the head node, the exchange head node exchanges all data.
The code is as follows:
template<class T>
class List
{
//A node with data type T
typedef _list_node<T> node;
public:
// Note that if the reference is not passed during parameter passing, the compiler will automatically generate a temporary copy
List<T>& operator=(List<T> lt)
{
swap(_head, lt._head);
return *this;
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
(4) Destructor
Use the clear function (which will be implemented later) to clear the data in the linked list and release the header node.
The code is as follows:
template<class T>
class List
{
public:
~List()
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
(5) Implementation of some simple functions
The functions implemented below are relatively simple, and the points needing attention have been marked with comments, which will not be repeated here.
The code is as follows:
template<class T>
class List
{
//A node with data type T
typedef _list_node<T> node;
public:
//Iterator with data type T
typedef _list_iterator<T, T&, T*> Iterator;
typedef _list_iterator<T, const T&, const T*> const_Iterator;
Iterator begin()
{
//_ head->_ Next is the actual header of the linked list (the first node storing valid data)
//_ head->_ The next type is node *, and the previous Iterator can be understood as type strong conversion here
return Iterator(_head->_next);
}
const_Iterator begin() const
{
return Iterator(_head->_next);
}
Iterator end()
{
//The tail is the head node
return Iterator(_head);
}
const_Iterator end() const
{
return Iterator(_head);
}
bool empty()
{
return begin() == end();
}
//Traverse to get the number of data in the linked list
size_t size()
{
size_t sz = 0;
Iterator it = begin();
while (it != end())
{
sz++;
it++;
}
return sz;
}
//Traverse and clear all nodes in the linked list
void clear()
{
Iterator it = begin();
while (it != end())
it = erase(it);
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
(6) Data insertion and deletion
1)insert
Insert an element before a position.
The code is as follows:
template<class T>
class List
{
public:
//Insert val before pos
void insert(Iterator pos, const T& val)
{
assert(pos._pnode != nullptr);
//Find the nodes before and after
node* cur = pos._pnode;
node* prev = cur->_prev;
node* newnode = new node(val);
//Nodes before and after connection
cur->_prev = newnode;
newnode->_next = cur;
newnode->_prev = prev;
prev->_next = newnode;
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
2)erase
Delete an element at a location. Note that in order to prevent the iterator from failing, the iterator of the next node should be returned.
The code is as follows:
template<class T>
class List
{
public:
//Delete pos location data
Iterator erase(Iterator pos)
{
assert(pos._pnode != nullptr);
assert(pos != end());
//Find the data before and after
node* prev = pos._pnode->_prev;
node* next = pos._pnode->_next;
//Delete the node at the current location
delete pos._pnode;
//connect
prev->_next = next;
next->_prev = prev;
return Iterator(next);
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};
3) Insertion and deletion of linked list header and footer data
You can reuse the insert and erase codes here, but pay attention to the position of parameters when passing parameters. See the notes for details.
The code is as follows:
template<class T>
class List
{
public:
void push_back(const T& val)
{
//Insert val (that is, the front of the head node) before end() to become a new tail node
insert(end(), val);
}
void push_front(const T& val)
{
//Insert val (that is, after the header node) before begin() to become a new header
insert(begin(), val);
}
void pop_back()
{
//--end() moves to the front of the head node (i.e. the last node)
erase(--end());
}
void pop_front()
{
erase(begin());
}
private:
node* _head;//Only one head node is needed, and all nodes in the linked list can be found according to it
};