List list

list list

Use of lists

list It's a two-way list , So its memory space can be discontinuous , Access data through pointers , This makes list The efficiency of random access is low , therefore list Not provided [] operator overloading . but list It can well support the insertion and deletion operations anywhere , Just move the pointer

List defined in < list > Header file

The prototype of the list class member function is as follows ：

//---- iterator iterators----
iterator begin(); // Return the header element to start the iterator 
iterator end(); // Returns the footer element as the end of the iterator 
reverse_iterator rbegin(); // The return footer element is the start of the reverse iterator 
reverse_iterator rend(); // Return the header element to the end of the reverse iterator 

//---- Capacity capacity----
bool empty(); // Test whether the table is empty 
size_type size(); // Returns the length of the list 
size_type max_size(); // Returns the maximum length that the list can hold 
void resize(size_type sz,T c=T()); // Reset the list length to sz,c Fill in the extension element 

//---- Element access element access----
front(); // Returns the header element 
back(); // Returns the footer element 

//---- List adjuster modifiers----
void assign(size_type n,const T& u); // List assignment n individual u value 
void push_front(const T& x); // Insert an element into the header 
void pop_front(); // Delete header element 
void push_back(const T& x); // Add an element to the end of the table 
void pop_back(); // Delete the footer element 
void insert(iterator pos,size_type n,const T& x); // In the list pos Insert n Element values x,pos from 1 rise 
iterator erase(iterator pos); // Delete the element at the specified position in the list ,pos from 1 rise 
void swap(list<T,Allocator>& lst); // And list lst Exchange elements 
void clear(); // clear list 

//---- List operation operations----
void remove(const T& value); // Delete values and in the list value All the same elements 
void remove_if(Predicate pred); // Delete the elements that meet the conditions in the list 
void unique(); // Delete list duplicate values 
void merge(list<T,Allocator>& x); // Merge list x, The list must be ordered 
void sort(); // Sort the list 
void sort(Compare comp); // List by comp Relation comparison sort 
void reverse(); // The list is in reverse order 

example ： List application examples

#include<iostream>
#include<string>
#include<list> // Use list  
using namespace std; // List defined in std Namespace  

int main()
{
    
	int A[]={
    15,36,7,17};
	list<int>::iterator It;
	list<int> L1,L2,L3(A,A+4); //L3: 15 36 7 17
	for(int i=1;i<=6;i++)
		L1.push_back(i); //L1: 1 2 3 4 5 6
	for(int i=1;i<=3;i++)
		L2.push_back(i*10); //L2: 10 20 30
	It=L1.begin(); advance(It,2); //It Point to 3( The first 3 Elements )
	L1.splice(It,L2); //L1: 1 2 10 20 30 3 4 5 6 , L2(empty)
	// here It Still point to 3( The first 6 Elements )
	L2.splice(L2.begin(),L1,It); //L1: 1 2 10 20 30 4 5 6 , L2: 3
	L1.remove(20); //L1: 1 2 10 30 4 5 6
	L1.sort(); //L1: 1 2 4 5 6 10 30
	L1.merge(L3); //L1: 1 2 4 5 6 10 15 30 36 7 17
	L1.push_front(L2.front()); //L1: 3 1 2 4 5 6 10 15 30 36 7 17
	L1.reverse(); //L1: 17 7 36 30 15 10 6 5 4 2 1 3
	for(It=L1.begin();It!=L1.end();++It)
		cout<<*It<<" ";
	return 0; 
}

Implementation details of the list

A list is a two-way linked list , Its basic functions include generating nodes , Insert node , Delete node , Find nodes, etc . for example ：

list<char> MyList; // The statement list<char> An instance of the template class 
MyList.push_back('a'); // Put an object into a list Behind 
MyList.push_front('b'); // Put an object into a list In front of 
// Use the iterator to find a list with a value of 'c' The node of 
list<char>::iterator FindIterator;
FindIterator = find(MyList.begin(),MyList.end(),'c');
if(FindIterator==MyList.end())
	cout<<"not find the char 'c'!"<<endl;
else
	cout<<"*FindIterator<<endl;

example ： Customize a one-way linked list class template

#include<iostream>
#include<cstdlib>
#include<string>
using namespace std;

template<class T>
class Node {
     // Node class 
	private:
		Node<T>*next;
	public:
		T data;
		Node(const T& item,Node<T>* ptrnext=NULL); // Constructors  
		void InsertAfter(Node<T> *p); // Insert a node after the current node p 
		Node<T> *DeleteAfter(); // Delete the successor node of the current node , And return its address  
		Node<T> *NextNode() const; // Find the address of the next node  
};

template<class T>
// function ： Constructors 
Node<T>::Node(const T& item,Node<T>* ptrnext) : data(item),next(ptrnext) {
     }

template<class T>
// function ： Find the address of the next node 
Node<T>*Node<T>::NextNode() const {
    
	return next;
}

template<class T>
// function ： Insert a node after the current node p
void Node<T>::InsertAfter(Node<T>*p) {
    
	p->next=next; //p The node pointer field points to the successor node of the current node 
	next=p; // The pointer field of the current node points to p node  
} 

template<class T>
// function ： Delete the successor node of the current node , And return its address 
Node<T> *Node<T>::DeleteAfter() {
    
	Node<T> *tempPtr=next; // Store the address of the node to be deleted in tempPtr in 
	if(next==NULL)
		return NULL;
	// If the current node has no successor node, null is returned 
	next=tempPtr->next; // Make the pointer field of the current node point to tempPtr The successor node of 
	return tempPtr; // Return the address of the deleted node  
} 

template<class T>
// function ： Generate node function 
Node<T> *GetNode(const T& item,Node<T> *nextPtr=NULL) {
    
	Node<T> *newNode;
	newNode=new Node<T>(item,nextPtr);
	if(newNode==NULL) {
    
		cout<<"Memory allocation failure!"<<endl;
		exit(1);
	}
	return newNode;	
} 

template<class T>
// function ： Generate linked list function 
Node<T> *CreateList(Node<T> *head,int n) {
    
	Node<T> *currPtr,*newNode,data;
	currPtr=head=GetNode(0); // Create a header node 
	for(;n>0;n--) {
     // establish n Node linked list 
		cin>>data;
		newNode=GetNode(data); // Create a new node 
		currPtr->next=newNode,currPtr=newNode; 
	} 
	currPtr->next=NULL; // Caudal node 
	return head; 
}

enum AppendNewLine {
     // Controls whether to wrap lines after the output node  
	noNewline,addNewline
}; 

template<class T>
// function ： Output linked list function 
void PrintList(Node<T> *head,AppendNewLine addnl=noNewline) {
    
	Node<T> *currPtr=head;
	while(currPtr!=NULL) {
    
		if(addnl==addNewline)
			cout<<currPtr->data<<endl;
		else
			cout<<currPtr->data<<" ";
		currPtr=currPtr->NextNode();
	}
} 

template<class T>
// function ： Find node function 
int FindNode(Node<T> *head,T &item,Node<T> *prevPtr) {
    
	Node<T> *currPtr=head;
	prevPtr=NULL;
	while(currPtr!=NULL) {
    
		if(currPtr->data=item)
			return 1;
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	return 0;
}