STL - це бібліотека стандартних шаблонів. Вона містить, наприклад, що часто зустрічаються способи організації даних - так називані контейнери: динамічні масиви, двонаправленi списки, стеки й ін. Крім того, STL містить безліч алгоритмів що часто зустрічаються: сортування (як на всій безлічі, так і на частині), знаходження мінімального й максимального значень й ін. Кожен такий алгоритм працює з різними типами контейнерів. Ви, наприклад, можете використати той самий алгоритм сортування як для динамічного масиву, так і для стека.
STL складається із трьох основних частин: контейнери, алгоритми й iтератори.
Частина перша. Вона містить різноманітні контейнери. Частина контейнерів зрозуміла і - це динамiчнi масиви, списки, черги й ін. Інша частина більше просунута, якщо можна так виразитися. Сюди, наприклад, ставляться так називані асоціативні контейнери. Основна їхня відмінна риса - це те, що значення, що зберігаються в них, шукаються по ключах. При цьому ключ може бути самим різним. Аналогія такого контейнера з життя - це телефонна книга. Там номера телефонів шукаються на прізвище власника або назви фірми.
У кожному контейнері крім властиво даних є методи для роботи із цими даними (для додавання, пошуку, видалення й ін.).
Друга частина бібліотеки STL - це алгоритми. Алгоритми не є частиною контейнерів, а утворять окрему підсистему. Але при цьому майже будь-який алгоритм може застосовуватися до майже будь-якого контейнеру. Т. е. викликаючи метод для деякого алгоритму, ми викликаємо цей метод сам по собі, а не для екземпляра деякого класу. Контейнер же, до якого застосовується алгоритм, передається як параметр.
І, нарешті, третя частина STL - це різноманітні iтератори. У першому наближенні iтератор - це деякий покажчик, що може оббігати всі елементи контейнера. iтератори грають такі ж ролі, що й індекс в елемента масиву. Через індекс масиву ми можемо одержати деякий елемент масиву, і через iтератор ми можемо одержати деякий елемент контейнера. Iтератори бувають різних типів: для руху тільки вперед, для руху в обидва боки й ін.
Приклад контейнера vector:
Vector є не чим іншим, як динамічним одномірним масивом - тобто ви можете додавати в нього елементи, видаляти їх і т.п.
Ввід приклад використання цього шаблона:
#include <iostream>// Додаємо потрібний простір імен.#include <vector>using namespace std;void main(){ // Повідомляємо вектор із цілих. vector <int> k; // Додаємо елементи в кінець вектора. k.push_back(22); k.push_back(11); k.push_back(4); // Показуємо всі елементи вектора. for (int i = 0; i<k.size(); i++) { cout<<k[i]<<"\n"; } cout<<"***\n"; // Видаляємо елемент із кінця вектора. k.pop_back(); // Показуємо всі елементи вектора. for (i = 0; i<k.size(); i++) { cout<<k[i]<<"\n"; } cout<<"***\n"; // Видаляємо всі елементи вектора k.clear(); // Перевіряємо, що вектор порожній. if(k.empty) { cout<<"Vector is empty\n"; }}Використані методи й змінні шаблона vector (push_back, pop_back, clear й empty) досить ясні з коментарів. Звернете ще увагу, що для доступу до окремих елементiв вектора ми використаємо оператор [] - як і для елементів масиву. Також зверніть увагу, що ми повинні підключити потрібний простір імен (vector).
Виведе цей код, як і слід було сподіватися, спочатку 22, 11 й 4, потім, після видалення останнього елемента вектора, 22 й 11, і потім, після видалення всіх елементів вектора, напис "Vector is empty"
А от ще які класи-контейнери є в STL:
list - двонаправлений список. Доступ до елементів можливий тільки послiдовний із двох сторін списку.
stack - стік.
map - асоціативний список. Зберігає дані у вигляді пари Джерело-Значення (з кожен ключем зв'язане тільки одне значення).
multimap - асоціативний список. Зберігає дані у вигляді пари Джерело-Значення (з кожен ключем зв'язано тільки кілька значень).
set - безліч. Всі його елементи унікальні.
multiset - безліч. У ньому можуть бути співпадаючі елементи.
queue - черга.
deque - двостороння черга.
bitset - набір бiтов (кожний з яких відповідає за відсутність / наявність чого-небудь).
Для використання цих шаблонів ви повинні написати на початку програми потрібний include. Як правило, include пишеться такий же, як ім'я шаблона (так, наприклад, для використання шаблона list треба написати #include ). Два виключення - для використання multimap треба в include додати map і для multiset - set.
Отже: контейнер - шаблон класу, службовець для зберігання даних. Простими словами: контейнер потрібний нам як "обгортка" навколо наших даних, щоб зберігати їх, наприклад, у списку. Такий список можна організувати із чисел float, з рядків string, з об'єктів створеного нами класу (структури), і т.д.
Приклад ітератора:
У першому наближенні iтератор - це покажчик на деякий елемент у контейнері. І, як й у випадку з покажчиками, добратися до елемента контейнера можна через безiменний iтератор.
От приклад коду:
#include <iostream>#include <vector>using namespace std;void main(){ // Повідомляємо вектор із цілих. vector <int> k; // Додаємо елементи в кінець вектора. k.push_back(22); k.push_back(11); k.push_back(4); // Повідомляємо iтератор. vector <int>::iterator p; // Установлюємо iтератор у початок // і пересуваємо його в циклі // на наступну позицію. for (p = k.begin(); p < k.end(); p++) { // Виводимо вміст елементів вектора // через безiменний iтератор. cout<<*p<<"\n"; }}Вихід: 22, 11 й 4.
Iтератор - спеціальний тип, службовець аналогом Си-шного покажчика, використається для проходу за списком, масиву, пошуку елемента в асоціативному списку, і т.д. Це дійсний аналог покажчика, до нього можна застосовувати операції ++ й -- , "зірочку" або -> для одержання значення. Операція ++ зрушує iтератор до наступного елемента динамічного масиву, списку, черги й т.п. Можна порівнювати два iтератора. Замість NULL, ознакою виходу за межі припустимих значень служить спеціальний iтератор, одержаний з контейнера за допомогою функції end().
Приклад алгоритму:
Розглянемо застосування алгоритмів на прикладі сортування елементів вектора.
#include <iostream>#include <vector>#include <algorithm>using namespace std; void main(){ // Повідомляємо вектор із цілих. vector <int> k; // Додаємо елементи в кінець вектора. k.push_back(22); k.push_back(11); k.push_back(4); k.push_back(100); vector <int>::iterator p; // Висновок невідсортованого вектора. for (p = k.begin(); p<k.end(); p++) { cout<<*p<<"\n"; } // Сортування вектора. sort(k.begin(), k.end()); // Висновок відсортованого вектора. cout<<"sorted:\n"; for (p = k.begin(); p<k.end(); p++) { cout<<*p<<"\n"; }}Як ви бачите, головна частина в нашій програмі - це рядок
... // Сортування вектора. sort(k.begin(), k.end()); ...При виклику функції sort ми вказуємо, від якого й до якого елементів ми робимо сортування. У нашому випадку ми сортуємо наш вектор від початку й до кінця.
Результатом виконання програми буде висновок чисел 4, 11, 22, 100 (саме в такому, відсортованому порядку).
Зверніть увагу, що функція sort не належить нашому вектору. Т. е. ми не пишемо щось начебто
... k.sort(...); ...Т. е. наш метод сортування (як й інші алгоритми) утворить окрему підсистему в бібліотеці STL (поряд, наприклад, з контейнерами - тим же вектором, наприклад).
Алгоритм - шаблон функції, що виконує конкретне завдання (пошук, сортування й т.д.) над будь-якими контейнерами. Функція-алгоритм приймає як параметри iтератори або покажчики.
Приклад зберігання об'єктів у списку / динамічному масиві:
#include < list>
#include < vector>
using namespace std;
struct MyStruct
{
int A;
float B;
char C[50];
}
void main()
{
vector < MyStruct> arr;
MyStruct obj;
arr.push_back(obj);
arr[0].A = 123;
list < MyStruct> thelist;
thelist.push_back(obj);
thelist.push_back(obj);
thelist.push_back(obj);
for(list< MyStruct>::iterator i = thelist.begin(); i != thelist.end(); i++)
{
// можна звернутися до структури так:
(*i).A = 123;
// а можна одержати посилання й працювати з нею:
MyStruct &thestruct = *i;
thestruct.B = -0.234;
strcpy(thestruct.C, "Some text");
}
}
приклад організації списка списків, масивів масивів і т.п.
У будь-якому контейнері можна зберігати вкладений контейнер. Для простоти запису, можна використати typedef-и:
#include < list>
#include < vector>
using namespace std;
// відключаємо попередження через занадто довгі імена типів
#pragma warning(disable: 4786)
void main()
{
typedef list< float> ListOfFloat; // список float-ов
typedef list< ListOfFloat> ListOfListOfFloat; // список списків float-ов
// як можна працювати зі списком списків:
ListOfListOfFloat thelist;
// додаємо 2 елементи в список списків:
thelist.resize(2);
// а можна й так:
ListOfFloat thelistinside;
thelistinside.push_back(-0.34f);
thelistinside.push_back(3.45f);
thelist.push_back(thelistinside);
// або от так:
thelist.push_back(ListOfFloat());
// проходимо в циклі по списках - зовнішньому й вкладеному
for(ListOfListOfFloat::iterator i1 = thelist.begin(); i1 != thelist.end(); i1++)
{
// для зручності, одержуємо посилання на вкладений список
ListOfFloat &thelistinside = *i1;
// проходимо по вкладеному списку
for(ListOfFloat::iterator i2 = thelistinside.begin(); i2 != thelistinside.end(); i2++)
{
float value = *i2;
}
}
}
Пояснення:
- створення списку й додавання елементів - за аналогією з vector-ом
- функції resize(), push_front(), clear(), begin() і інших - є в кожному контейнері (в vector-і в тому числі).
- copy(A, B, C) - алгоритм, що копіює всі елементи з контейнера або масиву, на який указує iтератор або покажчик C, у контейнер або масив, на який указують iтераторb або покажчики A й B, причому A указує на перший елемент, B указує на елемент, що перебуває після останнього елемента масиву або контейнера. Для будь-якого контейнера, У можна одержати за допомогою функції end(), для масиву - можна додати розмір масиву до покажчика на перший елемент (наприклад, values + 3).
- итератор ("псевдоуказатель") для кожного контейнера, створюваного нами, має свій відмінний тип. Для того, щоб оголосити iтератор i з контейнера
list< float>,
використається вираження
list< float> ::iterator i.
- як уже говорилося, для одержання значення, на яке вказує iтератор iтератор, використається зірочка: *i. Для переміщення за списком ми просто зрушуємо iтератор операцією ++.
- для того, щоб видалити елемент із "голови" або "хвоста" - використається пара функцій pop_front(), pop_back(). Для видалення довільного елемента використається функція erase(i), де i - це iтератор, що вказує на елемент.
- для вставки елемента в середину списку або масиву використається функція insert(i, v), де v - значення, що вставляє це, i - iтератор, що вказує на елемент, перед яким потрібно вставити значення.