π Author: Linux ape
π Introduction: CSDN blog expert ποΌ C/C + +, interview, question brushing and algorithm. Please consult me, pay attention to me and chat privately if you have any questions!
π Attention column: C/C + + interview customs collection (high quality articles are constantly updated...) π
catalogue
3.1 size(), clear(), empty() methods
3.2 push_front(),push_back() method
3.3 pop_front(),pop_back() method
3.5 rbegin() and rend() methods
3.6. 1 insert a single element
3.6. 2 insert n identical elements
3.6. 3 insert the element of the [first, last) interval at the position
3.7. 1 delete a single element
3.7. 2 delete the elements of the interval [first, last]
List is one of the longest used containers of STL. It is a knowledge point often encountered in daily use and interview. Let's explain list in detail below.
1, What is a list?
List is a container encapsulated by a two-way linked list, which can insert and delete elements with O(1) time complexity. However, like the linked list, elements cannot be accessed quickly through subscripts (e.g. g[i]), but can only be obtained through traversal.
Figure 1 Schematic diagram
Β 
2, Definition of List
2.1 header file
To use List, you need to import header files:
#include <list>
2.2 definitions
list<T>Variable name;
Where T is the data type, such as int, char, String, class, etc.
Here is an example of the definition:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
cout<<"t1 size = "<<t1.size()<<endl; // size = 0
list<int> t2(5); // Define a list of int type with length of 5 and initial value of 0
cout<<"t2 size = "<<t2.size()<<endl; // size = 5
list<int> t3(5, 10); // Define a list of int type with length of 5 and initial value of 10
cout<<"t3 size = "<<t3.size()<<endl; // size = 5
int idx = 0;
list<int>::iterator iter;
for(iter = t3.begin(); iter != t3.end(); ++iter) {
cout<<*iter<<" "; // *iter = 10
}
cout<<endl;
// Output: 10 10 10 10
list<int> t4(t3); // To initialize t4 with t3, it needs to be of the same type
list<int> t5(t3.begin(), t3.end()); // Initialize t5 with t3
}Output is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main t1 size = 0 t2 size = 5 t3 size = 5 10 10 10 10 10 linuxy@linuxy:~/defineDir$
You can also initialize using curly braces:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1{1,2,3,4,5,6}; // Define a list of int type named t1
list<int>::iterator iter;
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
}Output is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 2 3 4 5 6 linuxy@linuxy:~/defineDir$
2.3 common methods
size() : Returns the number of elements in the linked list; clear(): Empty all elements; empty(): Judge whether it is empty; push_front(): Add elements at the beginning of the linked list; push_back(): Add elements at the end of the linked list; pop_front(): Delete the elements at the beginning of the linked list; pop_back(): Delete the end element of the linked list; begin(): Returns the iterator pointing to the first element of the linked list; end(): Returns the iterator pointing to the last element of the linked list; rbegin(): Returns the iterator pointing to the last element of the linked list; (for backward traversal of elements) rend(): Returns the iterator pointing to the first element of the linked list; (for backward traversal of elements) insert(position, val): In the linked list position Insert element at position valοΌ insert(position, n, val): In the linked list position Position insertion n Elements valοΌ insert(position, first, last): In the linked list position Position insertion [first, last) Elements of interval; erase(position): delete position Elements of location; erase(first, last): Delete interval[first, last) Elements of location;
3, Example explanation
3.1 size(), clear(), empty() methods
The function prototype is:
size_type size() const // Returns the total number of elements stored in the linked list void clear() // Empty linked list bool empty() const // Judge whether the linked list is empty. If it is empty, it returns true. Otherwise, it returns false
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
cout<<"t1.size() = "<<t1.size()<<endl; // size = 0
cout<<"t1.empty() = "<<t1.empty()<<endl; // Judge whether it is empty
cout<<"--------------------------"<<endl;
t1.push_back(1); // Add an element at the end of t1
cout<<"t1 size = "<<t1.size()<<endl; // size = 1
cout<<"t1.empty() = "<<t1.empty()<<endl; // Judge whether it is empty
cout<<"--------------------------"<<endl;
t1.clear();
cout<<"t1 size = "<<t1.size()<<endl; // size = 1
cout<<"t1.empty() = "<<t1.empty()<<endl; // Judge whether it is empty
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main t1.size() = 0 t1.empty() = 1 -------------------------- t1 size = 1 t1.empty() = 0 -------------------------- t1 size = 0 t1.empty() = 1 linuxy@linuxy:~/defineDir$
3.2 push_front(),push_back() method
The function prototype is as follows:
void push_front (const value_type& val); // Add an element to the beginning of the linked list void push_back (const value_type& val); // Add an element to the end of the linked list
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
t1.push_front(10);
t1.push_back(20);
list<int>::iterator iter;
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<endl;
}
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 10 20 linuxy@linuxy:~/defineDir$
As you can see, the order of output is 10 and 20.
3.3 pop_front(),pop_back() method
The function prototype is as follows:
void pop_front(); // Delete the first (first) element of the linked list void pop_back(); // Delete the last element of the linked list
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::iterator iter; // iterator
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 1 2 3 4 5 6
t1.pop_front(); // Delete the first element of the linked list
t1.pop_back(); // Delete the last element of the linked list
cout<<"----------------------------"<<endl;
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 2 3 4 5
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 2 3 4 5 6 ---------------------------- 2 3 4 5 linuxy@linuxy:~/defineDir$
As you can see, the first and last elements of the linked list have been deleted.
3.4 begin() and end() methods
The function prototype is as follows:
iterator begin()οΌ // Returns an iterator pointing to the first element iterator end(); // Returns an iterator pointing to the last element
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::iterator iter; // Iterator for sequentially traversing a linked list
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 1 2 3 4 5 6
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 2 3 4 5 6 linuxy@linuxy:~/defineDir$
You can see that the elements in the linked list are output in sequence.
3.5 rbegin() and rend() methods
The function prototype is as follows:
reverse_iterator rbegin() // Returns a reverse iterator pointing to the last element reverse_iterator rend() // Returns a reverse iterator pointing to the first element
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::reverse_iterator iter; // reverse iterator
for(iter = t1.rbegin(); iter != t1.rend(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
//Output: 6 5 4 3 2 1
}Output is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 6 5 4 3 2 1 linuxy@linuxy:~/defineDir$
You can see that the linked list elements are output in reverse order.
Note: the iterator traversing the linked list needs to use the reverse iterator, for example, list < int >:: reverse in the above code_ iterator.
3.6 insert method
insert overloads multiple methods. Let's take a look.
3.6. 1 insert a single element
The function prototype is as follows:
iterator insert (const_iterator position, const value_type& val); // Insert element val at position
Note: if there is an element in the position position position in the linked list, the original element will be after the new element after the new element is inserted.
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::iterator iter;
for(iter = t1.begin(); iter != t1.end(); ++iter) {
if(*iter == 3) { // Insert element 7 at the position of element 3, so element 3 is located after 7
t1.insert(iter, 7);
}
}
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 1 2 7 3 4 5 6
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 2 7 3 4 5 6 linuxy@linuxy:~/defineDir$
It can be seen that 7 is inserted into the original position of 3. After insertion, 3 is behind 7.
3.6. 2 insert n identical elements
iterator insert (const_iterator position, size_type n, const value_type& val); // Insert n elements in position val
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::iterator iter;
for(iter = t1.begin(); iter != t1.end(); ++iter) {
if(*iter == 3) { // Insert five 7S after element 3
t1.insert(iter, 5, 7);
}
}
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 1 2 7 7 7 3 4 5 6
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 2 7 7 7 7 7 3 4 5 6 linuxy@linuxy:~/defineDir$
As you can see, five seven are inserted. After insertion, three rows are behind the last seven.
3.6. 3 insert the element of the [first, last) interval at the position
iterator insert (const_iterator position, InputIterator first, InputIterator last); // Insert the element of the [first, last) interval in the position position
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int> t2;
for(int i = 7; i <= 9; ++i) { // Insert element 7 8 9
t2.push_back(i);
}
list<int>::iterator iter;
for(iter = t1.begin(); iter != t1.end(); ++iter) {
if(*iter == 3) { // Insert element 7 8 9 at the position of element 3
t1.insert(iter, t2.begin(), t2.end());
}
}
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 1 2 7 8 9 3 4 5 6
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 2 7 8 9 3 4 5 6 linuxy@linuxy:~/defineDir$
You can see that 7, 8 and 9 are inserted into position 3 in t1. The iterators first and last can be as long as they are an interval, not necessarily begin() and end().
3.7 erase method
3.7. 1 delete a single element
The function prototype is as follows:
iterator erase (const_iterator position); // Delete the element at position
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::iterator iter = t1.begin();
++iter;
t1.erase(iter); // Delete 2
for(iter = t1.begin(); iter != t1.end(); ++iter) {
cout<<*iter<<" ";
}
cout<<endl;
// Output: 1 3 4 5 6
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 3 4 5 6 linuxy@linuxy:~/defineDir$
You can see that element 2 has been deleted.
3.7. 2 delete the elements of the interval [first, last]
The function prototype is as follows:
iterator erase (const_iterator first, const_iterator last); // Delete the elements of the [first, last) interval in the linked list
Let's take an example:
#include <iostream>
#Include < list > / / list header file
using namespace std; // Namespace. If not, std::list is used
int main() {
list<int> t1; // Define a list of int type named t1
for(int i = 1; i <= 6; ++i) { // Insert element 1 2 3 4 5 6
t1.push_back(i);
}
list<int>::iterator iter1, iter2;
iter2 = t1.begin();
++iter2;
iter1 = iter2;
++iter2;
++iter2; // iter1 points to element 2 and iter2 points to element 4
t1.erase(iter1, iter2); // Delete the elements in [2, 4) interval, so delete 2 and 3 elements in the linked list
for(iter1 = t1.begin(); iter1 != t1.end(); ++iter1) {
cout<<*iter1<<" ";
}
cout<<endl;
// Output 1 4 5 6
}The output result is:
linuxy@linuxy:~/defineDir$ g++ -o main main.cpp linuxy@linuxy:~/defineDir$ ./main 1 4 5 6 linuxy@linuxy:~/defineDir$
You can see that the elements of interval [2, 4) are deleted, i.e. 2 and 3.
IV. summary
The above is the explanation of the common methods of STL list. You can consider using list when you often insert / delete elements.
β Haowen recommendation β
The most popular Linux is it, and Ubuntu ranks sixth?
Detailed explanation of STL map that can be understood by zero Foundation
Master C/C + + memory leakage, prevent memory leakage and detection tools!
[ten thousand words] β€οΈ 8 sorting algorithms β€οΈ [suggested collection]
π Welcome to praise π, Collection β, Leaving a message. π¬