The underlying implementation of list container in C++ is usedTake the lead in bidirectional loop link listThe structure of , pointing to the previous and next nodes through a pointer. It also has the advantages and disadvantages of a two-way linked list,For example, the advantage is that data is not required to be moved when inserting and deleting at any location. The disadvantage is that it cannot be randomly accessed at any location. It must be traversed to the node to be accessed; and the list also requires additional space to store information of the previous and next nodes.
Let's learn about the common interfaces of list
1. Constructor
//Construct an empty listlist() //Copy constructionlist (const list& x); //Iterator construction, using templates can be suitable for different typestemplate <class InputIterator> list (InputIterator first, InputIterator last); //Construct n lists with val valueslist (size_type n, const value_type& val = value_type())
2. Iterator
//Return to the iterator at the start positioniterator begin(); const_iterator begin() const; //Return to the iterator at the end positioniterator end(); const_iterator end() const;
It should be noted that the iterator here is not a native pointer at the bottom, and the specific implementation is given later.
3. Capacity operation
//Judge whether it is emptybool empty() const; //Return the number of valid nodessize_type size() const;
4. Element acquisition
//Return the reference to the first elementreference front(); const_reference front() const; //Return the reference to the end elementreference back(); const_reference back() const;
5. Add, delete, modify and check
//Head plugvoid push_front (const value_type& val); //Tail insertvoid push_back (const value_type& val); //Head Deletevoid pop_front(); //Delete the endvoid pop_back(); //Insert at any positioniterator insert (iterator position, const value_type& val); //Delete at any locationiterator erase (iterator position); //Swap elements in two linked listsvoid swap (list& x); //Clear the elements in the linked listvoid clear();
After understanding the addition, deletion, search and modification of the linked list, we think about a question.
Does list cause iterator failure like vector and string? Since this is a chain structure, its memory is not continuous in physical space.Therefore, if you just insert an element, there will be no problem of iterator failure. Only the problem of iterator failure will occur when deleting, and only the iterator that deletes nodes will fail here.
The simulation implementation of list is given below
1. Node list_node design
The structure of a node is the structure of a bidirectional linked list. It can also be written as a structure that is directly publicly owned by the class members.
template<class T>
class list_node
{
public:
list_node<T>* _next;
list_node<T>* _prev;
T _val;
list_node(const T& val = T())//Default anonymous object :_next(nullptr)
,_prev(nullptr)
,_val(val)
{}
};2. Iterator design
The iterator design about const is different from the previous string and vector, and another layer of encapsulation of the node's pointer. Because here we need to support -> arrows and overloads. We usually want to access a pointer variable by dereference.Contents of stored data (_val); and -> is to visitMembers of the data content.From this feature, we can draw a conclusion that when implementing list iterators, the return types of overload dereferences and arrows are different, so how do we control them?
In fact, this effect can be achieved here only by controlling the template parameters. The specific code is as follows
template<class T,class Ref ,class Ptr>
class _list_iterator
{
public:
//In fact, iterator only borrows nodes for access, rather than managing these nodes, so the linked list manages nodes typedef list_node<T> Node;
typedef _list_iterator<T, Ref,Ptr> self;
Node* _node;
_list_iterator(Node* node)
:_node(node)
{}
Ref operator*()// Here we control the return type of dereference {
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
//Pre-option++ self& operator++()
{
_node = _node->_next;
return *this;
}
//Rear++ self operator++(int)
{
self temp(*this);
_node = _node->_next;
return temp;
}
//Previous- self& operator--()
{
_node = _node->_prev;
return *this;
}
//Rear- self operator--(int)
{
self temp(*this);
_node = _node->_prev;
return temp;
}
bool operator!=(const self& it) const
{
return _node != it._node;
}
bool operator==(const self& it) const
{
return _node == it._node;
}
};Here Ref controls the dereferenced return type, Ptr controls the return type of the arrow; and in this class, the typedef method is used to control the return types of self-increment and self-decrease.
And there is another advantage in writing this way that you can use normal template parameters for ordinary iterators, and use const template parameters for const iterators.
3. Simulation implementation of common interfaces
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef _list_iterator<T,T&,T*> iterator;//Inline Class typedef _list_iterator<T,const T&,const T*> const_iterator;
//The design of the const iterator here is wrong, because the const iterator hopes that the pointing content will not be modified //This design is that the iterator itself cannot be modified //typedef const _list_iterator<T> const_iterator;
iterator begin()
{
return _head->_next;//The single parameter constructor supports implicit type conversion }
const_iterator begin() const
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator end() const
{
return _head;
}
void empty_init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
list()
{
empty_init();
}
//lt2(lt1)
list(const list<T>& lt)
//list(const list& lt)//This is not recommended {
empty_init();
//Travel over lt1 and directly insert lt2 tail to lt1 //There is high efficiency of citation here for (const auto& e : lt)
{
push_back(e);
}
}
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
}
list<T>& operator=(list<T> lt)
//list& operator=(list lt)//This is the same as the copy structure above {
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)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());//Call here --, the prev of the head node is the tail }
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
return newnode;
}
iterator erase(iterator pos)//The iterator will be invalid here, and the iterator will return to the next position. {
assert(pos != end());
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return next;
}
size_t size()
{
size_t sz = 0;
iterator it = begin();
while (it != end())
{
++sz;
++it;
}
return sz;
}
private:
Node* _head;
};The commonly used interface implementations here are similar to the leading bidirectional linked lists in the data structure. What needs to be noted is the problem of the failure of the father iterator.
Finally, let’s summarize the advantages and disadvantages of vector and list
(1) Underlying structure: vector is continuously stored, a dynamic order table; list is discontinuous storage, a leading two-way circular link table
(2) Random access: vector supports [] random access; list does not support random access
(3) Insertion and deletion efficiency: The insertion and deletion of vector requires moving data; the insertion and deletion of list does not require moving data.
(4) Space utilization: The vector is a continuous storage space, which is not easy to cause memory fragmentation problems, and the space utilization rate is high; the list is a discontinuous storage space, and small nodes are prone to memory fragmentation problems, and the space utilization rate is low.
(5) Iterator: The iterator of vector is a native pointer; the iterator of list encapsulates the native pointer in another layer.
(6) Problem of iterator failure: When vector is inserted and deleted again, it will cause iterator to fail and need to be reassigned; list will only cause iterator failure when it is deleted again.
This is the article about the common interfaces of C++ list and simulated implementation example code. For more related contents of commonly used interfaces of C++ list, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!