Namespace CounterNameSpace 5 страница. list<char>::iterator p = lst.begin();

list < char >:: iterator p = lst. begin ();

while (p!= lst .end ()) {

cout << *p << " ";

p++;

}

Тут ітератор р ініціалізувався так, щоб він указував на початок списку. У процесі виконання чергового проходу циклу ітератор р інкрементується, щоб вказувати на наступний елемент списку. Цей цикл завершується, коли ітератор р вказує на кінець списку. Застосування таких циклів – звичайна практика під час використання бібліотеки STL. Наприклад, аналогічний цикл ми застосували для відображення вмісту вектора у попередньому розділі.

Оскільки списки є двоспрямованими, то заповнення їх елементами можна проводити з обох кінців. Наприклад, у процесі виконання наведеної нижче програми створюється два списки, причому елементи одного з них розташовані у порядку, зворотному стосовно іншого.

Код програми 22.7. Демонстрація механізму внесення елементів у список як з початку, так і з кінця

#include <iostream> // Для потокового введення-виведення

#include <list> // Для роботи зі списками

using namespace std; // Використання стандартного простору імен

int main ()

{

list < char > lst; // Створення порожнього списку

list < char > revlst; // Створення порожнього списку

int i;

// Поміщаємо значення у список

for (i=0; i<10; i++) lst. push_back ('A'+i);

// Відображаємо початковий вміст списку

cout << "Розмір списку lst = " << lst. size () << endl;

cout << "Початковий вміст списку: ";

list < char >:: iterator p;

/* Видаляємо елементи із списку lst і поміщаємо їх

у список revlst у зворотному порядку. */

while (! list. empty ()) {

p = lst. begin ();

cout << *p " ";

revlst. push_front (*p);

lst. pop_front ();

}

cout << endl << endl;

// Відображаємо реверсний вміст списку

cout << "Розмір списку revlst = ";

cout << revlst. size () << endl;

cout << "Реверсний вміст списку: ";

p = revlst. begin ();

while (p!= revlst .end ()) {

cout << *p " ";

p++;

}

cout << endl;

getch (); return 0;

}

Внаслідок виконання цієї програми на моніторі буде відображено такі результати:

Розмір списку lst = 10

Початковий вміст списку: A B C D E F G H I J

Розмір списку revlst = 10

Реверсний вміст списку: J I H G F E D C B A

У цій програмі список реверсує шляхом видалення елементів з початку списку lst і занесення їх у початок списку revlst.

22.4.2. Сортування списку

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

Код програми 22.8. Демонстрація механізму сортування списку

#include <iostream> // Для потокового введення-виведення

#include <list> // Для роботи зі списками

#include <cstdlib> // Для використання бібліотечних функцій

using namespace std; // Використання стандартного простору імен

int main ()

{

list < int > lst; // Створення порожнього списку

int i;

// Створення списку випадково вибраних цілих чисел

for (i=0; i<10; i++) lst. push_back (rand ());

// Відображення початкового вмісту списку

cout << "Початковий вміст списку:\n";

list < int >:: iterator p = lst. begin ();

while (p!= lst .end ()) {

cout << *p << " ";

p++;

}

cout << endl << endl;

// Сортування списку.

lst. sort ();

// Відображення відсортованого вмісту списку

cout << "Відсортований вміст списку:\n";

p = lst. begin ();

while (p!= lst .end ()) {

cout << *p << " ";

p++;

}

cout << endl;

getch (); return 0;

}

Ось як може виглядати один з можливих варіантів виконання цієї програми.

Початковий вміст списку:

41 18467 6334 26500 19169 15724 11478 29358 26962 24464

Відсортований вміст списку:

41 6334 11478 15724 18467 19169 24464 26500 26962 29358

22.4.3. Об'єднання одного списку з іншим

