[C Elemental] Comprensión preliminar de la lista class

[C Primaria] Comprensión preliminar de la clase de lista

2024-07-12

1. Biblioteca estándarlistaaamable

La capa inferior de la lista es una estructura de lista enlazada circular bidireccional con bits centinela.
En comparación con la estructura de lista enlazada individualmente de forward_list, el iterador de list es un iterador bidireccional
En comparación con contenedores estructurados secuencialmente como vector, la lista es más eficiente para insertar y eliminar en cualquier posición, pero no admite el acceso aleatorio en ninguna posición.
List es una clase de plantilla. Al usarla, debemos proporcionar el tipo de elemento.

Cuando utilice la clase de lista, debe incluir el archivo de encabezado<list>

2. Interfaces comunes de clase de lista.

1. Constructores de uso común

1. Constructor predeterminado, construye una lista enlazada vacía

list();

Por ejemplo:


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

2. Construya un objeto de lista e inicialícelo con n valores

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

Por ejemplo:


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

resultado de la operación:

3.Copiar constructor de clase de lista.

list(const list& x);

Por ejemplo:


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

resultado de la operación:

4. Utilice el constructor de inicialización del iterador.


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

Por ejemplo:


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

resultado de la operación:

2. Interfaces de capacidad de uso común

Sigue siendo lo mismo, déjenme hablar de ello juntos aquí.

1.tamaño,vacío,tamaño máximo,cambiar tamaño

tamaño:devolverlista enlazadaEl número de elementos en el contenedor.
size_type size() const;
vacío:devolverlistaSi el contenedor está vacío (es decir, sutamañoes 0).
(Nota: Esta función no modifica el contenedor de ninguna manera. Para borrarlista enlazadaEl contenido del contenedor, verlista::borrar。）
bool empty() const;
tamaño máximo(no se usa comúnmente): regresarlista enlazadaEl número máximo de elementos que puede contener el contenedor.
(Debido a limitaciones conocidas de implementación del sistema o de la biblioteca, este es el potencial máximo que un contenedor puede alcanzartamaño , pero no hay garantía de que el contenedor alcance ese tamaño: es posible que aún no pueda asignar almacenamiento en ningún momento antes de alcanzar ese tamaño. )
size_type max_size() const;
cambiar el tamaño:Cambiar el tamaño del contenedor para contenernorteorteorteorteorteelementos.
sinorteorteorteorteortemás pequeño que el contenedor actualtamaño, el contenido se reducirá a su estado anterior.norteorteorteorteorteelementos, eliminando los que sobran (y destruyéndolos).
sinorteorteorteorteorteMás grande que el contenedor actualtamaño, luego el contenido se expande insertando la cantidad requerida de elementos al final para lograrnorteorteorteorteorte la talla de.Si se especificaval, entonces el nuevo elemento se inicializará avalcopias; de lo contrario, se inicializan con el valor.
(Tenga en cuenta que esta función cambia el contenido real del contenedor insertando o borrando elementos del contenedor).
void resize (size_type n, value_type val = value_type());

Por ejemplo:


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

resultado de la operación:

3. Acceso y recorrido común

1.Iterador


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

Iterador: utilizado para obtener la posición del primer nodo y del último nodo en la lista vinculadaSiguiente posición (es decir, posición centinela)

Por ejemplo:


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

resultado de la operación:

2. Iterador inverso

iterador_inverso rbegin();

const_reverse_iterator rbegin() constante;

iterador_inverso rend();

const_reverse_iterator rend() constante;

Iterador inverso, rbegin obtiene la posición del último nodo en el contenedor, rend obtiene la posición del bit centinela en el contenedor


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

resultado de la operación:

Nota: El iterador inverso rit también debería usar ++ en lugar de --

3.frente y detrás

frente:

referencia frontal();

const_reference frente() const;

Devuelve una referencia a los datos almacenados en el primer nodo de la lista vinculada.

atrás:

referencia atrás();

const_reference atrás() const;

Devuelve una referencia a los datos almacenados en el último nodo de la lista enlazada.

Por ejemplo:


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

resultado de la operación:

4.Agregar, eliminar, verificar y modificar lista

1) push_front y pop_front

push_front se llama inserción de encabezado, insertando un elemento del encabezado de la lista vinculada

void push_front(const tipo_valor& val);

pop_front se llama eliminación de encabezado, que elimina un elemento del encabezado de la lista vinculada.

vacío pop_front();

void pop_front();

Por ejemplo:


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

resultado de la operación:

2) push_back y pop_back

