list usage details

The List container is a two-way linked List.

1, Overview

The list is realized by a double linked list, and the elements are also stored in the heap. Each element is placed in a piece of memory. Its memory space can be discontinuous. Data can be accessed through pointers. This feature makes its random access unusual and inefficient, so it does not provide overloading of [] operator. However, due to the characteristics of linked list, it can efficiently support insertion and deletion operations anywhere.

2, Definition and initialization

The header file of the corresponding container must be added before use:

#include <list> // list belong to std Name the domain, so you need to qualify it by naming, for example using std::list;

The codes defined are as follows:

list<int> a; // Define a int List of types a
list<int> a(10); // Define a int List of types a，And set the initial size to 10
list<int> a(10, 1); // Define a int List of types a，And set the initial size to 10 and the initial value to 1
list<int> b(a); // Define and use list a Initialization list b
deque<int> b(a.begin(), ++a.end()); // Will list a The first element in the list b Initial value of

In addition, you can directly use arrays to initialize vectors:

int n[] = { 1, 2, 3, 4, 5 };
list<int> a(n, n + 5); // Will array n The first five elements of the list a Initial value of

3, Basic operation

3.1 capacity function

• Container size: lst size();
• Maximum container capacity: lst max_ size();
• Change container size: lst resize();
• Empty container: lst empty();

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    list<int> lst;
    for (int i = 0; i<6; i++)
    {
        lst.push_back(i);
    }

    cout << lst.size() << endl; // Output: 6
    cout << lst.max_size() << endl; // Output: 357913941
    lst.resize(0); // Change element size
    cout << lst.size() << endl; // Output: 0
    if (lst.empty())
        cout << "Element is empty" << endl; // Output: element is empty

    return 0;
}

3.2 adding functions

• Add element to header: lst push_ front(const T& x);
• Last element: lst push_ back(const T& x);
• Insert an element anywhere: lst insert(iterator it, const T& x);
• Insert n identical elements at any position: lst insert(iterator it, int n, const T& x);
• Insert data between [force, last] of another vector: lst insert(iterator it, iterator first, iterator last);

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    list<int> lst;

    // Add element to head
    lst.push_front(4);
    // Add element at the end
    lst.push_back(5);
    // Insert an element anywhere
    list<int>::iterator it = lst.begin();
    lst.insert(it, 2);
    // Insert anywhere n Same element
    lst.insert(lst.begin(), 3, 9);
    // Insert another vector[forst,last]Data between
    list<int> lst2(5, 8);
    lst.insert(lst.begin(), lst2.begin(), ++lst2.begin());

    // Traversal display
    for (it = lst.begin(); it != lst.end(); it++)
        cout << *it << " "; // Output: 8 9 2 4 5
    cout << endl;

    return 0;
}

3.3 delete function

• Header delete element: lst pop_ front();
• Delete element at the end: lst pop_ back();
• Delete an element anywhere: lst erase(iterator it);
• Delete the element between [first,last]: lst erase(iterator first, iterator last);
• Empty all elements: lst clear();

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    list<int> lst;
    for (int i = 0; i < 8; i++)
        lst.push_back(i);

    // Header delete element
    lst.pop_front();
    // Delete element at the end
    lst.pop_back();
    // Delete an element anywhere
    list<int>::iterator it = lst.begin();
    lst.erase(it);
    // delete[first,last]Elements between
    lst.erase(lst.begin(), ++lst.begin());

    // Traversal display
    for (it = lst.begin(); it != lst.end(); it++)
        cout << *it << " "; // Output: 3 4 5 6
    cout << endl;

    // Empty all elements
    lst.clear();

    // judge list Is it empty
    if (lst.empty())
    cout << "Empty element" << endl; // Output: element is empty

    return 0;
}

3.4 access function

• Access the first element: lst front();
• Access the last element: lst back();

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    list<int> lst;
    for (int i = 0; i < 6; i++)
        lst.push_back(i);

    // Access the first element
    cout << lst.front() << endl; // Output: 0
    // Access the last element
    cout << lst.back() << endl; // Output: 5

    return 0;
}

3.5 other functions

