Condivisione della tecnologia

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. Libreria standardelencoTipo

Lo strato inferiore dell'elenco è una struttura di elenco collegato circolare bidirezionale con bit sentinella.
Rispetto alla struttura dell'elenco concatenato singolarmente di forward_list, l'iteratore di list è un iteratore bidirezionale
Rispetto ai contenitori strutturati in sequenza come i vettori, list è più efficiente nell'inserire ed eliminare in qualsiasi posizione, ma non supporta l'accesso casuale in nessuna posizione.
List è una classe template Quando la utilizziamo, dobbiamo fornire il tipo dell'elemento.

Quando si utilizza la classe list, è necessario includere il file di intestazione<list>

2. Interfacce comuni della classe list

1. Costruttori comunemente usati

1. Costruttore predefinito, costruisce un elenco collegato vuoto

list();

Per esempio:

void test()
{
	list<int> lt;
}

2. Costruisci un oggetto elenco e inizializzalo con n vals

list(size_type n, const value_type& val =  value_type());

Per esempio:

void test()
{
	list<int> lt(3, 1);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

3.Copia costruttore della classe elenco

list(const list& x); 

Per esempio:

void test()
{
	list<int> lt(3, 1);
	list<int> lt1(lt);
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

4. Utilizzare il costruttore di inizializzazione dell'iteratore

Template<class InputIterator>
 
list(InputIterator first, InputIterator last);

Per esempio:

void test()
{
	list<int> lt(3, 1);
	list<int> lt1(lt.begin(), lt.end());
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

2. Interfacce di capacità comunemente utilizzate

È sempre lo stesso, ne parliamo insieme qui.

1.size,vuoto,dimensione_massima,ridimensiona

misurare:ritornolista collegataIl numero di elementi nel contenitore.

size_type size() const;

vuoto:ritornoelencoSe il contenitore è vuoto (cioè il suomisurareè 0).
(Nota: questa funzione non modifica in alcun modo il contenitore. Da svuotarelista collegataIl contenuto del contenitore, vedielenco::cancella。）

bool empty() const;

dimensione_massima(non comunemente usato): ritornolista collegataIl numero massimo di elementi che il contenitore può contenere.
(A causa delle limitazioni note di implementazione del sistema o della libreria, questo è il potenziale massimo che un contenitore può raggiungeremisurare , ma non vi è alcuna garanzia che il contenitore raggiunga tale dimensione: potrebbe comunque non essere in grado di allocare spazio di archiviazione in qualsiasi momento prima di raggiungere tale dimensione. )

size_type max_size() const;

ridimensionare:Ridimensionare il contenitore per contenereNelementi.
SeNcontenitore più piccolo dell'attualemisurare, il contenuto verrà ridotto al precedenteNelementi, eliminando quelli che eccedono (e distruggendoli).
SeNContenitore più grande dell'attualemisurare, quindi il contenuto viene ampliato inserendo alla fine il numero di elementi richiesti da realizzareN la dimensione di.Se specificatovaloreore, il nuovo elemento verrà inizializzato suvaloreorecopie, altrimenti vengono inizializzate con valore.
(Nota che questa funzione modifica il contenuto effettivo del contenitore inserendo o cancellando elementi dal contenitore.)

void resize (size_type n, value_type val = value_type());

Per esempio:

​
void test()
{
	list<int> lt(3, 1);
	/*list<int> lt1(lt);*/
	list<int> lt1(lt.begin(), lt.end());
	list<int> lt2;
	cout << lt1.size() <<endl;
	cout << lt1.empty() <<endl;
	cout << lt2.empty() <<endl;
	lt1.resize(10);
	cout << lt1.size() << endl;
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}
 
​

risultato dell'operazione:

3. Accesso comune e attraversamento

1.Iteratore

iterator begin();
 
const_iterator begin() const;
 
iterator end();
 
const_iterator end() const;

Iteratore: utilizzato per ottenere la posizione del primo nodo e dell'ultimo nodo nell'elenco collegatoPosizione successiva (ovvero posizione sentinella)

Per esempio:

void test()
{
	list<int> lt(5, 2);
	list<int> ::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
}

risultato dell'operazione:

2. Iteratore inverso

iteratore inverso rbegin();

const_reverse_iterator rbegin() const;

iteratore inverso rend();

const_reverse_iterator rend() const;

Iteratore inverso, rbegin ottiene la posizione dell'ultimo nodo nel contenitore, rend ottiene la posizione del bit sentinella nel contenitore

void test()
{
	list<int> lt = { 1,23,4,4,5,2 };
	list<int> ::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
}

risultato dell'operazione:

Nota: anche l'iteratore inverso rit dovrebbe usare ++ invece di --

3.davanti e dietro

davanti:

riferimento anteriore();

riferimento_const front() const;

Restituisce un riferimento ai dati archiviati nel primo nodo dell'elenco collegato

Indietro:

riferimento indietro();

riferimento_const indietro() const;

Restituisce un riferimento ai dati archiviati nell'ultimo nodo dell'elenco collegato

Per esempio:

void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.front() << endl;
	cout << lt.back() << endl;
 
}

risultato dell'operazione:

4.Aggiungi, elimina, controlla e modifica l'elenco

1) push_front e pop_front

push_front si chiama inserimento head, inserendo un elemento dall'inizio della lista collegata

void push_front(const value_type& val);

pop_front è chiamato head deletion, che cancella un elemento dall'inizio dell'elenco collegato.

se vuoi che il tuo account sia attivo, puoi farlo cliccando sul pulsante "Accetto";

void pop_front();

Per esempio:

void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.front() << endl;
	lt.push_front(21345);
	cout << lt.front() << endl;
	lt.pop_front();
	cout << lt.front() << endl;
}

risultato dell'operazione:

2) push_back e pop_back

