forward list library

forward list library (tsz. forward list libraries)

1. (informatika) (forward list = singly linked list)

Az std::forward_list a C++11 óta elérhető, könnyű és hatékony egyelemű (singly-linked) lista-konténer. Elsődleges célja az alacsony memóriahasználat és a folyamatos, előre irányuló bejárás biztosítása. A következőkben részletesen bemutatjuk struktúráját, főbb műveleteit, komplexitását, összehasonlítását más STL-konténerekkel, tipikus felhasználási területeit, valamint néhány gyakorlati példát és jó tanácsot.

• Egyelemű láncolt lista: minden elem csak a következőre mutat (next), előzőre nem.
• Fejlesztés oka: az előd std::list (kétirányú láncolt lista) funkcionalitásának egyszerűsítése, memória- és időhatékonyság növelése.
• Helye az STL-ben: <forward_list> fejléc, a konténer része a <list>-hez hasonló láncolt tárolóknak.

#include <forward_list>
#include <iostream>

std::forward_list<int> fl1;                                 // üres lista
std::forward_list<int> fl2 = {1, 2, 3, 4};                  // inicializálás lista-literalből
std::forward_list<int> fl3(5, 42);                          // 5 elem, mindegyik 42
auto it = fl2.begin(); ++it;
fl2.insert_after(it, 99);                                   // beszúrás az it utáni pozícióra
fl2.erase_after(fl2.begin());                               // törlés az első elem utáni pozícióról

• begin() / cbefore_begin(): a lista kezdő előtti (saját) iterátora.
• before_begin(): iterator a fejtet előtti falcióra (insert/erase után használjuk).
• insert_after(pos, value), erase_after(pos): beszúrás/törlés a megadott elem után.
• push_front(), pop_front(): fej beszúrás/törlés (O(1)).
• empty(), size(): empty() O(1), size() nincs konstans időben (egyszerű használatkor iterál).

• Bejárás (iterálás): O(n)
• push_front, pop_front: O(1)
• insert_after, erase_after: adott pozíció után O(1)
• size(): O(n), mert nincs belső számláló
• clear(): O(n)
• merge(), splice_after(), remove(), unique(), reverse(): mindegyik O(n)

Az egyelemű láncolt szerkezet miatt a véletlenszerű hozzáférés (mint pl. operator) nem támogatott, csak sorozatos (szekvenciális) bejárásra alkalmas.

• Ha véletlenszerű indexelés kell → vector vagy deque.
• Ha gyakori beszúrás/törlés a lista közepén, és kétirányú bejárás is kell → list.
• Ha minimális memória és csak előre haladás → forward_list.

1. Stream-feldolgozás Amikor adatokat sorosan (pl. fájl- vagy hálózati stream) dolgozunk fel, és nincs szükség visszalépésre, a forward_list ideális, mert csak előre haladunk elemenként.
2. Funkcionális programozás minták Rekurzív, “immutable” jellegű algoritmusoknál előnyös, mivel másolatok készítése (másik fej beszúrása) könnyű.
3. Szabad memóriahasználat Nagy mennyiségű adatnál, ahol fontos a memóriahatékonyság (pl. beágyazott vagy memóriaérzékeny rendszerek).
4. Algoritmus-specifikus tároló Egyedi algoritmusoknál, melyek előre haladó linkelt struktúrát igényelnek (pl. lock-free, egyszerű üzenetsorok).

• merge() Összefűz két rendezett forward_list-et; in-place, konstans extra memóriaigénnyel.
• splice_after() Egy másik listából átmozgat elemeket úgy, hogy csak pointereket kötünk át: O(1) művelet, ha egyetlen elem.
• remove(), remove_if() Adott érték(ek) törlése elsődleges bejárással.
• unique() Sorozatos egyező elemek eltávolítása.
• reverse() Lista irányának megfordítása; in-place, O(n).
• sort() Nem elérhető! Egyelemű listán nincs beépített sort(). Ha kell, először másold át list-be, vagy használd külső algoritmust.

#include <forward_list>
#include <iostream>
#include <algorithm>

int main() {
    std::forward_list<int> numbers = {1, 3, 5, 7, 9};

    // push_front, pop_front
    numbers.push_front(0);  // {0,1,3,5,7,9}
    numbers.pop_front();    // {1,3,5,7,9}

    // insert_after & erase_after
    auto it = std::find(numbers.begin(), numbers.end(), 5);
    if (it != numbers.end()) {
        numbers.insert_after(it, 6);     // {1,3,5,6,7,9}
        numbers.erase_after(it);         // {1,3,5,7,9}
    }

    // remove_if: törli a páros számokat
    numbers.remove_if((int x){ return x % 2 == 0; });

    // merge: két rendezett lista összefésülése
    std::forward_list<int> evens = {2,4,6,8};
    numbers.merge(evens);

    // kiírás
    for (int x : numbers) {
        std::cout << x << ' ';
    }
    // Eredmény: 1 2 3 4 5 6 7 8 9
}

1. Csak előre haladás Ha visszalépésre vagy előző elemre hivatkozásra van szükség, válassz std::list-et!
2. Átmásolás vs. mozgatás A splice_after átmozgatja, nem másolja az elemet; ez gyorsabb, de figyelj, ha az eredeti listát még használod.
3. Előzetes kapacitás Nincs reserve(); minden beszúrás külön memóriakiosztással jár. Nagy listák esetén mérlegeld az allocator testreszabását.
4. Iterator invalidáció Beszúrás/törlés csak az adott pozíció utáni részt befolyásolja. A többi iterátor érvényes marad.
5. Rendezéshez konverzió Ha szükséged van sort()-ra, először másold át std::list-be, vagy más adatstruktúrát használj.

Az std::forward_list a C++ nyelvben egy könnyű, egyelemű láncolt lista, amely kiválóan alkalmas soros adatfeldolgozásra, memóriaérzékeny alkalmazásokra és egyszerű, előre haladó bejárást igénylő algoritmusokra. Bár kevésbé rugalmas, mint a kétirányú std::list, alacsonyabb memóriafoglalása és egyszerűbb működése miatt sok helyzetben előnyösebb. Használatakor érdemes tudatosan mérlegelni a konténer erősségeit és korlátait, hogy a legoptimálisabb megoldást választhassuk programunk számára.

• forward list library - Szótár.net (en-hu)
• forward list library - Sztaki (en-hu)
• forward list library - Merriam–Webster
• forward list library - Cambridge
• forward list library - WordNet
• forward list library - Яндекс (en-ru)
• forward list library - Google (en-hu)
• forward list library - Wikidata
• forward list library - Wikipédia (angol)