Forward_list Containerul oferă implementarea Lista singuri legată Structura de date. Stochează date în memorie necontigue, unde fiecare element indică următorul element din secvență. Acest lucru face ca introducerea și ștergerea mai rapidă odată ce poziția elementului este cunoscută.

Sintaxă

Lista de înaintare este definită ca STD :: Forward_list șablon de clasă în interiorul< Forward_list > Fișier antet.

Forward_listFL;

unde

• T: Tipul de date de elemente din lista înainte.
• F: Numele atribuit listei de înaintare.

Declarație și inițializare

O listă forward_ poate fi declarată și inițializată în mai multe moduri, așa cum se arată în exemplul de mai jos:

#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 

Exemplu: În programul de mai sus, suntem simpli lista inițializată inițial în trei moduri:

• Declaraţie Forward_list FL1 Creează o listă goală de numere întregi.
• Declaraţie Forward_list FL2 (34) Creează o listă înainte cu dimensiunea 3 și fiecare element fiind 4.
• Declaraţie Forward_list fl3 = {1 5 3 4} Creează o listă înainte și inițializează cu elementele formează lista inițializantă.

Operații de bază

Iată operațiunile de bază pe care le putem efectua pe o listă înainte:

1. Accesarea elementelor

Elementele listei înainte nu pot fi accesate folosind indici precum tablouri sau vectori. Trebuie să parcurgem secvențial lista de la început până la poziția dorită pentru a o accesa. Acest lucru se poate face prin creșterea ÎNCEPE() iterator, dar este mai bine să folosești Următorul() sau avans() funcţie.

Cu toate acestea, primul element al listei poate fi accesat cu ușurință faţă() metodă.

Exemplu:

#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

Exemplu: În programul de mai sus, primul element este tipărit folosind faţă() metodă. Pentru a accesa al treilea element Următorul() se folosește pentru a muta iteratorul două poziții de la început și *it este folosit pentru a dereferenta iteratorul.

2. Introducerea elementelor

Elementele pot fi introduse în lista înainte folosind insert_after () funcţie. Necesită iteratorul după care elementul trebuie introdus. Oricât de rapidă este susținută inserția rapidă în față push_front () metodă.

Exemplu:

#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 

Explicaţie: În acest program, primul element al listei forward_list este introdus în față folosind push_front () funcţie. Apoi un iterator este creat și mutat o poziție înainte folosind avans() funcţie. După aceea elementul 5 este introdus după al doilea element folosind insert_after () funcţie.

3. Actualizarea elementelor

Valoarea elementelor existente poate fi modificată pur și simplu prin accesarea acestora și folosind operator de atribuire Pentru a atribui noua valoare.

Exemplu:

logica de transfer de înregistrări

#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 de găsire

Lista de înaintare nu oferă nicio funcție de membru pentru a căuta un element, dar putem folosi găsi() algoritm pentru a găsi orice valoare dată.

Exemplu :

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

O listă înainte poate fi traversată folosind ÎNCEPE() şi Sfârşit() Iteratoare cu o buclă, dar putem merge doar înainte și nu înapoi.

Exemplu:

#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. Ștergerea elementelor

În lista înainte putem șterge elementul în poziția dată folosind erase_after () metodă. Această metodă duce iteratorul într -o poziție înainte de elementul țintă. Ștergerea rapidă din față este posibilă folosind pop_front () metodă.

Exemplu:

#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. Mărimea listei înainte

Forward_list nu are o funcție de mărime () încorporată. Pentru a -și găsi dimensiunea, trebuie să numărăm manual elementele traversând -o cu o buclă sau folosind distanța std ::.

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

Este folosit pentru a verifica dacă lista înainte_ este goală.
Returnează adevărat dacă lista este goală și falsă, altfel, permițând să verifice rapid dacă containerul nu are date.

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

Complexitatea timpului

Tabelul de mai jos listează complexitatea de timp a operațiunilor de mai sus pe lista înainte:

Lista de avansare vs lista