string npos c что это
Как string :: npos узнает, на какую строку я ссылаюсь?
Я работаю над книгой на C ++, и это только покрыто с помощью string::npos проверить, существует ли позиция символа в строке. Я не понимаю, как этот механизм мог знать, к какой строке я обращаюсь! Этот конкретный код считает количество вхождений подстроки.
Я понимаю, что он запускает цикл при первом появлении слова, увеличивая счетчик при каждом проходе, чтобы избежать повторного подсчета одной и той же подстроки, а затем в конце каждого цикла счетчик переходит на позицию следующего появления подстрока. Цикл останавливается, когда счетчик не существует как символьный индекс для строки.
Решение
Например, это может быть реализовано как:
Другие решения
Обратите внимание, что std::string::size_type является unsigned значение и int подписан Если std::string::npos не может быть представлен как int затем преобразование из std::string::npos в int является неопределенным поведением.
Он не знает, на какую строку вы ссылаетесь, npos это просто статический член const, который представляет максимальное значение, представимое и в этом случае представляет и eror, если мы посмотрим, что cppreference говорит о станд :: basic_string :: НСС :
Это специальное значение, равное максимальному значению, представляемому типом size_type. Точное значение зависит от контекста, но обычно оно используется либо как индикатор конца строки функциями, которые ожидают строковый индекс, либо как индикатор ошибки функциями, которые возвращают индекс строки.
который соответствует определению для npos в проект стандарта C ++ в разделе 21.4 Шаблон класса basic_string параграф 5:
что немного странно, так как с size_type является неподписанный но из-за интегральных правил преобразования в разделе 4.7 Интегральные преобразования который говорит:
Если тип назначения является беззнаковым, полученное значение является наименьшим целым числом без знака, соответствующим исходному целому числу (по модулю 2n, где n — число битов, используемых для представления типа без знака). […]
В противном случае, если новый тип без знака, значение преобразуется путем многократного добавления или
вычитание больше, чем максимальное значение, которое может быть представлено в новом типе
пока значение не окажется в диапазоне нового типа.
Работа со строками на этапе компиляции в современном C++
Если вы программируете на C++, то наверняка задавались вопросом почему нельзя сравнить два строковых литерала или выполнить их конкатенацию:
Впрочем, как говорится, «нельзя, но если очень хочется, то можно». Ломать стереотипы будем под катом, причем прямо на этапе компиляции.
Зачем все это нужно
В одном из проектов, над которым я работал, было принято использовать std::string в качестве строковых констант. В проекте было несколько модулей, в которых были определены глобальные строковые константы:
Кроме того, такой подход имеет еще ряд недостатков. Во-первых, брошенное при создании глобального объекта исключение не отлавливается. Во-вторых, инициализация происходит при выполнении программы, что тратит драгоценное процессорное время.
Именно тогда у меня возникла идея о работе со строками на этапе компиляции, которая в итоге и привела к написанию этой статьи.
В этой статье рассмотрим строки, операции над которыми можно проводить на этапе компиляции. Назовем такие строки статическими.
Все реализованные операции были включены в библиотеку для работы со статическими строками. Исходные коды библиотеки доступны на github, ссылка в конце статьи.
Для использования библиотеки требуется как минимум C++14.
Определение статической строки
Определим статическую строку как массив символов, для удобства будем считать, что строка всегда оканчивается нулевым символом:
Здесь можно пойти по другому пути, и определить строку как кортеж символов. Мне этот вариант показался более трудоемким и менее удобным. Поэтому здесь он рассмотрен не будет.
Создание статической строки
Посмотрите на определение строки hello выше, оно просто ужасно. Во-первых, нам нужно заранее вычислять длину массива. Во-вторых, нужно не забыть записать нулевой символ в конец. В-третьих, все эти запятые, скобки и кавычки. Определенно, с этим нужно что-то делать. Хотелось бы написать как-нибудь так:
Здесь нам поможет одна из форм вариативного шаблона, которая позволяет развернуть шаблонные аргументы как индексы для агрегатной инициализации нашей статической строки из строкового литерала:
Уже лучше, но индексы все же приходится писать руками. Здесь также отметим, что если указывать не все индексы, то можно получить подстроку строкового литерала, а если записать их в обратном порядке, то и его инверсию:
Это соображение очень пригодится нам в дальнейшем.
Теперь нам нужно как-то сгенерировать последовательность индексов строки. Для этого применим трюк с наследованием. Определим пустую структуру (нужно же что-то наследовать) с набором искомых индексов в качестве шаблонных параметров:
Определим структуру-генератор, которая будет генерировать индексы по одному, храня счетчик в первом параметре:
Позаботимся и о конечной точке рекурсии, когда все индексы сгенерированы (счетчик равен нулю), мы отбрасываем счетчик и генератор превращается в нужную нам последовательность:
В итоге, функция создания статической строки будет выглядеть так:
Напишем аналогичную функцию для статической строки, она пригодится нам далее:
Поскольку длина строкового литерала нам известна, мы можем автоматически сгенерировать последовательность индексов, напишем обертку для функции выше:
Эта функция позволяет сделать ровно то, что мы хотели в начале главы.
В случае отсутствия аргументов будем возвращать пустую статическую строку, которая состоит только из нулевого символа:
Также нам понадобится создавать строку из кортежа символов:
К слову, все, что далее будет описано в этой статье, опирается на приемы, которые описаны в данной главе. Поэтому, если что-то осталось непонятным, лучше перечитать главу еще раз.
Вывод статической строки в поток
Здесь все просто. Так как наша строка оканчивается нулевым символом, достаточно вывести в поток данные массива:
Преобразование статической строки в std::string
Здесь тоже ничего сложного. Инициализируем строку данными массива:
Сравнение статических строк
Будем сравнивать строки посимвольно, пока не выявим различия, либо не достигнем конца хотя бы одной из строк. Поскольку constexpr for еще не изобрели, воспользуемся рекурсией и тернарным оператором:
В дальнейшем, нам понадобится расширенная версия компаратора, введем индивидуальный индекс для каждой их строк, также ограничим количество сравниваемых символов:
Такая версия компаратора позволит нам сравнивать не только строки целиком, но и отдельные подстроки.
Конкатенация статических строк
Для конкатенации используем тот же вариативный шаблон, что и в главе про создание статической строки. Инициализируем массив сначала символами первой строки (без учета нулевого символа), затем второй, и наконец добавляем нулевой символ в конец:
Реализуем также вариативный шаблон для конкатенации произвольного количества строк или строковых литералов:
Операции поиска в статической строке
Рассмотрим операции поиска символа и подстроки в статической строке.
Поиск символа в статической строке
Поиск символа не представляет особенной сложности, рекурсивно проверяем символы по всем индексам и возвращаем первый индекс в случае совпадения. Также дадим возможность задавать начальную позицию поиска и порядковый номер совпадения:
Константа static_string_npos указывает на то, что поиск не увенчался успехом. Определим ее следующим образом:
Аналогично реализуем поиск в обратном направлении:
Определение вхождения символа в статическую строку
Для определения вхождения символа достаточно попробовать поискать его:
Подсчет количества вхождений символа в статическую строку
Подсчет количества вхождений реализуется тривиально:
Поиск подстроки в статической строке
Так как предполагается, что статические строки будут относительно небольшими, не будем здесь реализовывать алгоритм Кнута-Морриса-Пратта, реализуем простейший квадратичный алгоритм:
Аналогично реализуем поиск в обратном направлении:
Определение вхождения подстроки в статическую строку
Для определения вхождения подстроки достаточно попробовать поискать ее:
Определение, начинается/кончается ли статическая строка с/на заданной подстроки
Применив ранее описанный компаратор мы можем определить, начинается ли статическая строка с заданной подстроки:
Аналогично для окончания статической строки:
Работа с подстроками статической строки
Здесь рассмотрим операции, связанные с подстроками статической строки.
Получение подстроки, префикса и суффикса статической строки
Как мы отметили ранее, для получения подстроки нужно сгенерировать последовательность индексов, с заданным начальным и конечным индексами:
Реализуем получение подстроки с проверкой начала и конца подстроки с помощью static_assert :
Префикс — это подстрока, начало которой совпадает с началом исходной статической строки:
Аналогично для суффикса, только совпадает конец:
Разделение статической строки на две части по заданному индексу
Чтобы разделить статическую строку по заданному индексу, достаточно вернуть префикс и суффикс:
Реверсирование статической строки
Для реверсирования статической строки напишем генератор индексов, который генерирует индексы в обратном порядке:
Теперь реализуем функцию, которая реверсирует статическую строку:
Вычисление хэша статической строки
Вычислять хэш будем по следующей формуле:
H(s) = (s0 + 1) ⋅ 33 0 + (s1 + 1) ⋅ 33 1 +… + (sn — 1 + 1) ⋅ 33 n — 1 + 5381 ⋅ 33 n mod 2 64
Преобразование числа в статическую строку и обратно
Преобразование числа в статическую строку
Для преобразования числа в статическую строку нам нужно получить все цифры числа, преобразовать их в соответствующие символы и составить из этих символов строку.
Для получения всех цифр числа будем использовать генератор, аналогичный генератору последовательности индексов. Определим последовательность символов:
Реализуем генератор символов цифр, храня текущее число в первом параметре, а цифры в следующих, очередная цифра добавляется в начало последовательности, а число делится на десять:
Если текущее число равно 0, то отбрасываем его, возвращая последовательность цифр, больше преобразовывать нечего:
Следует также учесть случай, когда первоначальное число равно нулю, в этом случае нужно вернуть нулевой символ, иначе нуль будет преобразован в пустую последовательность символов, а потом и в пустую строку:
Реализованный генератор прекрасно работает для положительных чисел, но не пригоден для отрицательных. Определим новый генератор, добавив в начало еще один шаблонный параметр — знак преобразуемого числа:
Будем обрабатывать число также, как показано выше, но с учетом знака:
Отбрасываем число после обработки, если оно отрицательно, добавим символ знака минуса:
Отдельно позаботимся о преобразовании нуля:
Наконец, реализуем функции преобразования:
Преобразование статической строки в число
Для преобразования статической строки в число нужно преобразовать символы в цифры, а затем сложить их, предварительно домножив на соответствующую степень десятки. Выполняем все действия рекурсивно, для пустой строки возвращаем нуль:
Для преобразования знаковых чисел, нужно учесть, что отрицательные числа начинаются с символа знака минуса:
Вопросы удобства использования библиотеки
К этому моменту библиотеку уже возможно полноценно использовать, но некоторые моменты вызывают неудобство. В этой главе рассмотрим как можно сделать использование библиотеки более удобным.
Объект статической строки
Упакуем строку и реализованные методы в объект. Это позволит использовать более короткие имена методов, а также реализовать операторы сравнения:
Операторы сравнения
Использование компаратора в виде функции неудобно и нечитаемо. Определим глобальные операторы сравнения:
Макросы работы с числами
Для удобства преобразования числа в статическую строку и обратно определим соотвествующие макросы:
Примеры использования библиотеки
Ниже приведены примеры реального использования реализованной библиотеки.
Конкатенация статических строк и строковых литералов:
Конкатенация статических строк, строковых литералов и чисел:
Итерация по символам в обоих направлениях:
Ссылки
Библиотеку, реализующую все вышеперечисленное, можно взять в моем github
Спасибо за внимание, замечания и дополнения приветствуются.
Update
Реализовал пользовательский литерал _ss для создания статических строк из строковых литералов:
Функцию make_static_string() запрятал во внутренний немспейс, все стало выглядеть приятнее:
Добавил шаблонный параметр Char вместо char:
Сделал специализации для char и whar_t, нижние используются в качестве неймспейсов, чтобы дергать статическую concat, которую внес в структуру статической строки:
Теперь все работает и для «широких» литералов:
Поправил метод size(), теперь size() и length() возвращают длину строки без учета нулевого символа, для получения размера массива нужно использовать sizeof():
Обновленная версия лежит на github
Спасибо всем за полезные комментарии.
Update 2
В ходе обсуждения с AndreySu появился еще один способ реализации статических строк, где символы передаются как шаблонные параметры:
Детальное рассмотрение этого варианта выходит за рамки статьи, буду рад, если кто-то из читателей займется доведением его до ума.
Строки и потоки ввода-вывода C++
Кувшинов Д.Р.
Кодировки
Кодировка символов — способ записи последовательности символов (строки) с помощью последовательности натуральных чисел (“кодов”). В простейшем случае кодировка задаётся таблицей символов, в которой перечислены все доступные символы, и каждому из них присвоен код (номер). Как правило, в более сложных случаях такая таблица всё равно есть, но кодировка включает в себя особенности оформления кодов с целью уменьшения размера сообщения в байтах.
ASCII
ASCII (от American Standard Code for Information Interchange — “американский стандартный код для обмена информацией”) — кодировка символов, получившая широкое распространение.
Кодировка ASCII содержит 128 символов, каждому из которых соответствует своя последовательность семи бит (двоичная запись номера символа).
Управляющие символы
Первые 32 кода и последний (символ 127) выделены для специальных управляющих символов. Большинство этих кодов были важны во времена использования телетайпов и других подобных устройств, напрямую управлявшихся последовательностью переданных на них символов, и в настоящее время практически не используются. Символ 127 ( DEL ) использовался для уничтожения содержимого перфоленты при записи поверх старого содержимого (код 127 соответствует семи пробитым отверстиям).
| Номер | Номер16 | Символ | Запись в C | Смысл |
|---|---|---|---|---|
| 0 | 00 | null character NUL | \0 | нулевой символ — конец си-строки |
| 7 | 07 | bell BEL | \a | звуковой сигнал |
| 8 | 08 | backspace BS | \b | сдвинуть каретку влево на одну позицию |
| 9 | 09 | horizontal tabulation TAB | \t | сдвинуть каретку вправо до следующей колонки |
| 10 | 0A | line feed LF | \n | сдвинуть каретку вниз на одну строку (новая строка) |
| 11 | 0B | vertical tabulation VT | \v | сдвинуть каретку вниз до следующей группы строк |
| 12 | 0C | form feed FF | \f | подать новый лист |
| 13 | 0D | carriage return CR | \r | вернуть каретку на начало строки |
| 27 | 1B | escape ESC | \x1b | переключиться в режим приёма управляющей последовательности |
| 127 | 7F | delete DEL | \x7f | удалить следующий символ |
располагались в шрифтах выше букв), подчёркивания (пропечатать символ _ поверх подчёркиваемого текста).
Печатные символы
| Номера | Номера16 | Символы | Запись в C |
|---|---|---|---|
| 32 | 20 | пробел | пробел |
| 34 | 22 | двойные кавычки « | \» |
| 39 | 27 | кавычка ‘ | \’ |
| 48–57 | 30–39 | цифры 0–9 | 0 – 9 |
| 65–90 | 41–5A | заглавные латинские буквы A–Z | A – Z |
| 92 | 5C | обратная косая черта \ | \\ |
| 95 | 5F | знак подчёркивания | _ |
| 97–122 | 61–7A | строчные латинские буквы a–z | a – z |
Восьмибитные кодировки
К сожалению, такие восьмибитные кодировки не могли решить проблему как кодирования письменностей, в которых большое количество знаков (например, китайская) или записи текстов, включающих символы из разных письменностей.
Юникод
Кодировка UTF-32 (UTF-32BE для BE-порядка байт, UTF-32LE для LE-порядка байт) передаёт каждую кодовую позицию 4-байтным целым (номером в UCS, поэтому UTF-32 также обозначают как UCS-4). Эта кодировка сравнительно удобна для работы с Юникод-текстами в памяти, но считается недостаточно компактной для задач хранения и передачи текстов. К сожалению, даже в случае UTF-32 одному знакоместу (графическому изображению символа) на экране может соответствовать больше одного 4-байтного кода, его формирующих.
Кодировка UTF-8 передаёт каждую кодовую позицию последовательностью байт (от 1 до 4). При этом, текст в кодировке ASCII является текстом в кодировке UTF-8 (обратная совместимость), а для представления дополнительных символов используются байты с установленным старшим битом. Данная кодировка на данный момент является самым распространённым способом передачи текстов по сети Интернет. Её преимуществами, в частности, являются компактность представления символов ASCII и независимость от порядка байт (нет проблемы big endian vs little endian).
Тема работы с Юникодом (и строковыми данными вообще) очень обширна и содержит множество тонкостей, здесь рассматриваются лишь некоторые простые элементы в аспекте программирования на C и C++. Для серьёзного изучения как Юникода, так и затронутых здесь разделов стандартной библиотеки C++ следует обратиться к специализированным источникам.
Типы символов в C++
В начале развития стандарта Юникод в C++ был введён новый тип символа — wchar_t (т.е. “широкий символ” wide character ), по определению являющийся целочисленным типом с диапазоном, достаточным для представления всех символов, доступных на данной системе. Так как поначалу предполагалось, что Юникоду “хватит” 16 бит для представления всех номеров UCS, в некоторых системах (например, Windows) был закреплён 16-битный wchar_t. В современных GNU/Linux-системах используется 32-битный wchar_t, подходящий для кодировки UTF-32.
Литералы
Символьные литералы
Стандартные экранированные последовательности для некоторых управляющих символов, а также специальных символов (обратная косая черта, кавычки) приведены в таблицах выше в колонках под заголовком “Запись в C”.
При записи непосредственно символа в литерал, компилятор может оставить код в той кодировке, в которой символ был введён, либо преобразовать в некоторую кодировку “по умолчанию”. Например, исходный код может быть набран в кодировке UTF-8, в которой кириллические знаки записываются двухбайтными кодами, но компилятор Visual C++ при оформлении символьного литерала типа char (один байт) преобразует их к кодировке Windows-1251.
Выбор конкретного типа символа осуществляется с помощью префикса.
| Тип | Префикс | Пример | Стандарт | Диапазон |
|---|---|---|---|---|
| char | нет | ‘a’ | C90 | системная кодировка |
| wchar_t | L | L’ф’ | C++98 | системная кодировка |
| char16_t | u | u’ф’ | С++11 | UCS-2 |
| char32_t | U | U’∀’ | C++11 | UCS-4 |
| char8_t | u8 | u8’z’ | C++17 (план) | ASCII |
Строковые литералы
Строковый литерал — представление константной последовательности символов непосредственно в тексте программы. Строковые литералы записываются в двойных кавычках и могут не содержать ни одного символа. Максимальное допустимое количество символов с строковом литерале определяется компилятором.
Каждому строковому литералу соответствует константный массив соответствующего символьного типа, содержащий символы литерала в соответствующей символьному литералу кодировке плюс завершающий нулевой символ. Поэтому реальный размер такого массива, по крайней мере, на единицу больше числа символов в нём.
Строковый литерал может содержать такие же экранированные последовательности, как символьный литерал. Каждой экранированной последовательности соответствует один символ.
Расположенные подряд строковые литералы, разделённые лишь пробельными символами и комментариями, автоматически конкатенируются в один строковый литерал. Например:
| Префикс | Пример | Кодировка | Тип символа | Стандарт |
|---|---|---|---|---|
| нет | «two words» | системная | char | C90 |
| L | L»два слова» | системная | wchar_t | C++98 |
| R | R»!(C:\User\)!» | см. ниже | см. ниже | C++11 |
| u | u»∀ε>0 ∃δ « | UTF-16 | char16_t | C++11 |
| U | U»A∨¬A» | UTF-32 | char32_t | C++11 |
| u8 | u8″escape-знак» | UTF-8 | char8_t | C++11 |
Префикс R (от англ. raw — “сырой”) позволяет ввести строку без экранирования символов: все символы между R“ разделитель ( и ) разделитель ” включаются в литерал. Здесь разделитель — произвольная последовательность символов, которая выбирается так, чтобы она (с закрывающей скобкой) не встречалась в самой строке. Перед префиксом R можно поставить префикс, определяющий тип символа и кодировку.
Стандартный заголовочный файл cstring
Си-строка или нуль-терминированная строка — структура данных, представляющая собой массив символов, последний из которых (и только он) является нулевым. Так как нулевой символ маркирует конец си-строки, для передачи её в функцию достаточно передать указатель на её начало. Любой указатель на символ некоторой си-строки является указателем на её подстроку — тоже си-строку.
Заголовочный файл cstring содержит базовый функционал для работы с си-строками и массивами символов (байт). Массивы байт передаются парой (указатель (типа void* ), размер (в байтах)). Далее приведены краткие описания некоторых стандартных функций, объявленных в этом заголовочном файле.
Для краткости даны объявления функций только для языка C. В случае C++ нередко существуют аналогичные пары функций с различной константностью (C “теряет” константность), например, в C:
В то же время в C++ (в пространстве имён std) имеется сразу два варианта:
Блоки памяти
Си-строки
Все эти функции порождают неопределённое поведение, если в качестве параметра, подразумевающего передачу адреса си-строки с завершающим нулём, передаётся указатель, не указывающий на си-строку.
Также существуют аналоги данных функций для работы с wchar_t и многобайтными кодировками.
Стандартный заголовочный файл string
Возможности C++ позволяют определить тип данных, объекты которого самостоятельно управляют массивом символов (строкой) и предоставляют набор удобных в использовании базовых операций.
| Тип строки | Тип элемента | Стандарт |
|---|---|---|
| string | char | C++98 |
| wstring | wchar_t | C++98 |
| u16string | char16_t | C++11 |
| u32string | char32_t | C++11 |
Все перечисленные строковые типы по существу устроены одинаково и предоставляют одинаковые с точностью до типа данных наборы операций. Фактически они являются объектами, управляющими динамическими массивами символов, в которых и хранятся строки. В отличие от си-строк, данные объекты позволяют хранить произвольные символы, включая нулевые. Строки можно сравнивать с помощью обычных операций сравнения вроде == и (используется лексикографический порядок).
Простейшие операции с объектами string
Далее приведены примеры использования некоторых возможностей стандартных строк.
В заголовочном файле string также определены удобные функции преобразования между числами и их строковыми представлениями:
Создание строк
Класс string предоставляет набор конструкторов, некоторые из которых могут пригодиться, например, при выполнении заданий из самостоятельной 11.
Примеры даны в двух вариантах: определение переменной типа string и создание временного объекта типа string.
Вставка, удаление и замена подстрок
Вставка подстрок может осуществляться с помощью функций append (в конец) и insert (на произвольную позицию).
Поиск в строке
Элементы библиотеки Iostreams
Базовые элементы
Вывод текстового представления значения value в stdout выполняется с помощью оператора
Далее идёт листинг, демонстрирующий некоторые возможности средств текстового ввода-вывода стандартной библиотеки C++. Возможно, не всё из этого будет понятно на данном этапе, однако, оно может пригодиться в дальнейшем.
“Задержка экрана” в простых случаях может быть выполнена с помощью чтения символа с cin (функции get и ignore ). Если буфер ввода пуст, то исполнение программы остановится до тех пор, пока пользователь не введёт что-нибудь.
К сожалению, такой нехитрый приём не работает в ряде случаев, когда поток ввода содержит неопределённое количество “мусора”. Более универсальный метод представлен в примере по ссылке.
Использование fstream
В целом, можно считать, что объекты ifstream ведут себя как cin, а объекты ofstream ведут себя как cout.
Файл позволяет произвольно изменять позицию чтения (для ifstream) и позицию записи (для ofstream).
Допускается открытие одного и того же файла сразу несколькими объектами ifstream. Каждый из них будет читать данные со своей позиции чтения.
Использование sstream
Аналогично, можно считать, что объекты istringstream ведут себя как cin, а объекты ostringstream ведут себя как cout. Функция-член str() позволяет обращаться к содержимому потока как к строке типа string: str() возвращает копию содержимого потока в виде строки, а str(строка) устанавливает новое содержимое потока.
В случае записи “поверх” уже записанных данных потоки вывода (и ostringstream и ofstream) просто затирают символы на позиции записи. Вставка символов или удаление “хвоста” не осуществляются.
Впрочем, данное действие довольно бессмысленно. Если мы хотим показать, что идёт некий процесс, можно выполнять небольшую часть работы между сменами знака “палочки”. В примере ниже функция do_next_job выполняет некоторый фрагмент задачи и возвращает true, если надо продолжить ожидание, и false, если работа завершена:
iostream-типы
Существует набор стандартных типов, механически сочетающих в себе интерфейсы потока ввода istream и потока вывода ostream. В частности, они предоставляют две независимых позиции: позицию чтения и позицию записи. С их помощью можно работать с файлом (тип fstream ) или строкой (тип stringstream ) как с расширяемым массивом байт, который можно и читать и изменять.
Пример использования stringstream для тестирования функции, читающей данные из потока в примере 0520-euclid_norm_2.cpp: