list：
list It is a sequential container that can be inserted and deleted at any position within the constant range , And the container can iterate back and forth .
list The bottom layer of is bidirectional 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, point to the previous element and the next element by pointer .
list And forward_list Very similar ： The main difference is that forward_list It's a single linked list , You can only iterate forward , Has made it simpler and more efficient .
Compared with other sequential containers (array,vector,deque),list It is usually inserted at any position , Removing elements is more efficient .
Compared with other sequential containers ,list and forward_list The biggest drawback is that random access to any location is not supported , such as ： To visit list
The third 6 Elements , Must be from a known location ( Like the head or the tail ) Iterate to this location .
structure ：
Constructors ：
* list() Construct empty list
* list (size_type n, const value_type& val = value_type())
Constructive list Included in n The first value is val The elements of
* list (const list& x) copy constructor
* list (InputIterator first, InputIterator last) use [first, last) Element construction in interval list
iterator ：
* begin() Returns the iterator of the first element
* end() Returns the iterator next to the last element
* rbegin() Returns the value of the first element reverse_iterator, Namely end position
* rend() Returns the next position of the last element reverse_iterator, Namely begin position
* cbegin() (C++11) Returns the value of the first element cosnt_iterator
* cend() (C++11) Returns the next position of the last element const_iterator
* crbegin() (C++11) Namely crend() position
* crend() (C++11) Namely crbegin() position
capacity：
* bool empty() const testing list Is it empty , Yes, back true, Otherwise, return false
* size_t size() const return list The number of valid nodes in
function ：
* void push_front (const value_type& val) stay list Insert a value of before the first element val The elements of
* void pop_front() delete list The first element in
* void push_back (const value_type& val) stay list The tail insertion value is val The elements of
* void pop_back() delete list The last element in
* iterator insert (iterator position, const value_type& val) stay list
position Position insertion The input value is val The elements of
* void insert (iterator position, size_type n, const value_type& val)
stay list position Position insertion n The first value is val The elements of
* void insert (iterator position, InputIterator first, InputIterator last)
stay list position Position insertion [first, last) Elements in interval
* iterator erase (iterator position) delete list position Location element
* iterator erase (iterator first, iterator last) delete list in [first, last) area Elements in the space
* void swap (list& x) Exchange two list Elements in
* void resize (size_type n, value_type val = value_type()) take list Change of the number of effective elements in
reach n individual , For the extra elements val fill
* void clear() empty list Effective elements in
notes ：
push_back Tail insertion ： Construct the elements first , The element is then copied to the node , Call constructor before inserting , Call copy constructor again
emplace_back Tail insertion ： Construct the node first , Then the constructor is called to directly construct objects in the node.
emplace_back than push_back More efficient , One less call to copy constructor
list Iterator failure for ：
The invalid iterator of the iterator points to an invalid node , That is, the node has been deleted . because list The underlying structure of is a bidirectional circular linked list with leading nodes
, As a result list It will not cause list The cause of iterator failure of , Invalid only when deleted , And only the iterator pointing to the deleted node fails , Other iterators are not affected .
void TestListIterator1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin();
while (it != l.end()) { // erase() After function execution ,it The node pointed to has been deleted ,
// therefore it invalid , In the next use it Time , It must be assigned a value first l.erase(it); ++it; } }
terms of settlement ： In the implementation erase Will return the iterator of the deleted element .
void TestListIterator1() { int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
list<int> l(array, array+sizeof(array)/sizeof(array[0])); auto it = l.begin();
while (it != l.end()) { it = l.erase(it); // Save the current location to delete //list<int> ::iterator
to_delete=it2; //it2++;// Go back first //L.erase(to_delete);// Delete the node again } }
notes ：erase() function ： Delete an element in the container .
Technology