Kontenery sekwencyjne

Kontenery sekwencyjne
elementy są przechowywane w kolejności, w której zostały wstawione.

array<T, size_t>

  • tablica o stałym rozmiarze (fixed size array).
  • adaptuje dla statycznej tablicy pełny interfejs kontenera wymagany przez standard
  • szybki dostęp do dowolnego elementu
  • plik nagłówkowy: <array>

vector<T>

  • podobny do tablicy
  • może się rozrastać w zależności od potrzeb
  • szybkie dodawanie i usuwanie możliwe jedynie na końcu pojemnika
  • szybki dostęp do dowolnego elementu
  • plik nagłówkowy: <vector>

deque<T>

  • kolejka o dwóch końcach
  • szybkie dodawanie z początku i końca
  • szybki dostęp do poszczególnych elementów
  • plik nagłówkowy: <deque>

list<T>

  • szybkie wstawianie i usuwanie elementów
  • brak dostępu do dowolnego elementu na liście
  • plik nagłówkowy: <list>

std::array

std::array<T, N> implementuje tablicę o stałym rozmiarze (fixed size array). Spełnia (prawie) wszystkie wymagania dla kontenera przez co jest dużo wygodniejsza w użyciu niż tablica typu C-style.

Plik nagłówkowy <array>

namespace std
{
    template <typename T, size_t Size>
    struct array
    {
        T _Elems[Size];

        using value_type = T;
        using size_type = size_t;
        using difference_type = ptrdiff_t;
        using pointer = T *;
        using const_pointer = const T *;
        using reference = T&;
        using const_reference = const T&;

        using iterator = _Array_iterator<_Ty, _Size>;
        using const_iterator = _Array_const_iterator<_Ty, _Size>;

        using reverse_iterator = _STD reverse_iterator<iterator>;
        using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

        constexpr reference operator[](size_type pos) noexcept
        {
            return _Elems[pos];
        }

        constexpr iterator begin() noexcept
        {   // return iterator for beginning of mutable sequence
            return (iterator(_Elems, 0));
        }


        constexpr iterator end() noexcept
        {   // return iterator for end of mutable sequence
            return (iterator(_Elems, _Size));
        }

        //... rest of implementation
    };
}

Inicjalizacja

Ponieważ std::array jest agregatem, możliwa jest inicjalizacja agregatowa.

Jest też jedynym kontenerem standardowym, którego elementy są inicjalizowane w sposób domyślny (default initialized).

std::array<int, 4> a; // items of a have undefined value

std::array<int, 4> arr1 = { {} }; // { 0, 0, 0, 0 }
std::array<int, 4> arr2 = { { 1, 2 } }; // { 1, 2, 0, 0 }
std::array<int, 4> arr3 = { { 1, 2, 3, 4 } }; // { 1, 2, 3, 4 };
std::array<int, 6> arr4 = { 1, 2, 3, 4, 5, 6 }; // possible warning

Od C++17 można w celu inicjalizacji wykorzystać mechanizm dedukcji parametrów klasy szablonowej:

std::array arr = { 1, 2, 3, 4, 5, 6 }; // std::array<int, 6>

static_assert(arr.size() == 6);
static_assert(is_same_v<decltype(arr)::value_type, int>);

for(const auto& item : arr)
    std::cout << item << ' ';
std::cout << '\n';

Zwracanie tablicy z funkcji

Jedną z zalet tablic std::array jest to, że można je zwracać z funkcji:

auto cross_product(const std::array<int, 3>& a, const std::array<int, 3>& b) -> std::array<int, 3>
{
    return {{
        a[1] * b[2] - a[2] * b[1],
        a[2] * b[0] - a[0] * b[2],
        a[0] * b[1] - a[1] * b[0],
    }};
}

Interoperacyjność z tablicami C

Metoda data() zwraca wskaźnik do typu danych przechowywanych w tablicy. Umożliwia to współpracę z kodem używającym klasycznych tablic C.

namespace LegacyCode
{
    void use_tab(int* tab, size_t size)
    {
        cout << "using tab: ";
        for (int* it = tab; it != tab + size; ++it)
            cout << *it << " ";
        cout << '\n';
    }
}

