Some summary of the list containers in the STL

1. About the list container

A list is a sequential container. The function of list container is actually very similar to the two-way linked list in the data structure. The data elements in list are concatenated into a linear list in the logical sense through the linked list pointer. In other words, list also has the main advantage of the linked list. The implementation of a list looks something like this: each node of a list has three fields: the precursor element pointer field, the data field, and the successor element pointer field. The precursor element pointer field holds the first address of the precursor element. The data domain is the data of the node. The next element pointer field holds the first address of the next element. In fact, there are some similarities between list and circular linked list, that is, the pointer field of the precursor element of the head node stores the first address of the tail element in the linked list, while the pointer field of the successor element of the tail node of list stores the first address of the head node. In this way, list actually constitutes a two-way circular chain. Since the list element node is not required to be in a continuous segment of memory, it is obvious that fast random access is not supported in the list, so for the iterator, the iterator can only be moved to the next/precursor node element by the "++" or "--" operation. You can't do +n or -n operations on iterators, which is different from vector and so on.

I think it is necessary to compare the three commonly used sequences:

Vector: Vector and built - in an array of similar, with a continuous memory space, can very good support random access, namely the [] operator, but because of its memory space is continuous, so in the middle of insertion and deletion would cause a copy of the memory block, on the other hand, when inserted into the more elements, the reserved memory space may not be good enough, you need to apply for a big enough memory and copies of the original data to the new memory space. These affect the efficiency of the vector, but actually the most used is the vector container, it is recommended to use the vector efficiency most of the time is generally good.

The list: List is a bidirectional linked list in the data structure (according to the sgi STL source code), so its memory space is discontinuous and data is accessed through Pointers. This feature makes its random access very inefficient, so it does not provide overloading of the [] operator. But because of the nature of linked lists, it can support deletions and insertions anywhere with great efficiency.

A deque: Deque is a double-ended queue, its implementation is not clear, but it is known that it has the following two characteristics: it supports the [] operator, that is, it supports random access, and the efficiency of vector is not much different, it supports the operation on both ends: push_back,push_front,pop_back,pop_front, etc., and on both ends of the operation and the efficiency of list.

Therefore, in the actual use, how to choose which of the three containers, should be based on your needs, specific can follow the following principles:
1. If you need efficient random access, regardless of insert and delete efficiency, use vector
2. If you need a lot of inserts and deletions and don't care about instant access, use list
3. If you need instant access and are concerned with the insertion and deletion of data at both ends, use deque.

2. Functions commonly used in list

2.1 constructor in list:

List () declares an empty list;

List (n) declares a list of n elements, each constructed by its default constructor T()

List (n,val) declares a list of n elements, each of which is derived by its copy constructor T(val)

List (n,val) declares the same list as above

List (first,last) declares a list whose initial values are derived from the elements in the sequence specified by the interval

--------------------------------------------------------------------------------

2.2 begin() and end() : By calling the member function begin() of the list container to get an iterator pointing to the starting position of the container, you can call the function end() of the list container to get the next position at the end of the list, which is equivalent to: the NTH +1 position a[n] in int a[n], which does not exist in fact and cannot be accessed, and is often used as the end condition of loop end judgment.

--------------------------------------------------------------------------------

2.3 push_back() and push_front() : Use the member functions of list push_back and push_front to insert an element into the list. Where push_back() is inserted from the end of the list, and push_front() is inserted from the head of the list.

--------------------------------------------------------------------------------

2.4 empty() : use empty() to determine whether the list is empty.

--------------------------------------------------------------------------------

2.5 the resize () : If the call resize(n) changes the length of the list to only hold n elements, the excess elements will be removed, and if the extension is needed, the default constructor T() is called to add the elements to the end of the list. If resize(n,val) is called, the extension element is constructed by calling the constructor T(val) function, and the rest is the same.

--------------------------------------------------------------------------------

2.6 the clear () : Empty all the elements in the list.

--------------------------------------------------------------------------------

2.7 front() and back() : The header element in the list container is obtained by front(), and the last element in the list container is obtained by back(). But one thing to note is that when the list is empty, what happens when you call front() and back()? In fact, it will not read the data normally, but this is not an error, so we should pay attention when programming, I think it is best to call the empty() function to determine whether the list is empty before using it.

--------------------------------------------------------------------------------

2.8 pop_back and pop_front() : By deleting the last element, the first element is deleted by pop_front(); The sequence must not be empty, if calling pop_back() and pop_front() while the list is empty crashes the program.

--------------------------------------------------------------------------------

2.9 the assign () : Similar to the operation in vector, there are two cases. The first is: l1. Assign (n,val) changes the element in l1 into n T(val). In the second case, l1.assign(l2.begin(),l2.end()) assigns values in l2 between l2.begin() and l2.end() to l1.

--------------------------------------------------------------------------------

2.10 swap () : Swap two linked lists (two reloads), one is l1.swap(l2); The other one is swap(l1,l2), which can swap linked lists.

--------------------------------------------------------------------------------

2.11 reverse () : Complete the inverse of list by reverse().

--------------------------------------------------------------------------------

2.12 the merge () : Merge the two lists and make them ascending by default (also modifiable), l1.merge(l2, greater) < int > ()); After the end of the call, l2 becomes empty, and the elements in l1 contain the original elements in l1 and l2, and they are sorted and ascending. The default is actually ascending, greater < int > () can be omitted, and greater < int > () is variable or not in ascending order.

Take a look at the following program:

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<int> l1;
    list<int> l2(2,0);
    list<int>::iterator iter;
    l1.push_back(1);
    l1.push_back(2);
    l2.push_back(3);
    l1.merge(l2,greater<int>());//The default is actually ascending order
    for(iter = l1.begin() ; iter != l1.end() ; iter++)
    {
        cout<<*iter<<" ";
    }
    cout<<endl<<endl;
    if(l2.empty())
    {
        cout<<"l2  Become empty   !!!!! ";
    }
    cout<<endl<<endl;
    return 0;
}

Operation results:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201309/2013092510164710.jpg ">

2.13 the insert () : Inserts one or more elements (three overloads) at the specified location:

L1. Insert (l1. The begin (), 100); Insert 100 at the beginning of l1.

L1. Insert (l1. The begin (), 2200); Insert two hundreds at the beginning of l1.

L1. Insert (l1. The begin (), l2. The begin (), l2. The end ()); Insert elements of l2 from start to finish at the start of l1.

--------------------------------------------------------------------------------

2.14 erase () : Delete an element or an element of a region (two overloads)

L1. Erase (l1. The begin ()); Remove the first element of l1.

L1. Erase (l1. The begin (), l1. The end ()); Remove the elements of l1 between begin() and end().