всі повідомлення Olej

Про Olej

Стаж практичних програмних розробок близько 40 лет. Викладач міжнародної софтверної компанії Global Logic. Постійний автор публікацій IBM Developer Works. Науковий редактор книжкового видавництва комп'ютерної літератури "Символ-Плюс", Санкт-Петербург.

Робота з локалізованими рядками




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

результатом буде:

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

У такій рядку поруч з рівним успіхом можуть стояти символи найрізноманітнішої природи: різних мов, спеціальні математичні символи, загальноприйняті в їхК.Є. позначення з грецького алфавіту (α, е, Я, Fr., р, L, F, Про ...), музичні ноти і ін. Як ви, очевидно, розумієте, точно також в складі рядків широких символів, з рівним успіхом, можуть зустрічатися і символи латинського алфавіту (основна таблиця ASCII), при цьому кожен такий символ теж буде займати 2 или 4 байт (в залежності від угод прийнятих в операційній системі), на відміну від звичного 1 байта.

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

виконуємо:

Здавалося б, що (майже) все працює в точності як за підручником і навіщо нам якісь широкі локалізовані рядки? Але це оманлива ілюзія! Справа тут в тому, що деякі традиційні малі функції (strcat(), strcpy(), strdup(), strstr() та ін.) повертатимуть коректний результат. Це тому що вони виконують операції над байтами, байт за байтом, не вникаючи у внутрішню структуру копіюються символів.

Але інші операції (і помилковий результат strlen() на це вже наочно вказує) будуть працювати належним чином: strncpy(), strchr(), strsep(), strtok() та ін. И вони будуть створювати вам дуже несподівані результати, вельми складні для тлумачення. подивисявони як спрацює побайтовой реверс рядки, і як різниться його робота на англомовній та російськомовній рядку:

Чи спрацює це так, і це безперечно НЕ, що ви розраховували отримати:

Nа це ми закінчимо розгляд можливості подання російськомовних рядків традиційними масивами char[] і обробка їх традиційними малими функціями, і завершимо це розгляд висновком: работать з російськомовними рядками як масивом char можна только:

а). або коли ми використовуємо рядкові константи в незмінному вигляді, тільки як рядки для їх введення-виведення в незмінному вигляді;

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

У всіх решті випадків коректная робота з кирилицею можлива тільки як з масивами широких локалізованих символів wchar_t (з завершающім рядок широким нульовим символом L » 0′). Для роботи з таким поданням локалізованих рядків бібліотека C надає широкий набір малих функцій, повністю аналогічний традиційним рядковим функцій, але замість префікса str в їхніх іменах використовується префікс WCS: wcslen() замість strlen(), wcsncpy() замість strncpy() і т.д.

Подивимося як це працює на прикладі:

Такий ілюстрації цілком достатньо для того, щоб побачити прямі аналогії використання функцій роботи з символами wchar_t. той, хто має деякий досвід роботи з рядками char без зусиль перенесе його широкі рядки. Установка мовної локалі (виклик setlocale()) пристрою виведення (терміналу) - обов'язкова, тому що за замовчуванням програма C / C ++ встановлює локаль “C” (тадо склалося історично), яка допускає висновок тільки 128 символів молодшої половини 8-бітної таблиці ASCII.

У показаному написанні функція встановлює локаль, використовувану в операційній системі за замовчуванням - я припускаю, що ми експериментуємо в російськомовній встановленій системі. Новий стандарт мови (C99) вводить і новий формат для функцій форматування рядків (Printf(), Sprintf()) - %Ls, це форматування рядків wchar_t[].

ТТочно так само, як і з масивами char, які перейшли в C ++ з C, бібліотека C ++ вводить повну аналог контейнерного класу string, але що містить в своєму складі широкі локалізовані символи, і носить назву цей клас wstring:

Тут висновок рядка локалізованих символів (WS) повинен виводиться в потік виводу wcout (аналогічний за змістом cout, але відмінний від cout).

У показаному написанні: місце дії::глобальної( місце дії( “” ) ) - це установка локалі за замовчуванням в ООП манері C ++, аналогічно тому, як це було показано раніше в манері C.

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

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

Про локалізації символьних рядків




локалізація символьних рядків в с ++

Переважна кількість прикладів кодів з рядками C / C ++ (в будь-яких публікуються джерелах) оперує з нуль-термінальними масивами (ASCIZ) елементів char (в стилі C), або з контейнерним типом string (в стилі C ++), побудованим як надбудова над такими масивами. Все це чудово працює з рядками латинських (англомовних) символов, але може йти в рознос на рядках, містять символи іншомовних алфавітів (російська, китайський, арабська або іврит). Тут все не так просто ... і дуже погано описано в літературі, що й зрозуміло: англомовних авторів мало турбує питання іншомовної локалізації, а вітчизняні автори, у більшості, переписують і адаптують англомовні публікації, не приділяють уваги цій стороні питання.