std::array arr1 = { 1, 2, 3, 4, 5 };
LegacyCode::use_tab(arr.data(), arr.size());

Można wykorzystać std::array<char> jako bufor dla C-string’ów:

std::array<char,255> cstr;           // create static array of 41 chars

strcpy(cstr.data(),"hello, world"); // copy a C-string into the array
printf("%s\n", cstr.data());        // print contents of the array as C-string

Zamiana danych - swap

Metoda swap() umożliwia wymianę danych w tablicach tego samego typu. Złożoność tej operacji jest liniowa.

std::array<int, 4> arr1 = { { 1, 2, -1, 4} };
std::array<int, 4> arr2 = { {} };

utils::print(arr1, "arr1: ");
utils::print(arr2, "arr2: ");

arr1.swap(arr2);

cout << "\nAfter swap:\n";
utils::print(arr1, "arr1: ");
utils::print(arr2, "arr2: ");

arr1: [ 1 2 -1 4 ]
arr2: [ 0 0 0 0 ]
Swap:
arr1: [ 0 0 0 0 ]
arr2: [ 1 2 -1 4 ]

Interfejs krotki

Dla typu std::array zaimplementowany jest interfejs krotki (tuple interface). W rezultacie można traktować obiekty tablic jako homogeniczne krotki.

using ArrayAsTuple = std::array<int, 4>;

ArrayAsTuple t = { { 1, 2, 3, 4 } };
static_assert(std::tuple_size<ArrayAsTuple>::value == 4);
static_assert(std::is_same_v<std::tuple_element<1, ArrayAsTuple>::type, int>);
assert(std::get<1>(t) == 2);

Structured bindings (C++17)

Od C++17 std::array może być dekomponowane do zmiennych za pomocą mechanizmu structured bindings:

array coord = { { 1, 2, 3 } };

auto [x, y, z] = coord;

assert(x == 1);
assert(y == 2);
assert(z == 3);

std::vector

  • Plik nagłówkowy <vector>
  • Rozmiar może być ustalany w czasie wykonania programu
  • Elementy przechowywane są w sposób ciągły w pamięci
  • Może się rozrastać w zależności od potrzeb
  • Szybkie dodawanie i usuwanie jedynie na końcu (stała zamortyzowana złożoność czasowa)
  • Liniowa złożoność operacji wstawiania i usuwania elementów z dowolnego innego miejsca
  • Bardzo szybki dostęp do n-tego elementu zapisanego w wektorze - implementuje iterator o dostępie swobodnym

std::vector - szablon

Szablon

namespace std
{
    template <
        class T,
        class Allocator = std::allocator<T>
    > class vector
    {
        //...
    };
}

std::vector - konstruktory

Konstruktory - std::vector

vector::vector()

Tworzy pusty wektor

vector::vector(const vector &vec)

Tworzy wektor i kopiuje do niego wszystkie elementy z kontenera vec

vector::vector(vector &&vec)

Tworzy wektor i przenosi do niego wszystkie elementy z kontenera vec

vector::vector(sizeType n, const valueType &x)

Tworzy kontener posiadający n kopii elementu x

vector::vector(InIter first, Inlter last)

Tworzy kontener z elementami skopiowanymi z zakresu [first,last) określonego przez iteratory wejściowe first i last

std::vector<int> vec_int;
std::vector<std::string> vec_str(10, "item"s);
std::vector<double> vec_dbl = { 3.14, 1.15, 7.66, 6.65 };

std::vector<int> vec_int_backup(vec_int);
std::vector<std::string> vec_str_backup(vec_str.begin(), vec_str.end());

Ostrzeżenie

Należy uważać na wywołania konstruktorów za pomocą nawiasów klamrowych.

vector<int> vec1(4, 1); // vec1 contains { 1, 1, 1, 1 }
vector<int> vec2{4, 1}; // vec2 contains { 4, 1 }

Inicjalizacja w C++17

