Рядковий тип

В програмуванні, рядковий тип ( англ. string "Нитка, низка") - тип даних, значеннями якого є довільна послідовність (рядок) символів алфавіту. Кожна змінна такого типу (строкою змінна) може бути представлена ​​фіксованою кількістю байтів або мати довільну довжину.


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

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

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

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

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


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

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

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


1.1.1. Переваги

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

1.1.2. Недоліки

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

1.2. Метод "завершального байта"

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

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


1.2.1. Переваги

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

1.2.2. Недоліки

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

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

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

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

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

3. Операції

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

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

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

  • Переключення мови керуючими кодами. Метод не стандартизований і позбавляє текст самостійності (тобто послідовність символів без керуючого коду на початку втрачає сенс); використовувався в деяких ранніх русифікації ZX-Spectrum та БК.
  • Використання двох або більше байт для подання кожного символу ( UTF-16, UTF-32). Головним недоліком цього методу є втрата сумісності з попередніми бібліотеками для роботи з текстом при поданні рядка як ASCIIZ. Наприклад, кінцем рядка повинен вважатися вже не байт із значенням 0, а два або чотири поспіль йдуть нульових байтів, в той час як одиночний байт "0" може зустрічатися в середині рядка, що збиває бібліотеку "з пантелику".
  • Використання кодування з перемінним розміром символу. Наприклад, в UTF-8 частина символів представляється одним байтом, частина двома, трьома або чотирма. Цей метод дозволяє зберегти часткову сумісність зі старими бібліотеками (немає символів 0 усередині рядка і тому 0 можна використовувати як ознака кінця рядка), але призводить до неможливості прямої адресації символу в пам'яті за номером його позиції в рядку.
Перегляд цього шаблону Типи даних
Неінтерпретіруемие
Числові
Текстові

Символьний Строковий

Покажчик

Адреса Посилання

Композитні
Інші

Логічний Нижчий тип Колекція Перераховуються тип Виняток First-class function Opaque data type Recursive data type Семафор Потік Вищий тип Type class Unit type Void

Пов'язані теми