This article has participated in the call for good writing activities, click to view: back end, big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!
In the previous article, we introduced the overall structure and implementation of the deque container. The link is as follows:
Based on STL source code analysis deQUE container overall implementation and memory structure
Following the previous chapter, this article continues to analyze the realization principle of deQUE container insertion, deletion and value based on STL source code in GCC. From the perspective of the questioner, it analyzes what happened in the process of these operations, and explains the scenarios suitable for the use of deQUE container and matters needing attention when using it.
To clarify, I am using the GCC7.1.0 compiler, and the standard library source code is also in this version.
As usual, take a look at the outline of this article, which is as follows:
0. Deque iterator description
Before we start talking about the implementation of insert, delete, etc., let’s take a look at the special iterators of a deque.
Struct _Deque_iterator: struct _Deque_iterator: struct _Deque_iterator: struct _Deque_iterator: struct _Deque_iterator: struct _Deque_iterator: struct _Deque_iterator: struct _Deque_iterator
_Elt_pointer _M_cur; // Used to save the current position of the iterator
_Elt_pointer _M_first; // Save the start position of the buffer that the iterator currently belongs to
_Elt_pointer _M_last;// Save the end position of the current buffer to which the iterator belongs
_Map_pointer _M_node; // Used to save the current location of the iterator node
Copy the codeTherefore, the deque uses the above member variables to uniquely identify an iterator. The following insert and delete operations will use these member variables in many places, which will not be explained separately.
1. Insert an element into the deque
A deque can be inserted from either end of the queue, but it can also be inserted from the middle.
1.1 What happens when you insert it from both ends
Push_front (); push_front ();
void push_front(const value_type& __x)
{
// Insert directly from back to front when there is enough space in the header buffer
if (this->_M_impl._M_start._M_cur ! =this->_M_impl._M_start._M_first)
{
_Alloc_traits::construct(this->_M_impl,
this->_M_impl._M_start._M_cur - 1,
__x);
--this->_M_impl._M_start._M_cur;
}
else
// If the buffer is insufficient, you can apply for a new buffer instead of applying for a new node. If the nodes are insufficient, you can apply for a whole block of node memory again and copy all the addresses saved by the original node. However, the buffer does not copy
_M_push_front_aux(__x);
}
Copy the codeCombined with the code and comments, the flow from the header is clearer, as shown below:
According to the picture, the process of inserting a deque from the beginning is clear, but it is not clear how to do it when there are not enough nodes in the middle, so let’s continue.
The number of nodes in a deque is determined by the number of elements. Here is a formula: The default size of each buffer is 8 if the number of elements plus 2 is less than 8. That is, even if you specify 0 as the initial number of elements, it will be constructed with 8 nodes. Buffer will only apply for one.
In _M_push_front_aux, _M_reserve_map_at_front is called. According to this function, if the number of nodes to be added is greater than the number of remaining standby nodes at the head of the deque, Call the function _M_reallocate_map, so let’s look at the implementation of this function as follows:
template <typename _Tp, typename _Alloc>
void
deque<_Tp, _Alloc>::
_M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
{
const size_type __old_num_nodes
= this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
_Map_pointer __new_nstart;
if (this->_M_impl._M_map_size > 2* __new_num_nodes) {......// The day of the headinsert scene does not go here, so omitted
}
else
{
// Calculate the number of a new node. If the number of nodes to be added is smaller than the number of original nodes, multiply the number of original nodes by 2 and add 2 standby nodes. Otherwise, the number of old nodes + the number of nodes to be added +2
size_type __new_map_size = this->_M_impl._M_map_size
+ std::max(this->_M_impl._M_map_size,
__nodes_to_add) + 2;
// Apply for a new block of memory to store the node
_Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
__new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
+ (__add_at_front ? __nodes_to_add : 0);
std::copy(this->_M_impl._M_start._M_node,
this->_M_impl._M_finish._M_node + 1,
__new_nstart);
// Free the old node memory
_M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
this->_M_impl._M_map = __new_map;
this->_M_impl._M_map_size = __new_map_size;
}
this->_M_impl._M_start._M_set_node(__new_nstart);
this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
}
Copy the codeThis function is divided into two branches, and obviously we will go into the else branch at this time, it will first calculate a new node number, this number is usually on the basis of the original artistic work of high order with 2 plus 2 standby node, specific rules to see code comments, and then based on the current calculation node number to apply for a new memory for storage node, The original node memory is freed.
Push_back (); push_front (); push_back ();
In particular, if the size is specified during construction, then the default initialization is also performedpush_frontandpush_backIn other words, the value of the element is not changed. Therefore, it is better not to specify the size of the element when constructing, so that the subsequent calls will be clearer and correct.
1.2 What happens when you insert it in the middle
Insert from the middle needs to be inserted according to the iterator position, call insert function, an insert source code implementation as follows:
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
#if __cplusplus >= 201103L
insert(const_iterator __position, const value_type& __x)
#else
insert(iterator __position, const value_type& __x)
#endif
{
// The current iterator is inserted directly into the beginning
if (__position._M_cur == this->_M_impl._M_start._M_cur)
{
push_front(__x);
return this->_M_impl._M_start;
}
// The current iterator is inserted directly from the tail
else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
{
push_back(__x);
iterator __tmp = this->_M_impl._M_finish;
--__tmp;
return __tmp;
}
// This is the normal insertion from the middle
else
return _M_insert_aux(__position._M_const_cast(), __x);
}
Copy the codeAccording to the code, non-special cases, mainly see function _M_insert_aux implementation, the source code is as follows:
template<typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
value_type __x_copy = __x; // XXX copy
difference_type __index = __pos - this->_M_impl._M_start;
// If the insertion position is in the front part of the deque, move the front part from back to front
if (static_cast<size_type>(__index) < size(a) /2)
{
// Insert a bit in the header to see if the memory needs to be expanded
push_front(_GLIBCXX_MOVE(front()));
iterator __front1 = this->_M_impl._M_start;
++__front1;
iterator __front2 = __front1;
++__front2;
__pos = this->_M_impl._M_start + __index;
iterator __pos1 = __pos;
++__pos1;
// The first half of the element is moved forward by 1 bit. Of course, the previous header element is not reprocessed here
_GLIBCXX_MOVE3(__front2, __pos1, __front1);
}
// If the insertion position is in the back of the deque, move the back from front to back
else
{
// Insert 1 bit at the end to see if the memory needs to be expanded
push_back(_GLIBCXX_MOVE(back()));
iterator __back1 = this->_M_impl._M_finish;
--__back1;
iterator __back2 = __back1;
--__back2;
__pos = this->_M_impl._M_start + __index;
// Move the back half of this by 1 bit from front to back
_GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
}
// Insert data
*__pos = _GLIBCXX_MOVE(__x_copy);
return __pos;
}
Copy the codeAs you can see from the code, inserting from the middle is basically moving the first half of the container or the second half of the container depending on where you want to insert it, and whether you need to expand the container or not is still done by the head end and the tail end. As you can see here, the time complexity of the middle insert is O(n).
2. What happens when you delete an element from a deque
Delete, like insert, can be deleted from both ends, or can be deleted according to the specified location.
2.1 What Will Happen if both Ends are Deleted
Here to delete the tail as an example, the source code is as follows:
void pop_back(a) _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_nonempty();
if (this->_M_impl._M_finish._M_cur ! =this->_M_impl._M_finish._M_first)
{
--this->_M_impl._M_finish._M_cur;
_Alloc_traits::destroy(this->_M_impl,
this->_M_impl._M_finish._M_cur);
}
else
_M_pop_back_aux();
}
Copy the codeIterator at the end of the deque container, if the current position is not equal to the starting position, directly put forward a current position, and bring new elements of the destruction of the current position, that is the end of the iterator points to the current position is actually has already been deleted data, if is equal to the starting position, then you want to change the buffer, This calls the _M_pop_back_aux function, so let’s look at the implementation of this function:
template <typename _Tp, typename _Alloc>
void deque<_Tp, _Alloc>::
_M_pop_back_aux()
{
_M_deallocate_node(this->_M_impl._M_finish._M_first);
this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
_Alloc_traits::destroy(_M_get_Tp_allocator(),
this->_M_impl._M_finish._M_cur);
}
Copy the codeIn this case, the buffer where the current end iterator resides is released directly, and then the new current position is calculated before deleting. According to this logic, the time complexity of deleting the end is O(1).
A header deletion is very much the same as a tail deletion. Without further elaboration, let’s look at what a middle deletion looks like.
2.2 What happens if you delete it from the middle
Delete from the middle and call erase. The deque has a number of overloads to erase.
iterator
#if __cplusplus >= 201103L
erase(const_iterator __first, const_iterator __last)
#else
erase(iterator __first, iterator __last)
#endif
{ return _M_erase(__first._M_const_cast(), __last._M_const_cast()); }
Copy the codeThis function removes a piece of data from two locations and calls _M_erase directly.
template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::_M_erase(iterator __first, iterator __last)
{
// If the start position is equal to the end position, there is no need to delete it
if (__first == __last)
return __first;
// If the start position is equal to the start position of the container, and the end position is equal to the end position of the container, then the entire container can be emptied
else if (__first == begin() && __last == end())
{
clear(a);return end(a); }else
{
const difference_type __n = __last - __first;
const difference_type __elems_before = __first - begin(a);If the number of elements in front of the data segment to be inserted is less than the number of elements behind it, the data segment is processed from the beginning, otherwise it is processed from the end
if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2)
{
// If the start position of the data segment to be deleted is not equal to the start position of the container, then the remaining data is overwritten backwards
if(__first ! =begin())
_GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last);
// Delete extra elements
_M_erase_at_begin(begin() + __n);
}
else
{
// This is similar to if
if(__last ! =end())
_GLIBCXX_MOVE3(__last, end(), __first);
_M_erase_at_end(end() - __n);
}
return begin() + __elems_before; }}Copy the codeIn other words, to delete from the middle is to overwrite the data to be deleted with the header or tail data, and then delete the redundant data from the header and tail data. In this process, if the data segment to be deleted has a span of the buffer, the buffer will also be destroyed.
According to the above logic, the time to remove elements from the middle is order (n).
2.3 How to empty the entire DeQUE container
Clear the deque using the clear function as follows:
void
clear(a) _GLIBCXX_NOEXCEPT
{ _M_erase_at_end(begin()); }
Copy the codeThe _M_erase_at_end function deletes all buffers from the input parameter to the end of the container, and all buffers are cleared in the process.
3. Deque retrieves elements and iterates
3.1 Get elements using subscripts and at functions
The subscript is the overloaded operator [], as follows:
reference
operator[](size_type __n) _GLIBCXX_NOEXCEPT
{
__glibcxx_requires_subscript(__n);
return this->_M_impl._M_start[difference_type(__n)];
}
Copy the codeIterator (deque_iterator); iterator (deque_iterator);
reference
operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
{ return* (*this + __n); }
Copy the code*this+__n calls another overloaded operator + from _Deque_iterator: operator +;
_Self
operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
return __tmp += __n;
}
Copy the codeOperator += = (operator +=); operator += (operator +=);
_Self& operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
{
const difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
_M_cur += __n;
else
{
const difference_type __node_offset =
__offset > 0 ? __offset / difference_type(_S_buffer_size())
: -difference_type((-__offset - 1)
/ _S_buffer_size()) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first + (__offset - __node_offset
* difference_type(_S_buffer_size()));
}
return *this;
}
Copy the codeThis is where you actually get the data, which is not easy, because there are four overloaded operator functions called, and the subscript time is O(1).
The source of the at function is as follows:
reference at(size_type __n) const
{
_M_range_check(__n);
return (*this)[__n];
}
Copy the codeAs you can see from the code, the at simply checks the boundary value, and then calls the subscript operator function directly.
The deque also takes O(1) to get elements by subscript or at.
3.2 Traversing a Deque
We don’t think iterating through a deque is too complicated. We don’t think iterating through a deque is too complicated. We do not think iterating through a deque is too complicated.
#include <iostream>
#include <deque>
using namespace std;
int main(a)
{
deque<int> dq(10.5);// Construct a deque with 10 elements and all elements of 5
deque<int>::const_iterator it = dq.begin(a);for(; it ! = dq.end(a); ++it ) { cout <<"The first" << it - dq.begin() < <The value of each element is: << *it << endl;
}
return 0;
}
Copy the codeIt is no different from vector traversal, except that the operator overloads functions.
4. Deque container usage summary
Now we summarize the deque as follows:
- A deque is a double-ended queue with a contiguous segment of memory called a node. Each node holds an address, either empty or pointing to a buffer block.
- The elements of a DEQUE are actually stored in buffer blocks one by one, so the expansion of a DEQUE or a large number of data emptying will involve the operation of applying for dynamic memory for many times or releasing dynamic memory for many times.
- It can be inserted and deleted from both ends, and the time complexity is O(1).
- You can insert and delete from the middle, and then you move the elements, so the time is O(n);
- Because it is a double-ended queue, both of which operate by address, the speed of deque to obtain elements is also very fast, and the time complexity is O(1).
Then according to the above summary, we know if you need at the same time from the beginning and end for insertion or deletion, use the deque container will be more efficient, such as waiting in line when a vote of 12306 to rob scenario, then need to enter the queue, here first if you get the tickets need to be removed from the queue, a deque container can be used at this time.
Well, this article is for everyone to introduce here, feel the content of your useful, remember to click on the like and follow oh ~