Мова програмування С ++

Мова програмування С ++

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

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

Будучи одною з найпопулярніших мов програмування, C ++ широко використовується для розробки програмного забезпечення.  Область його застосування включає створення операційних систем, різноманітних прикладних програм, драйверів пристроїв, додатків для вбудованих систем, високопродуктивних серверів, а також розважальних програм (ігор).  Існує безліч реалізацій мови C ++, як безкоштовних, так і комерційних і для різних платформ.  Наприклад, на платформі x86 це GCC, Visual C ++, Intel C ++ Compiler, Embarcadero (Borland) C ++ Builder і інші.  C ++ зробив величезний вплив на інші мови програмування, в першу чергу на Java і C #.
Синтаксис C ++ успадкований від мови C. Одним з принципів розробки було збереження сумісності з C. Проте, C ++ не є в строгому сенсі надбезліччю C;  безліч програм, які можуть однаково успішно транслюватися як компіляторами C, так і компіляторами C ++, досить велике, але не включає всі можливі програми на C.

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

Поняття  STL

У STL міститься кілька основних сутностей.  Три найбільш важливі з них - це контейнери, алгоритми і ітератори.  Контейнер - це спосіб організації зберігання даних (стек, зв'язний список, черга).  Ще один контейнер - це масив, але він настільки тривіальний і популярний, що вбудований в C ++ і більшість інших мов програмування.  Контейнери бувають найрізноманітніші, і в STL включені найбільш корисні з них.  Контейнери STL підключаються до програми за допомогою шаблонних класів, а значить, можна легко змінити тип збережених в них даних.  Під алгоритмами в STL увазі процедури, застосовувані до контейнерів для обробки їх даних різними способами.  Наприклад, є алгоритми сортування, копіювання, пошуку і об'єднання.  Алгоритми представлені в STL у вигляді шаблонних функцій.  Однак вони не є методами класів-контейнерів.  Навпаки, це абсолютно незалежні функції.  Насправді, однією з найбільш привабливих рис STL є універсальність її алгоритмів.  Їх можна використовувати не тільки в об'єктах класів-контейнерів, а й у звичайних масивах і навіть у власних контейнерах.  (Контейнери, проте, містять методи для виконання деяких специфічних завдань.) Ітератори - це узагальнення концепції покажчиків: вони посилаються на елементи контейнера.  Їх можна інкрементіровать, як звичайні покажчики, і вони будуть посилатися послідовно на всі елементи контейнера.  Ітератори - ключова частина всього STL, оскільки вони пов'язують алгоритми з контейнерами.  Їх можна уявити собі у вигляді кабелю, що зв'язує колонки вашої стереосистеми або комп'ютер з його периферією.

Контейнери у мові програмування C++

Контейнер - це об'єкт, який може містити в собі інші об'єкти.  Існує кілька різних типів контейнерів.  Наприклад, клас vector визначає динамічний масив, deque створює двосторонню чергу, а list являє зв'язний список.  Ці контейнери називаються послідовними контейнерами (sequence containers), тому що в термінології STL послідовність це лінійний список.  STL також визначає асоціативні контейнери (associative containers), які забезпечують ефективне витяг значень на основі ключів.
Таким чином, асоціативні контейнери зберігають пари "ключ / значення".  Прикладом може служити map.  Цей контейнер зберігає пари "ключ / значення", в яких кожен ключ є унікальним.  Це полегшує витяг значення по заданому ключу.

Послідовні контейнери

У послідовних контейнерах дані зберігаються подібно до того, як будинки стоять на вулиці - в ряд.  Кожен елемент зв'язується з іншими за допомогою номера своєї позиції в ряду.  Всі елементи, крім кінцевих, мають по одному сусідові з кожного боку.  Прикладом послідовного контейнера є звичайний масив.  Проблема з масивами полягає в тому, що їх розміри потрібно вказувати при компіляції, тобто у вихідному коді.  На жаль, під час написання програми зазвичай не буває відомо, скільки елементів буде потрібно записати в масив.  Тому, як правило, розраховують на гірший варіант, і розмір масиву вказують «із запасом».  В результаті при роботі програми з'ясовується, що або в масиві залишається дуже багато вільного місця, або все-таки не вистачає осередків, а це може привести до чого завгодно, аж до зависання програми.  У STL для боротьби з такими труднощами існує контейнер vector.  Але з масивами є ще одна проблема.  Припустимо, в масиві зберігаються дані про працівників, і ви відсортували їх за алфавітом відповідно до прізвищами.  Тепер, якщо потрібно буде додати співробітника, прізвище якого починається з букви Л, то доведеться зрушити всіх працівників з прізвищами на М - Я, щоб звільнити місце для вставки нового значення.  Все це може займати досить багато часу.  У STL є контейнер список, який заснований на ідеї зв'язного списку і який вирішує це питання.  Третім представником послідовних контейнерів є чергу з двостороннім доступом.  Це комбінація стека і звичайної черги.  Стек, як ви пам'ятаєте, працює за принципом LIFO (останній увійшов - перший вийшов).  Тобто і введення, і висновок даних в стеку проводиться «зверху».  У черзі ж, навпаки, використовується принцип FIFO (перший прийшов - першим вийшов): дані надходять «зверху», а виходять «знизу».  Черга з двостороннім доступом, треба думати, використовує комбінований порядок обміну даних.  І вносити значення в чергу з двостороннім доступом, і виводити з неї можна по обидва боки.  Це досить гнучкий інструмент, він цінний не тільки сам по собі, але може служити базою для стеків черг, у чому ми незабаром зможемо переконатися.

Асоціативні контейнери

Асоціативний контейнер - це вже дещо інша організація даних.  Дані розташовуються не послідовно, доступ до них здійснюється за допомогою ключів.  Ключі - це просто номери рядків, вони зазвичай використовуються для вибудовування зберігаються елементів в певному порядку і модифікуються контейнерами автоматично.  Прикладом може служити звичайний орфографічний словник, де слова сортуються за алфавітом.  Ви просто вводите потрібне слово (значення ключа), наприклад «кавун», а контейнер конвертує його в адресу цього елемента в пам'яті.  Якщо відомий ключ, доступ до даних здійснюється дуже просто.  У STL є два типи асоціативних контейнерів: безлічі і відображення.  І ті й інші контейнери зберігають дані у вигляді дерева, що дозволяє здійснювати швидку вставку, видалення і пошук даних.  Безлічі і відображення є дуже зручними і при цьому досить універсальними інструментами, які можуть застосовуватися в дуже багатьох ситуаціях.  Але здійснювати сортування і виконувати інші операції, що вимагають випадкового доступу до даних, незручно.  Безлічі простіше і, можливо, через це більш популярні, ніж відображення.  Безліч зберігає набір елементів, що містять ключі - атрибути, які використовуються для впорядкування даних.  Наприклад, безліч може зберігати об'єкти класу person, які упорядковуються в алфавітному порядку.  Як ключ при цьому використовується значення name.  При такій організації даних можна дуже швидко знайти потрібний об'єкт, здійснюючи пошук по імені об'єкта (шукаємо об'єкт класу person по атрибуту name).  Якщо в безлічі зберігаються значення одного з базових типів, таких, як int, ключем є сам елемент.  Деякі автори називають ключем весь об'єкт, що зберігається в безлічі, але ми будемо вживати термін ключовий об'єкт, щоб підкреслити, що атрибут, який використовується для впорядкування (ключ), - це не обов'язково весь елемент даних.  Відображення зберігає пари об'єктів.  Один кортеж в такий «базі даних» складається з двох «атрибутів»: ключовий об'єкт і цільової (асоційований) об'єкт.  Цей інструмент часто використовується в якості контейнера, кілька нагадує масив.  Різниця лише в тому, що доступ до даних здійснюється не за номером елемента, а за спеціальним індексом, який сам по собі може бути довільного типу.  Тобто ключовий об'єкт служить індексом, а цільової - значенням цього індексу.  Контейнери відображення і безліч дозволяють зіставляти тільки один ключ даним значенням.  Це має сенс в таких, наприклад, випадках, як зберігання списку працівників, де кожному імені зіставляється унікальний ідентифікаційний номер.  З іншого боку, мульти відображення і мультимножини дозволяють зберігати кілька ключів для одного значення Наприклад, слову «ключ» в тлумачному словнику можна порівнювати кілька статей.

Контейнерні класи

Кожен контейнер має певний для нього оллокатор (allocator).  Allocator управляє виділенням пам'яті для контейнера.  Оллокатором за замовчуванням є об'єкт класу allocator, але ви можете визначати свої власні оллокатори, якщо це необхідно для спеціалізованих додатків.  Для більшості застосувань оллокатора за замовчуванням цілком достатньо.
Контейнери реалізовані за допомогою шаблонних класів.  Наприклад, нижче показу на специфікація шаблону контейнера deque.  Всі контейнери використовують схожі специфікація: template <class T, class Allocator = allocator <T> class deque Тут узагальнений тип T специфікує тип об'єктів, що зберігаються в deque.  Оллокатор, використовуваний deque, специфікований Allocator;  за замовчуванням це стандартному клас для оллокаторів.  Для переважної більшості додатків ви будете просто застосовувати allocator за замовчуванням, то ж стосується всього коду цієї глави.  Однак ви можете визначати власні типи оллокаторів, коли потрібна спеціальна схема виділення пам'яті.

Ітератори

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

  1. довільного доступу
  2. двох направленого доступу
  3. прямого доступу 
  4. вхідного доступу
  5. вихідного доступу

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

Всі ітератори повинні підтримувати типи операцій з покажчиками, допустимі для їх категорії.  Наприклад, клас вхідного ітератора повинен підтримувати операції ->, ++, *, == і! =.  Більш того, операція * не може використовуватися для надання значення.
На відміну від вхідного, ітератор довільного доступу повинен підтримувати операції ->, +, ++, -, -, *, <,>, <=,> =, - =, + =, ==,! = І []  .
До того ж операція * повинна дозволяти присвоювання.

Алгоритми

Алгоритми виконують дії над контейнерами.  Їх можливості включають ініціалізацію, сортування, пошук, злиття, заміну і трансформацію вмісту контейнера.  Багато алгоритми оперують діапазонами елементів в контейнері.
алгоритми:

 Знову ж, користувацька функція визначає, що саме робити з даними, причому тип повертається нею результату повинен відповідати типу цільового контейнера.

Списки та їх методи

Контейнер STL під назвою список являє собою двічі зв'язаний список, в якому кожен елемент зберігає покажчик на сусіда зліва і справа.  Контейнер містить адресу першого і останнього елементів, тому доступ до обох кінців списку здійснюється дуже швидко.
Методи.
push_front (), front () і pop_front () аналогічні методам pop_back () з векторів.

Вектор, його методи та переваги

Вектори - це, так би мовити, розумні масиви.  Вони займаються автоматичним розміщенням себе в пам'яті, розширенням і звуженням свого розміру в міру вставки або видалення даних.  Вектори можна використовувати в якійсь мірі як масиви, звертаючись до елементів за допомогою звичного оператора [].  Випадковий доступ виконується дуже швидко в векторах.  Також досить швидко здійснюється додавання (або проштовхування) нових даних в кінець вектора.  Коли це відбувається, розмір вектора автоматично збільшується для того, щоб було, куди покласти нове значення.
Так само існує досить велика кількість корисних методів для вектора:

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

Далі буде...