STL: konteynerlər və alqoritmlər

Bu dərsdə öyrənəcəksən

Tapşırığa uyğun STL konteynerini seçmək
std::map ilə açar–qiymət cütlərini saxlamaq və saymaq
std::set ilə təkrarsız elementlər toplusu yaratmaq
İteratorlar və <algorithm> funksiyaları ilə çeşidləmək, axtarmaq və saymaq

Olimpiadada milyon ədədi çeşidləmək lazımdır. Çeşidləmə alqoritmini sıfırdan yazıb onu sazlamaq bir saat çəkər. C++ proqramçısı isə cəmi bir sətir yazır: std::sort(v.begin(), v.end());. Bu sehr STL-dən (Standard Template Library — standart şablonlar kitabxanası) gəlir: hazır, yoxlanılmış və çox sürətli verilən strukturları və alqoritmlər toplusu.

STL-in üç hissəsi

Konteynerlər verilənləri saxlayır: std::vector, std::map, std::set və başqaları.
İteratorlar konteynerdəki mövqeyi göstərir: v.begin() birinci elementi, v.end() isə sonuncudan sonrakı yeri göstərir.
Alqoritmlər (<algorithm> faylı) iteratorlarla verilən aralıqda işləyir: çeşidləyir, axtarır, sayır, çevirir.

Konteyner	Nə saxlayır	Axtarış sürəti
`std::vector<T>`	ardıcıl elementlər, indekslə	qiymətə görə axtarış: O(n)
`std::map<K, V>`	açara görə çeşidlənmiş açar–qiymət cütləri	O(log n)
`std::set<T>`	çeşidlənmiş, təkrarsız elementlər	O(log n)
`std::unordered_map<K, V>`	sırasız açar–qiymət cütləri (heş cədvəli)	orta hesabla O(1)

Ən çox işlədilən konteynerlər

std::map: açar və qiymət

std::map (<map> faylı) lüğət kimidir: hər açara bir qiymət uyğun gəlir və açarlar təkrarlanmır. Elementlər həmişə açara görə çeşidlənmiş saxlanır. Aşağıda sinifdə keçirilən sorğunun səslərini sayırıq: count[v] açar yoxdursa, onu 0 qiyməti ilə yaradır, ++ isə artırır.

C++

#include <iostream>
#include <map>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> votes = {"tea", "coffee", "tea", "juice", "tea", "coffee"};
    std::map<std::string, int> count;
    for (const std::string& v : votes) {
        count[v]++;
    }
    for (const auto& entry : count) {
        std::cout << entry.first << ": " << entry.second << '\n';
    }
    std::cout << "Kinds: " << count.size() << '\n';

    if (count.find("milk") == count.end()) {
        std::cout << "Nobody chose milk\n";
    }
    return 0;
}

Gözlənilən nəticə

coffee: 2
juice: 1
tea: 3
Kinds: 3
Nobody chose milk

Açarlar əlifba sırası ilə çıxdı. Hər element pair-dir: first açar, second qiymətdir.

std::set: təkrarsız elementlər

std::set (<set> faylı) hər qiyməti yalnız bir dəfə saxlayır və elementləri avtomatik çeşidləyir. Artıq mövcud olan qiyməti insert ilə əlavə etsən, heç nə dəyişmir. Bu, təkrarları silmək və «bu qiymət olubmu?» sualına tez cavab vermək üçün idealdır.

C++

#include <iostream>
#include <set>

int main() {
    std::set<int> numbers = {5, 1, 4, 1, 5, 9, 2, 6, 5};
    numbers.insert(3);
    numbers.insert(4);
    std::cout << "Size: " << numbers.size() << '\n';
    for (int n : numbers) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
    std::cout << std::boolalpha << (numbers.count(7) > 0) << '\n';
    return 0;
}

Gözlənilən nəticə

Size: 7
1 2 3 4 5 6 9 
false

Doqquz ədəddən altısı təkrarsızdır; 3 əlavə olundu, 4 isə artıq var idi.

Alqoritmlər

<algorithm> faylında onlarla hazır funksiya var və onların hamısı eyni qaydada işləyir: aralığın əvvəlini və sonunu iterator kimi alırlar. std::find tapdığı elementin iteratorunu, tapmadıqda isə end() qaytarır. Cəmləmə üçün std::accumulate <numeric> faylındadır.

C++

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    std::vector<int> v = {42, 7, 19, 73, 7, 50};

    std::sort(v.begin(), v.end());
    for (int x : v) {
        std::cout << x << ' ';
    }
    std::cout << '\n';

    auto it = std::find(v.begin(), v.end(), 19);
    if (it != v.end()) {
        std::cout << "19 found at index " << (it - v.begin()) << '\n';
    }
    std::cout << "Sevens: " << std::count(v.begin(), v.end(), 7) << '\n';
    std::cout << "Max: " << *std::max_element(v.begin(), v.end()) << '\n';
    std::cout << "Sum: " << std::accumulate(v.begin(), v.end(), 0) << '\n';
    return 0;
}

Gözlənilən nəticə

7 7 19 42 50 73 
19 found at index 2
Sevens: 2
Max: 73
Sum: 198

Alqoritm	Nə edir
`std::sort(b, e)`	artan sıra ilə çeşidləyir
`std::reverse(b, e)`	sıranı tərsinə çevirir
`std::find(b, e, x)`	`x`-in iteratorunu və ya `e`-ni qaytarır
`std::count(b, e, x)`	`x`-in neçə dəfə olduğunu sayır
`std::max_element(b, e)`	ən böyük elementin iteratoru
`std::binary_search(b, e, x)`	çeşidlənmiş aralıqda sürətli axtarış, `true`/`false`

İnteraktiv

Simulyasiya yüklənir…

Sadə çeşidləmə alqoritmləri n² qədər addım atır. std::sort isə n · log n qədər müqayisə ilə işləyir — milyon element üçün bu, minlərlə dəfə azdır.

Əsas fikirlər

STL = konteynerlər + iteratorlar + alqoritmlər.
std::map açara görə çeşidlənmiş açar–qiymət cütlərini saxlayır; m[k] olmayan açarı 0 ilə yaradır.
std::set hər qiyməti bir dəfə saxlayır və çeşidlənmiş saxlayır.
v.end() sonuncu elementdən sonrakı yerdir; std::find tapmadıqda onu qaytarır.
std::sort, std::count, std::max_element kimi hazır alqoritmlər öz dövrünü yazmaqdan daha qısa və etibarlıdır.

Özünü yoxla

10 sual. Hər düzgün cavab XP qazandırır.

1 / 10

Hansı konteyner elementləri təkrarsız və çeşidlənmiş saxlayır?