[C Elementary] Compréhension préliminaire de la liste class

[C Elementary] Compréhension préliminaire de la classe de liste

2024-07-12

1. Bibliothèque standardlisteegentil

La couche inférieure de la liste est une structure de liste chaînée circulaire bidirectionnelle avec des bits sentinelles.
Par rapport à la structure de liste à chaînage unique de forward_list, l'itérateur de list est un itérateur bidirectionnel
Par rapport aux conteneurs structurés séquentiellement tels que le vecteur, la liste est plus efficace pour l'insertion et la suppression à n'importe quelle position, mais elle ne prend en charge l'accès aléatoire à aucune position.
List est une classe de modèle Lorsque nous l'utilisons, nous devons donner le type de l'élément.

Lorsque vous utilisez la classe list, vous devez inclure le fichier d'en-tête<list>

2. Interfaces communes de la classe list

1. Constructeurs couramment utilisés

1. Constructeur par défaut, construit une liste chaînée vide

list();

Par exemple:


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

2. Construisez un objet liste et initialisez-le avec n vals

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

Par exemple:


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

résultat de l'opération :

3.Copier le constructeur de la classe list

list(const list& x);

Par exemple:


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

résultat de l'opération :

4. Utilisez le constructeur d'initialisation de l'itérateur


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

Par exemple:


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

résultat de l'opération :

2. Interfaces de capacité couramment utilisées

C’est toujours pareil, laissez-moi en parler ensemble ici.

1.taille,vide,taille_max,redimensionner

taille:retourliste chaînéeLe nombre d'éléments dans le conteneur.
size_type size() const;
vide:retourlisteSi le conteneur est vide (c'est-à-dire sontailleest 0).
(Remarque : Cette fonction ne modifie en aucun cas le conteneur. Pour effacerliste chaînéeLe contenu du conteneur, voirliste::effacer。）
bool empty() const;
taille max(pas couramment utilisé) : retourliste chaînéeLe nombre maximum d'éléments que le conteneur peut contenir.
(En raison des limitations connues de l'implémentation du système ou de la bibliothèque, il s'agit du potentiel maximum qu'un conteneur peut atteindre.taille , mais rien ne garantit que le conteneur atteindra cette taille : il se peut qu'il ne soit toujours pas en mesure d'allouer du stockage à tout moment avant d'atteindre cette taille. )
size_type max_size() const;
redimensionner:Redimensionner le conteneur pour contenirnéléments.
sinplus petit que le conteneur actueltaille, le contenu sera réduit à son état précédentnéléments, en supprimant ceux qui dépassent (et en les détruisant).
sinPlus grand que le conteneur actueltaille, puis le contenu est développé en insérant le nombre requis d'éléments à la fin pour obtenirn la taille de.Si spécifiéval, alors le nouvel élément sera initialisé àvalcopies, sinon elles sont initialisées en valeur.
(Notez que cette fonction modifie le contenu réel du conteneur en insérant ou en effaçant des éléments du conteneur.)
void resize (size_type n, value_type val = value_type());

Par exemple:


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 << " ";
	}
}

résultat de l'opération :

3. Accès commun et traversée

1.Itérateur


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

Itérateur : utilisé pour obtenir la position du premier nœud et du dernier nœud dans la liste chaînéePosition suivante (c'est-à-dire position sentinelle)

Par exemple:


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

résultat de l'opération :

2. Itérateur inverse

itérateur_inverse rbegin();

const_reverse_iterator rbegin() const;

reverse_iterator rend();

const_reverse_iterator rend() const;

Itérateur inverse, rbegin obtient la position du dernier nœud dans le conteneur, rend obtient la position du bit sentinelle dans le conteneur


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;
	}
}

résultat de l'opération :

Remarque : le rit de l'itérateur inverse doit également utiliser ++ au lieu de --

3.avant et arrière

devant:

référence avant();

const_reference front() const;

Renvoie une référence aux données stockées dans le premier nœud de la liste chaînée

dos:

référence arrière();

const_reference retour() const;

Renvoie une référence aux données stockées dans le dernier nœud de la liste chaînée

Par exemple:


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

résultat de l'opération :

4.Ajouter, supprimer, vérifier et modifier la liste

1) push_front et pop_front

push_front est appelé insertion de tête, insérant un élément de la tête de la liste chaînée

void push_front(const valeur_type& val);

pop_front est appelé suppression de tête, qui supprime un élément de la tête de la liste chaînée.

void pop_front();

void pop_front();

Par exemple:


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;
}

résultat de l'opération :

2) push_back et pop_back

push_back est appelé insertion de queue, insérant un élément à partir de la fin de la liste chaînée

void push_back(const type_valeur& val);

pop_back est appelé suppression de queue, qui supprime un élément de la fin de la liste chaînée.

void pop_back();

Par exemple:


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;
}

résultat de l'opération :

3) trouver


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

Recherchez val dans la plage de deux itérateurs et renvoyez l'itérateur là où il se trouve

Par exemple:


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 << " ";
	}
}

résultat de l'opération :

Remarque : Cette fonction n'est pas une fonction membre de list, mais une fonction de la bibliothèque standard. Plusieurs conteneurs partagent la fonction de recherche.

Comme vous pouvez le voir, on peut directement déréférencer l'itérateur de la liste et modifier son contenu, mais l'itérateur ne devrait-il pas pointer vers le nœud ? Pourquoi le déréférencer peut-il modifier les données ?

En fait, l'itérateur de la liste n'est pas simulé et implémenté à l'aide du pointeur écologique d'origine, et doit être encapsulé en bas, ce qui sera reflété dans le code source de l'implémentation simulée de la liste.

4) insérer

itérateur insert(position de l'itérateur, const value_type& val);

void insert(position de l'itérateur, type_taille n, const type_valeur& val);

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

modèle<class InputIterator>

void insert(position de l'itérateur, InputIterator premier, InputIterator dernier);

Insérer un ou plusieurs éléments devant la position

Par exemple:


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 << " ";
	}
}

résultat de l'opération :

Des étudiants attentifs ont peut-être découvert que l’opération d’insertion d’une liste estNe rendra pas l'itérateur invalide, car le nœud pointé par pos reste inchangé et la position relative ne change pas.

Cependant, l'opération de suppression de la liste rendra définitivement l'itérateur invalide, et seul l'itérateur pointant vers le nœud supprimé sera invalide, et les autres itérateurs ne seront pas affectés.

5) effacer


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

Supprimez l'élément à la position ou tous les éléments de la plage [premier, dernier)

Par exemple:


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 << " ";
	}
}

résultat de l'opération :


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 << " ";
	}
}

résultat de l'opération :

6) échanger

void swap(vecteur& x);

Échanger deux objets de liste

Par exemple:


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;
}

résultat de l'opération :

7) attribuer

modèle<class InputIterator>

void assign(InputIterator premier, InputIterator dernier);

void assign(taille_type n, const valeur_type& val);

Spécifiez le nouveau contenu de la liste, remplacez son contenu actuel et modifiez le nombre de nœuds

Par exemple:


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 << " ";
	}
}

résultat de l'opération :

8) clair

void effacer();

Supprimer tous les nœuds de la liste chaînée

Par exemple:


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

résultat de l'opération :

5.Interface de modification de commande de liste

(1）trier

vide trier();

modèle<class Compare>

void sort(Comparer comp);

En raison de la particularité de la structure de la liste, la fonction de tri de la bibliothèque standard ne peut pas être utilisée, car l'itérateur ne peut pas effectuer d'opérations de soustraction.

Et dans la documentation C++, nous pouvons voir que le tri dans la bibliothèque standard limite également le type d'itérateur à accès aléatoire (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);

Les itérateurs ont plusieurs catégories fonctionnelles :

Itérateur unidirectionnel, ne peut faire que ++
Itérateur bidirectionnel, peut être ++ et --
Itérateur aléatoire, peut être ++, --, + et -

Cependant, la fonction de tri de la liste n'est pas nécessaire, car l'efficacité du tri direct de la liste chaînée est beaucoup plus lente que la copie vers le vecteur, le tri puis la recopie vers la liste chaînée.

(2）inverse

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

Inverser la liste chaînée

Par exemple:


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;
 
}

résultat de l'opération :

S'il y a des erreurs, veuillez me corriger.

Partage de technologie

[C Elementary] Compréhension préliminaire de la classe de liste

1. Bibliothèque standardlisteegentil

2. Interfaces communes de la classe list

1. Constructeurs couramment utilisés

1. Constructeur par défaut, construit une liste chaînée vide

2. Construisez un objet liste et initialisez-le avec n vals

3.Copier le constructeur de la classe list

4. Utilisez le constructeur d'initialisation de l'itérateur

2. Interfaces de capacité couramment utilisées

1.taille,vide,taille_max,redimensionner

3. Accès commun et traversée

1.Itérateur

2. Itérateur inverse

3.avant et arrière

4.Ajouter, supprimer, vérifier et modifier la liste

1) push_front et pop_front

2) push_back et pop_back

3) trouver

4) insérer

5) effacer

6) échanger

7) attribuer

8) clair

5.Interface de modification de commande de liste

(1）trier

(2）inverse

Profil personnel

mes coordonnées