Один впорядкований список можна об'єднати з іншим. Як результат ми отримаємо впорядкований список, який охоплює вміст двох початкових списків. Новий список залишається у списку, який його викликає, а другий список стає порожнім. У наведеному нижче прикладі виконується об'єднання двох списків. Перший список містить букви ACEGI, а другий – букви BDFHJ. Ці списки потім об'єднуються, внаслідок чого утворюється впорядкована послідовність букв ABCDEFGHIJ.

Код програми 22.9. Демонстрація механізму об'єднання двох списків

#include <iostream> // Для потокового введення-виведення

#include <list> // Для роботи зі списками

using namespace std; // Використання стандартного простору імен

int main ()

{

list < char > lst1, lst2; // Створення двох порожніх списків

int i;

// Створення двох списків з випадково вибраними цілими числами

for (i=0; i<10; i+=2) lst1. push_back ('A'+i);

for (i=1; i<11; i+=2) lst2. push_back ('A'+i);

// Відображення початкового вмісту першого списку

cout << "Вміст списку lst1: ";

list < char >:: iterator p = lst1. begin ();

while (p!= lst1 .end ()) {

cout << *p;

p++;

}

cout << endl << endl;

// Відображення початкового вмісту другого списку

cout << "Вміст списку lst2: ";

p = lst2. begin ();

while (p!= lst2 .end ()) {

cout << *p;

p++;

}

cout << endl << endl;

// Тепер об'єднуємо ці два списки.

lst1. merge (lst2);

if (lst2. empty ()) cout << "Список lst2 тепер порожній.\n";

// Відображення об'єднаного вмісту першого списку

cout << "Вміст списку lst1 після об'єднання:\n";

p = lst1. begin ();

while (p!= lst1 .end ()) {

cout << *p << " ";

p++;

}

cout << endl;

getch (); return 0;

}

Результати виконання цієї програми є такими:

Вміст списку lst1: ACEGI

Вміст списку lst2: BDFHJ

Список lst2 тепер порожній.

Вміст списку lst1 після об'єднання:

A B C D E F G H I J

22.4.4. Зберігання у списку об'єктів класу

Розглянемо приклад, у якому список використовують для зберігання об'єктів типу myClass. Звернемо Вашу увагу на те, що для об'єктів типу myClass перевантажено оператори "<", ">", "!=" і "==". Для деяких компіляторів може виявитися зайвим визначення всіх цих операторів, або ж доведеться додати деякі інші з них. У бібліотеці STL ці функції використовуються для визначення впорядкування і рівності об'єктів у контейнері. Хоча список не є впорядкованим контейнером, необхідно мати засіб порівняння елементів, який застосовується у процесі їх пошуку, сортування або об'єднання.

Код програми 22.10. Демонстрація механізму зберігання у списку об'єктів класу

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <list> // Для роботи зі списками

#include <cstring> // Для роботи з рядковими типами даних

using namespace std; // Використання стандартного простору імен

class myClass { // Оголошення класового типу

int a, b;

int sum;

public:

myClass() { a = b = 0;}

myClass(int izm, int jzm) { a = izm; b = jzm; sum = ф + b;}

int getSum() { return sum;}

friend bool operator <(const myClass &a_ob, const myClass &b_ob);

friend bool operator >(const myClass &a_ob, const myClass &b_ob);

friend bool operator ==(const myClass &a_ob, const myClass &b_ob);

friend bool operator!=(const myClass &a_ob, const myClass &b_ob);

};

bool operator <(const myClass &a_ob, const myClass &b_ob)

{ return a_ob.sum < b_ob.sum; }

bool operator >(const myClass &a_ob, const myClass &b_ob)

{ return a_ob.sum > b_ob.sum; }

bool operator ==(const myClass &a_ob, const myClass &b_ob)

{ return a_ob.sum == b_ob.sum; }

bool operator!=(const myClass &a_ob, const myClass &b_ob)

{ return a_ob.sum!= b_ob.sum; }

int main ()

{

int i;

list <myClass> lst1; // Створення першого списку.

for (i=0; i<10; i++) lst1. push_back (myClass(i, i));

cout << "Перший список: ";

list <myClass>:: iterator p = lst1. begin ();

while (p!= lst1 .end ()) {

cout << p->getSum() << " ";

p++;

}

cout << endl;

list <myClass> lst2; // Створення другого списку.

for (i=0; i<10; i++) lst2. push_back (myClass(i*2, i*3));

cout << "Другий список: ";

p = lst2. begin ();

while (p!= lst2 .end ()) {

cout << p->getSum() << " ";

p++;

}

cout << endl;

// Тепер об'єднуємо списки lst! і lst2.

lst1. merge (lst2);

// Відображаємо об'єднаний список.

cout << "Об'єднаний список: "; p = lst1. begin ();

while (p!= lst1 .end ()) {

cout << p->getSum() << " ";

p++;

}

cout << endl;

getch (); return 0;

}

Ця програма створює два списки об'єктів типу myClass і відображає їх вміст. Потім виконується об'єднання цих двох списків з подальшим відображенням нового вмісту остаточного списку. Отже, програма відображає на екрані такі результати:

Перший список: 0 2 4 6 8 10 12 14 16 18

Другий список: 0 5 10 15 20 25 30 35 40 45

Об'єднаний список: 0 0 2 4 5 6 8 10 10 12 14 15 16 18 20 25 30 35 40 45

22.5. Поняття про відображення

Клас map підтримує асоціативний контейнер, у якому унікальним ключам відповідають певні значення. По суті, ключ – це просто ім'я, яке присвоєне певному значенню. Після того, як значення збережено у контейнері, до нього можна отримати доступ, використовуючи його ключ. Таким чином, в найширшому сенсі відображення – це список пар "ключ-значення". Якщо нам відомий ключ, то ми можемо легко знайти значення. Наприклад, ми могли б визначити відображення, у якому як ключ використовують ім'я людини, а як значення – його телефонний номер. Асоціативні контейнери стають все більш популярними у програмуванні.

Відображення – це асоціативний контейнер.

Як ми вже зазначали вище, відображення може зберігати тільки унікальні ключі. Ключі-дублі­ка­ти не дозволені. Щоб створити відображення, яке б давало змогу зберігати не унікальні ключі, використовується клас multimap.

Контейнер map має наступну шаблонну специфікацію.

template < class Key, class myType, class Сomp = less <Key>,

class Allocator = allocator < pair < const Key myType>>> class map

Тут Key – тип даних ключів, myType – тип значень, що зберігаються (що відображаються), а Сomp – функція, яка порівнює два ключі. За замовчуванням як функція порівняння використовується стандартна функція-об'єкт less. Елемент Allocator означає розподільник пам'яті, який за замовчуванням використовує стандартний розподільник allocator. Клас map має такі конструктори:

explicit map (const Сomp &cmpfn = Сomp (),

const Allocator & a = Allocator ());

map (const map <Key, myType, Сomp Allocator > & ob >);

template < class InIter > map (InIter start, InIter end,

const Сomp &cmpfn = Сomp (), const Allocator & a = Allocator ());

Перша форма конструктора створює порожнє відображення. Друга призначена для створення відображення, яке містить ті самі елементи, що і відображення ob. Третя створює відображення, яке містить елементи у діапазоні, заданому ітераторами start і end. Функція, задана параметром cmpfn (якщо вона задана), визначає характер впорядкування відображення.

У загальному випадку будь-який об'єкт, який використовується як ключ, повинен визначати конструктор за замовчуванням і перевантажувати оператор "<" (а також інші необхідні оператори порівняння). Ці вимоги для різних компіляторів різні.

Для класу map визначено такі оператори порівняння:

==, <, <=,!=, > i >=.

Функції-члени, визначені для класу map, представлено в табл. 22.4. В їх описі під елементом key_type розуміють тип ключа, а під елементом value_type значення виразу pair <Key, myType>.

Пари "ключ-значення" зберігаються у відображенні як об'єкти класу pair, який має таку шаблонну специфікацію:

