Podstawowe Algorytmy w C++: Sortowanie, Wyszukiwanie i Generowanie

Standardowe Algorytmy STL

Zamiast pisać własne pętle, C++ oferuje zoptymalizowane algorytmy w nagłówku <algorithm> oraz <numeric>. Oto cztery kluczowe kategorie:

1. Sortowanie (Sorting)

Najczęściej używaną funkcją jest std::sort. Działa ona w czasie $O(N \log N)$ .

cpp

std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end()); // Sortuje rosnąco

2. Wyszukiwanie (Searching)

std::find: Szuka elementu w dowolnym kontenerze (złożoność liniowa).
std::binary_search: Bardzo szybkie wyszukiwanie w posortowanych danych.

cpp

auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) { /* Znaleziono! */ }

3. Kopiowanie (Copying)

std::copy pozwala przenieść dane z jednego miejsca do drugiego. Często używane z std::back_inserter.

cpp

std::vector<int> v2;
std::copy(v.begin(), v.end(), std::back_inserter(v2));

4. Generowanie ciągów i wypełnianie

std::fill: Wypełnia zakres jedną wartością.
std::iota: (z nagłówka <numeric>) Generuje rosnący ciąg liczb (np. 1, 2, 3...).

cpp

std::vector<int> data(10);
std::iota(data.begin(), data.end(), 1); // Wypełnia od 1 do 10

Dobra praktyka: Używaj algorytmów zamiast ręcznych pętli for. Są one lepiej zoptymalizowane przez kompilator i rzadziej zawierają błędy typu „off-by-one”.

Standardowe Algorytmy STL

Zamiast pisać własne pętle, C++ oferuje zoptymalizowane algorytmy w nagłówku <algorithm> oraz <numeric>. Oto cztery kluczowe kategorie:

1. Sortowanie (Sorting)

Najczęściej używaną funkcją jest std::sort. Działa ona w czasie

O(N \log N)

cpp

std::vector<int> v = {5, 2, 8, 1, 9};
std::sort(v.begin(), v.end()); // Sortuje rosnąco

2. Wyszukiwanie (Searching)

std::find: Szuka elementu w dowolnym kontenerze (złożoność liniowa).

std::binary_search: Bardzo szybkie wyszukiwanie w posortowanych danych.

cpp

auto it = std::find(v.begin(), v.end(), 8);
if (it != v.end()) { /* Znaleziono! */ }

3. Kopiowanie (Copying)

std::copy pozwala przenieść dane z jednego miejsca do drugiego. Często używane z std::back_inserter.

cpp

std::vector<int> v2;
std::copy(v.begin(), v.end(), std::back_inserter(v2));

4. Generowanie ciągów i wypełnianie

std::fill: Wypełnia zakres jedną wartością.

std::iota: (z nagłówka <numeric>) Generuje rosnący ciąg liczb (np. 1, 2, 3...).

cpp

std::vector<int> data(10);
std::iota(data.begin(), data.end(), 1); // Wypełnia od 1 do 10

Dobra praktyka: Używaj algorytmów zamiast ręcznych pętli for. Są one lepiej zoptymalizowane przez kompilator i rzadziej zawierają błędy typu „off-by-one”.

Podstawowe Algorytmy w C++: Sortowanie, Wyszukiwanie i Generowanie

Standardowe Algorytmy STL

1. Sortowanie (Sorting)

2. Wyszukiwanie (Searching)

3. Kopiowanie (Copying)

4. Generowanie ciągów i wypełnianie

Może Cię zainteresować

Napisy w stylu C: Tablice typu char i znak null

Biblioteka <cmath> w C++ – Niezbędnik Matematyczny

Zrozumieć Dyrektywę #include w C++

Podstawowe Algorytmy w C++: Sortowanie, Wyszukiwanie i Generowanie

Standardowe Algorytmy STL

1. Sortowanie (Sorting)

2. Wyszukiwanie (Searching)

3. Kopiowanie (Copying)

4. Generowanie ciągów i wypełnianie

Może Cię zainteresować

Napisy w stylu C: Tablice typu char i znak null

Biblioteka <cmath> w C++ – Niezbędnik Matematyczny

Zrozumieć Dyrektywę #include w C++