Loading…
43
Transcript
Стандартна бібліотека шаблонів STL
<щочтЩЩВизначення п1 >
Що таке бібліотека STL?
Стандартна бібліотека шаблонів (Standard Template Lіbrary – STL) - бібліотека, що побудована на шаблонах класів і функцій, що забезпечує можливість уніфікованої роботи з різними типами даних
Ядро STL складається з 4-х основних компонентів:
Контейнери
Ітератори
Алгоритми
Розподільники пам'яті
Взаємозв'язок основних компонентів STL
<Взаємозв'язок основних компонентів STL>
Концепція STL заснована на поділі даних і операцій. Дані знаходяться під керуванням контейнерних класів, а операції визначаються адаптуємими алгоритмами. Ітератори виконують функції «клею», пов’язуючи ці два компоненти. Завдяки їм будь-який алгоритм може працювати з будь-яким контейнером.
Компоненти
STL
<Копое2>
Існує сім основних типів і три похідних
Контейнери
<Контейнери>
Послідовні контейнери
Послідовні
Вектори
Вектори
масиви довільного розміру.
+ Підтримують швидкий доступ за номером елемента, швидке додавання і видалення в кінці.
- Повільно - додавання і видалення в середині.
Списки
+ Швидкі додавання і вставка.
- Повільний доступ до середини масиву
Списки
Двосторнні черги
Двосторонні черги
+ Швидке додавання і видалення в будь-якому кінці, доступ за номером.
- Повільне додавання і видалення з середини.
може тільки збільшуватися (++)
може як збільшуватися (++), так і зменшуватися (- -)
може переміщатися на довільне число елементів (+ n, - k)
вказує на вхідний потік і може зчитувати дані в контейнер (використовується тільки для читання)
<Ітератори>
Ітератори
вказує на вихідний потік і виводить елементи (використовується тільки для запису)
Алгоритми - шаблонні функції, які працюють з контейнерами через ітератори
Алгоритми
<Алгоритми>
Зазвичай алгоритм отримує в якості параметрів початок і кінець оброблюваної послідовності
Різним алгоритмах потрібні різні типи ітераторів, наприклад, сортування вимагає ітератор довільного доступу (тому працює тільки з векторами і деками), а копіювання - прямий ітератор.
Асоціативні контейнери
Асоціативні контейнери реалізовані на основі збалансованих дерев
<3>
1
Безлічі - зберігає набір елементів, що містять ключі-атрибути, використовувані для упорядкування даних
2
Словник зберігає пари об'єктів - ключ + будь-який об'єкт.
Контейнери з дублікатами підтримують повторювані ключі.
3
Види АК
<Види АК>
Приклад
<Приклад>
Переваги та недоліки STL
Переваги
Недоліки
<4>
Переваги
Для кожного контейнера можна визначити додаткові ітератори і інтерфейси, що дозволить оптимально налаштувати його для вирішення конкретного завдання.
4
Кожен контейнер забезпечує стандартний інтерфейс у вигляді набору операцій, так що один контейнер може використовуватися замість іншого, причому це не тягне істотної зміни коду.
1
Контейнери за визначення однорідні, тобто повинні містити елементи одного типу, але можливе створення різнорідних контейнерів як контейнерів покажчиків на загальний базовий клас.
5
Додаткова спільність використання забезпечується через стандартні ітератори.
Переваги
2
Алгоритми, що входять до складу STL, призначені для роботи з вмістом контейнерів. Всі алгоритми являють собою шаблонні функції, отже, їх можна використовувати для роботи з будь-яким контейнером.
Кожен контейнер пов'язаний з розподільником пам'яті - аллокатором, який можна перевизначити з тим, щоб реалізувати власний механізм розподілу пам'яті.
6
3