Категорія Архіви: Бібліотеки C ++

Робота з файлами в C++. Частина 2 – бібліотека fstream.




клас ofstream

зворотний класу ifstream, який ми розглянули раніше, і покликаний для запису в файл.

Як і в ifstream, для відкриття або створення файлу використовується конструктор або метод ВІДЧИНЕНО().

або конструктором:

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

За перевірку на відкритість файлу відповідає все та ж is_open()

Принцип той же. Так само можна перевірити чи відкритий файл, використавши в логічному вираженні саму файлову змінну:

оператор <<

Перенаправляє форматований вивід в файл. Принцип той же, що і у аналога з iostream.

Призначений для виведення в текстові файли. Управляється операціями форматування такими як ширина() или SETF(). Їх аналоги повністю рівні однойменною методам з iostream.

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

оператор endl

Аналогічно оператору з iostream проводить запис перекладу каретки на новий рядок в текстових файлах.

метод write

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

Цей метод приймає два параметри: Покажчик на блок даних і кількість байт, який цей блок займає. У прикладі рядок займає strlen() байт, ціле sizeof() (яке дасть 4 на 32-х бітних операционках для цілого і 8 для речового).

Ще раз варто акцентувати, що на відміну від форматированного виведення оператором <<, метод запис() не виводить дані в текстовому поданні.

метод близько

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

такий “відкладений” слив називається “коммітов” (від латинського commit). До речі цим ефектом вельми вдало користуються системи управління базами даних, де вставляються записи потрапляють в сховище в пам'яті (званої транзакцією). І тільки після спеціальної команди скопом пишуться в сам файл бази. метод близько() якраз приклад такої команди закриває транзакцію разом з файлом.

Варто про всяк випадок згадати, що якщо потрібно зробити Комміт даних без закриття самого файлу, потрібно застосувати метод врівень()

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

Методи форматування width, точність

як і в iostream, для красивої розмітки даних в файлі можуть застосовуватися методи форматування даних для виведення оператором << .

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

 

Методи позиціонування seekp, tellp

Для переходу по файлу як і у випадку з ifstream існує функція перестановки позиції. називається вона seekp() і отримує ті ж параметри що і описані вище для seekg().

Для отримання поточної позиції в байтах від початку файлу використовується аналогічна функція tellp().

Відео про роботу з файлами в С ++:

Нові уроки з програмування:

Робота з файлами в C++. Частина 1 – бібліотека fstream.




заголовок fstream надає функціонал для зчитування даних з файлу і для запису в файл. В цілому він дуже схожий на хедер iostream, який працює з консоллю, оскільки консоль це теж файл. Тому всі основні операції такі ж, за дрібними відмінностями, як в попередній темі по iostream.

Найбільш часті операції наступне:

  1. Оператори перенаправлення вводу виводу – << і >>
  2. Методи запису і читання рядків getline() і get() c ставити()
  3. Передача потокового запис і читання методами запис() і зчитування()
  4. Методи відкриття створення і закриття файлів ВІДЧИНЕНО() і близько()
  5. Методи перевірки чи відкритий файл is_open() і чи досягнуто кінець файлу ВФ()
  6. Налаштування форматированного виведення для >> за допомогою ширина() і точність()
  7. операції позиціонування tellg(), tellp() і seekg(), seekp()

Це не всі можливості, які надає бібліотека fstream. Розглядати всі зараз ми не будемо, оскільки їх коло застосування досить вузький. Познайомимося з вищепереліченими. Почнемо з класу читання.

клас ifstream

Надає можливості для читання файлів. Відкрити файл можна двома способами: викликавши метод ВІДЧИНЕНО() або вказавши шлях до нього в конструкторі. Вам необхідно підготувати текстовий файл, перед тем, як почати набирати код. На диску d створіть папку з ім'ям 1 і в ній створіть файл з розширенням txt – “файл.txt”.

Відкриття файлу в конструкторі виглядає так:

