FRAMÅTLISTA I C ++ STL

Forward_List container tillhandahåller implementering av ensam länkad lista datastruktur. Den lagrar data i icke-kontinuerligt minne där varje element pekar på nästa element i sekvensen. Detta gör infogning och radering snabbare när elementets position är känd.

Syntax

Framåtlistan definieras som std :: framåt_lista klassmall inuti < Forward_List > rubrikfil.

Forward_List fl;

där

T: Datatyp av element i framåtlistan.
F: Namn tilldelat listan.

Deklaration och initialisering

En framåt_lista kan deklareras och initialiseras på flera sätt som visas i exemplet nedan:

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

Produktion

4 4 4 1 5 3 4

Exempel: I programmet ovan är vi enkla initialiserade framåtlistan på tre sätt:

Påstående Forward_List Fl1 Skapar en tom framåtlista med heltal.
Påstående Forward_List FL2 (34) Skapar en framåtlista över storlek 3 och med varje element 4.
Påstående Forward_List FL3 = {1 5 3 4} Skapar en framåtlista och initialiseras med elementen från initialiseringslistan.

Grundläggande verksamhet

Här är de grundläggande operationerna vi kan utföra på en framåtlista:

1. Åtkomst till element

Framåtlistans element kan inte nås med index som matriser eller vektorer. Vi måste gå igenom listan i följd från början till önskad position för att komma åt den. Detta kan göras genom att öka börja() iterator men det är bättre att använda nästa() eller förskott() fungera.

Det första elementet i listan kan enkelt nås av främre() metod.

Exempel:

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

Produktion

1 3

Exempel: I ovanstående program trycks det första elementet med hjälp av främre() metod. För att komma åt det tredje elementet nästa() används för att flytta iteratorn två positioner från början och *det används för att avvisa iteratorn.

2. Infoga element

Element kan sättas in i framåtlistan med insert_after () fungera. Det kräver iteratorn, varefter elementet ska sättas in. Men snabb insättning på framsidan stöds av push_front () metod.

Exempel:

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

Produktion

1 5 3 4

Förklaring: I detta program infogas det första elementet i framåt_listan framtill med push_front () fungera. Sedan skapas en iterator och flyttade en position framåt med förskott() fungera. Efter det elementet 5 sätts in efter det andra elementet med insert_after () fungera.

3. Uppdatera element

Värdet på befintliga element kan ändras helt enkelt genom att komma åt dem och använda uppdragsoperatör för att tilldela det nya värdet.

Exempel:

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

Produktion

111 333

4. Hitta element

Framåtlistan ger ingen medlemsfunktion för att söka efter ett element men vi kan använda hitta() algoritm för att hitta ett givet värde.

Exempel :

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

Produktion

5. Traversing

En framåtlista kan korsas med börja() och avsluta() Iteratorer med en slinga men vi kan bara gå framåt och inte bakåt.

Exempel:

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

Produktion

1 5 3 4

6. Ta bort element

I framåtlistan kan vi ta bort elementet på den givna positionen med erase_after () metod. Denna metod tar iteratorn till en position före målelementet. Snabb borttagning framifrån är möjlig med hjälp av Pop_front () metod.

Exempel:

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

Produktion

5 3

7. Storleken på framåtlistan

Forward_List har inte en inbyggd storlek () -funktion. För att hitta dess storlek måste vi manuellt räkna elementen genom att korsa den med en slinga eller använda std :: avstånd.

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

Produktion

Size of forward_list: 4

8. Tom ()

Det används för att kontrollera om framåt_listan är tom.
Den returnerar sant om listan är tom och falsk på annat sätt tillåter att snabbt verifiera om behållaren inte har några 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  ;   }

Produktion

The forward_list is empty. The forward_list is not empty.

Tidskomplexitet

Tabellen nedan visar tidskomplexiteten för ovanstående operationer på framåtlistan:

Drift	Tidskomplexitet
Åtkomst till första elementet	O (1)
Åtkomst till ^th element	På)
Sätt fram på framsidan	O (1)
Infoga efter specifik position	På)
Ta bort första elementet	O (1)
Ta bort efter specifik position	På)
Genomgång	På)

Framåtlista vs -lista

Särdrag	Forward_List	lista
Typ av länkad lista	Ensam länkad lista	Dubbelt länkad lista
Genomgång	Kan bara korsa framåt	Kan korsa både framåt och bakåt
Minnesanvändning	Använder mindre minne (endast en pekare per nod)	Använder mer minne (två pekare per nod)
Införande/radering	Snabb insättning och radering men bara vid eller efter en given position	Snabb insättning och borttagning var som helst (före eller efter en position)
Funktioner som stöds	Begränsad jämfört med lista (ingen storlek () inga omvända iteratorer)	Mer komplett gränssnitt inklusive storlek () omvänd () dubbelriktade iteratorer.