Мова C - вельми старий мову програмування, а C ++ успадковує з нього формати і стримується вимогами синтаксичної сумісності з C. Для того, щоб не мати в C / C ++ проблем з такими рядками (званими локалізованими) потрібно розуміти що там з цими локалізаціями відбувається ...

історичний, символи (char) представлялися (1963 рік) стандартом ASCII як молодші 7 біт одного байта, при цьому старший 8-й біт призначався для контролю помилок, що виникли при передачі даних. Таке кодування дозволяє кодувати максимально всього 128 різних символів, і цього числа ледве вистачає на символи англійського алфавіту (великі і малі), цифрові (код 0x30-0x39), керуючі (код менше 0x20) і спеціальні символи. Коли виникала необхідність представлення національних алфавітів, вводилася альтернативна таблиця символів, наприклад KOI-7 для російської мови. Перемикання в потоці вводу-виводу на альтернативну таблицю символів вироблялося символом з кодом 0x18 (код називається: управління пристроєм 2) в потоці, а повернення до основну таблицю ASCII - символом з кодом 0x17 (управління пристроєм 1).

пізніше, з середини 80-х років, з часу широкого поширення IBM PC і заміни ними комп'ютерів інших сімейств, стандарт ASCII було розширено на 8-й біт байта char, байт міг представляти 256 символов: молодші 127 представляли вихідну таблицю ASCII (з латинським шрифтом), а старші - національний алфавіт. Але, оскільки національні алфавіти можуть бути найрізноманітнішими, то для підтримки кожного з них треба було ввести свою кодову сторінку, например, для російської мови це можуть бути сторінки CP-866 (MS в), CP-1251 (в ОС Windows), Ні-8г (в UNIX, Linux) - і кожна з цих сторінок пропонує свій, відрізняється від інших, порядок символів російської мови. При этом, для коректного відображення (або декодування) будь локалізованої символьного рядка потрібно обов'язково знати кодову сторінку в якій вона представлена.

Для того, щоб покласти край цьому вавілонського стовпотворіння мовних кодових сторінок, був запропонований (1991м) стандарт уявлення UNICODE, під час передачі сигналу якого кожен символ кодується 32-біт значенням (4 байта, але не всі 32-біт значення припустимі). Застосування даного стандарту дозволяє закодувати величезну кількість символів різних систем писемності. документи, закодовані за стандартом UNICODE, можуть містити в єдиному тексті японські та китайські ієрогліфи, букви латиниці, кирилиці, грецького алфавіту (α, е, Я, Fr., р, L, F, Про ...), математичні символи, символи музичної нотної нотації, символи вимерлих, рідкісних, екзотичних народностей. При цьому немає необхідності в перемиканні кодових сторінок. Наприклад, ось як виглядають деякі символи мови, позначеного як “singaliskii”:

Перший UNICODE стандарт був випущений в 91-му році. Останній на даний момент - в 2017 і він описує 136755 різноманітних символів.

Але UNICODE - це ще тільки стандарт уявлення кожного символу. Для подання цього символу в конкретній операційній системі (або мовою програмування) потрібна ще система кодування символів UNICODE.

  • Досить широко використовуються системи кодування:
    UTF-32 - для подання кожного символу використовуються 4 байта, безпосереднє чисельне значення коду UNICODE
  • UTF-32 - для подання найбільш часто використовуваних символів використовуються 2 байта (перші 65536 позицій), а інші видаються у вигляді у вигляді «сурогатних пар». Таке кодування використовується в операційних системах Windows починаючи з Windows NT.
  • UTF-32 - для подання кожного символу використовуються сукупність електронних даних змінної довжини: от 1 байта для символів основної таблиці ASCII, до 6 байт для рідко використовуваних символів (символи російського алфавіту кодуються 2-мя байтами). Це кодування створювалася пізніше інших для операційних систем Plan 9 і Inferno в 1992р. Кеном Томпсоном и Робертом Пайком с коллегами, і увійшла як єдина і основна кодування символьних рядків в більш пізніх мовах програмування Python і Go. Таке кодування використовується, на сьогодні повсюдно, в POSIX / UNIX операційних системах, Linux.

