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