Ітератори

Ітератор – це якийсь узагальнений покажчик. Звичайні покажчики мови програмування С + +
є окремим випадком ітераторів, що дозволяють працювати з різними
структурами даних і типами універсальним способом. Будь-який алгоритм
(Універсальна обчислювальна процедура), приймаючи в якості параметрів
ітератори, при їх обробці не замислюється про тип даних, на які
передані ітератори посилаються.


бувають п'яти видів:


вхідні (input);
вихідні (output);
односпрямовані (forward);
двонаправлені (bidirectional);
довільного доступу (random access).

Вхідні ітератори служать для читання адресованих даних. Вихідні, навпаки,
адресують об'єкти, в які дані повинні бути записані. Однонаправлені
ітератори володіють всіма властивостями вхідних і вихідних, а також можуть
переміщатися від початку послідовності адресованих даних в кінець. Що
стосується двонаправлених ітераторів, то вони не тільки володіють властивостями
односпрямований, але й здатні переміщатися в будь-якому напрямку по ланцюжку
даних: як вперед, так і назад. довільного доступу самі
універсальні. Вони володіють функціональністю всіх чотирьох інших ітераторів.
До речі кажучи, покажчики мови Сі + + також є ітераторами довільного
доступу.


Бібліотека STL побудована так, що ітератор більш старшого типу може бути
підставлений замість молодшого. Так, ітератор довільного доступу може замінити
двонаправлений, двонаправлений може бути підставлений замість односпрямованого
і т. д.


Застосовуючи ітератори, важливо враховувати такий елемент, як індикатор кінця
діапазону (end-of-range), тобто елемент, що йде безпосередньо за кінцем
ланцюжка адресованих ітератором даних. Дуже схоже на схему адресації рядків у
мовою Сі + +, коли ознакою кінця рядка є символ "". Але при роботі з
ітераторами індикатором кінця діапазону може бути будь-яке число.


Алгоритми


У бібліотеці STL існує група функцій, які виконують деякі стандартні
дії, наприклад пошук, перетворення, сортування, копіювання і т. д. Вони
називаються алгоритмами. Параметрами для алгоритмів, як правило, служать
ітератори. Алгоритму немає ніякого діла до типу переданого йому ітератора.
Головне, щоб останній підпадав під певну категорію. Наприклад, якщо
параметром алгоритму повинен бути односпрямований ітератор, то підставляється
ітератор повинен бути або односпрямованим, або двонаправленим, або ж
ітератором довільного доступу.


Прикладом алгоритму може служити equal. Він порівнює два ланцюжки даних,
адресованих вхідними ітераторами, і описаний таким чином:

template <class InputIterator1, class InputIterator2>
bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

Перший параметр – вхідний ітератор, який вказує на перший ланцюжок
порівнюваних даних. Другий адресує індикатор кінця діапазону даних. Третій
параметр – друга ланцюжок порівнюваних даних. А ось фрагмент порівняння двох
векторів (масивів) v1 і v2:

bool isEqual = equal(v1.begin(), v1.end(), v2.begin());

Тут використані стандартні методи векторів: begin () повертає ітератор,
налаштований на початок ланцюжка даних, а end () повертає індикатор виходу за
діапазон. Якщо всі елементи векторів попарно рівні один одному, то equal поверне
значення "істина" (true).


Відзначимо, що всі алгоритми можна розділити на дві основні категорії: ті,
які змінюють дані, і ті, які їх не змінюють.


Контейнери


Бібліотека STL має в своєму арсеналі елементи, звані контейнерами.
Контейнери – це об'єкти, що зберігають у собі інші об'єкти. У STL таких
контейнерів десять:


vector – масив з довільним доступом, найчастіше застосовується в тих
випадках, коли треба послідовно додавати дані в кінець ланцюжка;


list – схожий на вектор, але ефективний при додаванні і видаленні даних
в будь-яке місце ланцюжка;


deque – контейнер, зручний для вставки даних на початок або кінець;


set – набір унікальних елементів, відсортованих у певному
порядку;


multiset – те ж, що і set, але може містити повторювані
копії;


map – забезпечує доступ до значень по ключах;


multimap – те ж, що і map, але допускає повторювані ключі;


stack – дані додаються в одному порядку, а виймаються в
зворотному;


queue – дані додаються і виймаються в тому ж порядку;


priority queue – те ж, що і queue, але може сортувати дані по
пріоритету.


Треба відзначити, що всі алгоритми працюють з методами контейнерів, не вдаючись
в деталі їх реалізації. Так, якщо алгоритму потрібно визначити, чи рівний один
елемент з контейнера іншому, він просто викликає перевантажений оператор
порівняння "operator = = ()", реалізований в контейнері.


Функціональні об'єкти


Функціональні об'єкти – це об'єкти, у яких заданий перевантажений оператор
виклику функції "operator ()()". Вони дуже важливі для ефективного використання.
У тих місцях, де передбачається передача покажчиків на функцію, створюється
інтерфейс, що приймає об'єкт з реалізованим перевантаженим оператором виклику
функції. Всі оператори зазвичай пишуться як inline, що дає додатковий
виграш у швидкості.


