ELŐRE LISTA A C ++ STL -BEN

Előremeneti_list A Container biztosítja a Egyedül összekapcsolt lista adatszerkezet. Az adatokat nem kötött memóriában tárolja, ahol az egyes elemek a sorrend következő elemére mutatnak. Ez gyorsabbá teszi a beillesztést és a törlést, ha az elem helyzete ismert.

Szintaxis

Az előremenő lista meghatározva van STD :: Forward_list osztálysablon a < előremeneti_list > fejlécfájl.

előremeneti_list Fl;

ahol

T: Az elemek adattípusa az előző listában.
F: Az előző listához rendelt név.

Nyilatkozat és inicializálás

A Forward_list többféle módon deklarálható és inicializálható, az alábbi példában látható módon:

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

Kibocsátás

4 4 4 1 5 3 4

Példa: A fenti programban háromféle módon egyszerűen inicializált előrejelző lista:

Nyilatkozat előremeneti_list Fl1 Készít egy üres előremenő számot az egész számokról.
Nyilatkozat előremeneti_list FL2 (34) Készít egy előretekintési listát a 3. méretről, és mindegyik elem 4.
Nyilatkozat előremeneti_list fl3 = {1 5 3 4} Készít egy előretekintő listát, és inicializálja az elemekkel az inicializáló listát.

Alapvető műveletek

Itt vannak az alapvető műveletek, amelyeket az előremenő listán végezhetünk:

1. Hozzáférés az elemekhez

Az előremenő lista elemei nem érhetők el olyan indexekkel, mint tömbök vagy vektorok. A hozzáféréshez a kezdetektől kezdve át kell mennünk a listán. Ezt megteheti a növekedéssel kezdődik() iterator, de jobb használni következő() vagy előleg() funkció.

A lista első eleme azonban könnyen hozzáférhető elülső() módszer.

Példa:

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

Kibocsátás

1 3

Példa: A fenti programban az első elemet a használatával nyomtatják ki elülső() módszer. A harmadik elem eléréséhez következő() az iterátor két pozíciójának elejétől és a kezdetektől és *azt az iterátor megsemmisítésére használják.

2.

Az elemek beilleszthetők az előremeneti listába insert_after () funkció. Ez megköveteli azt az iterátort, amely után az elemet be kell helyezni. Bármennyire a fronton a gyors beillesztést támasztja alá push_front () módszer.

Példa:

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

Kibocsátás

1 5 3 4

Magyarázat: Ebben a programba a Forward_list első eleme a push_front () funkció. Ezután létrehozzák egy iterátort, és egy pozíciót előre mozgatnak a előleg() funkció. Ezután az elem 5 a második elem után behelyezik a insert_after () funkció.

3. Az elemek frissítése

A meglévő elemek értéke egyszerűen megváltoztatható a hozzáféréssel és a használatával megbízó üzemeltető az új érték hozzárendeléséhez.

Példa:

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

Kibocsátás

111 333

4. Elem megtalálása

Az előrejelző lista nem biztosít semmilyen tag funkciót egy elem kereséséhez, de használhatjuk a lelet() algoritmus az adott érték megtalálásához.

Példa :

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

Kibocsátás

5. Traversing

Az előremenő lista áthaladhat a használatával kezdődik() és vége () iterátorok hurokkal, de csak előrehaladhatunk, és nem hátra.

Példa:

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

Kibocsátás

1 5 3 4

6. Az elemek törlése

Az előző listában törölhetjük az elemet az adott helyzetben ERASE_AFTER () módszer. Ez a módszer az iterátort egy helyzetbe hozza a cél elem előtt. A gyors törlés az elülső oldalról lehetséges pop_front () módszer.

Példa:

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

Kibocsátás

5 3

7. Az előrejelző lista mérete

A FORRED_LIST nem rendelkezik beépített méret () funkcióval. A méretének megtalálásához manuálisan kell számolnunk az elemeket úgy, hogy áthaladunk egy hurokkal vagy STD :: távolság használatával.

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

Kibocsátás

Size of forward_list: 4

8. Üres ()

Arra használják, hogy ellenőrizze, hogy a Forward_list üres -e.
Igaz, ha a lista üres és hamis, egyébként lehetővé teszi, hogy gyorsan ellenőrizze, hogy a konténernek nincs -e adat.

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

Kibocsátás

The forward_list is empty. The forward_list is not empty.

Idő bonyolultság

Az alábbi táblázat felsorolja a fenti műveletek időbeli bonyolultságát az előrejelző listán:

Művelet	Idő bonyolultság
Hozzáférés az első elemhez	O (1)
Hozzáférés n ^TH elem	On)
Helyezze el az elejét	O (1)
Helyezze be meghatározott helyzet után	On)
Az első elem törlése	O (1)
Törlés meghatározott helyzet után	On)
Átjáró	On)

Forward List VS Lista

Jellemző	előremeneti_list	lista
A kapcsolódó lista típusa	Egyedül összekapcsolt lista	Kétszeresen összekapcsolt lista
Átjáró	Csak előrehaladhat	Átjárhat mind előre, mind hátra
Memóriahasználat	Kevesebb memóriát használ (csomópontonként csak egy mutatót)	Több memóriát használ (csomópontonként két mutatót)
Beillesztés/törlés	Gyors beillesztés és törlés, de csak egy adott helyzetben vagy után	Gyors beillesztés és törlés bárhol (egy pozíció előtt vagy után)
Támogatott funkciók	Korlátozott a listához képest (nincs méret () nincs fordított iterátor)	Teljesebb interfész, beleértve a méret () fordított () kétirányú iterátorokat.