Od C++17 można inicjalizować wektor w prostszy sposób wykorzystując mechanizm dedukcji typów dla argumentów klas szablonowych:

std::vector vec = { 1, 2, 3, 4 };

std::array arr = { 1, 2, 3, 4, 5 };

std::vector backup(begin(arr), end(arr)); // deduction of T from pair of iterators

std::vector - metody dostępu

Metody dostępowe wektora:

reference vector::front()

zwraca pierwszy element wektora

reference vector::back()

zwraca ostatni element wektora

reference vector::operator[](sizeType n)

zwraca element o indeksie n

reference vector::at(sizeType n)

zwraca element o indeksie n - rzuca wyjątki std::out_of_range gdy n>=size()

Rozmiar, pojemność, maksymalny rozmiar

sizeType vector::size() const

zwraca liczbę elementów znajdujących się w kontenerze

sizeType vector::capacity() const

zwraca maksymalną liczbę elementów, które można zapisać w kontenerze bez zmiany jego rozmiaru

sizeType vector::max_size() const

zwraca maksymalną liczbę elementów, które można zapisać w kontenerze

bool vector::empty() const

jeżeli kontener jest pusty zwraca true

Przykład

std::vector<int> vec_int(3, 0);
vec_int[0] = 1;
vec_int.at(1) = 2;
vec_int[2] = 3;

std::cout << vec_int.front() << '\n';

try
{
    vec_int.at(300) = 2;
}
catch (const std::out_of_range& e)
{
    std::cerr << "out_of_range: " << e.what() << std::endl;
}

std::vector - iteratory

_images/vector_iterators_.svg

Metody zwracające iteratory

const_iterator vector::begin() const
iterator vector::begin()
const_iterator vector::cbegin() const

zwraca iterator wskazujący na pierwszy element

iterator vector::end()
const_iterator vector::end() const
const_iterator vector::cend() const

zwraca iterator wskazujący na pozycję znajdującą się z ostatnim elementem zapisanym w kontenerze

reverse_iterator vector::rbegin()
const_reverse_iterator vector::rbegin() const
const_reverse_iterator vector::crbegin() const

zwraca wsteczny iterator wskazujący na ostatni element kontenera

reverse_iterator vector::rend()
const_reverse_iterator vector::rend() const
const_reverse_iterator vector::crend() const

zwraca wsteczny iterator wskazujący na pozycję poprzedzającą pierwszy element wektora

Przykład

#include <vector>
using namespace std;
...
vector<int> vec_int(10);

for (auto cit = vec_int.cbegin(); cit != vec_int.cend(); ++cit)
    cout << *cit << endl;

int count = 0;
for (auto it = vec_int.begin(); it != vec_int.end(); ++it)
    *it = ++count;

std::vector - wstawianie elementów

Do wektora można wstawiać elementy za pomocą następujących metod:

void vector::push_back(const T &elem)

wstawia na koniec wektora kopię wartości elementu elem.

void vector::push_back(T &&elem)

wstawia na koniec wektora przenosząc wartość elementu elem.

iterator vector::insert(iterator pos, const T &elem)

wartość elementu elem zostaje wstawiona do wektora przed pozycją wskazywaną przez pos

iterator vector::insert(iterator pos, T &&elem)

wartość elementu elem zostaje przeniesiona do wektora przed pozycją wskazywaną przez pos

iterator vector::insert(iterator pos, InputIt first, InputIt last)

wstawia do kontenera elementy z zakresu [first; last) przed pozycją pos

iterator vector::insert(iterator, initializer_list<T> il)

wstawia elementy z listy inicjalizacyjnej przed pozycją pos

std::vector<int> v;

v.push_back(1);
v.push_back(2);
v.insert(v.begin(), 0)
v.insert(v.end(), {3, 4, 5});

// v -> 0, 1, 2, 3, 4, 5

Operacje emplace

Od wersji C++11 istnieją nowe metody:

reference vector::emplace_back(Args&&... args)

wstawia na koniec obiekt skonstruowany „w miejscu” (in-place). Konstruktor elementu jest wywoływany z użyciem argumentów args.

