Iteratorlar, algoritmlar va ranges - Zamonaviy C++

C++ standart kutubxonasida yuzdan ortiq algoritm bor. Ular qo'lda yozilgan halqalardan qisqaroq, xavfsizroq va ko'pincha tezroq.

Iterator nima #

C++

#include <print>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <numeric>
#include <ranges>
#include <map>

C++

int main()
{
    std::vector<int> v{10, 20, 30, 40, 50};

    auto boshi = v.begin();
    auto oxiri = v.end();

    std::println("birinchi element: {}", *boshi);
    std::println("elementlar soni:  {}", oxiri - boshi);

    // Iterator - ko'rsatkichga o'xshash
    ++boshi;
    std::println("bir qadam keyin:  {}", *boshi);

    boshi += 2;
    std::println("yana ikki qadam:  {}", *boshi);

    // Oxirgi element - end() dan bir qadam oldin
    std::println("oxirgi element:   {}", *(oxiri - 1));

    std::println("");
    std::println("DIQQAT: end() oxirgi elementdan KEYINGI joyga ishora qiladi");
    std::println("uni o'qish - aniqlanmagan xulq-atvor");

    return 0;
}

Natija

birinchi element: 10
elementlar soni:  5
bir qadam keyin:  20
yana ikki qadam:  40
oxirgi element:   50

DIQQAT: end() oxirgi elementdan KEYINGI joyga ishora qiladi
uni o'qish - aniqlanmagan xulq-atvor

Yarim ochiq oraliq: [begin, end)

Barcha standart algoritmlar yarim ochiq oraliq bilan ishlaydi: boshi kiradi, oxiri kirmaydi.

Foydalari:

Foyda	Izoh
Elementlar soni = `end - begin`	Qo'shimcha hisob yo'q
Bo'sh oraliq oddiy ifodalanadi	`begin == end`
Chegara xatolari kamayadi	"Bir kam yoki bir ko'p" muammosi
Ketma-ket oraliqlar ulanadi	`[a,b)` va `[b,c)`

Bu yondashuv C++ ga xos emas - Python ning range(0, 5) ham xuddi shunday ishlaydi.

Qo'lda halqa va algoritm #

C++

int main()
{
    std::vector<int> sonlar{5, 3, 9, 1, 7, 3, 8};

    // 1. Qidirish
    bool topildiQolda = false;
    for (int x : sonlar) {
        if (x == 7) {
            topildiQolda = true;
            break;
        }
    }
    bool topildiAlgoritm = std::ranges::find(sonlar, 7) != sonlar.end();

    std::println("qidirish:  qo'lda {} | algoritm {}",
                 topildiQolda, topildiAlgoritm);

    // 2. Yig'indi
    int yigindiQolda = 0;
    for (int x : sonlar) {
        yigindiQolda += x;
    }
    int yigindiAlgoritm = std::accumulate(sonlar.begin(), sonlar.end(), 0);

    std::println("yig'indi:  qo'lda {} | algoritm {}",
                 yigindiQolda, yigindiAlgoritm);

    // 3. Eng katta
    int engQolda = sonlar[0];
    for (int x : sonlar) {
        if (x > engQolda) {
            engQolda = x;
        }
    }
    int engAlgoritm = *std::ranges::max_element(sonlar);

    std::println("eng katta: qo'lda {} | algoritm {}",
                 engQolda, engAlgoritm);

    // 4. Sanash
    int soniQolda = 0;
    for (int x : sonlar) {
        if (x == 3) {
            ++soniQolda;
        }
    }
    auto soniAlgoritm = std::ranges::count(sonlar, 3);

    std::println("3 lar soni: qo'lda {} | algoritm {}",
                 soniQolda, soniAlgoritm);

    return 0;
}

Natija

qidirish:  qo'lda true | algoritm true
yig'indi:  qo'lda 36 | algoritm 36
eng katta: qo'lda 9 | algoritm 9
3 lar soni: qo'lda 2 | algoritm 2

Algoritm nima uchun afzal

Natija bir xil, lekin farq bor:

Jihat	Qo'lda halqa	Algoritm
Niyat	Kodni o'qish kerak	Nom o'zi aytadi
Indeks xatosi	Mumkin	Yo'q
Optimallashtirish	Sizdan	Kutubxonadan
Sinovdan o'tganmi	Yo'q	Yillar davomida
Uzunlik	5-7 qator	1 qator

