Forward_list Containerul oferă implementarea Lista singuri legată Structura de date. Stochează date în memorie necontigue, unde fiecare element indică următorul element din secvență. Acest lucru face ca introducerea și ștergerea mai rapidă odată ce poziția elementului este cunoscută.

Sintaxă

Lista de înaintare este definită ca STD :: Forward_list șablon de clasă în interiorul < Forward_list > Fișier antet.

Forward_list FL;

unde

• T: Tipul de date de elemente din lista înainte.
• F: Numele atribuit listei de înaintare.

Declarație și inițializare

O listă forward_ poate fi declarată și inițializată în mai multe moduri, așa cum se arată în exemplul de mai jos:

   #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  

Exemplu: În programul de mai sus, suntem simpli lista inițializată inițial în trei moduri:

• Declaraţie Forward_list FL1 Creează o listă goală de numere întregi.
• Declaraţie Forward_list FL2 (34) Creează o listă înainte cu dimensiunea 3 și fiecare element fiind 4.
• Declaraţie Forward_list fl3 = {1 5 3 4} Creează o listă înainte și inițializează cu elementele formează lista inițializantă.

Operații de bază

Iată operațiunile de bază pe care le putem efectua pe o listă înainte:

1. Accesarea elementelor

Elementele listei înainte nu pot fi accesate folosind indici precum tablouri sau vectori. Trebuie să parcurgem secvențial lista de la început până la poziția dorită pentru a o accesa. Acest lucru se poate face prin creșterea ÎNCEPE() iterator, dar este mai bine să folosești Următorul() sau avans() funcţie.

Cu toate acestea, primul element al listei poate fi accesat cu ușurință faţă() metodă.

Exemplu:

   #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 

Exemplu: În programul de mai sus, primul element este tipărit folosind faţă() metodă. Pentru a accesa al treilea element Următorul() se folosește pentru a muta iteratorul două poziții de la început și *it este folosit pentru a dereferenta iteratorul.

2. Introducerea elementelor

Elementele pot fi introduse în lista înainte folosind insert_after () funcţie. Necesită iteratorul după care elementul trebuie introdus. Oricât de rapidă este susținută inserția rapidă în față push_front () metodă.

Exemplu:

   #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ţie: În acest program, primul element al listei forward_list este introdus în față folosind push_front () funcţie. Apoi un iterator este creat și mutat o poziție înainte folosind avans() funcţie. După aceea elementul 5 este introdus după al doilea element folosind insert_after () funcţie.

3. Actualizarea elementelor

Valoarea elementelor existente poate fi modificată pur și simplu prin accesarea acestora și folosind operator de atribuire Pentru a atribui noua valoare.

Exemplu:

   #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. Element de găsire

Lista de înaintare nu oferă nicio funcție de membru pentru a căuta un element, dar putem folosi găsi() algoritm pentru a găsi orice valoare dată.

Exemplu :

   #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. Traversare

O listă înainte poate fi traversată folosind ÎNCEPE() şi Sfârşit() Iteratoare cu o buclă, dar putem merge doar înainte și nu înapoi.

Exemplu:

   #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. Ștergerea elementelor

În lista înainte putem șterge elementul în poziția dată folosind erase_after () metodă. Această metodă duce iteratorul într -o poziție înainte de elementul țintă. Ștergerea rapidă din față este posibilă folosind pop_front () metodă.

Exemplu:

   #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. Mărimea listei înainte

Forward_list nu are o funcție de mărime () încorporată. Pentru a -și găsi dimensiunea, trebuie să numărăm manual elementele traversând -o cu o buclă sau folosind distanța std ::.

   #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. Gol ()

Este folosit pentru a verifica dacă lista înainte_ este goală.
Returnează adevărat dacă lista este goală și falsă, altfel, permițând să verifice rapid dacă containerul nu are date.

   #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.  

Complexitatea timpului

Tabelul de mai jos listează complexitatea de timp a operațiunilor de mai sus pe lista înainte:

Lista de avansare vs lista