FREMOVER I C ++ STL

Forward_list Container gir implementering av Enkelt koblet liste datastruktur. Den lagrer data i ikke-sammenhengende minne der hvert element peker på neste element i sekvensen. Dette gjør innsetting og sletting raskere når elementets plassering er kjent.

Syntaks

Fremoverliste er definert som STD :: Forward_list Klassemal inne i < Forward_list > Headerfil.

Forward_list fl;

hvor

T: Datatype av elementer i listen fremover.
F: Navn tildelt fremoverlisten.

Erklæring og initialisering

En forward_list kan deklareres og initialiseres på flere måter som vist i eksemplet nedenfor:

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

Produksjon

4 4 4 1 5 3 4

Eksempel: I programmet ovenfor er vi enkel initialisert fremoverliste på tre måter:

Uttalelse Forward_list FL1 Oppretter en tom liste over heltall.
Uttalelse Forward_list FL2 (34) Oppretter en fremoverliste over størrelse 3 og med hvert element som er 4.
Uttalelse Forward_list fl3 = {1 5 3 4} Oppretter en fremoverliste og initialiserer med elementene fra Initializer -listen.

Grunnleggende operasjoner

Her er de grunnleggende operasjonene vi kan utføre på en fremover liste:

1. Å få tilgang til elementer

Forward Lists elementer kan ikke nås ved hjelp av indekser som matriser eller vektorer. Vi må gå gjennom listen sekvensielt fra starten til ønsket posisjon for å få tilgang til den. Dette kan gjøres ved å øke begynne() iterator, men det er bedre å bruke Neste () eller avansere() funksjon.

Imidlertid kan det første elementet på listen enkelt få tilgang til front() metode.

Eksempel:

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

Produksjon

1 3

Eksempel: I programmet ovenfor skrives det første elementet ved bruk av front() metode. For å få tilgang til det tredje elementet Neste () brukes til å flytte iteratoren to posisjoner fra begynnelsen og *den brukes til å henvise iteratoren.

2. Sett inn elementer

Elementer kan settes inn i fremoverlisten ved hjelp av insert_after () funksjon. Det krever iterator som elementet skal settes inn. Imidlertid støttes rask innsetting foran push_front () metode.

Eksempel:

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

Produksjon

1 5 3 4

Forklaring: I dette programmet settes det første elementet i Forward_list push_front () funksjon. Deretter opprettes en iterator og flyttet en posisjon fremover ved hjelp av avansere() funksjon. Etter det elementet 5 settes inn etter det andre elementet ved hjelp av insert_after () funksjon.

3. Oppdatering av elementer

Verdien av eksisterende elementer kan endres ganske enkelt ved å få tilgang til dem og bruke Oppdragsoperatør for å tilordne den nye verdien.

Eksempel:

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

Produksjon

111 333

4. Finne element

Fremoverlisten gir ingen medlemsfunksjon for å søke etter et element, men vi kan bruke finne() algoritme for å finne en gitt verdi.

Eksempel :

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

Produksjon

5. Traversing

En fremoverliste kan krysses ved hjelp av begynne() og slutt() Iteratorer med en sløyfe, men vi kan bare bevege oss fremover og ikke bakover.

Eksempel:

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

Produksjon

1 5 3 4

6. Slette elementer

I fremoverliste kan vi slette elementet i den gitte posisjonen ved hjelp av erase_after () metode. Denne metoden tar iteratoren til en posisjon før målelementet. Rask sletting fra fronten er mulig ved bruk av POP_FRONT () metode.

Eksempel:

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

Produksjon

5 3

7. Størrelse på fremoverliste

Forward_list har ikke en innebygd størrelse () -funksjon. For å finne størrelsen må vi manuelt telle elementene ved å krysse den med en sløyfe eller bruke STD :: avstand.

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

Produksjon

Size of forward_list: 4

8. tom ()

Det brukes til å sjekke om fremover_listen er tom.
Det returnerer sant hvis listen er tom og usant, ellers tillater å raskt bekrefte om beholderen ikke har noen 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  ;   }

Produksjon

The forward_list is empty. The forward_list is not empty.

Tidskompleksitet

Tabellen nedenfor viser tidskompleksiteten til ovennevnte operasjoner på fremoverliste:

Operasjon	Tidskompleksitet
Få tilgang til det første elementet	O (1)
Tilgang n ^th element	På)
Sett inn foran	O (1)
Sett inn etter spesifikk stilling	På)
Slett første element	O (1)
Slett etter spesifikk stilling	På)
Traversal	På)

Fremover liste vs liste

Trekk	Forward_list	liste
Type koblet liste	Enkelt koblet liste	Dobbeltkoblet liste
Traversal	Kan bare krysse fremover	Kan krysse både fremover og bakover
Minnebruk	Bruker mindre minne (bare en peker per node)	Bruker mer minne (to pekere per node)
Innsetting/sletting	Rask innsetting og sletting, men bare på eller etter en gitt stilling	Rask innsetting og sletting hvor som helst (før eller etter en stilling)
Funksjoner støttet	Begrenset sammenlignet med liste (ingen størrelse () ingen omvendte iteratorer)	Mer komplett grensesnitt inkludert størrelse () reverse () toveis iteratorer.