CKTIS / C++
std::forward_list: jednokierunkowy kontener węzłowy
std::forward_list przechowuje jednokierunkowy łańcuch i oferuje stałoczasowe operacje po znanym poprzedniku.
Wersja: C++23
Składnia
template<class T, class Allocator = std::allocator<T>>
class std::forward_list;
// Selected operations:
iterator before_begin() noexcept;
void push_front(const T& value);
iterator insert_after(const_iterator position, const T& value);
iterator erase_after(const_iterator position);std::forward_list<T, Allocator> z <forward_list> jest sekwencyjnym kontenerem węzłowym z iteratorami postępującymi. Nie zapewnia dostępu losowego, operator[], back(), push_back() ani nawet size(). Element osiąga się, idąc od begin(), więc dotarcie do pozycji kosztuje liniowo.
Przykład tworzy 2 3, dodaje 1 z przodu, a następnie wstawia 9 po pierwszym elemencie; iteracja drukuje 1 9 2 3. before_begin() daje specjalny, niedereferencjonowalny iterator poprzedzający pierwszy węzeł, dzięki czemu insert_after, emplace_after i erase_after mogą także zmieniać początek.
Wstawienie lub usunięcie pojedynczego elementu po znanym poprzedniku ma stały koszt, podobnie jak samo przepięcie znanych końców łańcucha; warianty licznikowe i zakresowe skalują się z liczbą tworzonych, usuwanych lub przenoszonych elementów, a znalezienie poprzednika może być liniowe. Wstawianie nie unieważnia iteratorów ani referencji do istniejących elementów; usunięcie unieważnia tylko te do usuwanych elementów. Nie wolno dereferencjonować before_begin() ani end(), a erase_after(pos) wymaga istniejącego następcy. Operacje przenoszące węzły między listami, takie jak splice_after, wymagają zgodnych alokatorów zgodnie z ich warunkami wstępnymi.
Przykłady
#include <forward_list>
#include <iostream>
int main() {
std::forward_list<int> values{2, 3};
values.push_front(1);
values.insert_after(values.begin(), 9);
bool first = true;
for (int value : values) {
if (!first) std::cout << ' ';
std::cout << value;
first = false;
}
std::cout << '\n';
}
Wynik
1 9 2 3
std::forward_list → 1 9 2 3