[C Elementar] Compreensão preliminar da lista class

[C Elementary] Compreensão preliminar da classe de lista

2024-07-12

1. Biblioteca padrãolistaatipo

A camada inferior da lista é uma estrutura de lista vinculada circular bidirecional com bits sentinela.
Comparado com a estrutura de lista vinculada individualmente de forward_list, o iterador de list é um iterador bidirecional
Comparado com contêineres estruturados sequencialmente, como vetor, a lista é mais eficiente na inserção e exclusão em qualquer posição, mas não suporta acesso aleatório em qualquer posição.
List é uma classe de modelo. Ao usá-la, precisamos fornecer o tipo do elemento.

Ao usar a classe list, você precisa incluir o arquivo de cabeçalho<list>

2. Interfaces comuns da classe de lista

1. Construtores comumente usados

1. Construtor padrão, constrói uma lista vinculada vazia

list();

Por exemplo:


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

2. Construa um objeto de lista e inicialize-o com n vals

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

Por exemplo:


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

resultado da operação:

3.Copiar construtor da classe de lista

list(const list& x);

Por exemplo:


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

resultado da operação:

4. Use o construtor de inicialização do iterador


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

Por exemplo:


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

resultado da operação:

2. Interfaces de capacidade comumente usadas

Ainda é o mesmo, deixe-me falar sobre isso juntos aqui.

1.tamanho,vazio,tamanho_máximo,redimensionar

tamanho:retornarlista vinculadaO número de elementos no contêiner.
size_type size() const;
vazio:retornarlistaSe o contêiner está vazio (ou seja, se estátamanhoé 0).
(Nota: Esta função não modifica o contêiner de forma alguma. Para limparlista vinculadaO conteúdo do recipiente, consultelista::limpar。）
bool empty() const;
tamanho máximo(não comumente usado): retornarlista vinculadaO número máximo de elementos que o contêiner pode conter.
(Devido às limitações conhecidas de implementação do sistema ou da biblioteca, este é o potencial máximo que um contêiner pode alcançartamanho , mas não há garantia de que o contêiner atingirá esse tamanho: ele ainda poderá não conseguir alocar armazenamento em nenhum momento antes de atingir esse tamanho. )
size_type max_size() const;
redimensionar:Redimensione o contêiner para contereelementos.
seemenor que o contêiner atualtamanho, o conteúdo será reduzido ao seu valor anterioreelementos, removendo aqueles que excedem (e destruindo-os).
seeMaior que o contêiner atualtamanho, então o conteúdo é expandido inserindo o número necessário de elementos no final para alcançare o tamanho de.Se especificadovalee, então o novo elemento será inicializado paravaleecópias, caso contrário, elas serão inicializadas com valor.
(Observe que esta função altera o conteúdo real do contêiner inserindo ou apagando elementos do contêiner.)
void resize (size_type n, value_type val = value_type());

Por exemplo:


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 da operação:

3. Acesso e travessia comuns

1.Iterador


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

Iterador: usado para obter a posição do primeiro nó e do último nó na lista vinculadaPróxima posição (ou seja, posição sentinela)

Por exemplo:


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

resultado da operação:

2. Iterador reverso

iterador reverso rbegin();

const_reverse_iterator rbegin() const;

iterador reverso rend();

const_reverse_iterator rend() const;

Iterador reverso, rbegin obtém a posição do último nó no contêiner, rend obtém a posição do bit sentinela no contêiner


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 da operação:

Nota: O iterador reverso rit também deve usar ++ em vez de --

3.frente e verso

frente:

referência front();

const_reference front() const;

Retorna uma referência aos dados armazenados no primeiro nó da lista vinculada

voltar:

referência back();

const_reference voltar() const;

Retorna uma referência aos dados armazenados no último nó da lista vinculada

Por exemplo:


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

resultado da operação:

4.Adicionar, excluir, verificar e modificar lista

1) push_front e pop_front

push_front é chamado de inserção de cabeçalho, inserindo um elemento do cabeçalho da lista vinculada

void push_front(const tipo_de_valor& val);

pop_front é chamado de exclusão de cabeçalho, que exclui um elemento do cabeçalho da lista vinculada.

vazio pop_front();

void pop_front();

Por exemplo:


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 da operação:

2) push_back e pop_back

