Forward_list Container stellt die Implementierung von bereit einfach verknüpfte Liste Datenstruktur. Es speichert Daten im nicht zusammenhängenden Speicher, wobei jedes Element auf das nächste Element in der Sequenz zeigt. Dies beschleunigt das Einfügen und Löschen, sobald die Position des Elements bekannt ist.

Syntax

Weiterleitungsliste ist definiert als std::forward_list Klassenvorlage innerhalb der < vorwärts_liste > Header-Datei.

vorwärts_liste fl;

Wo

• T: Datentyp der Elemente in der Vorwärtsliste.
• F: Der der Weiterleitungsliste zugewiesene Name.

Deklaration und Initialisierung

Eine „forward_list“ kann auf verschiedene Arten deklariert und initialisiert werden, wie im folgenden Beispiel gezeigt:

   #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  

Beispiel: Im obigen Programm initialisieren wir die Vorwärtsliste einfach auf drei Arten:

• Stellungnahme vorwärts_liste FL1 Erstellt eine leere Vorwärtsliste von Ganzzahlen.
• Stellungnahme vorwärts_liste fl2(34) Erstellt eine Vorwärtsliste der Größe 3 und jedes Element ist 4.
• Stellungnahme vorwärts_liste fl3 = {1 5 3 4} erstellt eine Vorwärtsliste und initialisiert mit den Elementen aus der Initialisierungsliste.

Grundlegende Operationen

Hier sind die grundlegenden Operationen, die wir für eine Weiterleitungsliste ausführen können:

1. Auf Elemente zugreifen

Auf die Elemente der Vorwärtsliste kann nicht über Indizes wie Arrays oder Vektoren zugegriffen werden. Wir müssen die Liste der Reihe nach vom Anfang bis zur gewünschten Position durchgehen, um darauf zuzugreifen. Dies kann durch Inkrementieren erfolgen beginnen() Iterator, aber es ist besser zu verwenden nächste() oder Vorauszahlung() Funktion.

Auf das erste Element der Liste kann jedoch leicht zugegriffen werden Front() Verfahren.

Beispiel:

   #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 

Beispiel: Im obigen Programm wird das erste Element mit gedruckt Front() Verfahren. Um auf das dritte Element zuzugreifen nächste() wird verwendet, um den Iterator um zwei Positionen vom Anfang zu verschieben und *Es wird verwendet, um den Iterator zu dereferenzieren.

2. Elemente einfügen

Elemente können mit in die Vorwärtsliste eingefügt werden insert_after() Funktion. Es benötigt den Iterator, nach dem das Element eingefügt werden soll. Allerdings wird das schnelle Einsetzen an der Vorderseite durch unterstützt push_front() Verfahren.

Beispiel:

   #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  

Erläuterung: In diesem Programm wird das erste Element der Forward_list vorne mit eingefügt push_front() Funktion. Dann wird ein Iterator erstellt und mit dem um eine Position nach vorne verschoben Vorauszahlung() Funktion. Danach das Element 5 wird nach dem zweiten Element mit eingefügt insert_after() Funktion.

3. Elemente aktualisieren

Der Wert vorhandener Elemente kann einfach durch Zugriff und Verwendung geändert werden Zuweisungsoperator um den neuen Wert zuzuweisen.

Beispiel:

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

Die Vorwärtsliste bietet keine Mitgliedsfunktion zum Suchen nach einem Element, wir können jedoch die verwenden finden() Algorithmus, um einen beliebigen Wert zu finden.

Beispiel :

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

Eine Vorwärtsliste kann mit durchlaufen werden beginnen() Und Ende() Iteratoren mit einer Schleife, aber wir können uns nur vorwärts und nicht rückwärts bewegen.

Beispiel:

   #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. Elemente löschen

In der Vorwärtsliste können wir das Element an der angegebenen Position mit löschen erase_after() Verfahren. Diese Methode bringt den Iterator an eine Position vor dem Zielelement. Ein schnelles Löschen von vorne ist mit möglich pop_front() Verfahren.

Beispiel:

   #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. Größe der Weiterleitungsliste

Forward_list verfügt nicht über eine integrierte size()-Funktion. Um seine Größe zu ermitteln, müssen wir die Elemente manuell zählen, indem wir es mit einer Schleife durchlaufen oder std::distanz verwenden.

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

Es wird verwendet, um zu prüfen, ob die Forward_list leer ist.
Es gibt „true“ zurück, wenn die Liste leer ist, andernfalls „false“, sodass schnell überprüft werden kann, ob der Container keine Daten enthält.

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

Zeitkomplexität

In der folgenden Tabelle ist die zeitliche Komplexität der oben genannten Vorgänge in der Weiterleitungsliste aufgeführt:

Weiterleitungsliste vs. Liste