Так ми просимо відкрити файл txt з ім'ям файл.txt, який лежить в папці з назвою 1, а папка знаходиться на диску d.

Використання методу open() зручно, якщо програміст не хоче відразу прив'язуватися до файлу. Раптом потрібно властивість класу або глобальну змінну, ну а відкривати файл вже потім. Якщо ж потрібно відкрити файл всередині якоїсь функції, попрацювати з ним і закрити, то можна прописати шлях до файлу прямо в конструкторі. Загалом залежить від ситуації.

відкривши файл, бажано прописати перевірку: відкрився він? Так як є ряд причин, за якими файл може не відкритися, а ми цього не побачимо. Наприклад, файлу з вказаним ім'ям немає в прописаної папці або шлях вказано невірно. Можна піти двома шляхами: перевірити змінну файлу в логічному вираженні (застосувавши оператор “!”, наприклад) або використовувати метод is_open() :

Так все відпрацює нормально і файл відкриється:

fstream бібліотека, робота з файлами в с ++, програмування для початківцівТепер спробуйте вписати назву папки НЕ 1, а 2 ifstream файл ("d:\\<стиль діапазон ="колір: #ff0000;"><сильний>2</сильний>\\файл.txt”); і знову запустіть програму. Так як папки з вказаним ім'ям ми не створювали, то і файл, естественно, не може бути відкритий:

fstream бібліотека, робота з файлами в с ++, програмування для початківців

Другий варіант перевірки з використанням методу is_open() :

метод is_open() вернет 1, якщо файл знайдений і успішно відкритий. інакше поверне 0 і спрацює код прописаний в блоці else.

Якщо файл не відкритий – бажано обробити помилку. Як правило, якщо вся робота програми пов'язана з файлом пишуть якесь повідомлення в консоль, і ставлять вихід з програми. При серйозні помилки прийнято повертати якийсь код виконання (число), який буде характеризувати ту чи іншу помилку. Коди для кожного виду помилок автор програми може придумувати свої. Один із способів обробки помилок в програмі ми розглядали в статті Винятки в С ++.

Якщо файл успішно відкритий, з нього можна зчитувати.

оператор зчитування >>

Так само як і в iostream зчитування можна організувати оператором >>, який вказує в яку змінну буде вироблено зчитування:

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

До речі цей оператор досить зручний, якщо стоїть завдання розділити файл на слова:

Методы getline() і отримати()

Зчитування цілого рядка до перекладу каретки проводиться так само як і в iostream методом getline(). Причому рекомендується використовувати його перевизначення версію у вигляді функції, якщо зчитується рядок типу string:

Якщо ж читати потрібно в масив символів char[], то або get() либо getline() саме як методи:

Принцип в загальному той же, що і в аналогах з iostream: Вказується в параметрах буфер (переменная, куди буде проводитися читання), або точніше покажчик на блок пам'яті (якщо змінна оголошена статично: буфер символ[255] наприклад, то пишеться в параметри &буфер), вказується максимальна кількість зчитуваного (в прикладі це n), щоб не сталося переповнення і вихід за межі буфера і в разі потреби символ-роздільник, до якого буде зчитування (в прикладі це пробіл). Сподіваюся я не боляче наступлю на хобот фанатикам Сі, якщо сажу що ці дві функції на 99% взаємозамінні, і на 95% можуть бути замінені методом зчитування().

метод зчитування()

Схожий на попередній приклад?

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

метод близько()

закриває файл. Навіть додати нічого. Єдина мабуть ремарка – від того, що файл, відкритий для читання, не буде закритий цим методом як правило гірше не стане. Дуже рідкісні ситуації, коли відкритий для читання файл псується, якщо завершити програму не закриваючи файл. Пов'язана ця псування насамперед з нестандартними пристроями типу стримерів на магнітній стрічці або яких небудь потокових хитрих промислових контролерів, але по феншую варто запам'ятати – відкритий файл повинен бути закритий. Це вважається хорошим тоном.

метод ВФ()

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

метод seekg()

Виробляє установку поточної позиції в потрібну, що вказується числом. У цей метод так само передається спосіб позиціонування:

  • ios_base::end – Відрахувати нову позицію з кінця файлу
  • ios_base::благати – Відрахувати нову позицію з початку файлу (абсолютне позиціонування)
  • ios_base::дворняжка – Перескочити на n байт починаючи від поточної позиції у файлі (по умолчанию)

метод tellg()

Іноді потрібно отримувати інформацію про те, скільки вже прочитано. У цьому допоможе метод tellg():

Він повертає значення типу int, яке показує скільки вже пройдено в байтах. Його можна використовувати в парі з методом seekg(), щоб отримувати розмір файлу:

Як приклад роботи методів бінарного читання можна розібрати такий класс:

Подібні обгортки-класи зручно використовувати, якщо зустрічається завдання читати з бінарного файлу цілі структури.

Відео про роботу з файлами в С ++:

Нові уроки з програмування:

SQRT() - Функція бібліотеки cmath




SQRT( значення );

функція sqrt() бібліотеки cmath (math.h) приймає параметр value і повертає його квадратний корінь.

якщо параметр ( в нашем случае – значення) негативний, виникає помилка.

Результат виконання показаний в онлайн компіляторі ideone

приклад роботи функції sqrt c ++

Нові уроки з програмування:

бух() - Функція бібліотеки cmath




бух(a, b);

функція POW() бібліотеки cmath приймає два параметри: a, b. Перше число a (базове) зводиться до степеня b.

Повертає значення ab .

Результат виконання 23 , 53, 52 :

бух () - функція бібліотеки cmath

 

Нові уроки з програмування:

fma () – функція бібліотеки cmath




fma(a, b, c);

Функція fma() бібліотеки cmath приймає три параметри: a, b – значення для множення, c – значення для додавання.

Повертає значення a * b + c.

Результат виконання ( 2 * 2 + 3):

fma () - функція бібліотеки cmath

Нові уроки з програмування:

Дороговкази в контейнерах. STL (частина 16)




покажчики в контейнерах, STL, програмування для початківців

Контейнери STL істотно знижують складність написання коду, працюючого з динамічними структурами даних і, найголовніше, підвищують його безпомилковість. Але в деяких випадках, при роботі з великими елементами даних в контейнерах, ця техніка може породжувати неминучу втрату продуктивності. Это связано с тем, що починаючи з операції приміщення елемента в контейнер, і всі наступні переміщення елементів можуть вимагати копіювання елементів.

Примітка: Ступінь вираженості таких ефектів залежить і від типу контейнера, і від розглянутих операцій. Наприклад, операції взаємного обміну 2-х елементів в ході сортування потребуватиме 3-х копіювань для контейнера типу vector і не потребуватиме додаткових копіювань для контейнера list. Але операції початкового приміщення елемента в контейнер (push_back(), вставити() та ін.) завжди виконуються копіюванням.

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

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

16-1

(Зверніть увагу, що завершувати це додаток потрібно по Ctrl + D - End Of File ... в Widows, мабуть, по Ctrl + Z.)

Але! ... Спеціально були залишені налагоджувальні «сліди» спрацьовувань конструкторів і деструкторів записів, і записи конструюються 8 раз, а деструкція спрацьовує тільки 4, для локального масиву в точці виходу з блоку. Локальний масив для нас взагалі не представляє інтересу. Він введений для спрощення прикладу тільки як набір ініціюючих значень. А ось для записів, розміщені в контейнер, знищення записів не відбувається, і ми отримуємо відверту витік пам'яті. Але гірше того, після того як ми видаляємо елемент з контейнера (не роблячи додаткових дій), ми і не зможемо видалити запис, викликавши для неї delete. Это потому, що після виклику прати() ми втратили до запису єдиний шлях доступу через итератор (в коді показаний цикл з прати(), так наочніше, что эквивалентно ясно(), ефект якого, буде тим же самим).

висновок, який може бути зроблений з прикладу, виглядає так:

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

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

Тут деяку допомогу можуть надати розумні покажчики з останніх стандартів C ++ (shared_ptr или weak_ptr, але не unique_ptr і не старий добрий і проблемний auto_ptr), нам для цього в попередньому коді досить змінити 4 рядки:

У Windows для shared_ptr необхідний #include <пам'ять> , а в інших системах не обов'язково.

И поведінка додатки істотно зміниться:

16-2

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

Нові уроки з програмування:

Адаптери. STL (частина 15)




stack, Програмування для початківців

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

Найпростіше показати, як з'являються адаптери на прикладі адаптерів контейнерів: stack (стек), queue (черга), priority_queue (черга з пріоритетами). Уже з їх перерахування зрозуміло, що:

  • Це дуже широко і часто використовувані структури даних;

  • Для них не потрібні якісь окремі реалізації. Для забезпечення їх функціональності можна використовувати (адаптувати) в якості базового будь-який зі стандартних контейнерів STL, який забезпечує операції типу push_back, pop_back или pop_front (в залежності від типу адаптера);

  • «Зайві» операції з арсеналу базового контейнера для адаптера потрібно виключити (щоб не створювати спокуси ... наприклад, операцію індексації, якщо vector використовується для адаптації стека);

И, замість громіздких шаблонних синтаксичних визначень (заголовки <stack>, <queue> і т. п.), звернемося до прикладів…

Почнемо зі стека: стек характерний тим, що отримати доступ до його елементів можна лише з одного кінця, званого вершиною стека. Це колекція даних, що функціонує за принципом LIFO (Last In - First Out). Ось такий простенький приклад розкриває нам практично всю функціональність стека:

Проаналізуємо код і зробимо деякі висновки:

  • перше визначення stack<string> (ми його далі не використовуємо) оголошує змінну стек, елементами якого є рядки. Звертаємо увагу на те, що об'єкти string самі по собі є контейнерами STL. Таким образом, стек може містити елементи будь-якої глибини укладення контейнерів (що властиво і будь-яким іншим контейнерів STL).

  • таке визначення ( stack<string> ) ви зможете побачити, як опис стека в переважній більшості прикладів. Багато авторів і не підозрюють, що може бути по-іншому. Але ми скористаємося іншим визначенням: stack< string, vector<string> > - Це стек рядків (багато в чому еквівалентний попередньому), але побудований на базовому класі vector<string>. Як базові можуть використовуватися, например, vector, list і deque, або навіть ваш власний контейнерний клас, розширює базові. По умолчанию (так як в 1-м визначенні) використовується база deque. Іноді запитують: чому не можна написати (визначити так в реалізації stack): stack< vector<string> > (прибравши дублювання string)? Тому що (і це цілком можливо) це буде опис зовсім іншого типу: стек векторів строк (см. вище зауваження про структурну вкладеності контейнерів).

  • далі слід ініціалізація початкового стану з вектора рядків. відзначте, що такий трюк допустимо тільки в стандарті C ++ 11.

  • Далі ми бачимо практично всі операції (методи), вимагаються від стека: push() – заталківаніе об'єкта в стек, top() – отримання посилання на елемент в вершині стека, pop() – викидання верхнього елементу, size() – поточний розмір стека, empty() – перевірка на порожнечу.

  • Як легко зрозуміти, адаптер stack втратив властиві базовому контейнеру методи (at(), [ ] та ін.), але придбав (перевизначенням) свої власні (push(), pop()).

Тепер подивимося що з цього вийшло:

stack, Програмування для початківців

Розібравшись зі стеком тепер елементарно просто перенести аналогії на чергу. На противагу стеку – це колекція даних, що функціонує за принципом FIFO (First In - First Out). (Це така «труба», в один кінець якої щось втікає, а з іншого кінця потім випливає.)

Спеціально залишимо для черги приклад практично незмінним, внісши правки, необхідні семантикою мови:

Від нас вимагали змінити:

  • Черга не може бути побудована на базовому контейнері vector у якого немає методу pop_front(), але може будуватися на list, deque, або будь-якому іншому контейнері, реализующем базовий набір методів (front(), push_back(), pop_front()), за замовчуванням використовується deque.

  • У адаптера queue немає методу top(), а є метод аналогічного змісту front().

І в результаті отримуємо (порівняйте з результатами для стека!):

stack, Програмування для початківців

Нові уроки з програмування:

Узагальнені чисельні алгоритми. STL (частина 14)




Узагальнені чисельні алгоритми STL c ++наступну, дуже потрібну і дуже потужну групу STL алгоритмів представляють узагальнені чисельні алгоритми (заголовки <числовий>). Це не якісь особливі обчислювальні методи, як можна подумати виходячи з назви. це алгоритми, що дозволяють застосовувати загальновідомі бібліотечні або свої власні обчислювальні функції до всієї сукупності елементів контейнера. А оскільки так, то і викликаються вони подібно до всіх інших алгоритмам STL. Використовуються такі узагальнені алгоритми, головним чином в математичних обчисленнях стосовно контейнерів, що містить числові елементи. Але це зовсім не обов'язково. І якщо вас не цікавлять чисельні обчислення (наприклад з області цифрової обробки сигналів), то ви можете просто безболісно пропустити цю частину викладу…

Перерахуємо представлені STL узагальнені чисельні алгоритми: йота (створення монотонно зростаючій послідовності), накопичуватися (накопичення), inner_product (skalyarnoe proïzvedenïe), partial_sum (часткова сума), adjacent_difference (суміжна різницю).

Ілюстрацію роботи найкраще провести на самому використовуваному і інтуїтивно зрозумілій алгоритмі накопичуватися. Цей алгоритм редукує (зменшує розмірність) контейнера з накопиченням значень. Зокрема, для простих числових значень він згортає vector<> или list<> до одиночного скалярного результуючого значення.

алгоритм накопичуватися (як, втім, і більшість інших) має 2 синтаксичні форми:

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

Не зрозуміло? Це потужна техніка, і зараз все стане зрозуміло з прикладу…

У математичній статистиці знаходять застосування кілька видів середнього значення для числової послідовності:

  • Среднее арифметическое:

    SA1

  • середнє геометричне:

    sg2

  • середнє гармонійне:

    SR3

  • середнє квадратичне:

    SQ4

Чи не станемо заглиблюватися в зміст кожного з варіантів. Ми зробимо додаток, яке підраховує ці середні і ще деякі характеристики (дисперсію, середньоквадратичне відхилення) для введеної числової послідовності. Вхідну послідовність вводимо або з терміналу, або перенаправленням з попередньо підготовленого файлу даних:

Як легко бачити, кожна із записаних вище складних математичних формул обчислюється всього лише в один рядок, використовуючи техніку узагальнених алгоритмів:

Узагальнені чисельні алгоритми stl в c ++

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

Узагальнені чисельні алгоритми stl в c ++

Повернемося до вивчення коду. Перший виклик алгоритму накопичуватися( b, е, 0. ) демонструє 1-ю форму використання: значення контейнера підсумовуються з початковим значенням 0.0.

попередження!: Запис точки в константі початкового значення, яка вказує, що це дійсне значення - принципово важливо. Без цього код компілюватиметься навіть без попереджень, але виконуватися з абсолютно невірними і вкрай складно тлумаченими результатами! Это связано с тем, що алгоритми визначені як template, і тип 3-го параметра визначить для якого типу даних будуть задіяні внутрішні операції при накопиченні.

Всі решта (4 штуки) виклики накопичуватися() використовують 2-ю форму виклику – передають 4-м параметром функцію накопичення. Як видно з прикладів, вона приймає параметрами поточний накопичене значення і черговий елемент контейнера. А повертає результат накопичує операції. Для наочності, все накопичують функції записані в прикладі в простому і ясному вигляді. На практиці, щоб уникнути залежності від типу оброблюваних даних, їх також зазвичай записують, як шаблонні функції. Тоді це може виглядати так:

нарешті, Зверніть увагу, якщо не звернули досі, що при накопиченні сум ми використовуємо початкове значення 0 (3-й параметр накопичуватися() ), а при накопиченні творів, естественно, 1, з відповідним типом даних.

Нові уроки з програмування:

Сортування структур. СТЛ Частина 13




сортування структур з ++, stl для початківцівПоказання в попередній частині різноманітні сортування - Гнучкий і красивий механізм на всі випадки життя. Ось тільки на практиці сортувати в чистому вигляді послідовності майже ніколи не доводиться. Це все з області навчально-показових завдань. На практиці куди частіше стоїть завдання сортувати досить об'ємні структури даних (об'ємні навіть не за своїм розміром, а по числу своїх полів). І сортувати (або перевпорядковувати) їх має бути за значеннями самих різних полів цих самих структур. Але і тут на допомогу приходять STL алгоритми, особливо при використанні їх разом з функторами.

