lists stl
Dowiedz się wszystkiego o listach w STL wraz z ich wdrażaniem.
Listy są kontenerami sekwencyjnymi. Listy zawierają elementy w nieciągłych lokalizacjach. Omówiliśmy tablice i wektory w naszych poprzednich samouczkach.
W przypadku kontenerów tablicowych i wektorowych, ponieważ te kontenery przechowują dane w ciągłej pamięci, operacja wstawiania w środku tych kontenerów okazuje się bardzo kosztowna, ponieważ musimy odpowiednio przesuwać istniejące elementy, aby zrobić miejsce na nowy element.
=> Zobacz tutaj, aby zapoznać się z pełną listą samouczków C ++.
scal kod źródłowy sortowania c ++
Czego się nauczysz:
Przegląd
Lista jest kontenerem, który przezwycięża tę wadę kontenerów tablicowych i wektorowych. Pozwala nam wstawiać elementy w dowolnym miejscu na liście bez większego narzutu. Ale listy są wolniejsze niż wektory, jeśli chodzi o przemierzanie.
W tym samouczku zobaczymy implementację list w STL wraz z różnymi operacjami przechodzenia, manipulacjami i listami dostępu z przykładami.
Zauważ, że większość operacji na listach jest podobna do operacji na wektorach, a zatem czytelnicy, którzy już przeczytali nasz samouczek na temat wektorów, nie będą mieli problemów z interpretacją koncepcji list.
Deklaracja i inicjalizacja
Aby zaimplementować kontener list i wykorzystać wszystkie jego zalety, musimy dołączyć plik nagłówkowy do naszego programu.
#include Ogólna deklaracja kontenera listy to
std::list listName; Na przykład,możemy zadeklarować listę o nazwie „mylist” typu int w następujący sposób:
std::list mylist; Możemy też zainicjować listę w momencie deklaracji lub dodać do niej elementy za pomocą jednej z obsługiwanych przez nią operacji.
Zobaczmy, jak możemy zainicjować utworzoną powyżej listę.
std::list mylist = {1, 1, 2, 3, 5}; Powyższa inicjalizacja zostanie umieszczona w pamięci, jak pokazano poniżej:
Po zainicjowaniu listy możemy uzyskać dostęp do elementów listy za pomocą iteratora. Funkcje iteratora „begin” i „end” pomagają nam przechodzić przez elementy listy.
Uwaga: Iterator listy obsługuje również inne iteratory, takie jak iteratory odwrotne (rbegin, rend), iteratory stałe (cbegin, cend) i stałe iteratory odwrotne (crbegin, crend) i mogą być używane w podobny sposób jak wektory.
Poniższy przykład pokazuje to.
#include #include #include #include using namespace std; int main() { list mylist = {1, 1, 2, 3, 5}; cout<<”List elements are: “; list::iterator it; for(it=mylist.begin();it!=mylist.end();++it) cout<<*it<<” “; }Wynik:
Elementy listy to: 1 1 2 3 5
Zatem w powyższym przykładzie zadeklarowaliśmy listę ciągu Fibonacciego. Następnie deklarujemy iterator tego samego typu co lista, a następnie używając pętli for, drukujemy zawartość listy od początku do końca.
Przejdźmy teraz do operacji lub funkcji, które udostępnia nam kontener w STL.
Operacje na listach
- Wstawić: Służy do wstawiania elementu w podanej pozycji. Zwraca iterator wskazujący na pierwszy wstawiony element.
insert (pos, num_elem, elem)
Gdzie,
pos => Pozycja, w której mają zostać wstawione nowe elementy.
num_elem => Liczba elementów do wstawienia; domyślnie 1.
item => Rzeczywista wartość do wstawienia.
Zrozummy funkcję wstawiania na przykładzie.
#include #include // for list operations using namespace std; int main() { list mylist = {1,1,2}; list::iterator it = mylist.begin(); // iterator to point to 4th position advance(it,` 3); // inserts 3 at 4th position mylist.insert(it, 3); cout << 'The list after inserting' << ' 1 element using insert() is : '; for (list::iterator i = mylist.begin();i != mylist.end();i++) cout << *i << ' '; cout << endl; }Wynik:
Lista po wstawieniu 1 elementu za pomocą insert () to: 1 1 2 3
To jest przykład wstawiania tylko jednego elementu na 4thpozycja na liście, która jest ostatecznie ostatnią pozycją. Stąd najpierw mamy listę, dla której zdefiniowaliśmy iterator wskazujący na początek listy. Następnie przenosimy ten iterator do 4thpozycji, a następnie wywołaj insert, aby wstawić 1 element.
Możemy również wstawić więcej niż jeden element, podając drugi parametr w funkcji insert. Jeśli nie jest określony, przyjmuje wartość domyślną 1.
- push_back :Dodaje nowy element na końcu listy.
- push_front :Dodaje nowy element na początku listy.
Zobaczmy przykład, który demonstruje użycie funkcji push_back i push_front.
#include #include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << '
'; } int main() { std::list mylist = {1, 1, 2, 3}; cout<<'List elements are: '; printlist(mylist); mylist.push_front(0); mylist.push_back(5); cout<<'
List contents after push_front and push_back: '; printlist(mylist); }Wynik:
Elementy listy to: 1 1 2 3
Zawartość listy po push_front i push_back: 0 1 1 2 3 5
W tym przykładzie najpierw tworzymy i wyświetlamy wszystkie dwa elementy, każdy z przodu iz tyłu, używając odpowiednio funkcji push_front i push_back. Dane wyjściowe pokazują zmienioną listę po wykonaniu obu funkcji.
- pop_back :Usuwa ostatni element z listy, zmniejszając w ten sposób rozmiar listy o 1.
- pop_front :Usuwa pierwszy element z listy, zmniejszając w ten sposób rozmiar listy o 1.
Poniższy przykład pokazuje użycie operacji pop_back i pop_front na liście.
#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << '
'; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); mylist.pop_front(); mylist.pop_back(); cout<<'
List contents after push_front and push_back: '; printlist(mylist); }Wynik:
Elementy listy to: 1 1 2 3 5
Wyświetl zawartość po push_front i push_back: 1 2 3
Jak opisano w definicji operacji, każda z operacji pop_front i pop_back usuwa element z przodu iz tyłu listy, tj. Odpowiednio pierwszy i ostatni element listy, a zatem za każdym razem zmniejsza rozmiar listy o 1.
- rozmiar :Zwraca rozmiar listy, tj. Liczbę elementów na liście.
- pusty :Sprawdza, czy lista jest pusta.
- wymazać :Usuwa element lub zakres elementów z listy.
- jasny :Usuwa wszystkie elementy z listy, nadając jej rozmiar 0.
Poniżej podano przykład, aby zademonstrować użycie wszystkich powyższych funkcji, tj. Rozmiar, opróżnij, usuń i wyczyść.
#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << '
'; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); cout<<'size of the list: '< Wynik:
Elementy listy to: 1 1 2 3 5
wielkość listy: 5
Lista po skasowaniu pierwszego elementu: 1 2 3 5
Nowy rozmiar listy: 4
wielkość listy po wyczyszczeniu: 0
Powyższy program demonstruje wszystkie cztery funkcje związane z pojemnością listy. Widzimy, że rozmiar listy zmniejsza się o 1, gdy usuwamy 1 element listy. Podczas gdy wywołujemy wyraźną operację na liście, rozmiar wynosi 0, co oznacza, że wszystkie elementy na liście są usuwane.
- z przodu :Zwraca wartość pierwszego elementu listy.
- z powrotem :Zwraca wartość ostatniego elementu listy.
- zamiana :Zamienia zawartość jednej listy zawartością innej listy o tym samym rozmiarze i typie.
- odwrócić :Algorytm, który odwraca listę.
- sortować :Sortuje podaną listę.
Poniższy przykład demonstruje użycie funkcji front, back, reverse, sort i swap.
#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << '
'; } int main() { std::list mylist = {1, 1, 2, 3, 5}; cout<<'List elements are: '; printlist(mylist); cout<<'
Front of the list: '< Wynik:
Elementy listy to: 1 1 2 3 5
Początek listy: 1
Powrót listy: 5
Odwrócona lista: 5 3 2 1 1
Zawartość listy nieparzystej: 1 3 5 7 9
Po zamianie
mylista: 1 3 5 7 9
Lista dziwnych: 5 3 2 1 1
W tym kodzie najpierw drukujemy przednie i tylne wartości listy mylist. Następnie ta lista jest odwracana i drukowana jest odwrócona lista. Następnie definiujemy jeszcze jedną listę nieparzystych liczb, które nie są w żadnej kolejności, i nazywamy algorytm „sortowania”, aby posortować tę listę. Następnie zamieniamy dwie listy za pomocą funkcji swap i drukujemy wymienione listy.
- splatać :Ta funkcja służy do przenoszenia zawartości jednej listy do innej listy w określonej pozycji.
Obie listy muszą być tego samego typu.
splice (pozycja, lista);
gdzie,
pozycja => Pozycja, w której zawartość listy ma zostać przeniesiona.
list => Lista, której elementy mają zostać przeniesione.
Poniższy przykład ilustruje użycie funkcji łączenia.
#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << '
'; } int main() { std::list mylist = {1, 1, 8,13}; cout<<'List elements are: '; printlist(mylist); list seclist = {2,3,5}; cout<<'list to be spliced: '; printlist(seclist); list:: iterator it = mylist.begin(); it ++; it++; mylist.splice(it,seclist); cout<<'
List contents after splicing at position 2: '; printlist(mylist); } Wynik:
Elementy listy to: 1 1 8 13
lista do łączenia: 2 3 5
Zawartość listy po splataniu w pozycji 2: 1 1 2 3 5 8 13
Plik przykład pokazuje, że używamy dwóch list. Najpierw iterator mylisty jest przenoszony na dwie pozycje, a następnie wywoływana jest funkcja splice w celu przeniesienia zawartości drugiej listy na trzecią pozycję pierwszej listy.
- iść :W przeciwieństwie do funkcji łączenia, której można użyć do przeniesienia zawartości jednej listy na inną w określonej pozycji, operacja scalania bezpośrednio łączy dwie listy w jedną listę. W przypadku operacji scalania obie listy muszą być posortowane.
Poniżej podano przykład ilustrujący funkcję scalania.
dodanie wartości do tablicy
#include #include #include using namespace std; void printlist(list mylist) { list :: iterator it; for(it = mylist.begin(); it != mylist.end(); ++it) cout <<*it<<' '; cout << '
'; } int main() { std::list mylist = {1, 1,2,3,5,8}; list seclist = {4,6,7}; cout<<'First List: '; printlist(mylist); cout< Wynik:
Pierwsza lista: 11 2 3 5 8
Druga lista: 4 6 7
Zawartość listy po połączeniu dwóch list:
1 1 2 3 4 5 6 7 8
Zatem w powyższym programie mamy dwie posortowane listy. Na tych dwóch listach nazywamy operację scalania. Wynikowa lista to posortowana lista zawierająca elementy obu list.
Wniosek
Doszliśmy do końca tego samouczka dotyczącego list w STL. Mamy nadzieję, że ten samouczek dałby ci ogromną wiedzę na temat list w STL.
=> Sprawdź tutaj, aby zobaczyć samouczki szkoleniowe od A do Z języka C ++ tutaj.
rekomendowane lektury