push_back se llama inserción de cola, insertando un elemento desde el final de la lista vinculada

void push_back(const tipo_valor& val);

pop_back se llama eliminación de cola, que elimina un elemento del final de la lista vinculada.

vacío pop_back();

Por ejemplo:


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

resultado de la operación:

3) encontrar


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

Encuentre val en el rango de dos iteradores y devuelva el iterador donde se encuentra

Por ejemplo:


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

resultado de la operación:

Nota: Esta función no es una función miembro de la lista, sino una función en la biblioteca estándar. Varios contenedores comparten la función de búsqueda.

Como puede ver, podemos desreferenciar directamente el iterador de la lista y modificar su contenido, pero ¿no debería el iterador apuntar al nodo? ¿Por qué desreferenciarlo puede modificar los datos?

De hecho, el iterador de la lista no se simula ni se implementa utilizando el puntero ecológico original, y debe encapsularse en la parte inferior, lo que se reflejará en el código fuente de la implementación simulada de la lista.

4) insertar

iterador insertar(iterador posición, const valor_tipo& val);

void insert(iterador posición, tamaño_tipo n, const valor_tipo& val);

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

plantilla<class InputIterator>

void insert(iterador posición, InputIterator primero, InputIterator último);

Insertar uno o más elementos delante de la posición

Por ejemplo:


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

resultado de la operación:

Los estudiantes cuidadosos pueden haber descubierto que la operación de inserción de lista esNo hará que el iterador deje de ser válido., porque el nodo señalado por pos permanece sin cambios y la posición relativa no cambia.

Sin embargo, la operación de eliminación de la lista definitivamente hará que el iterador deje de ser válido, y solo el iterador que apunta al nodo eliminado dejará de ser válido y otros iteradores no se verán afectados.

5) borrar


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

Eliminar el elemento en la posición o todos los elementos en el rango [primero, último)

Por ejemplo:


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

resultado de la operación:


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

resultado de la operación:

6) intercambiar

vacío intercambio (vector y x);

Intercambiar dos objetos de lista

Por ejemplo:


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

resultado de la operación:

7) asignar

plantilla<class InputIterator>

void asignar(InputIterator primero, InputIterator último);

void asignar(tamaño_tipo n, const valor_tipo& val);

Especifique contenido nuevo para la lista, reemplace su contenido actual y modifique el número de nodos

Por ejemplo:


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

resultado de la operación:

8) claro

vacío claro();

Eliminar todos los nodos en la lista vinculada

Por ejemplo:


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

resultado de la operación:

5. Interfaz de modificación de pedidos de lista

(1）clasificar

vacío ordenar();

plantilla<class Compare>

void sort(Comparar comp);

Debido a la particularidad de la estructura de la lista, la función de clasificación en la biblioteca estándar no se puede utilizar porque el iterador no puede realizar operaciones de resta.

Y en la documentación de C++, podemos ver que la clasificación en la biblioteca estándar también limita el tipo de iterador para que sea de acceso aleatorio (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);

Los iteradores tienen varias categorías funcionales:

Iterador unidireccional, solo puede hacer ++
Iterador bidireccional, puede ser ++ y --
Iterador aleatorio, puede ser ++, --, + y -

Sin embargo, la función de clasificación de la lista no es necesaria, porque la eficiencia de ordenar la lista vinculada directamente es mucho más lenta que copiar al vector, ordenar y luego copiar nuevamente a la lista vinculada.

(2）contrarrestar

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

Invertir la lista enlazada

Por ejemplo:


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

resultado de la operación:

Si hay algún error, corríjame.

Compartir tecnología

[C Primaria] Comprensión preliminar de la clase de lista

1. Biblioteca estándarlistaaamable

2. Interfaces comunes de clase de lista.

1. Constructores de uso común

1. Constructor predeterminado, construye una lista enlazada vacía

2. Construya un objeto de lista e inicialícelo con n valores

3.Copiar constructor de clase de lista.

4. Utilice el constructor de inicialización del iterador.

2. Interfaces de capacidad de uso común

1.tamaño,vacío,tamaño máximo,cambiar tamaño

3. Acceso y recorrido común

1.Iterador

2. Iterador inverso

3.frente y detrás

4.Agregar, eliminar, verificar y modificar lista

1) push_front y pop_front

2) push_back y pop_back

3) encontrar

4) insertar

5) borrar

6) intercambiar

7) asignar

8) claro

5. Interfaz de modificación de pedidos de lista

(1）clasificar

(2）contrarrestar

Perfil personal

Mi informacion de contacto