Повертаючись до того, що C / C ++ старе сімейство мов програмування, для подання в них локалізованих символів потрібно ввести новий тип даних - широкі символи wchar_t замість char (тип даних з'явився в стандарті C89, але, в повній мірі з API підтримки, тільки в стандарті C99). Замість малих функцій бібліотеки C виду str *() для широких пропонуються їх повні аналоги, але у вигляді wcs *() (замість префікса str записуємо префікс wcs). У різних системах wchar_t може мати різну розрядність (в Linux це int32_t, в Windows, int16_t) але для програміста це не має значення і не створює відмінностей.

Для роботи та перетворення мультибайтних послідовностей записаних в кодуванні UTF-8 в C / C ++ вводиться сімейство функцій виду mb *(): mbtowc(), mblen(), mbstowcs(), wcstombs() та ін. Це механізм взаємних перетворень між масивами char[] (в яких також виражаються рядки UTF-8) і wchar_t[]. Якщо ви не стикаєтеся з кодуванням UTF-8 (що з великою ймовірністю має місце в Windows), то ця група функцій вас не повинна займати.

аналогічно, замість контейнерного класу C ++ string вводиться аналогічний контейнерний клас широких символів wstring.

Саме про техніку роботи з широкими локалізованими рядками ми поговоримо в наступній статті. А поки 1-й елементарний приклад ... без коментарів - як привід для роздумів (зверніть увагу і поясніть, що виклик strlen() в кожному випадку дає число байт в рядку явно не відповідає візуально видиме число букв в ній):

P.S. З великою детальністю про локалізацію в C / C ++ і роботі з локалізованими рядками, хто цікавиться з більшою докладністю, можуть почитати тут: Мовна локалізація C / C ++ Мовна локалізація C / C ++ - там пояснень більш 22 сторінок формату офісного документа.

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

Дороговкази в контейнерах. 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() – «Стійка» сортування злиттям, стійкість якої означає, що вона зберігає відносний порядок рівних елементів після сортування. Це іноді дуже важливо. Складність цього алгоритму не набагато поступається сортувати();

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

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

Функціональні об'єкти. STL (частина 11)




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

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

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

функтор, з ++ для початківців, функціональний об'єкт, бібліотека стл, СТЛ

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

Тут в рядку cout << обчислювати( опер )( op1, op2 ) дії виконуються послідовно:

  • створюється тимчасовий об'єкт класса обчислювати конструктором з параметром опер;

  • для цього об'єкта виконується метод () (функціональний виклик) з двома параметрами;

  • операция, яка буде виконана в цьому функціональному виклику, залежить від того параметра опер, з яким був сконструйований об'єкт;

  • функціональний виклик повертає значення результату операції;

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

І в результаті ми отримуємо:

функтор, з ++ для початківців, функціональний об'єкт, бібліотека стл, СТЛ

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

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

Алгоритми. STL (частина 10)




розмір алгоритми, знайти(), копія(), copy_if(), рух(), swap_ranges(), remove_copy(), remove_copy_if(), зливатися(), set_intersection(), set_difference()Контейнери STL представляли б собою красиву вигадку досить далеку від практичного використання (як і було в перші роки існування STL), якби не таку обставину: через єдиної загальної природи всіх контейнерів основні алгоритми, що представляють інтерес на практиці, можуть бути реалізовані в узагальненому вигляді, застосовне до будь-яким типам контейнерів. Алгоритми - це сама об'ємна і найбільш затребувана частина бібліотеки. Надається настільки багато алгоритмів, що для детального опису їх всіх не вистачить і об'ємної книги. Нижче ми абсолютно умовно поділимо їх на групи і назвемо по іменах (і теж далеко не все), і тільки за деякими побудуємо приклади використання.

для кожного() Найбільш часто використовуваний алгоритм - це для кожного(): виконання дії для групи елементів (можливо всіх) контейнера. Нижче показано кілька прикладів роботи алгоритму для кожного() для масиву і вектора, точно також цей алгоритм може використовуватися з будь-яким СТЛ контейнером:

розмір алгоритми, знайти(), count(), count_if(), пошук(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), рівний()

Примітка: рядком 3 показана робота нової (введена стандартом C ++ 11) конструкції for( автоматичний &x : …), яка має подібний ефект присвоєння і може застосовуватися і до масивів і до контейнерів (в функції-операторі виведення вектора в потік показаний такий варіант). ця конструкція, взагалі то кажучи, не є складовою частиною бібліотеки STL або алгоритмів, але має той же ефект, що і алгоритм for_each(): застосувати послідовно до всіх елементів колекції.

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

знайти() Наступний за значимістю алгоритм - це знайти(). Як інтуїтивно зрозуміло з імені, це пошук деякого елемента в колекції. Зверніть увагу, що багато контейнери мають метод знайти(), який для об'єкта буде викликатися як obj.find(…), в той час як алгоритм буде викликатися як знайти( OBJ:iteator, ... ).

власне, це навіть не один цей алгоритм, а ціла велика їх група, яку можна об'єднати за ознакою того, що вони відбирають елементи колекції по якомусь ознакою, умові, предикату: знайти(), find_if(), find_if_not(), find_first_of(), find_end(), adjacent_find(). У цю ж групу, з деякою натяжкою, можна віднести і count(), count_if(), пошук(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), рівний() та ін.

Ще одна умовна група - це алгоритми, деяким чином «тасующіе» колекцію, переставляють елементи місцями, змінюють значення: заповнити(), replace_copy(), зворотний(), обертати(), rotate_copy(), тасування(), random_shuffle(), перетворення(), заміщати(), replace_if() та ін.

Ще група - це алгоритми працюють з 2-ма колекціями, доСпираючись і переміщують вміст (причому, возможно, між колекціями різного виду, например, vector<> в комплект<>): копія(), copy_if(), рух(), swap_ranges(), remove_copy(), remove_copy_if(), зливатися(), set_intersection(), set_difference() та ін.

И, нарешті, зовсім особлива група алгоритмів пов'язана з різноманітними угрупованнями елементів всередині колекції: сортувати(), stable_sort(), параметр відсортовано(), is_sorted_until() та ін. Цю цікаву групу ми відкладемо на потім, для окремої докладної розгляду.

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

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

  • Відправляйтеся в стандартний каталог </USR / вмикати / C ++> і знайдіть там хедер-файли файли виду stl_algo * - В них ви знайдете все прототипи функцій алгоритмів. Більш того, там же кожному прототипу передує ґрунтовний комментарий, яка пояснювала б призначення алгоритму, і пояснює параметри виклику.

  • Розгляньте приклади коду, використовують кілька основних засх алгоритмів STL - в мережі їх безліч. За аналогією елементарно просто відтворити поведінку і всіх інших алгоритмів.

Примітка: Ось через те, що бібліотеки шаблонних класів визначені в термінах template, повідомлення про синтаксичних помилках компіляції стають а). mnogoslovnиmi, на десятки рядків повідомлень і б). жахливо невиразними для пошуку помилок. Це зворотний бік медалі такого потужного механізму як template, і до цього потрібно бути готовим.