Eng muhimi birinchi qator. std::ranges::count(v, 3) ni ko'rgan odam darhol nima bo'layotganini tushunadi. Halqani esa o'qib chiqish kerak.

Bu kod ko'rib chiqishda ham tejaydi: xato bo'lmasligi kafolatlangan qismlarni tekshirish shart emas.

Eng ko'p ishlatiladigan algoritmlar #

C++

int main()
{
    std::vector<int> v{5, 2, 8, 1, 9, 3, 7};

    // Tartiblash
    std::vector<int> tartibli = v;
    std::ranges::sort(tartibli);
    std::println("sort:           {}", tartibli);

    // Teskari
    std::ranges::reverse(tartibli);
    std::println("reverse:        {}", tartibli);

    // O'zgartirish
    std::vector<int> kvadratlar(v.size());
    std::ranges::transform(v, kvadratlar.begin(),
                           [](int x) { return x * x; });
    std::println("transform:      {}", kvadratlar);

    // Filtrlab nusxalash
    std::vector<int> juftlar;
    std::ranges::copy_if(v, std::back_inserter(juftlar),
                         [](int x) { return x % 2 == 0; });
    std::println("copy_if (juft): {}", juftlar);

    // To'ldirish
    std::vector<int> toldirilgan(5);
    std::ranges::fill(toldirilgan, 42);
    std::println("fill:           {}", toldirilgan);

    // Ketma-ketlik
    std::vector<int> ketma(5);
    std::iota(ketma.begin(), ketma.end(), 100);
    std::println("iota:           {}", ketma);

    // Tekshiruvlar
    std::println("");
    std::println("hammasi musbat: {}",
                 std::ranges::all_of(v, [](int x) { return x > 0; }));
    std::println("biror juft:     {}",
                 std::ranges::any_of(v, [](int x) { return x % 2 == 0; }));
    std::println("hech biri >100: {}",
                 std::ranges::none_of(v, [](int x) { return x > 100; }));

    return 0;
}

Natija

sort:           [1, 2, 3, 5, 7, 8, 9]
reverse:        [9, 8, 7, 5, 3, 2, 1]
transform:      [25, 4, 64, 1, 81, 9, 49]
copy_if (juft): [2, 8]
fill:           [42, 42, 42, 42, 42]
iota:           [100, 101, 102, 103, 104]

hammasi musbat: true
biror juft:     true
hech biri >100: true

O'chirish - klassik tuzoq #

C++

int main()
{
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8};

    // std::remove elementlarni O'CHIRMAYDI
    auto yangiOxir = std::remove_if(v.begin(), v.end(),
                                    [](int x) { return x % 2 == 0; });

    std::println("remove_if dan keyin:");
    std::println("  hajm:     {} (o'zgarmadi!)", v.size());
    std::println("  mazmuni:  {}", v);
    std::println("  yangi oxir {} - indeksida", yangiOxir - v.begin());

    // Haqiqiy o'chirish uchun erase kerak
    v.erase(yangiOxir, v.end());
    std::println("");
    std::println("erase dan keyin:");
    std::println("  hajm:     {}", v.size());
    std::println("  mazmuni:  {}", v);

    // C++20 - bitta chaqiruv
    std::vector<int> ikkinchi{1, 2, 3, 4, 5, 6, 7, 8};
    auto ochirildi = std::erase_if(ikkinchi, [](int x) { return x % 2 == 0; });

    std::println("");
    std::println("std::erase_if (C++20):");
    std::println("  o'chirildi: {} ta", ochirildi);
    std::println("  mazmuni:    {}", ikkinchi);

    return 0;
}

Natija

remove_if dan keyin:
  hajm:     8 (o'zgarmadi!)
  mazmuni:  [1, 3, 5, 7, 5, 6, 7, 8]
  yangi oxir 4 - indeksida

erase dan keyin:
  hajm:     4
  mazmuni:  [1, 3, 5, 7]

std::erase_if (C++20):
  o'chirildi: 4 ta
  mazmuni:    [1, 3, 5, 7]

remove o'chirmaydi - u ko'chiradi

Bu C++ dagi eng chalkash nomlardan biri.

std::remove_if shartga mos kelmagan elementlarni boshga siljitadi va yangi mantiqiy oxirni qaytaradi. Konteyner hajmi o'zgarmaydi.

Sabab: algoritmlar iteratorlar bilan ishlaydi va ular konteynerni bilmaydi - demak uning hajmini o'zgartira olmaydi.

Klassik yechim - erase-remove idiomasi:

KOD

v.erase(std::remove_if(v.begin(), v.end(), shart), v.end());

C++20 dan boshlab qisqaroq yo'l bor:

Eski	Yangi
`v.erase(std::remove(v.begin(), v.end(), x), v.end())`	`std::erase(v, x)`
`v.erase(std::remove_if(...), v.end())`	`std::erase_if(v, shart)`

Yangisi qisqaroq va xato qilish qiyinroq.

erase-remove idiomasi - C++20 da nihoyat kerak emas

Ranges - C++20 #

C++

int main()
{
    std::vector<int> v{5, 2, 8, 1, 9, 3, 7, 4};

    // Eski uslub - begin/end juftligi
    std::vector<int> eski = v;
    std::sort(eski.begin(), eski.end());

    // Yangi uslub - butun konteyner
    std::vector<int> yangi = v;
    std::ranges::sort(yangi);

    std::println("eski:  {}", eski);
    std::println("yangi: {}", yangi);
    std::println("teng:  {}", eski == yangi);

    // Proyeksiya - qaysi maydon bo'yicha ishlash
    struct Talaba { std::string ism; int baho; };

    std::vector<Talaba> talabalar{
        {"Husanboy", 85}, {"Malika", 92}, {"Nodira", 78},
    };

    std::ranges::sort(talabalar, {}, &Talaba::baho);

    std::println("");
    std::println("bahoga qarab tartiblangan:");
    for (const auto& t : talabalar) {
        std::println("  {:<10} {}", t.ism, t.baho);
    }

    return 0;
}

Natija

eski:  [1, 2, 3, 4, 5, 7, 8, 9]
yangi: [1, 2, 3, 4, 5, 7, 8, 9]
teng:  true

bahoga qarab tartiblangan:
  Nodira     78
  Husanboy   85
  Malika     92

Proyeksiya - lambdasiz solishtirish

std::ranges::sort(talabalar, {}, &Talaba::baho) yozuvidagi uchinchi argument - proyeksiya.

U "har elementdan qaysi qismini olib solishtir" degani.

Eski usul bilan solishtiring:

KOD

std::sort(v.begin(), v.end(), [](const Talaba& a, const Talaba& b) {
    return a.baho < b.baho;
});

Yangi usul:

KOD

std::ranges::sort(v, {}, &Talaba::baho);

Ikkinchi argument ({}) - solishtirish funksiyasi; {} standart std::less degani.

Proyeksiya deyarli barcha ranges algoritmlarida bor: find, count_if, max_element va h.k.

Ko'rinishlar (views) #

C++

int main()
{
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // Filtrlash - lekin hech narsa hisoblanmaydi
    auto juftlar = v | std::views::filter([](int x) { return x % 2 == 0; });

    std::print("juftlar: ");
    for (int x : juftlar) {
        std::print("{} ", x);
    }
    std::println("");

    // Zanjir - hammasi bitta o'tishda
    auto natija = v
        | std::views::filter([](int x) { return x % 2 == 0; })
        | std::views::transform([](int x) { return x * x; })
        | std::views::take(3);

    std::print("juft -> kvadrat -> 3 ta: ");
    for (int x : natija) {
        std::print("{} ", x);
    }
    std::println("");

    // Boshqa foydali ko'rinishlar
    std::println("");
    std::print("teskari:     ");
    for (int x : v | std::views::reverse) {
        std::print("{} ", x);
    }
    std::println("");

    std::print("birinchi 4 tasiz: ");
    for (int x : v | std::views::drop(4)) {
        std::print("{} ", x);
    }
    std::println("");

    std::print("shart bajarilguncha:");
    for (int x : v | std::views::take_while([](int x) { return x < 5; })) {
        std::print(" {}", x);
    }
    std::println("");

    return 0;
}

Natija

juftlar: 2 4 6 8 10 
juft -> kvadrat -> 3 ta: 4 16 36 

teskari:     10 9 8 7 6 5 4 3 2 1 
birinchi 4 tasiz: 5 6 7 8 9 10 
shart bajarilguncha: 1 2 3 4

Ko'rinishlar dangasa ishlaydi

v | std::views::filter(...) yozuvi hech narsa hisoblamaydi va hech qanday xotira ajratmaydi.

Hisob faqat for halqasi element so'raganda boradi.

Bu katta farq:

	Eski usul	Ko'rinishlar
Oraliq natijalar	Yangi vektorlar	Yo'q
Xotira	Har bosqichda ajratiladi	Nol qo'shimcha
Nechta o'tish	Har bosqichda bittadan	Bitta
To'xtatish	Hammasi hisoblanadi	`take(3)` da to'xtaydi

Oxirgi qator amaliy: take(3) bo'lsa, ko'rinish uchtadan keyin umuman ishlamaydi. Eski usulda esa butun vektor filtrlanib, keyin uchtasi olinardi.

Diqqat: ko'rinish asl konteynerga ishora qiladi. Asl konteyner o'zgarsa yoki yo'q bo'lsa - ko'rinish yaroqsizlanadi (yana o'sha osilgan havola muammosi).