• Multiple element assignment: lst assign(int nSize, const T& x); // It is similar to assigning values with arrays during initialization
• Exchange elements of two containers of the same type: swap (list &, list &); Or lst swap(list&);
• Merge the elements of two lists (default ascending arrangement): lst merge();
• Insert another list: LST at any position splice(iterator it, list&);
• Delete adjacent duplicate elements in the container: lst unique();

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    // Multiple element assignment s
    list<int> lst1;
    lst1.assign(3, 1);
    list<int> lst2;
    lst2.assign(3, 2);
    
    // Exchange elements of two containers
    // swap(lst1, lst2); // ok
    lst1.swap(lst2);
    // Traversal display
    cout << "After exchange lst1: ";
    list<int>::iterator it;
    for (it = lst1.begin(); it!=lst1.end(); it++)
        cout << *it << " "; // Output: 2
    cout << endl;
    
    // Traversal display
    cout << "After exchange lst2: ";
    for (it = lst2.begin(); it != lst2.end(); it++)
        cout << *it << " "; // Output: 1
    cout << endl;

    list<int> lst3;
    lst3.assign(3, 3);
    list<int> lst4;
    lst4.assign(3, 4);
    // Merge elements of two lists
    lst4.merge(lst3); // Instead of simple splicing, it will be arranged in ascending order
    cout << "Consolidated lst4: ";
    for (it = lst4.begin(); it != lst4.end(); it++)
        cout << *it << " "; // Output: 3 3 4 4 4
    cout << endl;

    list<int> lst5;
    lst5.assign(3, 5);
    list<int> lst6;
    lst6.assign(3, 6);
    // stay lst6 At the second element of, spell access lst5
    lst6.splice(++lst6.begin(), lst5);
    cout << "Spliced lst6: ";
    for (it = lst6.begin(); it != lst6.end(); it++)
        cout << *it << " "; // Output: 6 5 5 6
    cout << endl;

    // Delete adjacent duplicate elements in the container
    list<int> lst7;
    lst7.push_back(1);
    lst7.push_back(1);
    lst7.push_back(2);
    lst7.push_back(2);
    lst7.push_back(3);
    lst7.push_back(2);
    lst7.unique();
    cout << "After deleting adjacent duplicate elements in the container lst7: ";
    for (it = lst7.begin(); it != lst7.end(); it++)
        cout << *it << " "; // Output: 1 2 3 2
    cout << endl;

    return 0;
}

4, Iterators and algorithms

1. Iterator

• Start iterator pointer: lst begin();
• End iterator pointer: lst end(); / / point to the next position of the last element
• Pointer to the start iterator of the constant: lst cbegin(); / / it means that the content cannot be modified through this pointer, but it can be modified in other ways, and the pointer can also be moved.
• Pointer to the end iterator of the constant: lst cend();
• Reverse iterator pointer to the last element: lst rbegin();
• Reverse iterator pointer to the previous element of the first element: lst rend();

#include <iostream>
#include <list>

using namespace std;

int main(int argc, char* argv[])
{
    list<int> lst;
    lst.push_back(1);
    lst.push_back(2);
    lst.push_back(3);

    cout << *(lst.begin()) << endl; // Output: 1
    cout << *(--lst.end()) << endl; // Output: 3
    cout << *(lst.cbegin()) << endl; // Output: 1
    cout << *(--lst.cend()) << endl; // Output: 3
    cout << *(lst.rbegin()) << endl; // Output: 3
    cout << *(--lst.rend()) << endl; // Output: 1
    cout << endl;

    return 0;
}

2. Algorithm

• Traversal element

list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); it++)
    cout << *it << endl;

• Element flip

#include <algorithm>
reverse(lst.begin(), lst.end());

• Element sorting

#include <algorithm>
sort(lst.begin(), lst.end()); // It is sorted from small to large

// If you want to sort from large to small, you can sort first and then reverse, or you can use the following method:
// Customize the comparator from large to small to change the sorting method
bool Comp(const int& a, const int& b) 
{
    return a > b;
}

sort(lst.begin(), lst.end(), Comp);

5, Summary

It can be seen that the usage of list is basically the same as that of vector and deque, except for the following differences:

• list is a bidirectional iterator, so it+=i is not supported;
• list does not support subscript access and at method access.

list common API s

list constructor

list<T> lstT;//list is implemented by template class, and the default construction form of object is:
list(beg,end);//The constructor copies the elements in the [beg, end) interval to itself.
list(n,elem);//The constructor copies n elem s to itself.
list(const list &lst);//Copy constructor.

• 1
• 2
• 3
• 4

list data element insertion and deletion operations

push_back(elem);//Add an element at the end of the container
pop_back();//Delete the last element in the container
push_front(elem);//Insert an element at the beginning of the container
pop_front();//Remove the first element from the beginning of the container
insert(pos,elem);//Insert a copy of the elem element in the pos position and return the location of the new data.
insert(pos,n,elem);//Insert n elem data in pos position, and there is no return value.
insert(pos,beg,end);//Insert the data of the [beg,end) interval in the pos position, and there is no return value.
clear();//Remove all data from the container
erase(beg,end);//Delete the data in the [beg,end) interval and return the position of the next data.
erase(pos);//Delete the data in pos position and return to the position of the next data.
remove(elem);//Delete all elements in the container that match the element value.

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

list size operation

size();//Returns the number of elements in the container
empty();//Determine whether the container is empty
resize(num);//Reassign the length of the container to num,
If the container becomes longer, the new location is populated with the default value.
If the container becomes shorter, the element whose end exceeds the length of the container is deleted.
resize(num, elem);//Reassign the length of the container to num,
If the container becomes longer, use elem Value populates the new location.
If the container becomes shorter, the element whose end exceeds the length of the container is deleted.

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

list assignment operation

assign(beg, end);//Assign the data copy in the [beg, end) interval to itself.
assign(n, elem);//Assign n elem copies to itself.
list& operator=(const list &lst);//Overloaded equal sign operator
swap(lst);//Swap lst with its own elements.

• 1
• 2
• 3
• 4

Access of list data

front();//Returns the first element.
back();//Returns the last element.

• 1
• 2

list reverse sort

reverse();//Reverse the linked list. For example, lst contains 1,3,5 elements. After running this method, lst contains 5,3,1 elements.
sort(); //list sort