Строковий тип - це

Подання в пам'яті

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

Основні проблеми в машинному поданні строкового типу:

рядки можуть мати досить істотний розмір (до декількох десятків мегабайтів);
змінюється з часом розмір - виникають труднощі з додаванням і видаленням символів.

У поданні рядків в пам'яті комп'ютера існує два принципово різних підходи.

Подання масивом символів

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

Злегка оптимізованим варіантом цього методу є т. Н. формат c-addr u (від англ. character-aligned address + unsigned number), застосовуваний в Форте. На відміну від Pascal strings, тут розмір масиву зберігається не спільно із строковими даними, а є частиною покажчика на рядок.

переваги

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

недоліки

проблеми зі зберіганням і обробкою символів довільної довжини;
збільшення витрат на зберігання рядків - значення «довжина рядка» також займає місце і в разі великої кількості рядків маленького розміру може істотно збільшити вимоги алгоритму до оперативної пам'яті;
обмеження максимального розміру рядка. У сучасних мовах програмування це обмеження скоріше теоретичне, так як зазвичай розмір рядка зберігається в 32-бітовому полі, що дає максимальний розмір рядка в 4 294 967 295 байт (4 гігабайти).

Метод «завершального байта»

Другий метод полягає в використанні «завершального байта». Одне з можливих значень символів алфавіту (як правило, це символ з кодом 0) вибирається в якості ознаки кінця рядка, і рядок зберігається як послідовність байтів від початку до кінця. Є системи, в яких в якості ознаки кінця рядка використовується не символ 0, а байт 0xFF (255) або код символу «$».

Метод має три назви - ASCIIZ (символи в кодуванні ASCII з нульовим завершальним байтом), C-strings (найбільшого поширення метод отримав саме в мові Сі) і метод нуль-терминировать рядків.

переваги

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

недоліки

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

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

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

Реалізація в мовах програмування

У перших мовах програмування взагалі не було строкового типу; програміст повинен був сам будувати функції для роботи з рядками того чи іншого типу.
У Сі використовуються нуль-терминировать рядки з повним ручним контролем з боку програміста.
У стандартному Паскалі рядок виглядає як масив з 256 байтів; перший байт зберігав довжину рядка, в інших зберігається її тіло. Таким чином, довжина рядка не може перевищувати 255 символів. У Borland Pascal 7.0 також з'явилися рядки «а-ля Сі» - очевидно, через те, що в число підтримуваних платформ увійшла Windows.
У Object Pascal і STL рядок є «чорним ящиком», в якому виділення / вивільнення пам'яті відбувається автоматично - без участі програміста. При створенні рядка пам'ять виділяється автоматично; як тільки на рядок не залишиться жодного посилання, пам'ять повертається системі. Перевага цього методу в тому, що програміст не замислюється над роботою рядків. З іншого боку, програміст має недостатній контроль над роботою програми в критичних до швидкості ділянках; також важко реалізується передача таких рядків як параметр в DLL. Також Object Pascal автоматично стежить, щоб в кінці рядка був символ з кодом 0. Тому якщо функція вимагає на вході нуль-терминировать рядок. для конвертації треба просто написати PAnsiChar (строковая_переменная) або PWideChar (строковая_переменная) (для Pascal), змінна .c_str () (для Builder / STL).
У C # та іншими мовами зі складанням сміття рядок є незмінним об'єктом; якщо рядок потрібно модифікувати, створюється інший об'єкт. Цей метод повільний і витрачає чимало тимчасової пам'яті, але добре поєднується з концепцією збірки сміття. Перевага цього методу в тому, що присвоювання відбувається швидко і без дублювання рядків. Також є деякий ручний контроль над конструюванням рядків (в Java. Наприклад, через клас StringBuffer) - це дозволяє зменшити кількість виділень і вивільнень пам'яті і, відповідно, збільшити швидкість.

Найпростіші операції з рядками

отримання символу за номером позиції (індексу) - в більшості мов це тривіальна операція;
конкатенація (з'єднання) рядків.

похідні операції

отримання підрядка за індексами початку і кінця;
перевірка входження одного рядка в іншу (пошук підрядка в рядку);
перевірка на збіг рядків (з урахуванням або без урахування регістру символів);
отримання довжини рядка;
заміна підрядка в рядку.

Операції при трактуванні рядків як списків

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

Більш складні операції

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

Можливі завдання для рядків на природній мові

порівняння на близькість зазначених рядків по заданому критерію;
визначення мови і кодування тексту на підставі ймовірностей символів і складів.

Подання символів рядка

До останнього часу один символ завжди кодувався одним байтом (8 двійкових бітів; застосовувалися також кодування з 7 битами на символ), що дозволяло представляти 256 (128 при семібітной кодуванні) можливих значень. Однак для повноцінного представлення символів алфавітів кількох мов (багатомовних документів, друкарських символів - кілька видів лапок. Тире. Декількох видів прогалин і для написання текстів на ієрогліфічних мовах - китайському. Японською та корейською) 256 символів недостатньо. Для вирішення цієї проблеми існує кілька методів:

Дивитися що таке "Строковий тип" в інших словниках:

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

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

Логічний тип - З технічних причин Bool перенаправляється сюди. Про Bool можна прочитати тут: stdbool.h. Логічний, логічний (англ. Boolean або logical data type) тип даних примітивний тип даних в інформатиці, які можуть приймати два можливих ... Вікіпедія

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

Вищий тип - (top type) в теорії типів, часто позначається як просто вершина або «закріпленим» символом (⊤), універсальний тип, тобто такий тип, який містить в собі кожен можливий об'єкт в потрібній системі типів. Вищий тип іноді іменується ... ... Вікіпедія

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

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

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