7 ma’ruza. Chiziqli konteynerlar va ularni qo’llash. Reja

7 - MA’RUZA. CHIZIQLI KONTEYNERLAR VA ULARNI QO’LLASH.


Reja:
1. Konteyner haqida tushuncha.
2. Diopazon haqida tushuncha.
3. Chiziqli konteynerlar.
4. Konteynerlarni qo’llash.

Kalit so’zlar: Konteyner, diopazon, chiziqli konteynerlar, iterator.

1. Konteyner haqida tushuncha.
Konteyner (container) - bu ob'ektlar bir xil turdagi qiymatlar to'plamini saqlashga qodir sinf ("massiv" tushunchasini umumlashtirish). Konteyner uning tarkibiga kirishni ta'minlaydi. C ++ standart kutubxonasida bu yordamchi elementlar iterator deb nomlangan massiv elementiga ko'rsatgich kontseptsiyasini umumlashtirishga asoslanadi.
2. Diopazon haqida tushuncha.
Bir juft yineluvchi diapason (range) ni belgilaydi - bu juftlikni birinchi iterator ko'rsatgan birinchi elementdan boshlab, ikkinchisini oldinga siljitish orqali sanab o'tish mumkin bo'lgan qiymatlar ketma -ketligining ta'rifi. uchraydi, ketma -ketlikning oxirini bildiradi va qo'g'irchoq elementga ishora qiladi, go'yo oxirgi elementdan keyin ketma -ketlikda turadi.
Bu ketma -ketlik konteyner, konteyner qismi, massiv, fayl bo'lishi mumkin yoki uni tezda yaratish mumkin.
Massivli diapazonga misol:
char data[] = "Hello, world!";
// Диапазон с 7-го элемента по 12-й содержит слово "world".
auto begin = data + 7; // Начало диапазона -- первый итератор в паре.
auto end = data + 12; // Конец диапазона -- второй итератор в паре.
assert(end - begin == 5); // Расстояние между итераторами == количеству элементов в диапазоне.
// Перечислим подряд все элементы диапазона.
while (begin != end)
cout.put(*begin++); // > world
3. Chiziqli konteynerlar.
Yagona bog'langan ro'yxat forward_list > bir turdagi iterator orqali T tipidagi elementlarga kirishni ta'minlaydi. Ro'yxat tugunlarni yaratish uchun A :: rebind orqali olingan ajratuvchidan foydalanadi. Bitta bog'langan ro'yxatning o'ziga xos xususiyati shundaki, elementlarni faqat berilgan pozitsiyadan keyin qo'shish va o'chirish mumkin:

• 
  insert_after - elementni kiritish;
  
• 
  emplace_after - o'tkazilgan parametrlar uchun konstruktorni chaqirib, yangi element yaratish;
  
• 
  erase_after - ob'ektni o'chirish.
  

Before_begin va cbefore_begin funktsiyalari tomonidan qaytariladigan "birinchi elementdan oldin" qo'shimcha qo'g'irchoq pozitsiyasi mavjud (const_iteratorni qaytaradigan variant). Ob'ektlarni boshiga kiritish mumkin: fl.push_front (element) ni chaqirish ekvivalentdir


fl.insert_after(fl.before_begin(), item)

xuddi shunday fl.emplace_front (...) (bu erda ... element konstruktor parametrlarining ixtiyoriy to'plami) ga teng

fl.emplace_after(fl.before_begin(), ...)
Pop_front funktsiyasi ro'yxatning birinchi elementini olib tashlaydi.
C ++ standart kutubxonasidagi ro'yxat konteynerlarining xususiyati yuqori darajadagi operatsiyalarni qo'llab-quvvatlashdir, bu operatsiyalarni amalga oshirish uchun faqat iteratorlardan samarali foydalanish mumkin emasligidan kelib chiqadi:

• 
  merge - birlashtirilgan ikkita saralangan ro'yxatni bittaga birlashtiradi, elementlar nusxalanmaydi, lekin o'ng ro'yxatdan chapga o'tkaziladi;
  
• 
  splice_after - o'tilgan ro'yxatni ko'rsatilgan elementdan keyin to'liq qo'shadi;
  
• 
  remove - qiymati berilganga teng bo'lgan barcha elementlarni olib tashlaydi;
  
• 
  remove_if - predikat bo'yicha barcha elementlarni olib tashlaydi;
  
• 
  reverse - elementlarning tartibini o'zgartiradi;
  
• 
  unique - ketma -ket barcha dublikatlarni olib tashlaydi;
  
• 
  sort  - ro'yxatni joyida tartiblaydi.
  

Umuman olganda, bu funktsiyalar mos keladigan standart algoritmlarga o'xshaydi (ularning ro'yxatini quyida tegishli bo'limda ko'ring), lekin ular hech bo'lmaganda tezroq bajariladi va maksimal darajada oddiy bajariladi, chunki bir xil standart universal saralash std :: sort (dan, to) iteratorlarga tasodifiy kirishni talab qiladi va shuning uchun ro'yxatlarga umuman taalluqli emas.

