Методів обробка рядкових масивів даних

   ВСТУП

   Актуальність  дослідження. Перший офіційний гід з новоствореної мови С++ з'явився рівно 25 років тому. Тоді ще мало кому відомий Б'єрн (Б'ярне в данській транскрипції) Страуструп 14 жовтня 1985 року представив мову програмування високого рівня, яка дозволяла писати програми для різних комп'ютерів, використовуючи майже незмінний програмний код, який був ближче до мови людей, аніж до машинних кодів.

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

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

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

   Розподілені системи, що функціонують на різних комп'ютерах, також розробляються на мові С++. Цьому сприяє те, що в широко поширених компонентних моделей CORBA і COM є зручні інтерфейси на мові С++.

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

   Об’єкт  дослідження – обробка одновимірних масивів.

   Предметом дослідження – обробка рядкових масивів даних.

   Мета  дослідження – простежити сутність методів обробка рядкових масивів даних.

     Завдання: Дано рядок, який складається з декількох слів які розділені проміжками, речення розділяються крапками (або знаками оклику, або знаками питання), унікальних слів в алфавітному порядку. 

   Джередьну базу курсової склали підручники, періодичні видання, інтернет ресурси.

   Структура та обсяг курсової праці. Робота складається  зі вступу, двох розділів та загального висновку, списку використаних джерел. Загальний обсяг курсової  40 сторінок, з них основного тексту 38. 
 
 
 
 
 
 
 
 
 
 
 

   РОЗДІЛ 1 Мова програмування С++

1. Історичні дані створення мови С++

   Говорячи  про С++ неможливо не згадати її предка – мову програмування С. То ж заглибимося трохи у історію. Почалося все  ще у 1965-1969 роках коли фірма Bell Laboratories разом з General Electric вела розробку операційної системи Multics. Планувалося, що це буде величезна та дуже складна система для великих машин (напр. серії PDP). Але у 1969 році Bell Laboratories вийшла з проекту. Частина співробітників почала роботу над дещо менш амбіційною  але простішою системою – UNIX, оскільки  Multics  будучи занадто складною була вже мертвою на момент свого народження. група під головуванням Кена Томсона ставила за мету створити зручне оточення для досліджень в області програмування. Першу версію було написано на асемблері. Така собі революція пройшла у 1972 році, клои запрошений до роботи тоді ще молодий хакер Деніс Річі разом з другом Брайоном Керінганом було підготовлено перший стандарт мови С, який по першим літерам їх прізвищ було названо «K&R C». У 1989 році було затверджено стандарт ANSI C розроблений компанією AT&T. Серед нововведень був дещо вдосконалений синтаксис та більш жорстка типізація. У 1999 році з’явився стандарт  ANSI C99 у якому з’явилися динамічні масиви, комплексі числа, підтримка Unicode та ін. Стандарт С99 підтриманий рядом компіляторів , що вільно розповсюджуються, у тому числі популярним  GCC. Натомість комерційні компілятори, як наприклад Microsoft Visual C, це розширення не підтримують, а вводять власні розширення та С++. С і досі широко використовується переважно у систематичному програмуванні, а крім того він сильно вплинув на багато інших мов програмування.

   Назва «Сі++» була вигадана Ріком Масситті і вперше було використана в грудні 1983 року. Раніше, на етапі розробки, нова мова називалася «Сі з класами». Ім'я, що вийшло у результаті, походить від оператора Сі «++» (збільшення значення змінної на одиницю) і поширеному способу присвоєння нових імен комп'ютерним програмам, що полягає в додаванні до імені символу «+» для позначення поліпшень. Згідно Страуструпу, «ця назва указує на еволюційну природу змін Cі». Виразом «С+» називали ранішню, не пов'язану з Сі++, мову програмування.

   Деякі програмісти на Сі можуть відмітити, що якщо виконуються вирази x=3; y=x++; то в результаті вийде x=4 і y=3, тому що x збільшується тільки після присвоєння його у. Проте якщо другий вираз буде y=++x; то вийде x=4 і y=4. Виходячи з цього, можна зробити висновок, що логічніше було б назвати мову не Сі++, а ++Сі. Проте обидва вирази c++ і ++c збільшують с, а крім того вираз c++ поширеніший.

   Педанти також можуть відмітити, що введення мови Сі++ не змінює самого Сі, тому найточнішим ім'ям було б «С+1». 

2. Особливості мови С++

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

   Нововведеннями  С++ порівняно з С є:

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

1.3. Технічний огляд мови С++ 

   В 1998 році мова С ++ була стандартизована Міжнародною організацією стандартизації під номером 14882:1998 — Мова Програмування С++. В даний час робоча група МОС працює над новою версією стандарту під кодовою назвою C++09 (раніше відомий як C++0X), який має вийти в 2009 році.

   Стандарт  С++ на 1998 рік складається з двох основних частин: ядра мови і стандартної бібліотеки. Стандартна бібліотека С++ увібрала в себе бібліотеку шаблонів STL, що розроблялася одночасно із стандартом. Зараз назва STL офіційно не вживається, проте в кругах програмістів на С++ ця назва використовується для позначення частини стандартної бібліотеки, що містить визначення шаблонів контейнерів, ітераторів, алгоритмів і функторів.

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

   Поза тим, існує величезна кількість бібліотек С++, котрі не входять в стандарт. У програмах на С++ можна використовувати багато бібліотек Сі.

   Стандартизація визначила мову програмування С++, проте за цією назвою можуть ховатися також неповні, обмежені достандартні варіанти мови. Спочатку мова розвивалася поза формальними рамками, спонтанно, у міру завдань, що ставилися перед ним. Розвиток мови супроводив розвиток кросс-компілятора Cfront. Нововведення в мові відбивалися в зміні номера версії кросс-компілятора. Ці номери версій кросс-компілятора розповсюджувалися і на саму мову, але стосовно теперішнього часу мову про версії мови С++ не ведуть.

Переваги  мови C++

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

  Недоліки мови C++

• Наявність безлічі можливостей, що порушують принципи типобезпеки приводить до того, що в С++- програми може легко закрастися важковловима помилка. Замість контролю з боку компілятора розробники вимушені дотримуватися вельми нетривіальних правил кодування. По суті ці правила обмежують С++ рамками якогось безпечнішої підмови. Більшість проблем типобезпеки С++ успадкована від С, але важливу роль в цьому питанні грає і відмова автора мови від ідеї використовувати автоматичне управління пам'яттю (наприклад, збірку сміття). Так візитною карткою С++ стали вразливості типу "переповнювання буфера".
• Погана підтримка модульності. Підключення інтерфейсу зовнішнього модуля через препроцесорну вставку заголовного файлу (#include) серйозно уповільнює компіляцію, при підключенні великої кількості модулів. Для усунення цього недоліку, багато компіляторів реалізують механізм прекомпіляциі заголовних файлів (англ. Precompiled Headers).
• Недостача інформації про типи даних під час компіляції (CTTI). Мова C++ є складною для вивчення і для компіляції.
• Деякі перетворення типів неінтуїтивні. Зокрема, операція над беззнаковим і знаковим числами видає беззнаковий результат.
• Препроцесор С++ (успадкований від C) дуже примітивний. Це приводить з одного боку до того, що з його допомогою не можна (або важко) здійснювати деякі завдання метапрограмування, а з іншою, в наслідку своєї примітивності, він часто приводить до помилок і вимагає багато дій з обходу потенційних проблем. Деякі мови програмування (наприклад, Scheme і Nemerle) мають набагато могутніші і безпечніші системи метапрограмування (також звані макросами, але макроси С/С++ вони мало нагадують).
• З кінця 20-го століття в співтоваристві С++ набуло поширення так зване метапрограмування на базі шаблонів. По суті, воно використовує особливості шаблонів C++ в цілях реалізації на їх базі інтерпретатора примітивної функціональної мови програмування, що виконується під час компіляції. Сама по собі дана можливість вельми приваблива, але, в наслідку вище згаданого, такий код вельми важко сприймати і відладжувати. Мови Lisp/Scheme, Nemerle і деякі інші мають могутніші і водночас простіші для сприйняття підсистеми метапрограмування. Крім того, в мові D реалізована порівнянна по потужності, але значно простіша в застосуванні підсистема шаблонного метапрограмування.
• Хоча декларується, що С++ мультипарадигмена мова, реально в мові відсутня підтримка функціонального програмування. Частково, даний пропуск усувається різними бібліотеками (Loki, Boost) що використовують засоби метапрограмування для розширення мови функціональними конструкціями (наприклад, підтримкою лямбд/анонімних методів), але якість подібних рішень значно поступається якості вбудованих у функціональні мови рішень. Такі можливості функціональних мов, як зіставлення зі зразком взагалі украй складно емулювати засобами метапрограмування.

  Критика мови C++

  C++ успадкував багато проблем мови C: 

• Операція присвоєння позначається як =, а операція порівняння як == . Їх легко сплутати, і така конструкція буде синтаксично правильною, але приведе до важковломимого багу. Особливо часто це відбувається в операторах if і while, наприклад, програміст може написати if (i=0) замість if (i==0) (Разом з тим, основна маса компіляторів видає в таких випадках попередження.) Уникнути помилку такого типу можна, якщо писати всі операції порівняння у такому вигляді: if (0==i). До того ж багато мов (Бейсик, Паскаль) використовують символ "=" саме в операціях порівняння.
• Операції присвоєння (=), інкрементациі (++), декрементациі (--) та інші повертають значення. У поєднанні з великою кількістю операцій це дозволяє, але не зобов'язує, програміста створювати код, що важко читається. З іншого боку, один з основних принципів мов C і C++ — дозволяти програмістові писати в будь-якому стилі, а не нав'язувати «хороший» стиль. До того ж це іноді дозволяє компілятору створювати оптимальніший код.
• Макроси (#define) є могутнім, але небезпечним засобом. У мові C++, на відміну від C, необхідність в небезпечних макросах з'являється значно рідше завдяки шаблонам і вбудованим функціям. Але в успадкованих стандартних С-бібліотеках багато потенційно небезпечних макросів.

   Дехто вважає недоліком мови C++ відсутність  системи збірки сміття. З іншого боку, в C++ є достатньо засобів (класи  з конструкторами і деструкторами, стандартні шаблони, передача параметрів за посиланням), що дозволяють майже  виключити використання небезпечних вказівників. Проте, відсутність вбудованої збірки сміття дозволяє користувачеві самому вибрати стратегію управління ресурсами. 

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

1.4. Стандартна  бібліотека мови С++ 

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

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

   Так само, як і в Сі, можливості бібліотек активізуються використанням директиви #include для включення стандартних файлів. Всього в стандарті С++ визначено 50 таких файлів.

    STL до включення в стандарт  С++ була сторонньою розробкою,  на початку — фірми HP, а потім  SGI. Стандарт мови не називає її «STL», оскільки ця бібліотека стала невід'ємною частиною мови, проте багато людей до цих пір використовують цю назву, щоб відрізняти її від решти частини стандартної бібліотеки (потоки введення/виводу (Iostream), підрозділ Сі тощо). Проект під назвою STLport, заснований на SGI STL, здійснює постійне оновлення STL, IОstream і рядкових класів. Деякі інші проекти також займаються розробкою приватних застосувань стандартної бібліотеки для різних конструкторських завдань. Кожен виробник компіляторів Сі++ обов'язково поставляє якусь реалізацію цієї бібліотеки, оскільки вона є дуже важливою частиною стандарту і широко використовується.

1.5. Нові можливості в порівнянні з Сі 

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

   У С++ з'явилися коментарі у вигляді  подвійної косої риски («//»), які  були в попереднику Сі — мові BCPL.

   Деякі особливості С++ пізніше були перенесені в Сі, наприклад ключові слова const і inline, оголошення в циклах for і коментарі в стилі С++ («//»). У пізніших реалізаціях Сі також були представлені можливості, яких немає в С++, наприклад макроси vararg і покращена робота з масивами-параметрами. 

1.6. Об'єктно-орієнтовані особливості мови С++ 

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

   Проблеми  старого підходу

   В мові C основним способом організації  даних були структури. Структура складається з набору полів, які ніяк не захищені. Якщо елементи структури мають змінну довжину, їх представляють у вигляді вказівників. Виділення і звільнення пам'яті під ці вказівники робляться вручну. Так, наприклад, одновимірний масив змінної довжини в мові C з перевіркою меж може представлятися таким чином:

   Така  реалізація небезпечна і неефективна  з багатьох причин:

• Необхідно викликати FreeArray і AllocArray. Програміст може забути викликати одну з цих функцій, або викликати її дуже рано/запізно, або двічі, або з вказівником на неправильний масив. Все це приводить до помилок, що важко виявити.
• Функції Elem і ChangeElem повільні.
• Немає ніякого способу перешкодити програмістам створювати і інші функції для роботи із структурою Array. Ці функції можуть робити з полями len і val будь-що.
• Немає ніякого способу перешкодити програмістам безпосередньо міняти поля len і val.
• Присвоєння об'єктів типу struct Array приведе до того, що їх поля val указуватимуть на одну і ту ж область пам'яті. Немає ніякого способу ні заборонити присвоєння, ні змінити таку поведінку.

   Мова  Сі++, використовуючи ООП, усуває всі  ці проблеми.

1.7. Не об'єктно-орієнтовані можливості мови С++ 

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

• Ключове слово inline означає, що функція є хорошим кандидатом на оптимізацію, при якій в місцях звернення до функції компілятор вставить тіло цієї функції, а не код виклику. Приклад: inline double Sqr(double x) {return x*x;}
• Замість функцій malloc і free, введені нові оператори new і delete. Якщо T — довільний тип, то
• new T виділяє пам'ять, достатню для розміщення одного об'єкту типу Т; після завершення виклику оператора, компілятор здійснює ініціалізацію об'єкта (викликаючи його конструктор, якщо такий був визначний) і повертає вказівник типу Т*.
• new T[n] виділяє пам'ять, достатню для розміщення n об'єктів типу Т; після завершення виклику оператора, компілятор здійснює ініціалізацію кожного з n об'єктів і повертає вказівник типу Т*.
• delete p — звільняє пам'ять, на яку посилається вказівник p, виділену для нього раніше операцією new T. Деініціалізація об'єкту (викликаючи деструктора) забезпечується компілятором ще до виклику оператора delete.
• delete [] p — звільняє область пам'яті, виділену для цього масиву раніше операцією new T[n]. Деініціалізація кожного елементу масиву забезпечується компілятором ще до виклику оператора.

   Як  видно, однією з принципових відмінностей операторів new та delete від своїх попередників, malloc і free, є обов'язковість ініціалізації об'єктів, пам'ять під які було призначено. Іншою відмінністю є те, що загальна реалізація (тобто визначена за умовчанням) оператора new не повертає нулеву вартість вказівника в випадку помилки призначення пам'яті (наприклад з причини її браку). Натомість, new кидає виняток (наприклад, std::bad_alloc в ситуації браку пам'яті). Так само як і для free, якщо вартістю аргументу оператора delete є 0, ані звільнення пам'яті, ані деініціація не відбувається (при тому, подібна ситуація не вважається помилковою).

• Функції можуть приймати аргументи за посиланням. Наприклад, функція void f(int& x) {x=3;} присвоює своєму аргументу значення 3. Функції також можуть повертати результат за посиланням, і посилання можуть бути поза всяким зв'язком з функціями. Наприклад, {double&b=a[3]; b=sin(b);} еквівалентно а[3]=sin(а[3]);. Посилання певною мірою схожі з вказівниками, з наступними особливостями: при описі посилання ініціалізувалися вказівкою на існуюче значення даного типу; посилання довічно указує на одну і ту ж адресу; при зверненні до посилання операція читання пам'яті за адресою посилання проводиться автоматично. На відміну від вказівників, посилання не може бути константним саме по собі, однак може посилатися на константний об'єкт. Наприклад, int const & const ref = a[3]; на відміну від int const * const ref = &a[3]; — є некоректним, з точки зору С++, виразом; в свою чергу, і int const & ref = a[3];, і int const * ref = &a[3]; — є цілком прийнятними.
• Можуть бути декілька функцій з одним і тим же ім'ям, але різними типами або кількістю аргументів (перевантаження функцій; при цьому тип значення, що повертається, на перевантаження не впливає). Наприклад, цілком можна писати:

• Один або  декілька останніх аргументів функції  можуть задаватися за умовчанням. Наприклад, якщо функція описана як void f(int x, int y=5, int z=10), виклики f(1), f(1,5) і f(1,5,10) еквівалентні.
• При описі функцій відсутність аргументів в дужках означає, на відміну від Сі, що аргументів немає, а не те, що вони невідомі. Якщо аргументи невідомі, треба користуватися багатокрапкою, наприклад int printf(const char* fmt …). Тип першого аргументу повинен бути заданий.
• Можна описувати оператори над новими типами. Наприклад, так:

   Оператори нічим не відрізняються від (інших) функцій. Не можна описувати оператори  над зумовленими типами (скажімо, перевизначати множення чисел); не можна вигадувати нові операції, яких немає в С++ (скажімо **); арність (кількість параметрів) і пріоритет операцій зберігається (скажімо, у виразі a+b*c спочатку виконуватиметься множення, а потім складання, до яких би типів не належали а, b і с.) Можна перевизначити оператор [] (з одним параметром) і () (з будь-яким числом параметрів).

• Додані простори імен namespace. Наприклад, якщо написати

   то  поза фігурними дужками ми повинні  звертатися до T, x, f, g як Foo::T, Foo::x, Foo::f, Foo::g. Якщо ми в якійсь одиниці трансляції (файл основного коду, наприклад myFile.cpp, та всі заголовкові файли що він  включає) хочемо звертатися до них безпосередньо, ми можемо написати

   Або ж

   Також можна створити синонім на вже  існуючий простір імен (наприклад, аби  уникнути постійно повторювати довгу  назву простору)

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

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

• Доданий новий тип bool, що має значення true і false. Операції порівняння повертають тип bool. Вирази в дужках після if, while приводяться до типу bool.
• // означає, що вся частина рядка, що залишилася, є коментарем.
• Додані шаблони (template). Наприклад, template<class T> T Min(T x, T у) {return x<y?x:y;} визначає функцію Min для будь-яких типів. Шаблони можуть задавати не тільки функції, але і типи. Наприклад, template<class T> struct Array{int len; T* val;}; визначає масив значень будь-якого типу, після чого ми можемо писати Array<float> x;
• Введена стандартна бібліотека шаблонів (STL, англ. Standard Template Library), що визначає шаблони і функції для векторів (одновимірних масивів довільної довжини), множин, асоціативних масивів (map), списків, символьних рядків, потоків введення-виводу і інші шаблони і функції.
• Якщо описана структура, клас (про класи див. нижче), об'єднання (union) або перерахування (enum), її ім'я є ім'ям типу, наприклад:

• Усередині структури або класу можна описувати нові типи, як через typedef, так і через опис інших структур або класів. Для доступу до таких типів поза структурою або класу, до імені типу додається ім'я структури і дві двокрапки:

1.8. Майбутній розвиток мови С++

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

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

   Проте (за станом на час написання цієї статті) серед компіляторів Сі++ все  ще продовжується битва за повну  реалізацію стандарту Сі++, особливо в області шаблонів — частини мови, зовсім недавно повністю розробленій комітетом стандартизації.