Competitive Programming'da STL ma'lumot tuzilmalari: set va map

Competitive programming'da std::set va std::map - bu C++ dagi standart assotsiativ konteynerlar bo'lib, insert, erase, find kabi amallarni $O(\log n)$ vaqt ichida samarali bajaradi. Odatda ular balanslangan binary search tree sifatida implement qilinadi, shuning uchun barcha elementlar (kalitlar) saralangan tartibda saqlanadi. Bu esa qiymatlar to'plamini yoki kalit-qiymat juftliklarini dinamik ravishda o'zgarib turadigan, lekin tartiblangan holda saqlash kerak bo'lganda juda foydali qiladi.

std::set

set - bu noyob (unique) kalitlarni saralangan tartibda saqlaydigan konteyner. Asosiy xususiyatlari:

• Dublikat yo'q: bir xil qiymatni qayta qo'shish hech narsani o'zgartirmaydi.
• Saralangan: iteratsiya qilganda kalitlar o'sish tartibida keladi.
• Tipik amallar: insert, erase, find, lower_bound, upper_bound.

Tipik e'lon qilish:

std::map

map - bu tartiblangan lug'at: u (key, value) kalit-qiymat juftliklarini saqlaydi, kalitlar noyob bo'ladi va strict weak ordering bo'yicha saralangan holda turadi.

Asosiy xususiyatlari:

• Har bir kalit ko'pi bilan bir marta uchraydi.
• Qiymatga kalit orqali operator[] yoki at bilan murojaat qilinadi.
• Qo'shish, o'chirish va qidirish $O(\log n)$ vaqt oladi.