bog'langan ro'yxat > ikki tomonlama iterator orqali elementlarga kirishni ta'minlaydi. Bitta bog'langan ro'yxatdan farqli o'laroq, elementlar berilgan pozitsiyadan oldin kiritiladi (qo'shish, joylashtirish, biriktirish funktsiyalari), oxiridan kiritish va o'chirish (push_back, emplace_back, pop_back), iterator ko'rsatgan elementni o'chirish (o'chirish) mavjud. . * _Funksiyalar yo'q.
deque > tasodifiy kirish iteratori orqali elementlarga kirishni ta'minlaydi. Xuddi ro'yxat kabi, u sizga har ikki tomondan elementlarni samarali qo'shish va olib tashlash imkonini beradi. Indeksga kirish uchun ikkita funksiya mavjud: [] operatori va at (indeks) operatori. Birinchisidan farqli o'laroq, ikkinchisi indeksni tekshiradi va noto'g'ri qiymatda out_of_range istisnosini chiqaradi.
Deque konteyner elementlarni ro'yxatga o'xshash o'zboshimchalik bilan joylashtirish va o'chirishga imkon beradi, lekin deque holatida bu operatsiyalar qimmatga tushadi: ular chiziqli o'lchamdagi konteyner uchun vaqt talab qilishi mumkin. Shuni ham yodda tutingki, elementlarni kiritish va o'chirish xotirada saqlangan elementlarning potentsial harakatlanishi tufayli oldindan saqlangan iteratorlar yoki ko'rsatgichlarni "chalkashtirib yuborishi" mumkin (agar ular ko'rsatgan elementlar o'chirilmasa, ro'yxat iteratorlari saqlanib qoladi) ...
dinamik massivi yoki vektor (bu erda ham qarang) vektor > tasodifiy kirish iteratori orqali elementlarga kirishni ta'minlaydi. Deque -dan farqli o'laroq, u elementlarni boshida kiritish va o'chirishga ruxsat bermaydi. Dinamik qator saqlangan elementlarning ulashgan xotira qismida joylashishini kafolatlaydi, uning manzili ma'lumotlar funktsiyasi tomonidan qaytariladi. Elementlar qo'shilganda va oldindan ajratilgan xotira tugagach, yangi, kattaroq dinamik massiv ajratilishi mumkin, bu erda elementlar ko'chiriladi. Bunday holda, eski xotira o'chiriladi, saqlangan barcha iteratorlar "buzilgan" va o'chirilgan ob'ektlar ko'rsatgichlariga teng bo'ladi.
Massiv sizga zaxira funktsiyasidan foydalangan holda etarli hajmdagi do'konni oldindan tayyorlashga imkon beradi (harakatlanuvchi elementlarga olib kelishi mumkin). Sig'im funktsiyasidan foydalanib, saqlash hajmini bilib olishingiz mumkin. Shrink_to_fit funktsiyasi amalda egallagan hajmni saqlashni ajratadi va elementlarni u erga ko'chiradi, bu esa ajratilmagan xotirani bo'shatadi.
statik massivi tasodifiy kirish iteratori orqali elementlarga kirishni ta'minlaydi va T [N] statik massiviga o'ralgan bo'lib, uning manzilini ma'lumotlar funktsiyasi yordamida olish mumkin. T [N] dan farqli o'laroq, massivi to'laqonli tip bo'lib, uning qiymatlari nusxa ko'chirilishi mumkin (qiymatlar bo'yicha funktsiyalarga o'tkaziladi), ularning qiymatlari avtomatik ravishda ularga ko'rsatgichlarga aylantirilmaydi. Nihoyat, agar xohlasangiz, massivini asosiy sinf sifatida ishlatish mumkin (lekin har qanday konteyner kabi ehtiyotkorlik bilan, chunki standart konteynerlar bu maqsad uchun mo'ljallanmagan va xususan, virtual funktsiyalarni o'z ichiga olmaydi). Siz elementlarga deque va vektor bilan bir xil tarzda indeks bo'yicha murojaat qilishingiz mumkin. Siz elementlar sonini o'zgartira olmaysiz, shuning uchun massiv elementlarni kiritish va o'chirish uchun hech qanday funktsiyalarni ta'minlamaydi. To'ldirish funktsiyasi qatorni uzatilgan qiymat nusxalari bilan to'ldiradi.