Функціональними об'єктами є всі арифметичні оператори: складання
(Plus), віднімання (addition), множення (times), ділення (divides), взяття
залишку (modulus) та поводження знака (negate). Є функціональні об'єкти для
обчислення рівності (equal_to), нерівності (not_equal_to), операції "більше"
(Greater), операції "менше" (less), операції "більше або дорівнює"
(Greater_equal), операції "менше або дорівнює" (less_equal). Для логічних
операторів є свої функціональні об'єкти: логічне "і" (logical_and),
логічне "або" (logical_or) і логічне "не" (logical_not).


Як приклад наведена програма (див. лістинг) З
застосуванням бібліотеки STL, що входить до складу пакету Borland C + + Builder. Це
маленький телефонний довідник.


Слід звернути увагу на те, що всі файли, що включаються згадуються без
розширень. h і. hpp. Це новий стиль включення файлів, який, можливо,
незабаром буде застосовуватись у всіх компіляторах мови Сі + +.



Лістинг

 / / Використовуємо контейнер map
# include <map>
/ / Основний включається файл STL
# include <algorithm>
/ / Використовуємо контейнер vector
# include <vector>
# include <iostream.h>
# include <string>
/ / Цей рядок обов'язково повинна бути,
/ / Інакше може статися конфлікт імен
using namespace std;
/ / Оголошуються два відображення
typedef map<string, long, less<string> > friendMap;
typedef map<long, string, less<long> > sortedMap;
/ / Створення імен для типів, які зберігаються в відображеннях
/ / Даних
typedef friendMap::value_type entry_type;
typedef sortedMap::value_type sorted_entry_type;
/ / Вивести в потік запис
void printEntry(const entry_type & entry)
{Cout <<entry.first <<":" <<entry.second <<endl;}
void printSortedEntry(const sorted_entry_type & entry)
{Cout <<entry.first <<":" <<entry.second <<endl;}
/ / Взяти перші цифри телефону
int prefix(const entry_type& entry)
{ return entry.second / 10000; }
/ / Порівняти перші цифри двох телефонів
bool prefixCompare (const entry_type & a, const entry_type & b)
{ return prefix(a) < prefix(b); }
/ / Функціональний об'єкт, що порівнює перші цифри телефонів
class checkPrefix {
public:
checkPrefix (int p) : testPrefix(p) { }
int testPrefix;
bool operator () (const entry_type& entry)
{ return prefix(entry) == testPrefix; }
};
/ / Власне довідник
class telephoneDirectory {
public:
/ / Додати запис
void addEntry (string name, long number)
{ database[name] = number; }
/ / Видалити запис
void remove (string name)
{ database.erase(name); }
/ / Поновити запис
void update (string name, long number)
{ remove(name); addEntry(name, number); }
/ / Показати на екрані всі записи
void displayDatabase()
/ / For_each перебирає всі записи по черзі і викликає
/ / Метод printEntry, який показує чергову запис
{For_each (database.begin (), database.end (), printEntry);}

void displayPrefix(int);

void displayByPrefix();

private:
/ / Тут зберігаються дані у вигляді контейнера set
friendMap database;
};
/ / Вивести всі записи для заданих перших
/ / Цифр телефону
void telephoneDirectory::displayPrefix(int prefix)
{
cout <<"Listing for prefix" <<prefix <<endl;
/ / Створюємо ітератор, що посилається на
/ / Контейнер із записами
map <string, long, less <string>>:: iterator where;
/ / Шукати з початку до кінця всі входження для заданих
/ / Перших цифр телефону
where = find_if (database.begin (), database.end (), checkPrefix (prefix));
while (where != database.end()) {
printEntry(*where);
where = find_if (+ + where, database.end (), checkPrefix (prefix));
}
cout <<"end of prefix listing" <<endl;
}
/ / Друкувати в порядку телефонних номерів
void telephoneDirectory::displayByPrefix()
{
cout <<"Display by prefix" <<endl;
/ / Ще один контейнер set для зберігання
/ / Відсортованих записів
sortedMap sortedData;
/ / Заповнити контейнер, сортуючи дані
for (friendMap::iterator i = database.begin(); i !=
database.end(); i++)
sortedData.insert (sortedMap:: value_type ((* i). second,
(* I). First));
/ / По черзі вивести відсортовані запису
for_each (sortedData.begin (), sortedData.end (), printSortedEntry);
cout <<"end display by prefix" <<endl;
}
/ / Точка входу в програму
int main() {
cout <<"Telephone Directory sample program" <<endl;
telephoneDirectory friends;
/ / Додавання записів в довідник
friends.addEntry("Samantha", 6342343);
friends.addEntry("Brenda", 5436546);
friends.addEntry("Fred", 7435423);
friends.addEntry("Allen", 6348723);
/ / Вивести дані по порядку
friends.displayDatabase();
/ / Вивести телефони, що починаються
/ / З цифри 634
friends.displayPrefix(634);
/ / Вивести дані, відсортувавши їх за номерами
friends.displayByPrefix();
cout <<"End of telephone directory sample program" <<endl;
return 0;
}

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*