SEZNAM VPŘED V C ++ STL

Forward_List kontejner poskytuje implementaci jednotlivě propojený seznam struktura dat. Ukládá data v ne-postisné paměti, kde každý prvek ukazuje na další prvek v sekvenci. To zrychluje vložení a deleci, jakmile je známa poloha prvku.

Syntax

Seznam dopřed je definován jako std :: forward_list Šablona třídy uvnitř < Forward_List > Soubor záhlaví.

Forward_List fl;

kde

T: Typ dat prvků v seznamu dopředu.
F: Název přiřazeného do seznamu dopředu.

Prohlášení a inicializace

Forward_List lze deklarovat a inicializovat několika způsoby, jak je uvedeno v níže uvedeném příkladu:

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

Příklad: Ve výše uvedeném programu jsme jednoduchý inicializovaný seznam dopředu třemi způsoby:

Prohlášení Forward_List FL1 Vytvoří prázdný seznam vpřed celých čísel.
Prohlášení Forward_List FL2 (34) Vytvoří seznam vpřed velikosti 3 a každý prvek je 4.
Prohlášení Forward_List fl3 = {1 5 3 4} Vytvoří seznam dopředu a inicializuje se pomocí prvků, které tvoří seznam inicializátoru.

Základní operace

Zde jsou základní operace, které můžeme provádět na seznamu dopředu:

1. Přístup k prvkům

Prvky Forward List nelze přistupovat pomocí indexů, jako jsou pole nebo vektory. Abychom k němu přistupovali, musíme postupně projít seznamem od začátku do požadované pozice. To lze provést zvýšením začít() iterátor, ale je lepší použít další() nebo záloha() funkce.

První prvek seznamu však lze snadno přistupovat přední() metoda.

Pří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

Příklad: Ve výše uvedeném programu je první prvek vytištěn pomocí přední() metoda. Přístup ke třetímu prvku další() se používá k přesunu iterátoru o dvou pozicích od začátku a *to se používá k dereferenci iterátoru.

2. vložení prvků

Prvky lze vložit do seznamu dopředu pomocí insert_after () funkce. Vyžaduje iterátor, po kterém má být prvek vložen. Rychlé vložení na přední straně je však podporováno push_front () metoda.

Pří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

Vysvětlení: V tomto programu je první prvek Forward_List vložen na přední straně pomocí push_front () funkce. Pak je vytvořen iterátor a posunul jednu polohu vpřed pomocí záloha() funkce. Poté je prvek 5 je vložen za druhým prvkem pomocí insert_after () funkce.

3. Aktualizace prvků

Hodnota stávajících prvků může být změněna jednoduše přístupem k nim a použitím Operátor přiřazení přiřadit novou hodnotu.

Pří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. Nalezení prvku

Seznam dopředného neposkytuje žádnou funkci člena pro vyhledávání prvku, ale můžeme použít nalézt() Algoritmus pro nalezení jakékoli dané hodnoty.

Pří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. Procházení

Seznam dopředu lze projít pomocí začít() a konec() Iterátoři se smyčkou, ale můžeme se pohybovat pouze vpřed a ne dozadu.

Pří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. Mazání prvků

V seznamu vpřed můžeme prvek smazat v dané pozici pomocí erase_after () metoda. Tato metoda posune iterátor do jedné polohy před cílovým prvkem. Rychlé vymazání zepředu je možné pomocí pop_front () metoda.

Pří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. Velikost seznamu dopředu

Forward_LIST nemá vestavěnou funkci velikosti (). Abychom našli svou velikost, musíme ručně spočítat prvky procházením smyčkou nebo pomocí vzdálenosti 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ázdné ()

Používá se ke kontrole, zda je Forward_LIST prázdný.
Vrátí pravdu, pokud je seznam prázdný a nepravdivý, jinak umožňuje rychle ověřit, zda kontejner nemá žádná data.

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.

Složitost času

Níže uvedená tabulka uvádí časovou složitost výše uvedených operací na seznamu Forward:

Operace	Složitost času
Přístup k prvnímu prvku	O (1)
Přístup n ^th živel	Na)
Vložte vpředu	O (1)
Vložte po konkrétní poloze	Na)
Odstranit první prvek	O (1)
Smazat po konkrétní poloze	Na)
Traversal	Na)

Seznam seznamem vpřed vs.

Funkce	Forward_List	seznam
Typ propojeného seznamu	Jednotlivě propojený seznam	Dvojnásobně propojený seznam
Traversal	Může procházet pouze dopředu	Může procházet dopředu i dozadu
Využití paměti	Používá méně paměti (pouze jeden ukazatel na uzel)	Používá více paměti (dva ukazatele na uzel)
Vložení/delece	Rychlé vložení a vymazání, ale pouze na dané poloze nebo po ní	Rychlé vložení a mazání kdekoli (před nebo po poloze)
Podporované funkce	Omezeno ve srovnání se seznamem (bez velikosti () Žádné reverzní iterátory)	Úplnější rozhraní včetně obousměrných iterátorů reverzní () reverzní ().