Ko'rinishni konteynerga aylantirish #

C++

int main()
{
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    auto korinish = v
        | std::views::filter([](int x) { return x % 3 == 0; })
        | std::views::transform([](int x) { return x * 10; });

    // C++23: to'g'ridan-to'g'ri
    auto natija = std::ranges::to<std::vector>(korinish);

    std::println("natija turi: std::vector<int>");
    std::println("mazmuni:     {}", natija);
    std::println("hajmi:       {}", natija.size());

    // C++20 da qo'lda
    std::vector<int> qolda;
    for (int x : korinish) {
        qolda.push_back(x);
    }
    std::println("");
    std::println("qo'lda:      {}", qolda);

    return 0;
}

Natija

natija turi: std::vector<int>
mazmuni:     [30, 60, 90]
hajmi:       3

qo'lda:      [30, 60, 90]

Iterator turlari #

C++

int main()
{
    std::vector<int> v{1, 2, 3, 4, 5};
    std::list<int> l{1, 2, 3, 4, 5};

    // vector - tasodifiy kirish: sakrash mumkin
    auto vIt = v.begin();
    vIt += 3;
    std::println("vector: begin() + 3 = {}", *vIt);

    // list - ikki tomonlama: faqat bir qadamdan
    auto lIt = l.begin();
    std::advance(lIt, 3);       // ichida 3 marta ++ qiladi
    std::println("list:   3 qadam keyin = {}", *lIt);

    // lIt += 3;                // KOMPILYATSIYA XATOSI

    std::println("");
    std::println("{:<22} {:<12} {}", "ITERATOR TURI", "KONTEYNER",
                 "NIMA QILA OLADI");
    std::println("{}", std::string(64, '-'));
    std::println("{:<22} {:<12} {}", "input", "oqim", "bir marta o'qish");
    std::println("{:<22} {:<12} {}", "forward", "forward_list", "++ va qayta o'qish");
    std::println("{:<22} {:<12} {}", "bidirectional", "list, map", "++ va --");
    std::println("{:<22} {:<12} {}", "random access", "vector, deque",
                 "+= n, sakrash");
    std::println("{:<22} {:<12} {}", "contiguous", "vector, array",
                 "xotirada ketma-ket");

    return 0;
}

Natija

vector: begin() + 3 = 4
list:   3 qadam keyin = 4

ITERATOR TURI          KONTEYNER    NIMA QILA OLADI
----------------------------------------------------------------
input                  oqim         bir marta o'qish
forward                forward_list ++ va qayta o'qish
bidirectional          list, map    ++ va --
random access          vector, deque += n, sakrash
contiguous             vector, array xotirada ketma-ket

Algoritm iterator turini talab qiladi

std::sort tasodifiy kirish iteratorini talab qiladi. Shuning uchun:

KOD

std::list<int> l{3, 1, 2};
std::ranges::sort(l);        // KOMPILYATSIYA XATOSI
l.sort();                    // list ning O'Z metodi - ishlaydi

Ba'zi konteynerlar umumiy algoritm o'rniga o'z metodini beradi - u ma'lumot tuzilishini bilgani uchun tezroq:

Konteyner	O'z metodi	Nima uchun
`list`	`.sort()`, `.remove()`, `.unique()`	Ko'rsatkichlarni qayta bog'laydi
`map`, `set`	`.find()`	Daraxt bo'ylab yuradi
`string`	`.find()`	Maxsus optimallashtirilgan

Qoida: konteynerda shu nomdagi metod bo'lsa - uni ishlating.

Amaliy misol #

C++

struct Buyurtma
{
    std::string mijoz;
    int summa;
    std::string holat;
};

