Forward_list Container leverer implementering af Enkelt linket liste datastruktur. Det gemmer data i ikke-sammenhængende hukommelse, hvor hvert element peger på det næste element i sekvensen. Dette gør indsættelse og deletion hurtigere, når elementets position er kendt.

Syntaks

Fremadsliste defineres som std :: fremad_list klasseskabelon inde i < Forward_list > header -fil.

Forward_list fl;

hvor

• T: Datatype af elementer på listen frem.
• F: Navn tildelt den forreste liste.

Erklæring og initialisering

En Forward_List kan erklæres og initialiseres på flere måder som vist i nedenstående eksempel:

   #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  

Eksempel: I ovenstående program er vi enkel initialiseret fremadrettet liste på tre måder:

• Erklæring Forward_list FL1 Opretter en tom fremadliste over heltal.
• Erklæring Forward_list FL2 (34) Opretter en fremadrettet liste over størrelse 3 og med hvert element er 4.
• Erklæring Forward_list fl3 = {1 5 3 4} Opretter en fremadrettet liste og initialiseres med elementerne fra initialiseringslisten.

Grundlæggende operationer

Her er de grundlæggende operationer, vi kan udføre på en fremadrettet liste:

1. adgang til elementer

Fremadsliste -elementer kan ikke fås adgang til ved hjælp af indeks som arrays eller vektorer. Vi er nødt til at gennemgå listen sekventielt fra starten til den ønskede position for at få adgang til den. Dette kan gøres ved at øge begynde() iterator, men det er bedre at bruge næste() eller fremskridt () fungere.

Imidlertid kan det første element på listen let fås adgang til front() metode.

Eksempel:

   #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 

Eksempel: I ovenstående program udskrives det første element ved hjælp af front() metode. For at få adgang til det tredje element næste() bruges til at flytte iteratoren to positioner fra begyndelsen og *det bruges til at derference iteratoren.

2. Indsættelse af elementer

Elementer kan indsættes på listen for fremad ved hjælp af insert_after () fungere. Det kræver iterator, hvorefter elementet skal indsættes. Uanset hvor hurtig indsættelse foran understøttes af push_front () metode.

Eksempel:

   #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  

Forklaring: I dette program indsættes det første element i Forward_Listen foran ved hjælp af push_front () fungere. Derefter oprettes en iterator og flyttes en position fremad ved hjælp af fremskridt () fungere. Derefter elementet 5 indsættes efter det andet element ved hjælp af insert_after () fungere.

3. Opdatering af elementer

Værdien af ​​eksisterende elementer kan ændres ved blot at få adgang til dem og bruge Tildelingsoperatør at tildele den nye værdi.

Eksempel:

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

Fremadslisten giver ingen medlemsfunktion til at søge efter et element, men vi kan bruge finde() Algoritme for at finde nogen given værdi.

Eksempel :

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

En fremadrettet liste kan krydses ved hjælp af begynde() og ende() Iteratorer med en løkke, men vi kan kun komme videre og ikke bagud.

Eksempel:

   #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. Sletning af elementer

På en fremadrettet liste kan vi slette elementet i den givne position ved hjælp af Erase_after () metode. Denne metode fører iteratoren til en position før målelementet. Hurtig sletning fra fronten er mulig ved hjælp af pop_front () metode.

Eksempel:

   #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. Størrelse på fremadrettet liste

Forward_list har ikke en indbygget størrelse () -funktion. For at finde dens størrelse er vi nødt til manuelt at tælle elementerne ved at krydse det med en løkke eller bruge std :: afstand.

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

Det bruges til at kontrollere, om fremadretningen er tom.
Det returnerer sandt, hvis listen er tom og falsk ellers tillader det hurtigt at verificere, om containeren ikke har nogen data.

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

Tidskompleksitet

Nedenstående tabel viser tidskompleksiteten af ​​ovenstående operationer på fremadrettet liste:

Fremadsliste vs liste