C++ STL introduction of 2 list use of two way linked lists (with program code)

1. Introduction

"Unlike other sequence containers, list and forward_list objects are designed be inserting and removing elements any position, even in the middle of the sequence."

Lists stores elements in a linked list in order. Compared to the vector (vector), it allows for fast insertion and deletion, but slow random access. (vector supports fast random access)

As mentioned in the previous article, list can add and remove headers, but vector can't.

Here are a few list specific functions. (from another point of view, how fast list is for deletion)

remove() removes the element from list
remove_if() removes the element as specified
reverse() inverts the element of list
sort() sorts list
unique() removes duplicate elements in list

2. Complete program code

/* Be sure to read the following program after you run it */ 
 
#include <list> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
void print(int num) 
{ 
 cout << num << " "; 
} 
 
bool IsOdd(int i) 
{ 
 return ((i & 1) == 1); 
} 
 
int main() 
{ 
 //1.  Initialize the  
 list<int> v; 
 list<int>::iterator iv; 
 
 v.assign(10, 2);// will 10 A value of 2 Is assigned to list In the  
 cout << v.size() << endl; // return list The actual number of elements  
 cout << endl; 
 
 //2.  add  
 v.push_front(666); 
 for (int i = 0; i < 10; i++) 
  v.push_back(i); 
 for_each(v.begin(), v.end(), print);// Need to be #include <algorithm> 
 cout << endl; 
 cout << v.size() << endl; 
 cout << endl; 
 
 //3.  Insert and traverse, reverse traverse and reverse  
 v.insert(v.begin() , 99);// Can't + and - the  
 v.insert(v.end() , 99); 
 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 for_each(v.rbegin(), v.rend(), print);// Do it on the reverse iterator ++ The operation will point to the front of the container 1 An element  
 cout << endl; 
 
 //1 The general traversal method  
 for(iv = v.begin(); iv != v.end(); ++iv) 
  cout << *iv << " "; 
 cout << endl; 
 
 v.reverse(); 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 for_each(v.rbegin(), v.rend(), print); 
 cout << endl; 
 cout << endl; 
 
 //4.  The sorting  
 v.sort();// Sort the list, the default is ascending.  
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 cout << endl; 
 
 //5.  delete  
 v.erase(v.begin()); 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 v.insert(v.begin() , 99);// reduction  
 
 // Remove all duplicate elements from the list  
 v.unique(); 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 
 // Get rid of all the 2 The elements of the  
 v.remove(2); 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 
 // Get rid of all odd Numbers  
 v.remove_if(IsOdd); 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 
 v.pop_front(); 
 v.pop_back(); 
 for_each(v.begin(), v.end(), print); 
 cout << endl; 
 cout << endl; 
 
 //6.  The query  
 cout << v.front() << endl; 
 cout << v.back() << endl; 
 
 //7.  empty  
 v.clear(); 
 cout << v.size() << endl;//0 
 for_each(v.begin(), v.end(), print); // already clear . v.begin()==v.end() Nothing will come of it.  
 
 return 0; 
} 

Of course, we can also use a dynamic array as the saved data type:

#include<iostream> 
#include<string> 
#include<list> 
using namespace std; 
 
int main() 
{ 
 list<char *> li; 
 list<char *>::iterator iter; 
 li.push_back("123"); 
 li.push_back("456"); 
 li.push_back("789"); 
 for (iter = li.begin(); iter != li.end(); ++iter) 
  cout << *iter << endl; 
 return 0; 
} 

Added 3.

Compare vector and list for queries (random retrieval) and maintenance (insert and delete) :

a) query

vector: since the elements in vector are stored continuously, we can access the n element directly.

list: since elements in list are not continuously stored in memory, the memory address of the next element is stored in the first element, so we have to access the previous element one by one before we can finally access the n element.

Of course, for sequential access, it's about two.

b) maintenance

vector: to insert/delete an element in vector, we need to move all the elements after the insert/delete position. If you have a large number of elements after vector inserts/deletes, it is clear that these moves and deletes will consume a lot of CPU time.

list: when you use list for these operations, you can save a lot of CPU time by simply modifying the pointer to the next element before inserting/deleting the element.

Reference site: http: / / www cplusplus. com/reference/list list /