Строковый тип

Поделись знанием:
(перенаправлено с «Строка (программирование)»)
Перейти к: навигация, поиск

В программировании, строковый тип (англ. string «нить, вереница») — тип данных, значениями которого является произвольная последовательность (строка) символов алфавита. Каждая переменная такого типа (строковая переменная) может быть представлена фиксированным количеством байтов либо иметь произвольную длину.





Представление в памяти

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

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

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

В представлении строк в памяти компьютера существует два принципиально разных подхода.

Представление массивом символов

В этом подходе строки представляются массивом символов; при этом размер массива хранится в отдельной (служебной) области. От названия языка Pascal, где этот метод был впервые реализован, данный метод получил название Pascal strings.

Слегка оптимизированным вариантом этого метода является т. н. формат c-addr u (от англ. character-aligned address + unsigned number), применяемый в Форте. В отличие от Pascal strings, здесь размер массива хранится не совместно со строковыми данными, а является частью указателя на строку.

Преимущества

  • программа в каждый момент времени содержит сведения о размере строки, поэтому операции добавления символов в конец, копирования строки и собственно получения размера строки выполняются достаточно быстро;
  • строка может содержать любые данные;
  • возможно на программном уровне следить за выходом за границы строки при её обработке;
  • возможно быстрое выполнение операции вида «взятие N-ого символа с конца строки».

Недостатки

  • проблемы с хранением и обработкой символов произвольной длины;
  • увеличение затрат на хранение строк — значение «длина строки» также занимает место и в случае большого количества строк маленького размера может существенно увеличить требования алгоритма к оперативной памяти;
  • ограничение максимального размера строки. В современных языках программирования это ограничение скорее теоретическое, так как обычно размер строки хранится в 32-битовом поле, что даёт максимальный размер строки в 4 294 967 295 байт (4 гигабайта);
  • при использовании алфавита с переменным размером символа (например, UTF-8), в размере хранится не количество символов, а именно размер строки в байтах, поэтому количество символов необходимо считать отдельно.

Метод «завершающего байта»

Второй метод заключается в использовании «завершающего байта»[1][2]. Одно из возможных значений символов алфавита (как правило, это символ с кодом 0) выбирается в качестве признака конца строки, и строка хранится как последовательность байтов от начала до конца. Есть системы, в которых в качестве признака конца строки используется не символ 0, а байт 0xFF (255) или код символа «$».

Метод имеет три названия — ASCIIZ (или asciz, символы в кодировке ASCII с нулевым завершающим байтом), C-strings (наибольшее распространение метод получил именно в языке Си) и метод нуль-терминированных строк.

Преимущества

  • отсутствие дополнительной служебной информации о строке (кроме завершающего байта);
  • возможность представления строки без создания отдельного типа данных;
  • отсутствие ограничения на максимальный размер строки;
  • экономное использование памяти;
  • простота получения суффикса строки;
  • простота передачи строк в функции (передаётся указатель на первый символ);

Недостатки

  • долгое выполнение операций получения длины и конкатенации строк;
  • отсутствие средств контроля за выходом за пределы строки, в случае повреждения завершающего байта возможность повреждения больших областей памяти, что может привести к непредсказуемым последствиям — потере данных, краху программы и даже всей системы;
  • невозможность использовать символ завершающего байта в качестве элемента строки.
  • невозможность использовать некоторые кодировки с размером символа в несколько байт (например, UTF-16), т.к. во многих таких символах, например Ā (0x0100), один из байтов равен нулю (в то же время, кодировка UTF-8 свободна от этого недостатка).

Использование обоих методов

В таких языках, как, например, Оберон, строка размещается в массиве символов определённой длины, причём её конец обозначается нулевым символом. По умолчанию, весь массив заполнен нулевыми символами. Такой способ позволяет объединить многие преимущества обоих подходов, а также избежать большинство их недостатков.

Представление в виде списка

Языки Erlang[3], Haskell[4], Пролог[5] используют для строкового типа список символов. Этот метод делает язык более «теоретически элегантным» за счёт соблюдения ортогональности в системе типов, но приносит существенные потери быстродействия.

Реализация в языках программирования

  • В первых языках программирования вообще не было строкового типа; программист должен был сам строить функции для работы со строками того или другого типа.
  • В Си используются нуль-терминированные строки с полным ручным контролем со стороны программиста.
  • В стандартном Паскале строка выглядит как массив из 256 байтов; первый байт хранил длину строки, в остальных хранится её тело. Таким образом, длина строки не может превышать 255 символов. В Borland Pascal 7.0 также появились строки «а-ля Си» — очевидно, из-за того, что в число поддерживаемых платформ вошла Windows.
  • В Object Pascal и C++ STL строка является «чёрным ящиком», в котором выделение/высвобождение памяти происходит автоматически — без участия программиста. При создании строки память выделяется автоматически; как только на строку не останется ни одной ссылки, память возвращается системе. Преимущество этого метода в том, что программист не задумывается над работой строк. С другой стороны, программист имеет недостаточный контроль над работой программы в критичных к скорости участках; также трудно реализуется передача таких строк в качестве параметра в DLL. Также Object Pascal автоматически следит, чтобы в конце строки был символ с кодом 0. Поэтому если функция требует на входе нуль-терминированную строку, для конвертации надо просто написать PAnsiChar(строковая_переменная) или PWideChar(строковая_переменная) (для Pascal), переменная.c_str() (для Builder/STL).
  • В C# и других языках со сборкой мусора строка является неизменяемым объектом; если строку нужно модифицировать, создаётся другой объект. Этот метод медленный и расходует немало временной памяти, но хорошо сочетается с концепцией сборки мусора. Преимущество этого метода в том, что присваивание происходит быстро и без дублирования строк. Также имеется некоторый ручной контроль над конструированием строк (в Java, например, через классы StringBuffer и StringBuilder) — это позволяет уменьшить количество выделений и высвобождений памяти и, соответственно, увеличить скорость.
    • В некоторых языках (например, Standard ML) кроме этого, есть дополнительный модуль для обеспечения ещё большей эффективности — «подстрока» (SubString). Его использование позволяет выполнять операции над строками без копирования их тел посредством манипулирования индексами начала и конца подстроки; физическое копирование происходит лишь при необходимости преобразовании подстрок в строки.

Операции

Простейшие операции со строками
  • получение символа по номеру позиции (индексу) — в большинстве языков это тривиальная операция;
  • конкатенация (соединение) строк.
Производные операции
  • получение подстроки по индексам начала и конца;
  • проверка вхождения одной строки в другую (поиск подстроки в строке);
  • проверка на совпадение строк (с учётом или без учёта регистра символов);
  • получение длины строки;
  • замена подстроки в строке.
Операции при трактовке строк как списков
  • свёртка;
  • отображение одного списка на другой;
  • фильтрация списка по критерию.
Более сложные операции
  • нахождение минимальной надстроки, содержащей все указанные строки;
  • поиск в двух массивах строк совпадающих последовательностей (задача о плагиате).
Возможные задачи для строк на естественном языке
  • сравнение на близость указанных строк по заданному критерию;
  • определение языка и кодировки текста на основании вероятностей символов и слогов.

Представление символов строки

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

  • Переключение языка управляющими кодами. Метод не стандартизирован и лишает текст самостоятельности (то есть последовательность символов без управляющего кода в начале теряет смысл); использовался в некоторых ранних русификациях ZX-Spectrum и БК.
  • Использование двух или более байт для представления каждого символа (UTF-16, UTF-32). Главным недостатком этого метода является потеря совместимости с предыдущими библиотеками для работы с текстом при представлении строки как ASCIIZ. Например, концом строки должен считаться уже не байт со значением 0, а два или четыре подряд идущих нулевых байта, в то время как одиночный байт «0» может встречаться в середине строки, что сбивает библиотеку «с толку».
  • Использование кодировки с переменным размером символа. Например, в UTF-8 часть символов представляется одним байтом, часть двумя, тремя или четырьмя. Этот метод позволяет сохранить частичную совместимость со старыми библиотеками (нет символов 0 внутри строки и поэтому 0 можно использовать как признак конца строки), но приводит к невозможности прямой адресации символа в памяти по номеру его позиции в строке.

Напишите отзыв о статье "Строковый тип"

Примечания

  1. queue.acm.org/detail.cfm?id=2010365
  2. [russian.joelonsoftware.com/Articles/BacktoBasics.html Joel on Software - Назад, к основам]
  3. Simon St. Laurent. Introducing Erlang. — O’Reilly Media, Inc., 2013. — P. 62. — 185 p. — ISBN 978-1-449-33176-4.
  4. Bryan O'Sullivan, Don Stewart, John Goerzen, Real World Haskell [book.realworldhaskell.org/read/characters-strings-and-escaping-rules.html Appendix B. Characters, strings, and escaping rules]
  5. SWI-Prolog Manual:[www.swi-prolog.org/pldoc/man?section=text-representation 5.2.2 Representing text: strings, atoms and code lists]

См. также

Отрывок, характеризующий Строковый тип



В просторной, лучшей избе мужика Андрея Савостьянова в два часа собрался совет. Мужики, бабы и дети мужицкой большой семьи теснились в черной избе через сени. Одна только внучка Андрея, Малаша, шестилетняя девочка, которой светлейший, приласкав ее, дал за чаем кусок сахара, оставалась на печи в большой избе. Малаша робко и радостно смотрела с печи на лица, мундиры и кресты генералов, одного за другим входивших в избу и рассаживавшихся в красном углу, на широких лавках под образами. Сам дедушка, как внутренне называла Maлаша Кутузова, сидел от них особо, в темном углу за печкой. Он сидел, глубоко опустившись в складное кресло, и беспрестанно покряхтывал и расправлял воротник сюртука, который, хотя и расстегнутый, все как будто жал его шею. Входившие один за другим подходили к фельдмаршалу; некоторым он пожимал руку, некоторым кивал головой. Адъютант Кайсаров хотел было отдернуть занавеску в окне против Кутузова, но Кутузов сердито замахал ему рукой, и Кайсаров понял, что светлейший не хочет, чтобы видели его лицо.
Вокруг мужицкого елового стола, на котором лежали карты, планы, карандаши, бумаги, собралось так много народа, что денщики принесли еще лавку и поставили у стола. На лавку эту сели пришедшие: Ермолов, Кайсаров и Толь. Под самыми образами, на первом месте, сидел с Георгием на шее, с бледным болезненным лицом и с своим высоким лбом, сливающимся с голой головой, Барклай де Толли. Второй уже день он мучился лихорадкой, и в это самое время его знобило и ломало. Рядом с ним сидел Уваров и негромким голосом (как и все говорили) что то, быстро делая жесты, сообщал Барклаю. Маленький, кругленький Дохтуров, приподняв брови и сложив руки на животе, внимательно прислушивался. С другой стороны сидел, облокотивши на руку свою широкую, с смелыми чертами и блестящими глазами голову, граф Остерман Толстой и казался погруженным в свои мысли. Раевский с выражением нетерпения, привычным жестом наперед курчавя свои черные волосы на висках, поглядывал то на Кутузова, то на входную дверь. Твердое, красивое и доброе лицо Коновницына светилось нежной и хитрой улыбкой. Он встретил взгляд Малаши и глазами делал ей знаки, которые заставляли девочку улыбаться.
Все ждали Бенигсена, который доканчивал свой вкусный обед под предлогом нового осмотра позиции. Его ждали от четырех до шести часов, и во все это время не приступали к совещанию и тихими голосами вели посторонние разговоры.
Только когда в избу вошел Бенигсен, Кутузов выдвинулся из своего угла и подвинулся к столу, но настолько, что лицо его не было освещено поданными на стол свечами.
Бенигсен открыл совет вопросом: «Оставить ли без боя священную и древнюю столицу России или защищать ее?» Последовало долгое и общее молчание. Все лица нахмурились, и в тишине слышалось сердитое кряхтенье и покашливанье Кутузова. Все глаза смотрели на него. Малаша тоже смотрела на дедушку. Она ближе всех была к нему и видела, как лицо его сморщилось: он точно собрался плакать. Но это продолжалось недолго.
– Священную древнюю столицу России! – вдруг заговорил он, сердитым голосом повторяя слова Бенигсена и этим указывая на фальшивую ноту этих слов. – Позвольте вам сказать, ваше сиятельство, что вопрос этот не имеет смысла для русского человека. (Он перевалился вперед своим тяжелым телом.) Такой вопрос нельзя ставить, и такой вопрос не имеет смысла. Вопрос, для которого я просил собраться этих господ, это вопрос военный. Вопрос следующий: «Спасенье России в армии. Выгоднее ли рисковать потерею армии и Москвы, приняв сраженье, или отдать Москву без сражения? Вот на какой вопрос я желаю знать ваше мнение». (Он откачнулся назад на спинку кресла.)
Начались прения. Бенигсен не считал еще игру проигранною. Допуская мнение Барклая и других о невозможности принять оборонительное сражение под Филями, он, проникнувшись русским патриотизмом и любовью к Москве, предлагал перевести войска в ночи с правого на левый фланг и ударить на другой день на правое крыло французов. Мнения разделились, были споры в пользу и против этого мнения. Ермолов, Дохтуров и Раевский согласились с мнением Бенигсена. Руководимые ли чувством потребности жертвы пред оставлением столицы или другими личными соображениями, но эти генералы как бы не понимали того, что настоящий совет не мог изменить неизбежного хода дел и что Москва уже теперь оставлена. Остальные генералы понимали это и, оставляя в стороне вопрос о Москве, говорили о том направлении, которое в своем отступлении должно было принять войско. Малаша, которая, не спуская глаз, смотрела на то, что делалось перед ней, иначе понимала значение этого совета. Ей казалось, что дело было только в личной борьбе между «дедушкой» и «длиннополым», как она называла Бенигсена. Она видела, что они злились, когда говорили друг с другом, и в душе своей она держала сторону дедушки. В средине разговора она заметила быстрый лукавый взгляд, брошенный дедушкой на Бенигсена, и вслед за тем, к радости своей, заметила, что дедушка, сказав что то длиннополому, осадил его: Бенигсен вдруг покраснел и сердито прошелся по избе. Слова, так подействовавшие на Бенигсена, были спокойным и тихим голосом выраженное Кутузовым мнение о выгоде и невыгоде предложения Бенигсена: о переводе в ночи войск с правого на левый фланг для атаки правого крыла французов.
– Я, господа, – сказал Кутузов, – не могу одобрить плана графа. Передвижения войск в близком расстоянии от неприятеля всегда бывают опасны, и военная история подтверждает это соображение. Так, например… (Кутузов как будто задумался, приискивая пример и светлым, наивным взглядом глядя на Бенигсена.) Да вот хоть бы Фридландское сражение, которое, как я думаю, граф хорошо помнит, было… не вполне удачно только оттого, что войска наши перестроивались в слишком близком расстоянии от неприятеля… – Последовало, показавшееся всем очень продолжительным, минутное молчание.
Прения опять возобновились, но часто наступали перерывы, и чувствовалось, что говорить больше не о чем.
Во время одного из таких перерывов Кутузов тяжело вздохнул, как бы сбираясь говорить. Все оглянулись на него.
– Eh bien, messieurs! Je vois que c'est moi qui payerai les pots casses, [Итак, господа, стало быть, мне платить за перебитые горшки,] – сказал он. И, медленно приподнявшись, он подошел к столу. – Господа, я слышал ваши мнения. Некоторые будут несогласны со мной. Но я (он остановился) властью, врученной мне моим государем и отечеством, я – приказываю отступление.
Вслед за этим генералы стали расходиться с той же торжественной и молчаливой осторожностью, с которой расходятся после похорон.
Некоторые из генералов негромким голосом, совсем в другом диапазоне, чем когда они говорили на совете, передали кое что главнокомандующему.
Малаша, которую уже давно ждали ужинать, осторожно спустилась задом с полатей, цепляясь босыми ножонками за уступы печки, и, замешавшись между ног генералов, шмыгнула в дверь.
Отпустив генералов, Кутузов долго сидел, облокотившись на стол, и думал все о том же страшном вопросе: «Когда же, когда же наконец решилось то, что оставлена Москва? Когда было сделано то, что решило вопрос, и кто виноват в этом?»
– Этого, этого я не ждал, – сказал он вошедшему к нему, уже поздно ночью, адъютанту Шнейдеру, – этого я не ждал! Этого я не думал!
– Вам надо отдохнуть, ваша светлость, – сказал Шнейдер.
– Да нет же! Будут же они лошадиное мясо жрать, как турки, – не отвечая, прокричал Кутузов, ударяя пухлым кулаком по столу, – будут и они, только бы…


В противоположность Кутузову, в то же время, в событии еще более важнейшем, чем отступление армии без боя, в оставлении Москвы и сожжении ее, Растопчин, представляющийся нам руководителем этого события, действовал совершенно иначе.
Событие это – оставление Москвы и сожжение ее – было так же неизбежно, как и отступление войск без боя за Москву после Бородинского сражения.
Каждый русский человек, не на основании умозаключений, а на основании того чувства, которое лежит в нас и лежало в наших отцах, мог бы предсказать то, что совершилось.
Начиная от Смоленска, во всех городах и деревнях русской земли, без участия графа Растопчина и его афиш, происходило то же самое, что произошло в Москве. Народ с беспечностью ждал неприятеля, не бунтовал, не волновался, никого не раздирал на куски, а спокойно ждал своей судьбы, чувствуя в себе силы в самую трудную минуту найти то, что должно было сделать. И как только неприятель подходил, богатейшие элементы населения уходили, оставляя свое имущество; беднейшие оставались и зажигали и истребляли то, что осталось.
Сознание того, что это так будет, и всегда так будет, лежало и лежит в душе русского человека. И сознание это и, более того, предчувствие того, что Москва будет взята, лежало в русском московском обществе 12 го года. Те, которые стали выезжать из Москвы еще в июле и начале августа, показали, что они ждали этого. Те, которые выезжали с тем, что они могли захватить, оставляя дома и половину имущества, действовали так вследствие того скрытого (latent) патриотизма, который выражается не фразами, не убийством детей для спасения отечества и т. п. неестественными действиями, а который выражается незаметно, просто, органически и потому производит всегда самые сильные результаты.
«Стыдно бежать от опасности; только трусы бегут из Москвы», – говорили им. Растопчин в своих афишках внушал им, что уезжать из Москвы было позорно. Им совестно было получать наименование трусов, совестно было ехать, но они все таки ехали, зная, что так надо было. Зачем они ехали? Нельзя предположить, чтобы Растопчин напугал их ужасами, которые производил Наполеон в покоренных землях. Уезжали, и первые уехали богатые, образованные люди, знавшие очень хорошо, что Вена и Берлин остались целы и что там, во время занятия их Наполеоном, жители весело проводили время с обворожительными французами, которых так любили тогда русские мужчины и в особенности дамы.
Они ехали потому, что для русских людей не могло быть вопроса: хорошо ли или дурно будет под управлением французов в Москве. Под управлением французов нельзя было быть: это было хуже всего. Они уезжали и до Бородинского сражения, и еще быстрее после Бородинского сражения, невзирая на воззвания к защите, несмотря на заявления главнокомандующего Москвы о намерении его поднять Иверскую и идти драться, и на воздушные шары, которые должны были погубить французов, и несмотря на весь тот вздор, о котором нисал Растопчин в своих афишах. Они знали, что войско должно драться, и что ежели оно не может, то с барышнями и дворовыми людьми нельзя идти на Три Горы воевать с Наполеоном, а что надо уезжать, как ни жалко оставлять на погибель свое имущество. Они уезжали и не думали о величественном значении этой громадной, богатой столицы, оставленной жителями и, очевидно, сожженной (большой покинутый деревянный город необходимо должен был сгореть); они уезжали каждый для себя, а вместе с тем только вследствие того, что они уехали, и совершилось то величественное событие, которое навсегда останется лучшей славой русского народа. Та барыня, которая еще в июне месяце с своими арапами и шутихами поднималась из Москвы в саратовскую деревню, с смутным сознанием того, что она Бонапарту не слуга, и со страхом, чтобы ее не остановили по приказанию графа Растопчина, делала просто и истинно то великое дело, которое спасло Россию. Граф же Растопчин, который то стыдил тех, которые уезжали, то вывозил присутственные места, то выдавал никуда не годное оружие пьяному сброду, то поднимал образа, то запрещал Августину вывозить мощи и иконы, то захватывал все частные подводы, бывшие в Москве, то на ста тридцати шести подводах увозил делаемый Леппихом воздушный шар, то намекал на то, что он сожжет Москву, то рассказывал, как он сжег свой дом и написал прокламацию французам, где торжественно упрекал их, что они разорили его детский приют; то принимал славу сожжения Москвы, то отрекался от нее, то приказывал народу ловить всех шпионов и приводить к нему, то упрекал за это народ, то высылал всех французов из Москвы, то оставлял в городе г жу Обер Шальме, составлявшую центр всего французского московского населения, а без особой вины приказывал схватить и увезти в ссылку старого почтенного почт директора Ключарева; то сбирал народ на Три Горы, чтобы драться с французами, то, чтобы отделаться от этого народа, отдавал ему на убийство человека и сам уезжал в задние ворота; то говорил, что он не переживет несчастия Москвы, то писал в альбомы по французски стихи о своем участии в этом деле, – этот человек не понимал значения совершающегося события, а хотел только что то сделать сам, удивить кого то, что то совершить патриотически геройское и, как мальчик, резвился над величавым и неизбежным событием оставления и сожжения Москвы и старался своей маленькой рукой то поощрять, то задерживать течение громадного, уносившего его вместе с собой, народного потока.