iterator vector::emplace(const_iterator pos, Args&&... args)

wstawia przed pozycją pos obiekt skonstruowany „w miejscu” (in-place). Konstruktor elementu jest wywoływany z użyciem argumentów args.

using namespace std;

struct Person
{
    string name;
    string surname;

    bool operator==(const Person& p) const
    {
        return std::tie(name, surname) == std::tie(p.name, p.surname);
    }
};

int main()
{
    std::vector<Person> staff;
    auto& person = staff.emplace_back("Jan", "Nowak");

    assert(person == staff.front());
}

std::vector - usuwanie elementów

Operacje erase() umożliwiają usuwanie elementów z wektora:

iterator vector::erase(iterator pos)

usuwa element wskazywany przez pos.

Iterator pos musi być prawidłowy i dereferencjowalny -> iterator zwracany przez end() nie może być w tym przypadku użyty

iterator vector::erase(iterator first, iterator last)

usuwa elementy w zakresie wskazywanym przez [first, last)

W obu przypadkach zwracany jest iterator wskazujący na następną pozycję po ostatnim usuniętym elemencie.

std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8 };

vec.erase(begin(vec) + 2, begin(vec) + 5);

// in vec after erase { 1, 2, 6, 7, 8 }

std::vector - ważność iteratorów

Wstawienie lub usunięcie elementów powoduje unieważnienie referencji, wskaźników oraz iteratorów odnoszących się do elementów następnych.

Jeśli wstawienie powoduje realokację unieważniane są wszystkie referencje, wskaźniki oraz iteratory odnoszące się do elementów kontenera.

Przykład nieprawidłowego kodu:

std::vector vec = { 1, 4, 5, 4, 2, 3, 4, 1 };

auto end = vec.end();
for (auto it = vec.begin(); it != end; ++it)
{
    if (*it == 4)
        v.erase(it); // WRONG!

}

Użycie funkcji reserve() jeśli spowoduje realokację także unieważnia wszystkie referencje, wskaźniki oraz iteratory odnoszące się do elementów kontenera

std::vector<string> words = { "hello", "stl", "!" };

std::string* ps = &words[0];

std::string& rs = words.back();

auto it = words.begin();
++it;

words.reserve(255); // reallocation

std::cout << *ps << " " << rs << " " << *it << '\n'; // undefined behavior

Efektywne stosowanie wektorów

Kontener typu std::vector to ciągły bufor pamięci (tablica) o rozmiarze odpowiednim do przechowywania n obiektów typu T.

Klasa std::vector posiada mechanizmy automatycznego zarządzania pamięcią bufora

  • metody służące do wstawiania oraz usuwania elementów
  • metody udostępniające zestaw metadanych o stanie kontenera
    • size()
    • capacity()
    • max_size()
_images/vector_inserting_.svg

Obiekt klasy vector potrafi automatycznie powiększać swoją pojemność. Algorytm rozrostu rozmiaru bufora jest zależny od implementacji. Zwykle bufor o n elementach jest zastępowany buforem o rozmiarze 2n

Procedura rozciągania bufora kontenera przedstawia się następująco:

  1. Przydział pamięci dla nowego bufora
  2. Skopiowanie (lub przeniesienie) elementów z starego do nowego bufora
  3. Zwolnienie dotychczasowego bufora

Rezerwacja pamięci dla bufora danych

Realokacja bufora w wektorze jest operacją czasochłonną. Należy się przed tym chronić rezerwując z góry bufor odpowiednio duży do planowanego rozmiaru kontenera.

std::vector<std::string> vec; // empty vec (size & capacity == 0)
vec.reserve(100);

for(int i = 0; i < 100; ++i)
    vec.push_back(std::to_string(i)); // efficient push_backs

Efektywne usuwanie elementów

Usunięcie elementu ze środka kontenera ma złożoność liniową.

vector<int> vec = { 1, 2, 3, 4, 6, 7, 8, 9, 10 };

vec.erase(begin(vec) + 2);

Jeśli nie zależy nam na zachowaniu porządku elementów w wektorze możemy zastosować wydajniejszy idiom:

template<typename T>
void efficient_erase(std::vector<T>& vec, std::vector<T>::iterator pos)
{
    std::swap(*pos, vec.back());
    vec.pop_back();
}

efficient_erase(vec, begin(vec) + 2);

Przechowywanie wskaźników w wektorze

W kontenerach standardowych mogą być przechowywane smart-pointer’y.

class Gadget { /*...*/ };

vector<unique_ptr<Gadget>> gadgets;

auto g = make_unique<Gadget>(6, "mp3 player");

gadgets.push_back(make_unique<Gadget>(1, "ipad")); // C++14
gadgets.push_back(move(g));
gadgets.emplace_back(make_unique<Gadget>(4, "smartphone"));

// caution!!!
gadgets.emplace_back(new Gadget{4, "smartphone"}); // may leak in C++11

gadgets.clear(); // deleting all gadgets stored in the vector

Kopiowanie wektora

Kopiowanie wektorów można wykonać na dwa sposoby:

  1. konstruując obiekt kontenera vector jako kopię innego kontenera tego typu - konstruktor kopiujący
  2. wywołując na rzecz istniejącego kontenera metodę assign()
string words[] = { "Szkolenie", "ze", "Standard",  "Template", "Library" };

vector<string> vec1(words, words + 5);
vector<string> vec2(vec1);
vector vec3(vec1); // since C++17


vec1.assign(vec3.rbegin(), vec3.rend());

Zamiana danych w wektorach

Efektywna zamiana danych między dwoma wektorami tego samego typu jest możliwa dzięki operacji swap()

std::vector<int> vec1 = { 1, 2, 3, 4, 5, 6, 7, 8 };
std::vector<int> vec2 = { 9, 10 };

vec1.swap(vec2); // zamiana danych w wektorach

Idiom zmniejszania bufora danych w wektorze wymaga użycia metody swap()

std::vector<int> vec(1000);
vec.erase(begin(vec) + 50, end(vec));

std::vector<int> temp(vec);
temp.swap(vec);

// krócej z wykorzystaniem obiektu tymczasowego
std::vector<int>(vec).swap(vec);

W C++11 możliwa jest zmiana wielkości zarezerwowanej przez wektor pamięci przy pomocy funkcji shrink_to_fit().

vec.shrink_to_fit(); // reallocation if necessary

Obsługa wyjątków

Jedyną funkcją, od której standard wymaga zgłaszania wyjątków, jest metoda at()

Jeśli funkcja wywołana przez wektor zgłasza wyjątki gwarantowane jest:

  • Jeśli za pomocą push_back() wstawiany jest element i wystąpi wyjątek, funkcja ta nie spowoduje żadnego skutku
  • Jeśli operacje kopiowania elementów nie zgłaszają wyjątków, funkcja insert() albo kończy się powodzeniem, albo nie powoduje żadnego skutku
  • Funkcja pop_back() nie zgłasza żadnych wyjątków
  • Funkcja swap() nie zgłasza żadnych wyjątków*
  • Jeśli używane są typy POD, każda operacja kończy się powodzeniem, albo nie powoduje żadnego skutku
  • Funkcje erase() oraz clear() nie zgłaszają wyjątków, jeśli operacje kopiowania nie zgłaszają wyjątków.

std::vector<bool>

Specjalizowana klasa przechowująca w wektorze wartości logiczne w postaci bitowej.

Posiada rozszerzony interfejs - operację flip()

std::vector<bool> vec_bool(7);
vec_bool[1] = true;
vec_bool[4] = true;

vec_bool.push_back(true);

std::copy(vec_bool.begin(), vec_bool.end(), std::ostream_iterator<int>(std::cout, " ") );
std::cout << '\n';

vec_bool[0].flip();
vec_bool.flip();

Problemy z typem vector<bool>

  1. nie jest poprawnym kontenerem STL - nie spełnia wymagań zdefiniowanych przez standard

    std::vector<int> vec = { 1, 2, 3 };
int* p = &c[0];