Як і було сказано вище, вивчення прикладів зніме безліч питань, а тому приступимо до коду … Тепер уважно стежте за руками (алгоритмів STL таку силу-силенну, що коментувати кожен – за межами розумного обсягу викладу, але всі вони працюють як один другому):

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

розмір алгоритми, знайти(), count(), count_if(), пошук(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), рівний()

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

Контейнери STL: встановити і мультімножество. Частина 9




клас і встановити мультімножество C ++, STL контейнери, set multiset для початківцівДосить часто на практиці потрібно контролювати тільки приналежність тих чи інших об'єктів до деякій підмножині. Такі колекції і в класичній математиці називаються безліч, до якого конкретний об'єкт може або належати, чи ні. І бібліотека STL надає такий вид контейнерів, який так і називається - комплект<> (безліч).

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

  • операція вставки (метод вставити()) нового значення ключа до безлічі повертає пару типу <итератор, bool> (просто, як для карта<>). У цій парі другий компонент (second, типу bool) вказує на успішність операції: якщо це true, то перший компонент повертається результату (first) дає итератор нового доданого елемента. Але це досить безглузде повертається значення: якщо повертається true, то нове значення успішно додано до безлічі, якщо ж повертається false, то воно вже присутній в безлічі раніше - в обох випадках кінцевий стан безлічі буде ідентичним (тому на практиці значення, що повертається вставити() зазвичай навіть не перевіряють ... а багато хто і не знають, що там взагалі передбачено повертається значення взагалі);

  • Для цього контейнера реалізований метод count() (як для MultiMap<>), але, оскільки значення ключа може бути присутнім в множин тільки в одиничному екземплярі, метод count() може повернути тільки 0, якщо таке значення відсутній, і 1 коли таке значення присутній.

  • Для контейнера реалізований метод знайдений(), який повертає итератор элемента, якщо значення знайдено, і итератор зі значенням end() якщо значення відсутній в безлічі.

Для демонстрації сказаного створимо додаток, яке N раз (параметр, задається в команді запуску додатка) в циклі генерує псевдовипадкове число в фіксованому діапазоні [0…іт] і поміщає його в безліч. Понятно, що при зростанні N більше ніж lim (а тим більше при N набагато більше lim), кожне число діапазону [0…іт] буде генеруватися все більше і більше число раз:

клас і встановити мультімножество C ++, STL контейнери, set multiset для початківців
Аргумент команди у властивостях налагодження не заданий

клас і встановити мультімножество C ++, STL контейнери, set multiset для початківців
Аргумент команди у властивостях налагодження дорівнює 5
клас і встановити мультімножество C ++, STL контейнери, set multiset для початківців
Аргумент команди у властивостях налагодження дорівнює 100

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

Але поведінка додатки радикально змінюється (для порівняння поруч показані результати 2-х додатків в ідентичних умовах):

клас і встановити мультімножество C ++, STL контейнери, set multiset для початківців

Видим, що для мультимножини значення 1, 2, 13, 17… відсутні в контейнері, а значення 18, например, присутній в ньому 5 раз.

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