Работа со строками на этапе компиляции в современном C++
Если вы программируете на C++, то наверняка задавались вопросом почему нельзя сравнить два строковых литерала или выполнить их конкатенацию:
auto str = "hello" + "world"; // ошибка компиляции
if ("hello" < "world") { // компилируется, но работает не так, как ожидалось
// ...
}
Впрочем, как говорится, «нельзя, но если очень хочется, то можно». Ломать стереотипы будем под катом, причем прямо на этапе компиляции.
Зачем все это нужно
В одном из проектов, над которым я работал, было принято использовать std: string в качестве строковых констант. В проекте было несколько модулей, в которых были определены глобальные строковые константы:
// plugin.h
const std::string PLUGIN_PATH = "/usr/local/lib/project/plugins/";
// ...
// sample_plugin.h
const std::string SAMPLE_PLUGIN_LIB = PLUGIN_PATH + "sample.so";
// ...
Думаю, вы уже догадались, что случилось в один прекрасный день. SAMPLE_PLUGIN_PATH приняла значение "sample.so", несмотря на то, что PLUGIN_PATH имела значение "/usr/local/lib/project/plugins/", как и ожидалось. Как это могло произойти? Все очень просто, порядок инициализации глобальных объектов не определен, в момент инициализации SAMPLE_PLUGIN_PATH переменная PLUGIN_PATH была пуста.
Кроме того, такой подход имеет еще ряд недостатков. Во-первых, брошенное при создании глобального объекта исключение не отлавливается. Во-вторых, инициализация происходит при выполнении программы, что тратит драгоценное процессорное время.
Именно тогда у меня возникла идея о работе со строками на этапе компиляции, которая в итоге и привела к написанию этой статьи.
В этой статье рассмотрим строки, операции над которыми можно проводить на этапе компиляции. Назовем такие строки статическими.
Все реализованные операции были включены в библиотеку для работы со статическими строками. Исходные коды библиотеки доступны на github, ссылка в конце статьи.
Для использования библиотеки требуется как минимум C++14.
Определение статической строки
Определим статическую строку как массив символов, для удобства будем считать, что строка всегда оканчивается нулевым символом:
template
using static_string = std::array;
constexpr static_string<6> hello = {'H', 'e', 'l', 'l', 'o', '\0'};
Здесь можно пойти по другому пути, и определить строку как кортеж символов. Мне этот вариант показался более трудоемким и менее удобным. Поэтому здесь он рассмотрен не будет.
Создание статической строки
Посмотрите на определение строки hello выше, оно просто ужасно. Во-первых, нам нужно заранее вычислять длину массива. Во-вторых, нужно не забыть записать нулевой символ в конец. В-третьих, все эти запятые, скобки и кавычки. Определенно, с этим нужно что-то делать. Хотелось бы написать как-нибудь так:
constexpr auto hello = make_static_string("hello");
Здесь нам поможет одна из форм вариативного шаблона, которая позволяет развернуть шаблонные аргументы как индексы для агрегатной инициализации нашей статической строки из строкового литерала:
template
constexpr static_string make_static_string(const char (& str)[Size]) {
return {str[Indexes] ..., '\0'};
}
constexpr auto hello = make_static_string<0, 1, 2, 3, 4>("hello"); // hello == "hello"
Уже лучше, но индексы все же приходится писать руками. Здесь также отметим, что если указывать не все индексы, то можно получить подстроку строкового литерала, а если записать их в обратном порядке, то и его инверсию:
constexpr hello1 = make_static_string<1, 2, 3>("hello"); // hello1 == "ell"
constexpr hello2 = make_static_string<4, 3, 2, 1, 0>("hello"); // hello2 == "olleh"
Это соображение очень пригодится нам в дальнейшем.
Теперь нам нужно как-то сгенерировать последовательность индексов строки. Для этого применим трюк с наследованием. Определим пустую структуру (нужно же что-то наследовать) с набором искомых индексов в качестве шаблонных параметров:
template
struct index_sequence {};
Определим структуру-генератор, которая будет генерировать индексы по одному, храня счетчик в первом параметре:
template
struct make_index_sequence : make_index_sequence {};
Позаботимся и о конечной точке рекурсии, когда все индексы сгенерированы (счетчик равен нулю), мы отбрасываем счетчик и генератор превращается в нужную нам последовательность:
template
struct make_index_sequence<0, Indexes ...> : index_sequence {};
В итоге, функция создания статической строки будет выглядеть так:
template
constexpr static_string make_static_string(const char (& str)[Size],
index_sequence) {
return {str[Indexes] ..., '\0'};
}
Напишем аналогичную функцию для статической строки, она пригодится нам далее:
template
constexpr static_string make_static_string(const static_string& str,
index_sequence) {
return {str[Indexes] ..., '\0'};
}
В дальнейшем, для каждой функции, принимающей строковый литерал foo(const char (& str)[Size]) будем писать аналогичную функцию, принимающую статическую строку foo(const static_string. Но я, для краткости, упоминать об этом не буду.
Поскольку длина строкового литерала нам известна, мы можем автоматически сгенерировать последовательность индексов, напишем обертку для функции выше:
template
constexpr static_string make_static_string(const char (& str)[Size]) {
return make_static_string(str, make_index_sequence{});
}
Эта функция позволяет сделать ровно то, что мы хотели в начале главы.
В случае отсутствия аргументов будем возвращать пустую статическую строку, которая состоит только из нулевого символа:
constexpr static_string<1> make_static_string() {
return {'\0'};
}
Также нам понадобится создавать строку из кортежа символов:
template
constexpr static_string make_static_string(char_sequence) {
return {Chars ..., '\0'};
}
К слову, все, что далее будет описано в этой статье, опирается на приемы, которые описаны в данной главе. Поэтому, если что-то осталось непонятным, лучше перечитать главу еще раз.
Вывод статической строки в поток
Здесь все просто. Так как наша строка оканчивается нулевым символом, достаточно вывести в поток данные массива:
template
std::ostream& operator<<(std::ostream& os, const static_string& str) {
os << str.data();
return os;
}
Преобразование статической строки в std: string
Здесь тоже ничего сложного. Инициализируем строку данными массива:
template
std::string to_string(const static_string& str) {
return std::string(str.data());
}
Сравнение статических строк
Будем сравнивать строки посимвольно, пока не выявим различия, либо не достигнем конца хотя бы одной из строк. Поскольку constexpr for еще не изобрели, воспользуемся рекурсией и тернарным оператором:
template
constexpr int static_string_compare(
const static_string& str1,
const static_string& str2,
int index = 0) {
return index >= Size1 && index >= Size2 ? 0 :
index >= Size1 ? -1 :
index >= Size2 ? 1 :
str1[index] > str2[index] ? 1 :
str1[index] < str2[index] ? -1 :
static_string_compare(str1, str2, index + 1);
}
В дальнейшем, нам понадобится расширенная версия компаратора, введем индивидуальный индекс для каждой их строк, также ограничим количество сравниваемых символов:
template
constexpr int static_string_compare(
const static_string& str1, size_t index1,
const static_string& str2, size_t index2,
size_t cur_length, size_t max_length) {
return cur_length > max_length || (index1 >= Size1 && index2 >= Size2) ? 0 :
index1 >= Size1 ? -1 :
index2 >= Size2 ? 1 :
str1[index1] > str2[index2] ? 1 :
str1[index1] < str2[index2] ? -1 :
static_string_compare(str1, index1 + 1, str2, index2 + 1, cur_length + 1, max_length);
}
Такая версия компаратора позволит нам сравнивать не только строки целиком, но и отдельные подстроки.
Конкатенация статических строк
Для конкатенации используем тот же вариативный шаблон, что и в главе про создание статической строки. Инициализируем массив сначала символами первой строки (без учета нулевого символа), затем второй, и наконец добавляем нулевой символ в конец:
template
constexpr static_string static_string_concat_2(
const static_string& str1, index_sequence,
const static_string& str2, index_sequence) {
return {str1[Indexes1] ..., str2[Indexes2] ..., '\0'};
}
template
constexpr static_string static_string_concat_2(
const static_string& str1, const static_string& str2) {
return static_string_concat_2(str1, make_index_sequence{},
str2, make_index_sequence{});
}
Реализуем также вариативный шаблон для конкатенации произвольного количества строк или строковых литералов:
constexpr auto static_string_concat() {
return make_static_string();
}
template
constexpr auto static_string_concat(Arg&& arg, Args&& ... args) {
return static_string_concat_2(make_static_string(std::forward(arg)),
static_string_concat(std::forward(args) ...));
}
Операции поиска в статической строке
Рассмотрим операции поиска символа и подстроки в статической строке.
Поиск символа в статической строке
Поиск символа не представляет особенной сложности, рекурсивно проверяем символы по всем индексам и возвращаем первый индекс в случае совпадения. Также дадим возможность задавать начальную позицию поиска и порядковый номер совпадения:
template
constexpr size_t static_string_find(const static_string& str, char ch, size_t from, size_t nth) {
return Size < 2 || from >= Size - 1 ? static_string_npos :
str[from] != ch ? static_string_find(str, ch, from + 1, nth) :
nth > 0 ? static_string_find(str, ch, from + 1, nth - 1) : from;
}
Константа static_string_npos указывает на то, что поиск не увенчался успехом. Определим ее следующим образом:
constexpr size_t static_string_npos = std::numeric_limits::max();
Аналогично реализуем поиск в обратном направлении:
template
constexpr size_t static_string_rfind(const static_string& str, char ch, size_t from, size_t nth) {
return Size < 2 || from > Size - 2 ? static_string_npos :
str[from] != ch ? static_string_rfind(str, ch, from - 1, nth) :
nth > 0 ? static_string_rfind(str, ch, from - 1, nth - 1) : from;
}
Определение вхождения символа в статическую строку
Для определения вхождения символа достаточно попробовать поискать его:
template
constexpr bool static_string_contains(const static_string& str, char ch) {
return static_string_find(str, ch) != static_string_npos;
}
Подсчет количества вхождений символа в статическую строку
Подсчет количества вхождений реализуется тривиально:
template
constexpr size_t static_string_count(const static_string& str, char ch, size_t index) {
return index >= Size - 1 ? 0 :
(str[index] == ch ? 1 : 0) + static_string_count(str, ch, index + 1);
}
Поиск подстроки в статической строке
Так как предполагается, что статические строки будут относительно небольшими, не будем здесь реализовывать алгоритм Кнута-Морриса-Пратта, реализуем простейший квадратичный алгоритм:
template
constexpr size_t static_string_find(const static_string& str, const static_string& substr, size_t from, size_t nth) {
return Size < SubSize || from > Size - SubSize ? static_string_npos :
static_string_compare(str, from, substr, 0, 1, SubSize - 1) != 0 ? static_string_find(str, substr, from + 1, nth) :
nth > 0 ? static_string_find(str, substr, from + 1, nth - 1) : from;
}
Аналогично реализуем поиск в обратном направлении:
template
constexpr size_t static_string_rfind(const static_string& str, const static_string& substr, size_t from, size_t nth) {
return Size < SubSize || from > Size - SubSize ? static_string_npos :
static_string_compare(str, from, substr, 0, 1, SubSize - 1) != 0 ? static_string_rfind(str, substr, from - 1, nth) :
nth > 0 ? static_string_rfind(str, substr, from - 1, nth - 1) : from;
}
Определение вхождения подстроки в статическую строку
Для определения вхождения подстроки достаточно попробовать поискать ее:
template
constexpr bool static_string_contains(const static_string& str, const static_string& substr) {
return static_string_find(str, substr) != static_string_npos;
}
Определение, начинается/кончается ли статическая строка с/на заданной подстроки
Применив ранее описанный компаратор мы можем определить, начинается ли статическая строка с заданной подстроки:
template
constexpr bool static_string_starts_with(const static_string& str, const static_string& prefix) {
return SubSize > Size ? false :
static_string_compare(str, 0, prefix, 0, 1, SubSize - 1) == 0;
}
Аналогично для окончания статической строки:
template
constexpr bool static_string_ends_with(const static_string& str, const static_string& suffix) {
return SubSize > Size ? false :
static_string_compare(str, Size - SubSize, suffix, 0, 1, SubSize - 1) == 0;
}
Работа с подстроками статической строки
Здесь рассмотрим операции, связанные с подстроками статической строки.
Получение подстроки, префикса и суффикса статической строки
Как мы отметили ранее, для получения подстроки нужно сгенерировать последовательность индексов, с заданным начальным и конечным индексами:
template
struct make_index_subsequence : make_index_subsequence {};
template
struct make_index_subsequence : index_sequence {};
Реализуем получение подстроки с проверкой начала и конца подстроки с помощью static_assert:
template
constexpr auto static_string_substring(const static_string& str) {
static_assert(Begin <= End, "Begin is greater than End (Begin > End)");
static_assert(End <= Size - 1, "End is greater than string length (End > Size - 1)");
return make_static_string(str, make_index_subsequence{});
}
Префикс — это подстрока, начало которой совпадает с началом исходной статической строки:
template
constexpr auto static_string_prefix(const static_string& str) {
return static_string_substring<0, End>(str);
}
Аналогично для суффикса, только совпадает конец:
template
constexpr auto static_string_suffix(const static_string& str) {
return static_string_substring(str);
}
Разделение статической строки на две части по заданному индексу
Чтобы разделить статическую строку по заданному индексу, достаточно вернуть префикс и суффикс:
template
constexpr auto static_string_split(const static_string& str) {
return std::make_pair(static_string_prefix(str), static_string_suffix(str));
}
Реверсирование статической строки
Для реверсирования статической строки напишем генератор индексов, который генерирует индексы в обратном порядке:
template
struct make_reverse_index_sequence : make_reverse_index_sequence {};
template
struct make_reverse_index_sequence<0, Indexes ...> : index_sequence {};
Теперь реализуем функцию, которая реверсирует статическую строку:
template
constexpr auto static_string_reverse(const static_string& str) {
return make_static_string(str, make_reverse_index_sequence{});
}
Вычисление хэша статической строки
Вычислять хэш будем по следующей формуле:
H (s) = (s0 + 1) ⋅ 330 + (s1 + 1) ⋅ 331 +… + (sn — 1 + 1) ⋅ 33n — 1 + 5381 ⋅ 33n mod 264
template
constexpr unsigned long long static_string_hash(const static_string& str, size_t index) {
return index >= Size - 1 ? 5381ULL :
static_string_hash(str, index + 1) * 33ULL + str[index] + 1;
}
Преобразование числа в статическую строку и обратно
В этой главе рассмотрим преобразование статической строки в целое число, а также обратное преобразование. Для простоты будем считать, что числа представлены типами long long и unsigned long long, это типы большой разрядности, то есть подходят для большинства случаев.
Преобразование числа в статическую строку
Для преобразования числа в статическую строку нам нужно получить все цифры числа, преобразовать их в соответствующие символы и составить из этих символов строку.
Для получения всех цифр числа будем использовать генератор, аналогичный генератору последовательности индексов. Определим последовательность символов:
template
struct char_sequence {};
Реализуем генератор символов цифр, храня текущее число в первом параметре, а цифры в следующих, очередная цифра добавляется в начало последовательности, а число делится на десять:
template
struct make_unsigned_int_char_sequence : make_unsigned_int_char_sequence {};
Если текущее число равно 0, то отбрасываем его, возвращая последовательность цифр, больше преобразовывать нечего:
template
struct make_unsigned_int_char_sequence<0, Chars ...> : char_sequence {};
Следует также учесть случай, когда первоначальное число равно нулю, в этом случае нужно вернуть нулевой символ, иначе нуль будет преобразован в пустую последовательность символов, а потом и в пустую строку:
template<>
struct make_unsigned_int_char_sequence<0> : char_sequence<'0'> {};
Реализованный генератор прекрасно работает для положительных чисел, но не пригоден для отрицательных. Определим новый генератор, добавив в начало еще один шаблонный параметр — знак преобразуемого числа:
template
struct make_signed_int_char_sequence {};
Будем обрабатывать число также, как показано выше, но с учетом знака:
template
struct make_signed_int_char_sequence :
make_signed_int_char_sequence {};
template
struct make_signed_int_char_sequence :
make_signed_int_char_sequence {};
Здесь есть один тонкий момент, обратите внимание на -(Value % 10). Здесь нельзя -Value % 10, так как диапазон отрицательных чисел на одно число шире диапазона положительных и модуль минимального числа выпадает из множества допустимых значений.
Отбрасываем число после обработки, если оно отрицательно, добавим символ знака минуса:
template
struct make_signed_int_char_sequence : char_sequence<'-', Chars ...> {};
template
struct make_signed_int_char_sequence : char_sequence {};
Отдельно позаботимся о преобразовании нуля:
template<>
struct make_signed_int_char_sequence : char_sequence<'0'> {};
Наконец, реализуем функции преобразования:
template
constexpr auto uint_to_static_string() {
return make_static_string(make_unsigned_int_char_sequence{});
}
template
constexpr auto int_to_static_string() {
return make_static_string(make_signed_int_char_sequence<(Value < 0), Value>{});
}
Преобразование статической строки в число
Для преобразования статической строки в число нужно преобразовать символы в цифры, а затем сложить их, предварительно домножив на соответствующую степень десятки. Выполняем все действия рекурсивно, для пустой строки возвращаем нуль:
template
constexpr unsigned long long static_string_to_uint(const static_string& str, size_t index) {
return Size < 2 || index >= Size - 1 ? 0 :
(str[index] - '0') + 10ULL * static_string_to_uint(str, index - 1);
}
template
constexpr unsigned long long static_string_to_uint(const static_string& str) {
return static_string_to_uint(str, Size - 2);
}
Для преобразования знаковых чисел, нужно учесть, что отрицательные числа начинаются с символа знака минуса:
template
constexpr long long static_string_to_int(const static_string& str, size_t index, size_t first) {
return index < first || index >= Size - 1 ? 0 :
first == 0 ? (str[index] - '0') + 10LL * static_string_to_int(str, index - 1, first) :
-(str[index] - '0') + 10LL * static_string_to_int(str, index - 1, first);
}
template
constexpr long long static_string_to_int(const static_string& str) {
return Size < 2 ? 0 :
str[0] == '-' ? static_string_to_int(str, Size - 2, 1) :
static_string_to_int(str, Size - 2, 0);
}
Вопросы удобства использования библиотеки
К этому моменту библиотеку уже возможно полноценно использовать, но некоторые моменты вызывают неудобство. В этой главе рассмотрим как можно сделать использование библиотеки более удобным.
Объект статической строки
Упакуем строку и реализованные методы в объект. Это позволит использовать более короткие имена методов, а также реализовать операторы сравнения:
template struct static_string {
constexpr size_t length() const {
return Size - 1;
}
constexpr size_t size() const {
return Size;
}
constexpr size_t begin() const {
return 0;
}
constexpr size_t end() const {
return Size - 1;
}
constexpr size_t rbegin() const {
return Size - 2;
}
constexpr size_t rend() const {
return std::numeric_limits::max();
}
constexpr bool empty() const {
return Size < 2;
}
constexpr auto reverse() const {
return static_string_reverse(*this);
}
template constexpr auto substring() const {
return static_string_substring(*this);
}
template constexpr auto prefix() const {
return static_string_prefix(*this);
}
template constexpr auto suffix() const {
return static_string_suffix(*this);
}
constexpr size_t find(char ch, size_t from = 0, size_t nth = 0) const {
return static_string_find(*this, ch, from, nth);
}
template constexpr size_t find(const static_string& substr, size_t from = 0, size_t nth = 0) const {
return static_string_find(*this, substr, from, nth);
}
template constexpr size_t find(const char (& substr)[SubSize], size_t from = 0, size_t nth = 0) const {
return static_string_find(*this, substr, from, nth);
}
constexpr size_t rfind(char ch, size_t from = Size - 2, size_t nth = 0) const {
return static_string_rfind(*this, ch, from, nth);
}
template constexpr size_t rfind(const static_string& substr, size_t from = Size - SubSize, size_t nth = 0) const {
return static_string_rfind(*this, substr, from, nth);
}
template constexpr size_t rfind(const char (& substr)[SubSize], size_t from = Size - SubSize, size_t nth = 0) const {
return static_string_rfind(*this, substr, from, nth);
}
constexpr bool contains(char ch) const {
return static_string_contains(*this, ch);
}
template constexpr bool contains(const static_string& substr) const {
return static_string_contains(*this, substr);
}
template constexpr bool contains(const char (& substr)[SubSize]) const {
return static_string_contains(*this, substr);
}
template constexpr bool starts_with(const static_string& prefix) const {
return static_string_starts_with(*this, prefix);
}
template constexpr bool starts_with(const char (& prefix)[SubSize]) const {
return static_string_starts_with(*this, prefix);
}
template constexpr bool ends_with(const static_string& suffix) const {
return static_string_ends_with(*this, suffix);
}
template constexpr bool ends_with(const char (& suffix)[SubSize]) const {
return static_string_ends_with(*this, suffix);
}
constexpr size_t count(char ch) const {
return static_string_count(*this, ch);
}
template constexpr auto split() const {
return static_string_split(*this);
}
constexpr unsigned long long hash() const {
return static_string_hash(*this);
}
constexpr char operator[](size_t index) const {
return data[index];
}
std::string str() const {
return to_string(*this);
}
std::array data;
};
Операторы сравнения
Использование компаратора в виде функции неудобно и нечитаемо. Определим глобальные операторы сравнения:
template
constexpr bool operator<(const static_string& str1, const static_string& str2) {
return static_string_compare(str1, str2) < 0;
}
Аналогично реализуем остальные операторы > <= >= == !=, для всех вариаций аргументов статических строк и строковых литералов. Здесь приводить их нет смысла из-за тривиальности.
Макросы работы с числами
Для удобства преобразования числа в статическую строку и обратно определим соотвествующие макросы:
#define ITOSS(x) int_to_static_string<(x)>()
#define UTOSS(x) uint_to_static_string<(x)>()
#define SSTOI(x) static_string_to_int((x))
#define SSTOU(x) static_string_to_uint((x))
Примеры использования библиотеки
Ниже приведены примеры реального использования реализованной библиотеки.
Конкатенация статических строк и строковых литералов:
constexpr auto hello = make_static_string("Hello");
constexpr auto world = make_static_string("World");
constexpr auto greeting = hello + ", " + world + "!"; // greeting == "Hello, World!"
Конкатенация статических строк, строковых литералов и чисел:
constexpr int apples = 5;
constexpr int oranges = 7;
constexpr auto message = static_string_concat("I have ", ITOSS(apples),
" apples and ", ITOSS(oranges), ", so I have ", ITOSS(apples + oranges), " fruits");
// message = "I have 5 apples and 7 oranges, so I have 12 fruits"
constexpr unsigned long long width = 123456789ULL;
constexpr unsigned long long height = 987654321ULL;
constexpr auto message = static_string_concat("A rectangle with width ", UTOSS(width),
" and height ", UTOSS(height), " has area ", UTOSS(width * height));
// message = "A rectangle with width 123456789 and height 987654321 has area 121932631112635269"
constexpr long long revenue = 1'000'000LL;
constexpr long long costs = 1'200'000LL;
constexpr long long profit = revenue - costs;
constexpr auto message = static_string_concat("The first quarter has ended with net ",
(profit >= 0 ? "profit" : "loss "), " of $", ITOSS(profit < 0 ? -profit : profit));
// message == "The first quarter has ended with net loss of $200000"
Парсинг URL:
constexpr auto url = make_static_string("http://www.server.com:8080");
constexpr auto p = url.find("://");
constexpr auto protocol = url.prefix(); // protocol == "http"
constexpr auto sockaddr = url.suffix
();
constexpr auto hp = sockaddr.split();
constexpr auto host = hp.first; // host == "www.server.com"
constexpr int port = SSTOI(hp.second); // port == 8080
Итерация по символам в обоих направлениях:
constexpr auto str = make_static_string("Hello");
for (size_t i = str.begin(); i != str.end(); ++i) // вперед
std::cout << str[i];
std::cout << std::endl; // Hello
for (size_t i = str.rbegin(); i != str.rend(); --i) // назад
std::cout << str[i];
std::cout << std::endl; // olleH
Ссылки
Библиотеку, реализующую все вышеперечисленное, можно взять в моем github
Спасибо за внимание, замечания и дополнения приветствуются.
