Lista_de_encaminhamento contêiner fornece a implementação de lista vinculada individualmente estrutura de dados. Ele armazena dados em memória não contígua, onde cada elemento aponta para o próximo elemento da sequência. Isso torna a inserção e a exclusão mais rápidas quando a posição do elemento é conhecida.

Sintaxe

A lista de encaminhamento é definida como std::forward_list modelo de classe dentro do < lista_de_encaminhamento > arquivo de cabeçalho.

lista_de_encaminhamento fl;

onde

• T: Tipo de dados dos elementos na lista de encaminhamento.
• F: Nome atribuído à lista de encaminhamento.

Declaração e inicialização

Um forward_list pode ser declarado e inicializado de várias maneiras, conforme mostrado no exemplo abaixo:

   #include          using     namespace     std  ;   void     printFL  (  forward_list   <  int  >&     fl  )     {      for     (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     'n'  ;   }   int     main  ()     {          // Creating an empty forward_list      forward_list   <  int  >     fl1  ;      // Creating a forward_list with      // default value      forward_list   <  int  >     fl2  (  3       4  );          // Creating a forward_list from an      // initializer list      forward_list   <  int  >     fl3     =     {  1       5       3       4  };          printFL  (  fl2  );      printFL  (  fl3  );      return     0  ;   }   

4 4 4 1 5 3 4  

Exemplo: No programa acima, somos uma lista direta inicializada de três maneiras:

• Declaração lista_de_encaminhamento FL1 cria uma lista direta vazia de inteiros.
• Declaração lista_de_encaminhamento fl2(34) cria uma lista direta de tamanho 3 e com cada elemento sendo 4.
• Declaração lista_de_encaminhamento fl3 = {1 5 3 4} cria uma lista de encaminhamento e inicializa com os elementos da lista de inicializadores.

Operações Básicas

Aqui estão as operações básicas que podemos realizar em uma lista de encaminhamento:

1. Acessando Elementos

Os elementos da lista de encaminhamento não podem ser acessados ​​usando índices como arrays ou vetores. Temos que percorrer a lista sequencialmente desde o início até a posição desejada para acessá-la. Isso pode ser feito incrementando começar() iterador, mas é melhor usar próximo() ou avançar() função.

No entanto, o primeiro elemento da lista pode ser facilmente acessado por frente() método.

Exemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Access the first element      cout      < <     fl  .  front  ()      < <     endl  ;          // Access third element      auto     it     =     next  (  fl  .  begin  ()     2  );      cout      < <     *  it  ;      return     0  ;   }   

1 3 

Exemplo: No programa acima, o primeiro elemento é impresso usando frente() método. Para acessar o terceiro elemento próximo() é usado para mover o iterador duas posições desde o início e *isto é usado para desreferenciar o iterador.

2. Inserindo Elementos

Os elementos podem ser inseridos na lista direta usando inserir_depois() função. Requer o iterador após o qual o elemento será inserido. No entanto, a inserção rápida na frente é suportada por push_front() método.

Exemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  5       4  };      // Inserting Element at front      fl  .  push_front  (  1  );          // Insert 3 after the second element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  insert_after  (  it       3  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }   

1 5 3 4  

Explicação: Neste programa o primeiro elemento da forward_list é inserido na frente usando o push_front() função. Em seguida, um iterador é criado e movido uma posição para frente usando o comando avançar() função. Depois disso o elemento 5 é inserido após o segundo elemento usando o inserir_depois() função.

3. Atualizando Elementos

O valor dos elementos existentes pode ser alterado simplesmente acessando-os e usando operador de atribuição para atribuir o novo valor.

Exemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Updating first element      fl  .  front  ()     =     111  ;      cout      < <     fl  .  front  ()      < <     endl  ;          // Updating third element      auto     it     =     next  (  fl  .  begin  ()     2  );      *  it     =     333  ;      cout      < <     *  it  ;      return     0  ;   }   

111 333 

4. Encontrando Elemento

A lista direta não fornece nenhuma função membro para procurar um elemento, mas podemos usar o encontrar() algoritmo para encontrar qualquer valor fornecido.

Exemplo :

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Finding 3      auto     it     =     find  (  fl  .  begin  ()     fl  .  end  ()     3  );          if     (  it     !=     fl  .  end  ())     cout      < <     *  it  ;      else     cout      < <     'Element not Found'  ;      return     0  ;   }   

3 

5. Atravessando

Uma lista de encaminhamento pode ser percorrida usando começar() e fim() iteradores com um loop, mas só podemos avançar e não retroceder.

Exemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };          // Traversing using range-based for loop      for  (  auto     i     :     fl  )      cout      < <     i      < <     ' '  ;      cout      < <     endl  ;          return     0  ;   }   

1 5 3 4  

6. Excluindo Elementos

Na lista direta, podemos excluir o elemento na posição determinada usando apagar_depois() método. Este método leva o iterador para uma posição antes do elemento de destino. A exclusão rápida pela frente é possível usando pop_front() método.

Exemplo:

   #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     fl     =     {  1       5       3       4  };      // Delete first element      fl  .  pop_front  ();          // Delete third element      auto     it     =     fl  .  begin  ();      advance  (  it       1  );      fl  .  erase_after  (  it  );          for     (  auto     x  :     fl  )     cout      < <     x      < <     ' '  ;      return     0  ;   }   

5 3  

7. Tamanho da lista de encaminhamento

forward_list não possui uma função size() integrada. Para encontrar seu tamanho, precisamos contar manualmente os elementos percorrendo-o com um loop ou usando std::distância.

   #include          #include         #include          using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  =  {  10    20    30    40  };      //Calculate size by counting elements using std:: distance      int     size  =  distance  (  flist  .  begin  ()  flist  .  end  ());      cout   < <  'Size of forward_list: '   < <  size   < <  endl  ;      return     0  ;   }   

Size of forward_list: 4  

8. vazio()

É usado para verificar se forward_list está vazio.
Ele retorna verdadeiro se a lista estiver vazia e falso caso contrário, permite verificar rapidamente se o contêiner não possui dados.

   #include          #include         using     namespace     std  ;   int     main  ()     {      forward_list   <  int  >     flist  ;      if     (  flist  .  empty  ())     {      cout      < <     'The forward_list is empty.'      < <     endl  ;      }      flist  .  push_front  (  10  );      if     (  !  flist  .  empty  ())     {      cout      < <     'The forward_list is not empty.'      < <     endl  ;      }      return     0  ;   }   

The forward_list is empty. The forward_list is not empty.  

Complexidade de tempo

A tabela abaixo lista a complexidade de tempo das operações acima na lista de encaminhamento:

Lista de encaminhamento vs lista