Linked lists have been learned as early as when we were learning data structures. When I was learning data structures, I implemented them in C language just like my last vector article. The code I wrote at that time was smelly and long, and I had to satisfy a lot of requirements. interface;
future/my_road – Code Cloud – Open Source China (gitee.com)
Open the link and you can find my stl simulation implementation code implementation
Because we talked about the reason why there is an stl container in the last article, this time we will go directly to the topic. Let’s look directly at our stl_list;
Just a precaution: the use of iterators in our list is very clever, so be prepared;
stl_list documentation:
cplusplus.com/reference/list/list/
Using documents to assist learning is more efficient!
The structure of our stl_list is a two-way leading circular linked list. This linked list has many benefits. It is not only convenient for us to traverse, but also convenient for us to search for deletions and insertions. More importantly, the efficiency of our tail insertion is greatly improved;
Let’s still look at its member variables, destructor and parameterless constructor as usual:
Member variables and parameterless constructors and destructors
template<class T>//Node class
struct list_node
{
T_data;
struct list_node* _next;
struct list_node* _prev;
list_node(const T & amp; data = T())
:_next(nullptr)
, _prev(nullptr)
{
_data = data;
}
};
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 list_emptyinit()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
list_emptyinit();
}
~list()//Consider what to do with the destruction of const objects
{
clear();
delete _head;
_head = nullptr;
}
private:
node* _head=nullptr;
};
The member variable of our list only has the _head pointer; its type is the pointer type of our node. We call the constructor of our node class (list_node) through the new node class, and open up the node on the heap like this A large space allows us to store data in it; this way we have our head node; after we have the head node, we need to start storing data;
List insertion and deletion functions
iterator erase(iterator pos)//Delete at pos
{
assert(pos != end());
node* next = pos._node->_next;
node* prev = pos._node->_prev;
next->_prev = prev;
prev->_next = next;
delete pos._node;
return iterator(next);
}
void insert(iterator pos, const T & amp; data)//Insert at pos
{
node* newnode = new node(data);
node* prev = pos._node->_prev;
prev->_next = newnode;
pos._node->_prev = newnode;
newnode->_next = pos._node;
newnode->_prev = prev;
}
void push_back(const T & amp; data)//Tail insertion
{
insert(end(),data);
}
void push_front(const T & amp; data)//head plug
{
insert(begin(),data);
}
void pop_back()//Tail deletion
{
erase(iterator(_head->_prev));
}
void pop_front()//Delete header
{
erase(begin());
}
Let’s look at our insertion function first. When we insert data at the pos position, we need to first get the iterator of the pos position. What is the iterator of the list here? We will talk about it later. It can help if we first understand it as something like a pointer. We find the pos position; we will insert our new new node at the pos position; the erase function also deletes the node at the pos position (it should be noted that deleting the node will definitely cause the iterator to fail, and we need to return our new iterator), These are all easy to understand. You should be able to understand it well by referring to my simulation implementation; now the remaining question is how to pass this iterator to our pos function? What exactly is an iterator?
Iterator:
As the name suggests, iterators are used to iterate and traverse things. How does it do it? Let’s first recall that our previous vector was an iterator written through native pointers in gcc, and iterators were written through encapsulated classes in VS; vector’s data is in a continuous space, so it can use native pointers. + + Traverse our vector directly, but our list cannot be traversed directly using our pointer + +. The list is not a continuous space. If the iterator of our list is a native pointer, will our + + traversal make it possible? The pointer points to a position behind our node in the physical space, but what we want is + + the back pointer points from our node to the next node pointed to by our next, so in order to satisfy this effect, we need to encapsulate our iterator and implement + + Operator overloading allows us to traverse the list;
typedef list_iterator<T> iterator;
typedef const_list_iterator<T> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
template<class T>
struct list_iterator
{
typedef list_node<T> node;
typedef list_iterator<T> iterator;
node* _node;
list_iterator(node* p)
:_node(p)
{}
T & operator *()
{
return _node->_data;
}
T* operator ->()
{
return &_node->_data;
}
iterator & operator + + ()
{
return _node->_next;
}
iterator operator + + (int)
{
node* tmp = _node;
_node= _node->_next;
return tmp;
}
iterator & operator --()
{
return _node->_prev;
}
iterator operator --(int)
{
node* tmp = _node;
_node = _node->_prev;
return tmp;
}
bool operator!=(const iterator & amp;it)
{
return it._node != _node;
}
bool operator==(const iterator & amp; it)
{
return it._node == _node;
}
};
template<class T>
struct list_const_iterator
{
typedef list_node<T> node;
typedef list_const_iterator<T> iterator;
node* _node;
list_const_iterator(node* p)
:_node(p)
{}
const T & operator *()
{
return _node->_data;
}
const T* operator ->()
{
return &_node->_data;
}
iterator & operator + + ()
{
return _node->_next;
}
iterator operator + + (int)
{
node* tmp = _node;
_node = _node->_next;
return tmp;
}
iterator & operator --()
{
return _node->_prev;
}
iterator operator --(int)
{
node* tmp = _node;
_node = _node->_prev;
return tmp;
}
bool operator!=(const iterator & amp; it)
{
return it._node != _node;
}
bool operator==(const iterator & amp; it)
{
return it._node == _node;
}
};
Let’s first look at the implementation in the class. In our iterator class, our member variable is only _node. Its type is still the pointer type of the node. We can use it to point to each item on our list. A node; in our iterator class, we overload operators such as * and + +, which enable our iterator class to have our own defined functions; in this way, we implement a non-const type Iterator class template, which can accept data of different T types;
But what happens if we pass a member variable of cosnt type? const list
But isn’t it very redundant for us to write code like this? We have to write so much code, and the only difference between our const and non-const iterator classes is const T & and const T*, so our boss is very awesome! They solved this problem in an ingenious way;
typedef list_iterator<T,T & amp;,T*> iterator;
typedef list_iterator<T,const T & amp;,const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end()const
{
return const_iterator(_head);
}
template<class T,class Ref,class Ptr>
struct list_iterator
{
typedef list_node<T> node;
typedef list_iterator<T, Ref,Ptr> iterator;
node* _node;
list_iterator(node* p)
:_node(p)
{}
Ref operator *()
{
return _node->_data;
}
Ptr operator ->()
{
return &_node->_data;
}
iterator & operator + + ()
{
return _node->_next;
}
iterator operator + + (int)
{
node* tmp = _node;
_node= _node->_next;
return tmp;
}
iterator & operator --()
{
return _node->_prev;
}
iterator operator --(int)
{
node* tmp = _node;
_node = _node->_prev;
return tmp;
}
bool operator!=(const iterator & amp;it)
{
return it._node != _node;
}
bool operator==(const iterator & amp; it)
{
return it._node == _node;
}
};
Are you very surprised when you see the above code? Hey! Why does this iterator have three template parameters? What’s going on? Don’t worry, let’s go back and take a look at the three template parameters we passed to our list_iterator:
We can see that what is transmitted in our list is T &, T* and constT &. Why is const T* transmitted like this? This is because we need to satisfy the iterator of our const variable; do our overloaded * and -> operators need to return T & amp; and T* respectively? Const variables require const T & and const T*, so we passed three template parameters to write our iterator class const type and non-const type together, which simplifies our code; because our What is written is an iterator template. We only need to change the parameters we pass so that our iterator can be instantiated into the iterator class we need;
And if the list we use is of const type, it must call our begin() and end() function interfaces when using iterators, because the member variable _head of our list is private and we must pass The above two interfaces are used to obtain our iterator, and our begin and end are two functions, and the access to the function will be based on the type of your list, so the begin and end we write have const types. and non-const types;
This is the charm of object-oriented languages. Our members are encapsulated and cannot be accessed outside the class! The iterator can only obtain the node pointer through the interface, and we don’t need to know the underlying layer outside the class, just pass the interface directly! So awesome!
Constructor
void list_emptyinit()
{
_head = new node;
_head->_next = _head;
_head->_prev = _head;
}
list()
{
list_emptyinit();
}
list(size_t n, const T & amp; data = T())
{
list_emptyinit();
for (int i = 0; i < n; i + + )
{
push_back(data);
}
}
list(iterator first, iterator last)
{
list_emptyinit();
while (first != last)
{
push_back(*first);
first++;
}
}
list(const_iterator first, const_iterator last)
{
list_emptyinit();
while (first != last)
{
push_back(*first);
first++;
}
}
void swap(list<T> & amp; n)
{
std::swap(_head, n._head);
}
list(const list<T> & lt)
{
list_emptyinit();
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
}
list & amp;operator=(const list<T> & amp;lt)
{
list<T> tmp(lt.begin(), lt.end());
swap(tmp);
return *this;
}
After passing the iterator level, we see that such a constructor is very simple. The above are several constructors that pass different parameters in a list, including those constructed through iterators and n identical data data constructed through n and data. To understand these constructors, you should read more authoritative documents and read the descriptions in the documents, which is more conducive to learning:
list::list – C++ Reference (cplusplus.com)
The above is the explanation from the authoritative document;
The above is an explanation of the important parts of stl_list;
2023.11.10
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57513 people are learning the system