push_back si chiama inserimento della coda, inserendo un elemento dalla fine della lista collegata

void push_back(const valore_tipo& val);

pop_back è chiamato eliminazione della coda, che elimina un elemento dalla fine dell'elenco collegato.

Se vuoi che il tuo account venga cancellato, clicca qui.

Per esempio:

void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.back() << endl;
	lt.push_back(21345);
	cout << lt.back() << endl;
	lt.pop_back();
	cout << lt.back() << endl;
}

risultato dell'operazione:

3) trovare

template <class InputIterator, class T>
 
InputIterator find(InputIterator first, InputIterator last, const T& val);

Trova val nell'intervallo di due iteratori e restituisce l'iteratore dove si trova

Per esempio:

void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	*pos = 114514;
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

Nota: questa funzione non è una funzione membro di list, ma una funzione nella libreria standard. Più contenitori condividono la funzione di ricerca.

Come puoi vedere, possiamo dereferenziare direttamente l'iteratore dell'elenco e modificarne il contenuto, ma l'iteratore non dovrebbe puntare al nodo? Perché il dereferenziamento può modificare i dati?

Infatti, l'iteratore dell'elenco non è simulato e implementato utilizzando il puntatore ecologico originale, e deve essere incapsulato in fondo, cosa che si rifletterà nel codice sorgente dell'implementazione simulata dell'elenco.

4) inserire

iteratore insert(posizione iteratore, const value_type& val);

void insert(posizione iteratore, size_type n, const value_type& val);

————————————————————————————————————————

modello<class InputIterator>

void insert(posizione iteratore, InputIterator primo, InputIterator ultimo);

Inserisci uno o più elementi davanti alla posizione

Per esempio:

void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	lt.insert(pos, 8848);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

Gli studenti più attenti potrebbero aver scoperto che l'operazione di inserimento della lista lo èNon farà sì che l'iteratore diventi non valido, perché il nodo puntato da pos rimane invariato e la posizione relativa non cambia.

Tuttavia, l'operazione di eliminazione dell'elenco renderà sicuramente non valido l'iteratore e solo l'iteratore che punta al nodo eliminato non sarà valido e gli altri iteratori non saranno interessati.

5) cancellare

iterator erase(iterator position);
 
iterator erase(iterator first, iterator last);

Elimina l'elemento in posizione o tutti gli elementi nell'intervallo [primo, ultimo)

Per esempio:

void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	lt.erase(lt.begin());
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
	lt.erase(lt.begin(),pos);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

6) scambiare

void swap(vettore& x);

Scambia due oggetti dell'elenco

Per esempio:

void test()
{
	list<int> lt;
	list<int> lt2(6, 12);
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.swap(lt2);
	for (auto i : lt2)
	{
		cout << i << " ";
	}
	cout << endl;
}

risultato dell'operazione:

7) assegnare

modello<class InputIterator>

void assign(InputIterator primo, InputIterator ultimo);

void assign(size_type n, const value_type& val);

Specificare il nuovo contenuto per l'elenco, sostituire il contenuto corrente e modificare il numero di nodi

Per esempio:

void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.assign(4, 0);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

risultato dell'operazione:

8) Cancella

vuoto chiaro();

Elimina tutti i nodi nell'elenco collegato

Per esempio:

void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.clear();
	cout << lt.size() << endl;
}

risultato dell'operazione:

5.Interfaccia di modifica dell'ordine dell'elenco

(1）ordinare

ordinamento vuoto();

modello<class Compare>

void sort(Confronta comp);

A causa della particolarità della struttura della lista, la funzione di ordinamento nella libreria standard non può essere utilizzata, perché l'iteratore non può eseguire operazioni di sottrazione.

E nella documentazione C++, possiamo vedere che l'ordinamento nella libreria standard limita anche il tipo di iteratore ad accesso casuale (RandomAccess)

default (1)	
template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)	
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Gli iteratori hanno diverse categorie funzionali:

• Iteratore unidirezionale, può fare solo ++
• Iteratore bidirezionale, può essere ++ e --
• Iteratore casuale, può essere ++, --, + e -

Tuttavia, la funzione di ordinamento dell'elenco non è necessaria, poiché l'efficienza dell'ordinamento diretto dell'elenco collegato è molto più lenta rispetto alla copia nel vettore, all'ordinamento e quindi alla copia nell'elenco collegato.

(2）inversione

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

Invertire l'elenco collegato

Per esempio:

void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	for (auto i : lt)
	{
		cout << i << " ";
	}
	cout << endl;
	lt.reverse();
	for (auto i : lt)
	{
		cout << i << " ";
	}
	cout << endl;
 
}

risultato dell'operazione:

---

Se ci sono errori, correggetemi.