ZOZNAM VPRED V C ++ STL

Forward_list kontajner poskytuje implementáciu jednotlivo prepojený zoznam Štruktúra údajov. Ukladá údaje do neúmyselnej pamäte, kde každý prvok poukazuje na ďalší prvok v sekvencii. Vďaka tomu je vloženie a vymazanie rýchlejšie, keď je známa poloha prvku.

Syntax

Zoznam vpred je definovaný ako Std :: Forward_list Šablóna triedy vo vnútri < Forward_list > Súbor hlavičky.

Forward_list fl;

kdekoľvek

T: Dátový typ prvkov v zozname Forward.
F: Názov priradený do zoznamu Forward.

Vyhlásenie

Forward_list je možné deklarovať a inicializovať niekoľkými spôsobmi, ako je uvedené v nižšie uvedenom príklade:

C++

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

Výstup

4 4 4 1 5 3 4

Príklad: Vo vyššie uvedenom programe sme jednoduchý inicializovaný zoznam vpred tromi spôsobmi:

Vyhlásenie Forward_list Fl1 Vytvorí prázdny zoznam vpred celé čísla.
Vyhlásenie Forward_list FL2 (34) Vytvorí predný zoznam veľkosti 3 a každý prvok je 4.
Vyhlásenie Forward_list fl3 = {1 5 3 4} Vytvorí zoznam vpred a inicializuje sa s prvkami, ktorý je uvedený v zozname inicializátor.

Základné operácie

Tu sú základné operácie, ktoré môžeme vykonať v zozname Forward:

1. Prístup k prvkom

K prvkom Forward List nie je možné pristupovať pomocou indexov, ako sú polia alebo vektory. Zoznam musíme prejsť postupne od začiatku do požadovanej polohy, aby sme k nemu získali prístup. To sa dá dosiahnuť zvýšením začať () iterátor, ale je lepšie používať Next () alebo Advance () funkcia.

K prvému prvku zoznamu je však možné ľahko získať prístup predný () metóda.

Príklad:

C++

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

Výstup

1 3

Príklad: Vo vyššie uvedenom programe je prvý prvok vytlačený pomocou použitia predný () metóda. Ak chcete získať prístup k tretiemu prvku Next () sa používa na presun iterátora dve pozície od začiatku a * sa používa na dereferenciu iterátora.

2. Vkladanie prvkov

Prvky môžu byť vložené do zoznamu vpred pomocou insert_after () funkcia. Vyžaduje iterátor, po ktorom sa má prvok vložiť. Avšak rýchle vloženie na fronte je podporované push_front () metóda.

Príklad:

C++

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

Výstup

1 5 3 4

Vysvetlenie: V tomto programe sa prvý prvok Forward_list vkladá vpredu pomocou push_front () funkcia. Potom je vytvorený iterátor a posunie jednu pozíciu vpred pomocou Advance () funkcia. Potom prvok 5 sa vkladá po druhom prvku pomocou insert_after () funkcia.

3. Aktualizácia prvkov

Hodnota existujúcich prvkov je možné zmeniť jednoducho prístupom k nim a používaním prevádzkovateľ prideľovania priradiť novú hodnotu.

Príklad:

C++

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

Výstup

111 333

4. Nájdenie prvku

Zoznam vpred neposkytuje žiadnu funkciu člena na vyhľadávanie prvku, ale môžeme použiť find () Algoritmus na nájdenie akejkoľvek danej hodnoty.

Príklad :

C++

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

Výstup

5. Prechodovanie

Zoznam vpred je možné prejsť pomocou začať () a koniec () Iterátori s slučkou, ale môžeme sa pohnúť vpred a nie dozadu.

Príklad:

C++

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

Výstup

1 5 3 4

6. Vymazanie prvkov

V zozname Forward môžeme prvok odstrániť v danej pozícii pomocou erase_after () metóda. Táto metóda posúva iterátor do jednej polohy pred cieľovým prvkom. Rýchle vymazanie spredu je možné pomocou pop_front () metóda.

Príklad:

C++

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

Výstup

5 3

7. Veľkosť zoznamu vpred

Forward_list nemá funkciu vstavanej veľkosti (). Aby sme našli jeho veľkosť, musíme manuálne spočítať prvky tým, že ich prejdeme slučkou alebo pomocou vzdialenosti STD ::.

C++

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

Výstup

Size of forward_list: 4

8. prázdny ()

Používa sa na kontrolu, či je Forward_list prázdny.
Vráti true, ak je zoznam prázdny a nepravdivý, inak umožňuje rýchlo overiť, či kontajner nemá žiadne údaje.

C++

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

Výstup

The forward_list is empty. The forward_list is not empty.

Zložitosť

Nižšie uvedená tabuľka uvádza časovú zložitosť vyššie uvedených operácií v zozname Forward:

Činnosť	Zložitosť
Prístup k prvému prvku	O (1)
Prístup n ^th prvok	O (n)
Vložiť vpredu	O (1)
Vložte po konkrétnej polohe	O (n)
Vymazať prvý prvok	O (1)
Odstráňte po konkrétnej polohe	O (n)
Priechod	O (n)

Zoznam vs.

Funkcia	Forward_list	zoznam
Typ prepojeného zoznamu	Jednotlivo prepojený zoznam	Dvojnásobne prepojený zoznam
Priechod	Môže prechádzať iba vpred	Môže prechádzať dopredu aj dozadu
Využitie pamäte	Používa menej pamäte (iba jeden ukazovateľ na uzol)	Používa viac pamäte (dva ukazovatele na uzol)
Vloženie/vymazanie	Rýchle vloženie a vymazanie, ale iba na alebo po danej polohe	Rýchle vloženie a vymazanie kdekoľvek (pred alebo po pozícii)
Podporované funkcie	V porovnaní so zoznamom (bez veľkosti () žiadne opakované iterátory)	Kompletnejšie rozhranie vrátane obojsmerných iterátorov s veľkosťou () reverznej ().