int main()
{
    std::vector<Buyurtma> buyurtmalar{
        {"Husanboy", 250000, "tolangan"},
        {"Malika", 1200000, "kutilmoqda"},
        {"Nodira", 450000, "tolangan"},
        {"Aziza", 90000, "bekor"},
        {"Kamola", 780000, "tolangan"},
        {"Dilnoza", 340000, "kutilmoqda"},
    };

    // To'langanlar yig'indisi
    int jami = 0;
    for (const auto& b : buyurtmalar
                       | std::views::filter([](const Buyurtma& x) {
                             return x.holat == "tolangan";
                         })) {
        jami += b.summa;
    }
    std::println("to'langan jami: {} so'm", jami);

    // Eng katta buyurtma
    auto eng = std::ranges::max_element(buyurtmalar, {}, &Buyurtma::summa);
    std::println("eng katta:      {} ({} so'm)", eng->mijoz, eng->summa);

    // Holatlar bo'yicha sanash
    std::map<std::string, int> holatlar;
    for (const auto& b : buyurtmalar) {
        ++holatlar[b.holat];
    }

    std::println("");
    std::println("holatlar bo'yicha:");
    for (const auto& [holat, soni] : holatlar) {
        std::println("  {:<12} {} ta", holat, soni);
    }

    // 300 000 dan katta buyurtmalar, summasi bo'yicha
    auto kattalar = std::ranges::to<std::vector>(
        buyurtmalar | std::views::filter([](const Buyurtma& b) {
            return b.summa > 300000;
        }));

    std::ranges::sort(kattalar, std::greater{}, &Buyurtma::summa);

    std::println("");
    std::println("300 000 dan katta buyurtmalar:");
    for (const auto& b : kattalar) {
        std::println("  {:<10} {:>9} so'm  {}", b.mijoz, b.summa, b.holat);
    }

    return 0;
}

Natija

to'langan jami: 1480000 so'm
eng katta:      Malika (1200000 so'm)

holatlar bo'yicha:
  bekor        1 ta
  kutilmoqda   2 ta
  tolangan     3 ta

300 000 dan katta buyurtmalar:
  Malika       1200000 so'm  kutilmoqda
  Kamola        780000 so'm  tolangan
  Nodira        450000 so'm  tolangan
  Dilnoza       340000 so'm  kutilmoqda

Amaliy topshiriq

Iteratorlar bilan vektorni aylanib chiqing.
end() nima uchun oxirgi elementdan keyin turishini tushuntiring.
To'rtta amalni qo'lda halqa va algoritm bilan yozib solishtiring.
remove_if dan keyin konteyner hajmini tekshiring.
erase-remove idiomasini va std::erase_if ni yozing.
std::ranges::sort ga proyeksiya bering.
filter, transform va take ni zanjirlab bog'lang.
Ko'rinishlar nima uchun xotira ajratmasligini tushuntiring.
std::list ni std::ranges::sort bilan tartiblashga urinib ko'ring.
Buyurtmalar ro'yxatini filtrlang, tartiblang va yig'indini hisoblang.

Xulosa #

Iterator - konteyner elementiga ishora qiluvchi obyekt.
Barcha algoritmlar yarim ochiq oraliq [begin, end) bilan ishlaydi.
Algoritm niyatni ko'rsatadi va indeks xatolarini yo'q qiladi.
remove_if elementlarni o'chirmaydi - u ularni siljitadi.
C++20 da std::erase_if bu tuzoqni yo'q qildi.
Ranges algoritmlarga butun konteynerni uzatish imkonini beradi.
Proyeksiya (&Tur::maydon) lambdasiz solishtirish beradi.
Ko'rinishlar dangasa: ular hech narsa hisoblamaydi va xotira ajratmaydi.
take(n) bo'lsa, ko'rinish n tadan keyin umuman ishlamaydi.
Konteynerda shu nomdagi o'z metodi bo'lsa - uni ishlating.

Keyingi bo'limda darslikning markaziy g'oyasi - RAII bilan tanishamiz.

Iterator nima #

Qo'lda halqa va algoritm #

Eng ko'p ishlatiladigan algoritmlar #

O'chirish - klassik tuzoq #

Ranges - C++20 #

Ko'rinishlar (views) #

Ko'rinishni konteynerga aylantirish #

Iterator turlari #

Amaliy misol #

Xulosa #

Xatolik topdingizmi?