push_back é chamado de inserção final, inserindo um elemento do final da lista vinculada

void push_back(const tipo_de_valor& val);

pop_back é chamado de exclusão final, que exclui um elemento do final da lista vinculada.

vazio pop_back();

Por exemplo:


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 da operação:

3) encontrar


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

Encontre val no intervalo de dois iteradores e retorne o iterador onde ele está localizado

Por exemplo:


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 da operação:

Nota: Esta função não é uma função membro da lista, mas uma função na biblioteca padrão. Vários contêineres compartilham a função find.

Como você pode ver, podemos desreferenciar diretamente o iterador da lista e modificar seu conteúdo, mas o iterador não deveria apontar para o nó? Por que a desreferenciação pode modificar os dados?

Na verdade, o iterador da lista não é simulado e implementado usando o ponteiro ecológico original, e precisa ser encapsulado na parte inferior, o que será refletido no código-fonte da implementação simulada da lista.

4）inserir

iterador insert(iterador posição, const value_type& val);

void insert(posição do iterador, tipo_de_tamanho n, const tipo_de_valor& val);

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

modelo<class InputIterator>

void insert(posição do iterador, InputIterator primeiro, InputIterator último);

Insira um ou mais elementos na frente da posição

Por exemplo:


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 da operação:

Estudantes cuidadosos podem ter descoberto que a operação de inserção de lista éNão fará com que o iterador se torne inválido, porque o nó apontado por pos permanece inalterado e a posição relativa não muda.

No entanto, a operação de exclusão da lista definitivamente fará com que o iterador se torne inválido, e apenas o iterador que aponta para o nó excluído será inválido e outros iteradores não serão afetados.

5) apagar


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

Exclua o elemento na posição ou todos os elementos no intervalo [primeiro, último)

Por exemplo:


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 da operação:


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 da operação:

6) trocar

void swap(vetor& x);

Trocar dois objetos de lista

Por exemplo:


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 da operação:

7）atribuir

modelo<class InputIterator>

void assign(InputIterator primeiro, InputIterator último);

void atribuir(tipo_tamanho n, const tipo_valor& val);

Especifique o novo conteúdo para a lista, substitua seu conteúdo atual e modifique o número de nós

Por exemplo:


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 da operação:

8）Limpar

vazio limpar();

Exclua todos os nós da lista vinculada

Por exemplo:


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

resultado da operação:

5. Interface de modificação de pedido de lista

(1）organizar

void classificar();

modelo<class Compare>

void sort(Comparar comp);

Devido à particularidade da estrutura da lista, a função de classificação da biblioteca padrão não pode ser utilizada, pois o iterador não pode realizar operações de subtração.

E na documentação C++, podemos ver que a classificação na biblioteca padrão também limita o tipo de iterador para acesso aleatório (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);

Os iteradores têm várias categorias funcionais:

Iterador unidirecional, só pode fazer ++
Iterador bidirecional, pode ser ++ e --
Iterador aleatório, pode ser ++, --, + e -

No entanto, a função de classificação da lista não é necessária, porque a eficiência de classificar a lista vinculada diretamente é muito mais lenta do que copiar para o vetor, classificar e depois copiar de volta para a lista vinculada.

(2）reverter

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

Reverter a lista vinculada

Por exemplo:


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 da operação:

Se houver algum erro, corrija-me.

Compartilhamento de tecnologia

[C Elementary] Compreensão preliminar da classe de lista

1. Biblioteca padrãolistaatipo

2. Interfaces comuns da classe de lista

1. Construtores comumente usados

1. Construtor padrão, constrói uma lista vinculada vazia

2. Construa um objeto de lista e inicialize-o com n vals

3.Copiar construtor da classe de lista

4. Use o construtor de inicialização do iterador

2. Interfaces de capacidade comumente usadas

1.tamanho,vazio,tamanho_máximo,redimensionar

3. Acesso e travessia comuns

1.Iterador

2. Iterador reverso

3.frente e verso

4.Adicionar, excluir, verificar e modificar lista

1) push_front e pop_front

2) push_back e pop_back

3) encontrar

4）inserir

5) apagar

6) trocar

7）atribuir

8）Limpar

5. Interface de modificação de pedido de lista

(1）organizar

(2）reverter

Perfil pessoal

minhas informações de contato