template < class kType, class vType > struct pair {

typedef kType first _type; // Тип ключа

typedef vType second _type; // Тип значення

kType first; // Містить ключ

vType second; // Містить значення

// Оголошення конструкторів

pair ();

pair (const kType & k, const vType & v);

template < class A, class B> pair (const <A, B> & ob);

}

Як зазначено у коментарях до цього фрагменту програми, член first містить ключ, а член second – значення, що відповідає цьому ключу.

22.5.1. Робота з відображеннями

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

template < class kType, class vType>

pair < kType, vType > make_pair (const kType &k, const vType &v);

Табл. 22.4. Функції-члени, визначені у класі map

Функція-член	Призначення
iterator begin(); const_iterator begin() const;	Повертає ітератор для першого елемента у відображенні
void clear();	Видаляє всі елементи з відображення
size_type count( const key_type & k) const;	Повертає кількість входжень ключа k у відображенні (1 або 0)
bool empty() const;	Повертає значення true, якщо це відображення порожнє, і значення false – в іншому випадку
iterator end(); const_iterator end() const;	Повертає ітератор, який вказує на кінець відображення
pair<iterator, iterator> equal_range(const key_type &k); pair<const_iterator, const_iterator> equal_range( const key_type &k) const;	Повертає пару ітераторів, які вказують на перший і останній елементи у відображенні, що містять заданий ключ
void erase(iterator i);	Видаляє елемент, на який вказує ітератор i
void erase(iterator start, iterator end);	Видаляє елементи у діапазоні, що задаються параметрами start і end
size_type erase( const key_type & k);	Видаляє з відображення елементи, ключі яких мають значення k
iterator find(const key_type & k); const_iterator find( const key_type &k) const;	Повертає ітератор, який відповідає заданому ключу. Якщо такий ключ не виявлено, то повертає ітератор, який відповідає кінцю відображення
allocator_type get_allocator() const;	Повертає розподільник пам'яті відображення
iterator insert(iterator i, const value_type &val);	Вставляє значення val у позицію елемента (або після нього), що задається ітератором i. Повертає ітератор, який вказує на цей елемент
template<class InIter> void insert(InIter start, InIter end);	Вставляє елементи заданого діапазону
pair<iterator, bool> insert(const value_type &val);	Вставляє значення val у відображення, що викликається. Повертає ітератор, який вказує на цей елемент. Елемент вставляється тільки у тому випадку, якщо його ще немає у відображенні. Якщо елемент було вставлено, то повертає значення pair<iterator, true>, інакше – значення pair<iterator, false>
key_compare key_Сomp() const;	Повертає об'єкт-функцію, яка порівнює ключі
iterator lower_bound( const key_type &k); const_iterator lower_bound( const key_type &k) const;	Повертає ітератор для першого елемента у відображенні, ключ якого дорівнює значенню k або більше за це значення
size_type max_size() const;	Повертає максимальну кількість елементів, яку може містити це відображення
reference operator[]( const key_type &i);	Повертає посилання на елемент, які задаються параметром i. Якщо цього елемента не існує, то вставляє його у відображення
reverse_iterator rbegin(); const_reverse_iterator rbegin() const;	Повертає реверсивний ітератор, який відповідає кінцю відображення
reverse_iterator rend(); const_reverse_iterator rend() const;	Повертає реверсивний ітератор, який відповідає початку відображення
size_type size() const;	Повертає поточну кількість елементів у відображенні
void swap(map<Key, myType, Сomp Allocator> &ob);	Виконує обмін елементами відображення, що викликається, і відображення ob|
iterator upper_bound( const key_type &k); const_iterator upper_bound( const key_type &k) const;	Повертає ітератор для першого елемента у відображенні, ключ якого є більшим від заданого значення k
value_compare value_Сomp() const;	Повертає об'єкт-функцію, яка порівнює значення