vector<bool> v(8);
bool* pb = &v[0]; // compilation error

  2. operator indeksowania nie zwraca typu referencyjnego (bool&) - zwraca tymczasowe obiekty proxy

    template <typename Allocator>
class std::vector<bool, Allocator>
{
public:
    class reference { /*....*/ };
    reference operator[](size_type n);
};

    W rezultacie aby iterować pętlą range-based-for po kontenerze z zamiarem zmiany elementów, należy użyć deklaracji auto&&:

    std::vector<bool> bits = { 0, 1, 1, 1, 0, 0, 0, 1 };

for(auto&& bit : bits)
{
    bit.flip();
    cout << bit;
}
cout << '\n';

std::deque

deque [„deck”] = double-ended queue - kolejka dwukierunkowa

namespace std
{
    template<
        class T,
        class Allocator = std::allocator<T>
    > class deque
    {
        //...
    };
}
  • Plik nagłówkowy: <deque>
  • Wstawianie elementów jest efektywne zarówno na początku jak i na końcu kontenera
  • Posiada operator []
  • Struktura wewnętrzna wprowadza dodatkowy etap pośredni w dostępie do elementów - operacje dostępu do elementów i ruchu iteratora są zwykle wolniejsze
  • Iteratory są inteligentnymi wskaźnikami nawigującymi po segmentach pamięci
  • Kontener deque nie oferuje możliwości sterowania pojemnością ani momentem realokacji
  • Bloki pamięci mogą zostać automatycznie zwolnione, gdy nie są już wykorzystywane

std::deque - operacje na końcach kolejki

Operacje wstawiania i usuwania na końcach kolejki

void deque::push_front(const valueType &x)

wstawianie na początek

void deque::pop_front()

usunięcie z początku

void deque::push_back(const valueType &x)

wstawianie na koniec

void deque::pop_back()

usunięcie ostatniego elementu

Podobnie jak wektor, od wersji C++11 mamy nowe metody wykorzystujące tworzenie obiektów „w miejscu”:

reference deque::emplace_back(Args &&args)
reference deque::emplace_front(Args &&args)
iterator deque::emplace(const_iterator pos, Args &&args)

wstawiają elementy przekazując do konstruktora typu argumenty args

std::deque<std::string> coll = { "middle" };

coll.push_back("last");
coll.emplace_back('!', 3);

coll.push_front("first");
coll.emplace_front('>', 3);

coll.emplace(coll.begin() + 2, '-', 3);

// coll { ">>>", "first", "---", "last", "!!!" }

coll.pop_back();
coll.pop_front();

// coll { "first", "---", "last" }

std::deque - ważność iteratorów

  • Operacje wstawiania na końcach kolejki - push_front(), push_back(), emplace_back(), emplace_front()
    • wszystkie związane z nią iteratory tracą ważność, natomiast wszystkie wskaźniki i referencje na elementy kolejki nie tracą ważności
  • Operacje wstawiania w środku - insert(), emplace()
    • unieważniają wszystkie iteratory i referencje (wskaźniki) do elementów kontenera
  • Operacje usuwania ostatniego elementu - pop_back()
    • tracą ważność iterator past-the-end oraz iterator i referencje do usuwanego elementu
  • Operacja usuwania pierwszego (ale nie ostatniego) elementu - pop_front()
    • unieważnia iteratory i referencje do usuwanego elementu
  • Operacja usuwania ze środka deque’a - erase()
    • unieważnia wszystkie iteratory i referencje (wskaźniki) do elementów kontenera

std::list

  • Jest kontenerem zoptymalizowanym do wstawiania lub usuwania elementów (stały czas)
  • Posiada liniową złożoność obliczeniową znalezienia n-tego elementów
  • Lista zapewnia iteratory dwukierunkowe.
  • Plik nagłówkowy: <list>
    • brak iteratorów o dostępie swobodnym.
  • Zaimplementowana została w postaci podwójnie łączonej listy (dwukierunkowej)
_images/list_.svg

Definicja:

namespace std
{
    template <
        typename T,
        typename Allocator = std::allocator<T>
    > class list
    {
        //...
    };
}

