C++11 lista jednokierunkowa - std::forward_list

Nowy standard dostarczył nam jedną z podstawowych struktur danych, czyli listę jednokierunkową. Przydatne linki:

• http://www.cplusplus.com/reference/forward_list/forward_list/
• http://en.cppreference.com/w/cpp/container/forward_list

W założeniu taka struktura ma umożliwiać szybkie wstawianie i usuwanie elementów, zajmuje też mniej pamięci niż standardowa lista (tylko jeden iterator - na element następny). Ciekawe jak by wypadła w konfrontacji z wektorem. Może kiedyś przeprowadzę test.

#include <iostream>
#include <forward_list>

int main()
{
    std::forward_list<int> f {3, 4, 5, 1, 2, 7, 9};

    std::forward_list<int>::iterator pos = f.before_begin();
    f.insert_after(pos, 404);

    for (std::forward_list<int>::iterator it = f.begin(); it != f.end(); ++it)
        std::cout << *it << " ";
    return 0;
}

Wyniki:

404 3 4 5 1 2 7 9

Lista jednokierunkowa posiada specjalne wersje metod (insert_after(), emplace_after(), erase_after()), operujących na iteratorach. Według konwencji np. insert(), powinno wstawiać element, przed danym iteratorem, ponieważ w liście jednokierunkowej jest to niemożliwe (bo nie mamy dostępu do elementu poprzedniego by w nim poprawić iterator next) biblioteka dostarcza metody insert_after().