Як бачите, функція make_pair () повертає парний об'єкт, який складається із значень, типи яких задано параметрами kType і vType. Перевага використання функції make_pair () полягає у тому, що типи об'єктів, які об'єднуються у пару, визначаються автоматично компілятором, а не безпосередньо задаються програмістом.

Можливості використання відображення продемонстровано у наведеному нижче коді програми. У цьому випадку у відображенні зберігається 10 пар "ключ-значення". Ключем слугує символ, а значенням – ціле число. Пари "ключ-значення" зберігаються так:

А 0

В 1

С 2

і т.д. Після збереження пар у відображенні користувачу пропонується ввести ключ (тобто букву з діапазону A-J), після чого виводиться значення, пов'язане з цим ключем.

Код програми 22.11. Демонстрація механізму використання простого відображення

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <map> // Для роботи з асоціативними контейнерами

using namespace std; // Використання стандартного простору імен

int main ()

{

map < char, int > mzm; // Створення порожнього відображення.

int i;

// Поміщаємо пари у відображення.

for (i=0; i<10; i++) {

mzm. insert (pair < char, int >('A'+i, i));

}

char ch;

cout << "Введіть ключ: "; cin >> ch;

map < char, int >:: iterator p;

// Знаходимо значення за заданим ключем.

p = mzm. find (ch);

if (p!= mzm .end ()) cout << p-> second;

else cout << "Такого ключа у відображенні немає.\n";

getch (); return 0;

}

Звернемо Вашу увагу на використання шаблонного класу pair для побудови пар "ключ-значення". Типи даних, що задаються pair -виразом, повинні відповідати типам відображення, в які вставляються ці пари.

Після ініціалізації відображення ключами і значеннями можна виконувати пошук значення за заданим ключем, використовуючи функцію find (). Ця функція повертає ітератор, який вказує на потрібний елемент або на кінець відображення, якщо заданого ключа не було знайдено. Внаслідок виявлення збігу значення, пов'язаного з ключем, можна знайти в члені second парного об'єкта типу pair.

У попередньому прикладі пари "ключ-значення" створювалися безпосередньо за допомогою шаблону pair < char, int >. І хоча у цьому немає нічого неправильного, часто простіше використовувати з цією метою функцію make_pair (), яка створює pair -об'єкт на основі типів даних, що використовуються як параметри. Наприклад, цей рядок коду програми також дасть змогу вставити у відображення mzm пари "ключ-значення" (під час використання попередньої програми):

mzm. insert (make_pair ((char)('A'+izm), izm));

У цьому записі, як бачите, виконується операція приведення до типу char, яка необхідна для перевизначення автоматичного перетворення в тип int результату додавання значення i з символом 'А'.

22.5.2. Зберігання у відображенні об'єктів класу

Подібно до всіх інших контейнерів, відображення можна використовувати для зберігання об'єктів, створюваних Вами типів. Наприклад, наведений нижче код програми створює простий словник на основі відображення слів з їх значеннями. Але спочатку вона створює два класи word і meaning. Оскільки відображення підтримує відсортований список ключів, програма також визначає для об'єктів типу word оператора "<". У загальному випадку оператор "<" необхідно визначати для будь-яких класів, які Ви плануєте використовувати як ключі. Деякі компілятори можуть зажадати визначення і інших операторів порівняння.

Код програми 22.12. Демонстрація механізму використання відображення для створення словника

#include <vcl>

#include <iostream> // Для потокового введення-виведення

#include <conio> // Для консольного режиму роботи

#include <map> // Для роботи з асоціативними контейнерами

#include <cstring> // Для роботи з рядковими типами даних

using namespace std; // Використання стандартного простору імен

class word {

char strMas[20];

public:

word() { strcpy (strMas, "");}

word(char *s) { strcpy (strMas, s);}

char * get () { return strMas;}

};

bool operator <(word a_ob, word b_ob)

{

return strcmp (a_ob. get (), b_ob. get ()) < 0;

Дата добавления: 2014-11-29