std::list - wstawianie i usuwanie elementów

Elementy można dodawać następującymi metodami:

void list::push_back(const valueType &x)

wstawia x jako ostatni element w kontenerze

void list::push_front(const valueType &x)

wstawia x jako pierwszy element w kontenerze

iterator list::insert(iterator pos, const valueType &x)

wstawia x przed element p i zwraca iterator wskazujący na x

iterator list::erase(iterator p)

usuwa element wskazywany przez pos i zwraca iterator do elementu następnego (po usuniętym)

Podobnie jak wektor, od wersji C++11 mamy nowe metody wykorzystujące tworzenie obiektów „w miejscu”:

reference list::emplace_back(Args &&args)
reference list::emplace_front(Args &&args)
iterator list::emplace(const_iterator pos, Args &&args)

wstawiają elementy przekazując do konstruktora typu argumenty args

std::list<std::string> lst = { "..." };
lst.push_back("C++");
lst.push_front("Szkolenie");

auto pos = find(lst.begin(). lst.end(), "C++");
pos = lst.erase(pos);
lst.insert(pos, { "z", "programowania", "w" });

std::list - ważność iteratorów

Operacje wstawiania i usuwania elementów nie powodują unieważnienia wskaźników, referencji ani iteratorów do innych elementów. Unieważniane są iteratory, referencje i wskaźniki do usuwanych elementów.

std::list - odporność na wyjątki

Lista realizuje obsługę wyjątków w taki sposób, że niemal każda operacja kończy się powodzeniem, albo nie powoduje zmiany stanu kontenera. Nie jest zatem możliwe wystąpienie stanu pośredniego, w którym zakończona zostałaby tylko połowa operacji.

Lista oferuje najlepsze gwarancje bezpieczeństwa w przypadku zgłaszania sytuacji wyjątkowych.

std::list - metody specjalne

Zawiera metody zoptymalizowane pod kątem operacji na liście dwukierunkowej

void list::sort()

Sortuje elementy przechowywane na liście

void list::merge(list<T> &lst)

Łączy aktualną posortowaną listę z inną, również posortowaną listą. Elementy z listy x są usuwane (po wyjściu z funkcji lista lst jest pusta)

void list::reverse()

Odwraca kolejność elementów na liście

void list::unique()

Usuwa z listy sąsiadujące ze sobą duplikaty elementów

void list::remove(const T &value)

Usuwa z listy wszystkie wystąpienia podanej wartości

void list::remove_if(Predicate pred)

Usuwa wszystkie elementy, dla których wywołanie pred(item) zwraca true

void list::splice(Iterator where, list &lst)

Przenosi wszystkie elementy kontenera lst do kontenera *this na rzecz którego została wywołana metoda i umieszcza je przed pozycją iteratora where. Żaden z elementów nie jest kopiowany lub przenoszony (przepinane są węzły).

void list::splice(Iterator where, list &lst, const_iterator it)

Przenosi węzeł wskazywany iteratorem it do listy *this. Węzeł jest wpinany przed elementem wskazywanym iteratorem it

void list::splice(Iterator where, list &lst, const_iterator first, const_iterator last)

Przenosi węzły z zakresu [first, last) listy ``lst do listy *this. Węzły są wpinane przed elementem wskazywanym iteratorem it

Przykład

list<string> lst_1 = { 5, 2, 5, 1, 7 };
list<string> lst_2 = {3, 5, 8, 2, 23, 5 };

// sorting
lst_1.sort();
lst_2.sort();

// merging sorted lists
lst_1.merge(lst_2); // lst_1 = { 1, 2, 2, 3, 5, 5, 5, 5, 7, 8, 23 }
assert(lst_2.size() == 0);

// removing elements
lst_1.remove(5); // lst_1 = { 1, 2, 2, 3, 7, 8, 23 }

// moving nodes between lists
list<int> lst_3 = { 101, 202 };
lst_3.splice(lst_3.begin(), lst_1); // lst3 = { 1, 2, 2, 3, 7, 8, 23, 101, 202 }
assert(lst_1.size() == 0);