Контейнери

Перед тим, як дати загальне визначення контейнера, спочатку як приклад сконструюємо простий контейнер на базі розглянутого раніше стека символів.

Ми можемо узагальнити стек символів до стека елементів будь-якого типу, оголосивши його як шаблон і замінивши конкретний тип char на параметр шаблону. Наприклад:

 

template<class T> class stack

{

T* v;

int max_size;

int top;

public:

class Underflow {};

class Overflow {};

class Bad_pop {};

stack(int s);

~ stack();

void push(T);

T pop();

};

 

Функції-члени можна визначити таким чином:

 

template<class T> void stack<T>::push(T c)

{

if (top = = max_size) throw Overflow();

v[top]= c;

top = top + 1;

}

template<class T> T stack<T>::pop()

{

if (top = = 0) throw Underflow();

top = top - 1;

return v[top];

}

 

Після цього стек можна використовувати таким чином:

 

stack<char> sc(200); // стек для 200 символів

stack<complex> scplx(30); // стек для 30 комплексних чисел

stack<list<int>> sli(45); // стек для 45 списків цілих чисел

void f()

{

sc.push(‘c’);

if (sc.pop() != ‘c’) throw Bad_pop();

scplx.push (complex(1,2));

if (scplx.pop() != complex(1,2)) throw Bad_pop();

}

 

Як шаблони можна визначити списки, вектори і т. д.

Клас, об'єкти якого можуть містити в собі набір елементів деякого типу, називають класом-контейнером або просто контейнером.

Стандартна бібліотека шаблонів STL надає найзагальніші й найкорисніші типи контейнерів. Основні| з них перелічені в табл. 8.2

 

Таблиця 8.2

Основні| контейнери бібліотеки STL

Контейнер	Призначення
vector<T> list<T> queue<T> stack<T> deque<T> prioryity_queue<T> set<T> multiset<T>   map<Key, val> multimap<Key, val>	Вектор змінного розміру елементів типу <T> Двозвязковий список Черга Стек Черга з двома кінцями Пріоритетна черга Множина Множина, в якій одне значення може зустрічатися кілька разів Асоціативний масив Асоціативний масив, в якому ключ (Key) може зустрічатися кілька разів.

8.4.2 Послідовності та ітератори

У стандартній бібліотеці С++ STL визначене поняття послідовності елементів і є механізм маніпулювання послідовностями за допомогою ітераторів.

Графічне представлення послідовності показано на мал. 8.1

 

Малюнок 8.1 Графічне представлення послідовності з бібліотеки STL

 

Послідовність має початок і кінець. Ітератор посилається на поточний елемент і надає операцію, що примушує його посилатися на наступний елемент послідовності. Кінцем послідовності є ітератор, що посилається на елемент, наступний за останнім елементом послідовності.

Таке визначення послідовності охоплює багато різних представлень, включаючи списки й масиви.

Для доступу до поточного елементу послідовності через ітератор в мові С++ використовується оператор розіменування| * (dereference), а оператор збільшення ++ використовується для того, щоб примусити ітератор посилатися на наступний елемент.

8.4.3 Узагальнені алгоритми

Щоб продемонструвати роботу узагальненого алгоритму, спочатку напишемо наступний код:

 

template<class In, class Out> void copy(In from, In too_far, Out to)

{

while (from != too_far)

{

*to = *from; // копіювання елементу, на який

// указує ітератор

++to; // перехід на наступний елемент контейнера

// у який іде копіювання

++from; // перехід на наступний елемент контейнера

// з якого йде копіювання

}

}

 

Приведений фрагмент копіює будь-який контейнер, для якого визначені ітератори. Вбудовані в С++ типи, такі як вказівники й масиви, мають відповідні операції, тому можна написати:

 

char vc1[200];

char vc2[500];

void f()

{

copy(&vc1[0] &vc1[200], &vc2[0]);

}

 

Всі контейнери стандартної бібліотеки С++ підтримують техніку ітераторів і послідовностей.

Два параметри шаблону In і Out використовуються для завдання типів джерела і приймача, оскільки вони можуть бути різними. Наприклад:

 

complex ас[200];

void g(vector<complex>&vc, list<complex>&lc)

{

copy(&ас[0] &ac[200], lc.begin());

copy(lc.begin(), lc.end(), vc.begin());

}

 

Ця функціякопіює масив у список і список у вектор. В стандартному контейнері begin() – це ітератор, що вказує на його перший елемент, end() – на елемент, наступний за останнім елементом.

У табл. 8.3 перелічені основні| узагальнені алгоритми бібліотеки STL.

 

Таблиця 8.3

Основні| узагальнені алгоритми бібліотеки STL

Функція

Опис

for_each()     find()   find_if()   count()   replace() replace_if()   copy() unique_copy() sort() merge()

Викликає функцію, задану як третій аргумент, для кожного елементу послідовності; має наступний список аргументів: sh.begin(), sh.end(), fun(…) Знаходить у послідовності перше входження аргументу Знаходить у послідовності першу відповідність предикату Підраховує число входжень елементу в послідовність Замінює елемент послідовності новим значенням Замінює елемент послідовності, відповідний предикату, новим значенням Копіює елементи послідовностей Копіює тільки різні елементи послідовностей Сортує елементи послідовностей Зливає відсортовані послідовності

 

Часто доводиться працювати з контейнером вказівників і бажано викликати функції-члени об'єктів, на які вони посилаються, а не функції над вказівниками. Наприклад, нам може знадобитися викликати функцію-член| shape::draw() для кожного елементу списку list<shape*>. Для вирішення цього завдання можна написати функцію – не член класу, яка викликатиме функцію-член| класу. Наприклад:

 

void draw(shape* p)

{

p->draw();

}

void f(list<shape*>&sh)

{

for_each(sh.begin(), sh.end(), draw);

}

 

або натомість:

 

void g(list<shape*> &sh)

{

for_each(sh.begin(), sh.end(), mem_fun(&shape::draw));

}

 

Стандартний бібліотечний шаблон mem_fun() приймає як аргумент вказівник на функцію-член і повертає те, що виробляє ця функція.

Механізм mem_fun() важливий, оскільки дозволяє використовувати стандартні алгоритми для контейнерів з поліморфними об'єктами.

9 СИСТЕМА ВВОДУ-ВИВОДУ МОВИ C++

Система вводу - виводу мови C++ так само, як і система вводу - виводу мови C, діє через потоки вводу – виводу.

Потік вводу - виводу — це логічний пристрій, який видає і приймає призначену для користувача інформацію. Потоки вводу – виводу (streams) мови C++ не слід плутати з потоками інструкцій програми (threads), паралельно виконуваними операційною системою.

Потік вводу - виводу зв'язується з фізичним пристроєм за допомогою системи вводу - виводу C++. Оскільки всі потоки вводу - виводу діють однаково, то не дивлячись на те, що програмісту доводиться працювати з абсолютно різними за характеристиками пристроями, система вводу - виводу надає для цього єдиний зручний інтерфейс.

Наприклад, функція, яка використовується для запису інформації на екран комп'ютера, цілком підійде як для запису інформації у файл на диску, так і для виводу її на принтер.