Подивимося типову модельну задачу, яку ми вже бачили раніше - опис навчальної групи або факультету:

Програма запитує номер поля дані, за яким вестиметься сортування (насправді - порівняння). Якщо цей номер вводиться, як позитивне число, то сортування по цьому полю йде в порядку зростання. Якщо ж номер вводиться зі знаком мінус - то порядок сортування змінюється на зворотний:

сортування структур з ++, stl для початківцівсортування структур з ++, stl для початківців

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

Нові уроки з програмування:

Сортування. STL (частина 12)




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

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

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

тепер, володіючи деякими знаннями про алгоритмах, функторах і загалом станом справ з угрупованнями, ми готові розглянути варіанти реалізації всього цього в своєму коді. Для початку ми різноманітними способами сортуємо числові послідовності. приклад Velikon, але він призначений не тільки, і не скільки, для ілюстрації, як для подальшого самостійного експериментування:

Перед компіляцією програми, в MVS натисніть Alt + F7 і внесіть Аргументи команди ?30 +3:сортування в с ++

Деяка громіздкість прикладу пов'язана з тим, що ми в одному коді об'єднуємо і всі надані STL алгоритми сортування, і різноманітні тестові сортовані послідовності, например:

  • кілька випадкових (?) послідовностей довжини 30, сортируемих з використанням (3) функтора порівняння, і деталізованим (+) висновком вхідний і вихідний послідовності:

    сортування в с ++

  • інверсна (зворотна, спадна) послідовність, сортируемое (6) «В купі» з використанням бінарного дерева (аргументи команди -30 +6 ):сортування в с ++

  • довга (1000000) послідовність, в тих же, що і попередній випадок, умовах, але з висновком тільки діагностики коректності результату (аргументи команди -1000000 6 ):

    сортування в с ++

Бібліотека STL надає 3 групи алгоритмів сортування:

  • сортувати() – найбільш швидке сортування в середньому ( O( N * журнал( N ) ), але яка може «провалюватися» в гіршому випадку до O( N * N ) (а це дуже поганий показник);

  • sort_heap() – сортування в «в купі», з використанням бінарного дерева, складність якої завжди не гірше O( N + N * журнал( N ) ) (це гірше сортувати() в середньому, але краще в найгіршому випадку);

  • stable_sort() – «Стійка» сортування злиттям, стійкість якої означає, що вона зберігає відносний порядок рівних елементів після сортування. Це іноді дуже важливо. Складність цього алгоритму не набагато поступається сортувати();

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

Нові уроки з програмування: