Что означает string :: npos в этом коде?
Что означает фраза std::string::npos в следующем фрагменте кода?
Значит не найдено.
Обычно это определяется так:
Лучше сравнивать с npos вместо -1, потому что код более разборчивый.
string::npos — это константа (вероятно -1 ), представляющая непозицию. Он возвращается методом, find когда шаблон не найден.
В документе string::npos говорится:
npos — это статическое значение константы члена с максимально возможным значением для элемента типа size_t.
В качестве возвращаемого значения оно обычно используется для обозначения сбоя.
Эта константа фактически определяется со значением -1 (для любого признака), которое, поскольку size_t является целочисленным типом без знака, становится максимально возможным представимым значением для этого типа.
size_t является беззнаковой переменной, поэтому ‘unsigned value = — 1’ автоматически делает ее максимально возможным значением для size_t : 18446744073709551615
std::string::npos — это индекс, определяемый реализацией, который всегда выходит за пределы любого std::string экземпляра. Различные std::string функции возвращают или принимают его, чтобы сигнализировать о конце строки. Обычно это какой-то беззнаковый целочисленный тип, и его значение обычно std::numeric_limits<std::string::size_type>::max () (благодаря стандартным целочисленным предложениям) обычно сопоставимо с -1 .
мы должны использовать string::size_type тип возвращаемого значения функции поиска, иначе сравнение с string::npos может не работать. size_type , который определяется распределителем строки, должен быть unsigned целочисленным типом. Распределитель по умолчанию, распределитель, использует тип size_t как size_type . Поскольку -1 он преобразуется в целочисленный тип без знака, npos является максимальным беззнаковым значением его типа. Однако точное значение зависит от точного определения типа size_type . К сожалению, эти максимальные значения различаются. Фактически, (unsigned long)-1 отличается от (unsigned short)- 1, если размер типов отличается. Таким образом, сравнение
может дать false, если idx имеет значение -1 и idx и string::npos имеет разные типы:
Один из способов избежать этой ошибки — проверить, не завершился ли поиск напрямую:
Однако часто вам нужен индекс соответствующей позиции символа. Таким образом, еще одно простое решение — определить собственное значение со знаком для npos:
Работа со строками на этапе компиляции в современном C++
Если вы программируете на C++, то наверняка задавались вопросом почему нельзя сравнить два строковых литерала или выполнить их конкатенацию:
Впрочем, как говорится, «нельзя, но если очень хочется, то можно». Ломать стереотипы будем под катом, причем прямо на этапе компиляции.
Зачем все это нужно
В одном из проектов, над которым я работал, было принято использовать std::string в качестве строковых констант. В проекте было несколько модулей, в которых были определены глобальные строковые константы:
Думаю, вы уже догадались, что случилось в один прекрасный день. SAMPLE_PLUGIN_PATH приняла значение «sample.so» , несмотря на то, что PLUGIN_PATH имела значение «/usr/local/lib/project/plugins/» , как и ожидалось. Как это могло произойти? Все очень просто, порядок инициализации глобальных объектов не определен, в момент инициализации SAMPLE_PLUGIN_PATH переменная PLUGIN_PATH была пуста.
Кроме того, такой подход имеет еще ряд недостатков. Во-первых, брошенное при создании глобального объекта исключение не отлавливается. Во-вторых, инициализация происходит при выполнении программы, что тратит драгоценное процессорное время.
Именно тогда у меня возникла идея о работе со строками на этапе компиляции, которая в итоге и привела к написанию этой статьи.
В этой статье рассмотрим строки, операции над которыми можно проводить на этапе компиляции. Назовем такие строки статическими.
Все реализованные операции были включены в библиотеку для работы со статическими строками. Исходные коды библиотеки доступны на github, ссылка в конце статьи.
Для использования библиотеки требуется как минимум C++14.
Определение статической строки
Определим статическую строку как массив символов, для удобства будем считать, что строка всегда оканчивается нулевым символом:
Здесь можно пойти по другому пути, и определить строку как кортеж символов. Мне этот вариант показался более трудоемким и менее удобным. Поэтому здесь он рассмотрен не будет.
Создание статической строки
Посмотрите на определение строки hello выше, оно просто ужасно. Во-первых, нам нужно заранее вычислять длину массива. Во-вторых, нужно не забыть записать нулевой символ в конец. В-третьих, все эти запятые, скобки и кавычки. Определенно, с этим нужно что-то делать. Хотелось бы написать как-нибудь так:
Здесь нам поможет одна из форм вариативного шаблона, которая позволяет развернуть шаблонные аргументы как индексы для агрегатной инициализации нашей статической строки из строкового литерала:
Уже лучше, но индексы все же приходится писать руками. Здесь также отметим, что если указывать не все индексы, то можно получить подстроку строкового литерала, а если записать их в обратном порядке, то и его инверсию:
Это соображение очень пригодится нам в дальнейшем.
Теперь нам нужно как-то сгенерировать последовательность индексов строки. Для этого применим трюк с наследованием. Определим пустую структуру (нужно же что-то наследовать) с набором искомых индексов в качестве шаблонных параметров:
Определим структуру-генератор, которая будет генерировать индексы по одному, храня счетчик в первом параметре:
Позаботимся и о конечной точке рекурсии, когда все индексы сгенерированы (счетчик равен нулю), мы отбрасываем счетчик и генератор превращается в нужную нам последовательность:
В итоге, функция создания статической строки будет выглядеть так:
Напишем аналогичную функцию для статической строки, она пригодится нам далее:
В дальнейшем, для каждой функции, принимающей строковый литерал foo(const char (& str)[Size]) будем писать аналогичную функцию, принимающую статическую строку foo(const static_string<Size>& str) . Но я, для краткости, упоминать об этом не буду.
Поскольку длина строкового литерала нам известна, мы можем автоматически сгенерировать последовательность индексов, напишем обертку для функции выше:
Эта функция позволяет сделать ровно то, что мы хотели в начале главы.
В случае отсутствия аргументов будем возвращать пустую статическую строку, которая состоит только из нулевого символа:
Также нам понадобится создавать строку из кортежа символов:
К слову, все, что далее будет описано в этой статье, опирается на приемы, которые описаны в данной главе. Поэтому, если что-то осталось непонятным, лучше перечитать главу еще раз.
Вывод статической строки в поток
Здесь все просто. Так как наша строка оканчивается нулевым символом, достаточно вывести в поток данные массива:
Преобразование статической строки в 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
Преобразование числа в статическую строку и обратно
В этой главе рассмотрим преобразование статической строки в целое число, а также обратное преобразование. Для простоты будем считать, что числа представлены типами long long и unsigned long long , это типы большой разрядности, то есть подходят для большинства случаев.
Преобразование числа в статическую строку
Для преобразования числа в статическую строку нам нужно получить все цифры числа, преобразовать их в соответствующие символы и составить из этих символов строку.
Для получения всех цифр числа будем использовать генератор, аналогичный генератору последовательности индексов. Определим последовательность символов:
Реализуем генератор символов цифр, храня текущее число в первом параметре, а цифры в следующих, очередная цифра добавляется в начало последовательности, а число делится на десять:
Если текущее число равно 0, то отбрасываем его, возвращая последовательность цифр, больше преобразовывать нечего:
Следует также учесть случай, когда первоначальное число равно нулю, в этом случае нужно вернуть нулевой символ, иначе нуль будет преобразован в пустую последовательность символов, а потом и в пустую строку:
Реализованный генератор прекрасно работает для положительных чисел, но не пригоден для отрицательных. Определим новый генератор, добавив в начало еще один шаблонный параметр — знак преобразуемого числа:
Будем обрабатывать число также, как показано выше, но с учетом знака:
Здесь есть один тонкий момент, обратите внимание на -(Value % 10) . Здесь нельзя -Value % 10 , так как диапазон отрицательных чисел на одно число шире диапазона положительных и модуль минимального числа выпадает из множества допустимых значений.
Отбрасываем число после обработки, если оно отрицательно, добавим символ знака минуса:
Отдельно позаботимся о преобразовании нуля:
Наконец, реализуем функции преобразования:
Преобразование статической строки в число
Для преобразования статической строки в число нужно преобразовать символы в цифры, а затем сложить их, предварительно домножив на соответствующую степень десятки. Выполняем все действия рекурсивно, для пустой строки возвращаем нуль:
Для преобразования знаковых чисел, нужно учесть, что отрицательные числа начинаются с символа знака минуса:
Вопросы удобства использования библиотеки
К этому моменту библиотеку уже возможно полноценно использовать, но некоторые моменты вызывают неудобство. В этой главе рассмотрим как можно сделать использование библиотеки более удобным.
Объект статической строки
Упакуем строку и реализованные методы в объект. Это позволит использовать более короткие имена методов, а также реализовать операторы сравнения:
Операторы сравнения
Использование компаратора в виде функции неудобно и нечитаемо. Определим глобальные операторы сравнения:
Аналогично реализуем остальные операторы > <= >= == !=, для всех вариаций аргументов статических строк и строковых литералов. Здесь приводить их нет смысла из-за тривиальности.
Макросы работы с числами
Для удобства преобразования числа в статическую строку и обратно определим соотвествующие макросы:
Примеры использования библиотеки
Ниже приведены примеры реального использования реализованной библиотеки.
Конкатенация статических строк и строковых литералов:
Конкатенация статических строк, строковых литералов и чисел:
Итерация по символам в обоих направлениях:
Ссылки
Библиотеку, реализующую все вышеперечисленное, можно взять в моем github
Спасибо за внимание, замечания и дополнения приветствуются.
Update
Реализовал пользовательский литерал _ss для создания статических строк из строковых литералов:
Функцию make_static_string() запрятал во внутренний немспейс, все стало выглядеть приятнее:
Добавил шаблонный параметр Char вместо char:
Сделал специализации для char и whar_t, нижние используются в качестве неймспейсов, чтобы дергать статическую concat, которую внес в структуру статической строки:
Теперь все работает и для «широких» литералов:
Поправил метод size(), теперь size() и length() возвращают длину строки без учета нулевого символа, для получения размера массива нужно использовать sizeof():
Обновленная версия лежит на github
Спасибо всем за полезные комментарии.
Update 2
В ходе обсуждения с AndreySu появился еще один способ реализации статических строк, где символы передаются как шаблонные параметры:
Детальное рассмотрение этого варианта выходит за рамки статьи, буду рад, если кто-то из читателей займется доведением его до ума.
Что означает string:: npos
лучше сравнивать с НКО, а не -1, потому что код более читаемым.
string::npos константа (наверное -1 ), представляющая не-позиции. Он возвращается методом find когда шаблон не был найден.
НКО — это статическое постоянное значение члена с максимально возможным значением для элемента типа size_t.
в качестве возвращаемого значения обычно используется для обозначения сбоя.
эта константа фактически определяется значением -1 (для любого признака), которое, поскольку size_t является беззнаковым интегральным типом, становится максимально возможным представимым значением для этого типа.
size_t является беззнаковой переменной, поэтому «unsigned value = — 1» автоматически делает его максимально возможным значением для size_t : 18446744073709551615
std::string::npos — Это определенный индекс реализации, который всегда выходит за рамки любого std::string экземпляра. Различные std::string функции возвращают его или принимают его для сигнала за пределами конца Строковой ситуации. Обычно он имеет некоторый целочисленный тип без знака, и его значение обычно std::numeric_limits<std::string::size_type>::max () который (благодаря стандартным целочисленным акциям) обычно сопоставим с -1 .
found будет npos в случае невозможности найти подстроку в строке поиска.
мы должны использовать string::size_type для возвращаемого типа функции find в противном случае сравнение с string::npos может не работать. size_type , который определяется распределителем строки, должен быть unsigned целочисленный тип. Распределитель по умолчанию, распределитель, использует тип size_t as size_type . Потому что -1 is преобразованные в беззнаковый интегральный тип, НКО-это максимальное беззнаковое значение его типа. Однако, точное значение зависит от точного определения типа size_type . К сожалению, эти максимальный значения различаются. На самом деле, (unsigned long)-1 отличается от (unsigned short)- 1 если размер типы различаются. Таким образом, сравнение
может дать false, если idx имеет значение -1 и idx и string::npos имеют различные типы:
один из способов избежать этой ошибки-проверить, не происходит ли поиск напрямую:
однако часто вам нужен индекс соответствующей позиции символа. Таким образом, еще одно простое решение это определить свой собственный подписанное значение для НКО:
теперь сравнение выглядит немного по-другому и даже удобнее:
он возвращается строковыми функциями, указывающими на ошибку / не найден и т. д.