Forward_list container verzorgt de uitvoering van enkelvoudig gekoppelde lijst gegevensstructuur. Het slaat gegevens op in een niet-aangrenzend geheugen, waarbij elk element naar het volgende element in de reeks verwijst. Dit maakt het invoegen en verwijderen sneller zodra de positie van het element bekend is.

Syntaxis

Voorwaartse lijst is gedefinieerd als std::forward_list klassensjabloon in de< forward_list > headerbestand.

Java-tekenreeks-subtekenreeks

forward_listfl;

waar

• T: Gegevenstype van elementen in de voorwaartse lijst.
• F: Naam toegewezen aan de doorstuurlijst.

Verklaring en initialisatie

Een forward_list kan op verschillende manieren worden gedeclareerd en geïnitialiseerd, zoals weergegeven in het onderstaande voorbeeld:

#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 

Voorbeeld: In het bovenstaande programma zijn we op drie manieren een eenvoudige geïnitialiseerde voorwaartse lijst:

• Stelling forward_list FL1 creëert een lege voorwaartse lijst met gehele getallen.
• Stelling forward_list fl2(34) creëert een voorwaartse lijst met grootte 3 en waarbij elk element 4 is.
• Stelling forward_list fl3 = {1 5 3 4} creëert een voorwaartse lijst en initialiseert met de elementen uit de initialisatielijst.

Basisbewerkingen

Dit zijn de basisbewerkingen die we kunnen uitvoeren op een voorwaartse lijst:

1. Toegang tot elementen

De elementen van de Forward List zijn niet toegankelijk via indices zoals arrays of vectoren. We moeten de lijst vanaf het begin tot aan de gewenste positie doorlopen om er toegang toe te krijgen. Dit kan door te verhogen beginnen() iterator, maar het is beter om te gebruiken volgende() of voorschot() functie.

Het eerste element van de lijst is echter gemakkelijk toegankelijk via voorkant() methode.

Voorbeeld:

#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

Voorbeeld: In het bovenstaande programma wordt het eerste element afgedrukt met behulp van voorkant() methode. Om toegang te krijgen tot het derde element volgende() wordt gebruikt om de iterator twee posities vanaf het begin te verplaatsen *Het wordt gebruikt om de iterator te derefereren.

2. Elementen invoegen

Elementen kunnen in de voorwaartse lijst worden ingevoegd met behulp van insert_after() functie. Het vereist de iterator waarna het element moet worden ingevoegd. Hoe snel het inbrengen aan de voorkant ook wordt ondersteund push_front() methode.

Voorbeeld:

#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 

Uitleg: In dit programma wordt het eerste element van de forward_list vooraan ingevoegd met behulp van de push_front() functie. Vervolgens wordt een iterator gemaakt en één positie vooruit verplaatst met behulp van de voorschot() functie. Daarna het element 5 wordt na het tweede element ingevoegd met behulp van de insert_after() functie.

3. Elementen bijwerken

De waarde van bestaande elementen kan eenvoudig worden gewijzigd door ze te openen en te gebruiken opdracht operator om de nieuwe waarde toe te wijzen.

Voorbeeld:

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

De doorstuurlijst biedt geen ledenfunctie om naar een element te zoeken, maar we kunnen de vinden() algoritme om een ​​bepaalde waarde te vinden.

Voorbeeld :

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

Een voorwaartse lijst kan worden doorlopen met behulp van beginnen() En einde() iterators met een lus, maar we kunnen alleen vooruit gaan en niet achteruit.

Voorbeeld:

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

In de voorwaartse lijst kunnen we het element op de gegeven positie verwijderen met behulp van wis_na() methode. Deze methode brengt de iterator naar één positie vóór het doelelement. Snel verwijderen vanaf de voorkant is mogelijk met behulp van pop_front() methode.

nieuwe lijnpython

Voorbeeld:

#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. Grootte van de doorstuurlijst

forward_list heeft geen ingebouwde size() functie. Om de grootte ervan te vinden, moeten we de elementen handmatig tellen door er met een lus doorheen te gaan of door std:: afstand te gebruiken.

#include    #include  #include    using namespace std; int main() {  forward_list<int> flist={10203040};  //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. leeg()

Het wordt gebruikt om te controleren of de forward_list leeg is.
Het retourneert waar als de lijst leeg en onwaar is, anders kunt u snel verifiëren of de container geen gegevens bevat.

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

Tijdcomplexiteit

De onderstaande tabel geeft een overzicht van de tijdscomplexiteit van de bovenstaande bewerkingen op de voorwaartse lijst:

Lijst doorsturen versus lijst