LINUX.ORG.RU

Хорошие библиотеки для обработки строк на C++

 ,


1

4

А есть ли для C++ хорошие библиотеки для обработки строк в функциональном стиле?

Чтобы можно было, например, решить задачу вида «разбить строку по символу переноса строки, удалить завершающие пробелы, отфильтровать непустые строки, вывести» как-то так:

std::string text = ...;
text.split('\n')
    .map([](auto s) { return s.trim(); })
    .filter([](auto s) { return !s.empty(); })
    .for_each([](auto s) { std::cout << s << std::endl; });

Разумеется, это всё ещё должно работать на базе string_view или аналога из библиотеки, чтобы не было лишних копирований и аллокаций. И без создания промежуточных контейнеров.

★★★★★

Пара мыслей не совсем по теме.

Ты хочешь не (с)только строки, но контейнеры в целом. Все, что ниже split в твоём примере, уже не про строки.

Пример кода — нечитаемая шляпа. Очень много синтаксического шума, из-за лямбд как минимум.

Дрочка string_view в случае generic алгоритмов не поможет, потому что окажись у тебя где-в пайплайне модификация строки (замена html тэгов например), весь твой view пойдёт по пизде. Для подобных запросов нужен другой контейнер, например cow-строки.

При обработке действительно больших объемов ты будешь парсить поток, а не одну строку. Весь твой «красивый» синтаксис тут же пукнет в лужу.

Попахивает поиском библиотеки для решения несуществующей задачи aka «сравнить перф с языком X».

filosofia
()

std::ranges

хорошие библиотеки

Тогда не знаю.

это всё ещё должно работать на базе string_view

Приспособление для отстрела ног.

ox55ff ★★★★★
()

Мне кажется, что условия «в функциональном стиле» и «чтобы не было лишних копирований и аллокаций. И без создания промежуточных контейнеров» плохо совместимы друг с другом.

Описанная задача не нова, это называется in-place parsing. На C такое можно сделать, расставляя внутри разбираемой строки ‘\0’ в нужных местах и сохраняя указатели на подстроки, так, например, работает pugixml и другие подобные парсеры. Можно сделать подобный парсер и на string_view, он будет потредлять немного больше памяти, т.к. надо сохранять еще и длины подстрок, зато можно не изменять исходную строку (сделать парсинг недеструктивным). Но делать генераторы парсеров для С++, да еще и внутриязыковые, а не в виде утилиты-генератора - тот еще мозготрах. Тем более в ФП-парадигме, которая накладывает дополнительные ограничеия.

annulen ★★★★★
()
Ответ на: комментарий от Ivan_qrt

Спасибо, с одной стороны стало короче, так как нет лямбды с реализацией trim, с другой стороны ranges::reverse_view не удовлетворяет условию contiguous_range, и теперь не получается создать из него string_view, только string, или я что-то упускаю

auto trim = views::transform(views::drop_while(::isspace) | views::reverse |
                             views::drop_while(::isspace) | views::reverse);
const string_view text = "Hello  \nC++  \n\n \n1\n 2\n 3 \n\n4 \n20!\n\n\n"sv;
ranges::filter_view words =
    text
    | views::split("\n"sv)
    | trim
    | views::filter([](auto s) { return !s.empty(); });
for (ranges::reverse_view w : words) {
    string s{w.begin(), w.end()};
    cout << quoted(s) << ", s.size() = " << s.size() << '\n';
}

Новый вариант: https://gcc.godbolt.org/z/vrEx146E1

Старый вариант: https://gcc.godbolt.org/z/1W8fhzPeG

fsb4000 ★★★★★
()
Последнее исправление: fsb4000 (всего исправлений: 1)

C/C++ не очень то и подходят для разбора строк по ряду причин:

1. Нет встроенного в язык типа string, не связанного напрямую с указателями;

2. Нет нормальных удобных range, как например в Аде и прочих ЯП;

3. Нет нормального разделения понятия байт/символ.

Но что не отнять так это скорость.

Dr64h ★★★
()
Ответ на: комментарий от Dr64h

C/C++ не очень то и подходят для разбора строк по ряду причин:

  1. Нет встроенного в язык типа string, не связанного напрямую с указателями;
  1. Строки лежат в памяти.
  2. C/C++ имеет прямой доступ и к памяти, и к ассемблеру со всякими SIMD.

Да кто может быть быстрее этого?!

raspopov
()
Ответ на: комментарий от ox55ff

А как std::string связан с указателями?

std::string не встроенный в язык тип, у базового типа не должно быть всяких надстроек по типу классов/контейнеров.

На базовом уровне C/C++ умеет работать со строками только через указатели, всё остальное надстройки/хаки/костыли.

И у C/C++ нет отдельного типа character и string несвязанных с целыми числами и арифметикой указателей.

Dr64h ★★★
()
Ответ на: комментарий от Dr64h
  1. Нет встроенного в язык типа string, не связанного напрямую с указателями;

Это признак состоятельного языка – способность реализовать на нем самом все необходимое.

  1. Нет нормальных удобных range, как например в Аде и прочих ЯП;

🤡

  1. Нет нормального разделения понятия байт/символ.

Бред. Начнем с того, что даже в STL есть std::u{8,16,32}string, закончим тем, что реализация конкретного класса строки никаким образом на пригодность или непригодность языка для чего-либо не влияет.

Siborgium ★★★★★
()
Ответ на: комментарий от filosofia

Пример кода — нечитаемая шляпа. Очень много синтаксического шума, из-за лямбд как минимум.

Не столько нечитаемая, сколько неоптимизируемая. Из-за лямбд как минимум

yoghurt ★★★★★
()

Кстати странно что ещё комбинаторных парсеров не предложили, ну или там какой-нибудь PEG. Кстати объединить их с ренжами-инплейсами-зеро аллокейшн и будет пушка

yoghurt ★★★★★
()
Ответ на: комментарий от Siborgium

Это признак состоятельного языка – способность реализовать на нем самом все необходимое.

Тогда зачем нам вообще C++, если всё можно реализовать на Си?

Как устроен range в Аде и разделение строк на подстроки ты видимо не видел.

Бред. Начнем с того, что даже в STL есть std::u{8,16,32}string.

Про wchar ты видимо тоже не вкурсе.

Dr64h ★★★
()
Ответ на: комментарий от fsb4000

Да, действительно, reverse_view теряет contiguous_range, не понятно, правда, почему? Если в одну сторону range был непрерывным, то и в обратную по идее должен быть.

Но убедившись в том, что получающиеся рэнжи непрерывны всегда можно дропнуть эти мерзкие типы получив из итераторов сырые указатели (&*).

Но, понятно, что это теряет часть смысла затеи, и можно навелосипедить полноценный trim, сохраняющий contiguous_range, но не обязательно.

У рэнжей вообще есть пачка не очевидных нюансов, потому они мне и не особо нравятся. В общем классический С++.

Ivan_qrt ★★★★★
()
Ответ на: комментарий от Dr64h

Тогда обоснуй почему в C/C++ не должно быть отдельного типа character и string для нормальной работы со строками.

потому что в природе нет нормального типа character. а есть куча их всяких, разного размера и разной кодировки.

со строками - аналогично.

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

alysnix ★★★
()
Ответ на: комментарий от alysnix

Посмотри реализацию строк в Аде, всё просчитывается в compile-time и укладывается в стек. Кодировку можно прикрутить какую угодно, система типов в Аде не ограничена, можно задать хоть 7-бит, хоть 48, к тому же есть и стандартные типы под это.

Если прям хочется raw строки в стиле Си, то их тоже можно достаточно просто реализовать через байты и массивы.

Что мешает сделать нечто подобное в плюсах?

Dr64h ★★★
()
Последнее исправление: Dr64h (всего исправлений: 1)
Ответ на: комментарий от Dr64h

Посмотри реализацию строк в Аде, всё просчитывается в compile-time и укладывается в стек.

utf-8 поддерживает?

7-бит char будет не выровнен по байтам или будет занимать 8-бит? Если будет не выровнен, то доступ только через битовые операции будет тормозным, а взятие подстрок невозможным. Если они выровнены, то это тоже, что и в плюсах, и чем оно лучше char8_t, char16_t, char32_t не очевидно.

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

Ivan_qrt ★★★★★
()
Ответ на: комментарий от Ivan_qrt

utf-8 поддерживает?

Да, там даже сами сорцы можно хоть на китайском писать, хоть на русском.

7-бит char будет не выровнен по байтам или будет занимать 8-бит?

Вероятно что выровняет до 8, зависит от того на каком железе ты компилируешь, если на железе будет выгоднее использовать условно 3 бита, то он выделит именно 3.

В общем нужен пример

Там суть такая что грубо говоря String, это массив из Character, а в Character можно класть только символы и массивы это именно массивы, а не замаскированные указатели.

Из меня объяснятель так себе. Может завтра если найду годный пример, то кину ссылку.

Dr64h ★★★
()
Последнее исправление: Dr64h (всего исправлений: 1)
Ответ на: комментарий от Dr64h

std::string не встроенный в язык тип

Это хорошо. Значит язык достаточно мощный, чтобы реализовать на самом себе всё что нужно. А если прибито костылями, то язычок так себе.

И у C/C++ нет отдельного типа character и string несвязанных с целыми числами и арифметикой указателей.

В каком случае это полезно?

ox55ff ★★★★★
()
Ответ на: комментарий от ox55ff
char str_a[256] = "Hello ";
char str_b[] = "world";
    
str_a = str_a + str_b; // в C/C++ не прокатит, в Аде сработает

str_a[1] += 100500; // В Аде не сработает
    
*str_a += 100500; // В Аде не сработает
    
char ch;
    
ch = '1'; // Сработает в обоих случаях
ch = 1;   // В Аде не сработает

Это если из простого брать.

Dr64h ★★★
()
Последнее исправление: Dr64h (всего исправлений: 2)
Ответ на: комментарий от Dr64h

str_a = str_a + str_b; // в C/C++ не прокатит, в Аде сработает

А не надо мешать в кучу c и c++. В крестах для строк есть соответствующий класс. Там можно склеивать через плюс.

str_a[1] += 100500; // В Аде не сработает
и т.д.

Ну да. Только непонятно зачем к символу добавлять число.

В общем сам себе выдумал проблему.

ox55ff ★★★★★
()
Ответ на: комментарий от ox55ff

А не надо мешать в кучу c и c++. В крестах для строк есть соответствующий класс. Там можно склеивать через плюс.

Представь что ты пишешь на голом железе, заморачиваться с raw строками не хочешь, как ты потащишь с собой std::string?

Ну да. Только непонятно зачем к символу добавлять число.

Фиг знает, сам видел как такое в парсерах проворачивают, видимо кто-то и такими хаками пользуется, можно к примеру и переменные перепутать.

Dr64h ★★★
()
Ответ на: комментарий от Dr64h

Представь что ты пишешь на голом железе, заморачиваться с raw строками не хочешь, как ты потащишь с собой std::string?

пишешь свой класс преаллокированной строки - то есть размещаемой прям на стеке, с нужными тебе операциями, типа конкатенации и тепе.

я много раз так делал и именно для голого железа.

alysnix ★★★
()
Ответ на: комментарий от alysnix

Ну тебе проще сделать целый класс для строк, уж не знаю на сколько это просто делается, но другим например было бы проще воспользоваться уже готовыми строками и не использовать классы вообще.

Dr64h ★★★
()
Ответ на: комментарий от Dr64h

да нет наверно в твоей аде таких строк.

это темплейт класса - строка фиксированной длины, содержащий внутри буфер на данный размер. тогда такая строка будет полностью лежать на стеке, если перменную обьявить на стеке, но есть ограничение на длину. Но такая ситуация для голого железа - это нормально. Естессно к ней можно конкатенировать другие такие строки и строковые константы, пока результат уложится в буфер.

фактически это обертка над строковыми функциями Си, типа strcat и прочими. но также можно там и длину строки хранить и реализовать строки аля паскаль, только фиксированные.

фиксированные строки тут используются чтобы не аллокировать на куче. что может быть накладным по времени для слабых процов.

короче я всегда для железа так делал и все пучком.

alysnix ★★★
()
Ответ на: комментарий от alysnix

Ты описал примерно, то что делает Ада со строками, там строка это массив символов фиксированного размера и с определённым заданным диапазоном через range.

То есть к примеру можно создать строку с диапазоном range(-10 .. 255) и обращаться к массиву по индексу, например str(-5) := 'А', или через диапазон str(10 .. 40) := «writing a substring».

P. S. Я спать, если будет время отпишусь завтра.

Dr64h ★★★
()
Последнее исправление: Dr64h (всего исправлений: 1)
Ответ на: комментарий от yoghurt

Не столько нечитаемая, сколько неоптимизируемая. Из-за лямбд как минимум

Оптимизируемость — отдельная история. Я давно не копал в этом направлении, но выглядит так, что лямбды можно заинлайнить и превратить весь алгоритм в обычный императивный код. Или в крайнем случае, можно понадеяться, что следующее поколение компиляторов это смогут.

Синтаксическое же уродство практически неискоренимо. Я больше читаю, чем пишу, код, и вот эти вот уродства бесят. Иногда (часто) можно наплевать на производительность. В таких случаях на первый план выходит выразительность кода. У подобных функциональных цепочек часто одна и та же судьба: сделали «красиво»; на следующем цикле разработки нужно дополнительно обработать промежуточный результат. Что делают обезьяны: херачат рядом ещё одну цепочку (вот где перф начинает действительно сосать); неандертальцы — расширяют цепочку ещё одним вызовом с сайд эффектами. Наиболее разумные индивиды рвут цепочки и теряют всю функциональную грацию.

filosofia
()
Ответ на: комментарий от Dr64h

Представь что ты пишешь на голом железе, заморачиваться с raw строками не хочешь, как ты потащишь с собой std::string?

В чём проблема использовать std::string на голом железе?

В отстуствие new?

Ну, std::string не использует new, он использует аллокаторы.

Какой-нибудь pmr::unsynchronized_pool_resource + std::string и будет std::string использовать только стек…

fsb4000 ★★★★★
()
Ответ на: комментарий от Dr64h

Да, там даже сами сорцы можно хоть на китайском писать, хоть на русском.

Сорцы на китайском - это прекрасно. Строки поддерживают utf8? И доступ к символам по байтовый или по codepoint’ам, которые переменной длинны и может быть сделан только в рантайме? И что будет, когда у такой строки попытаешься получить доступ к 5-ому эл-ту (str[5]), полный перебор строки с разбивкой на символы и исключениями в случае некорректных codepoint’ов?

Это всё, просто, не совсем вяжется с тем, что ты описывал, а как может быть по другому, я не знаю. Если там не так, но utf-8 поддерживается из коробки, то это очень интересно.

Вероятно что выровняет до 8, зависит от того на каком железе ты компилируешь, если на железе будет выгоднее использовать условно 3 бита, то он выделит именно 3.

Я не уверен, как именно поведут себя компиляторы с++ в случае не кратного 8 битам char’а. Возможно и в стандарте с этим косяки есть (но по идее нет). И в теории это прекрасно, что язык может работать с произвольными разрядностями char.

Но на практике весь пользовательский код и с вероятностью 90% вся стандартная библиотека от этого сдохнет, т.к. весь код рассчитан на то, что в байте 8 бит без исключений. Да и современного железа, в котором в байте не кратное 8 число бит не существует.

А в остальном, судя по-всему, в аде всё ровно так же, как в c++, так что не понятно, на что ты сетуешь.

Там суть такая что грубо говоря String, это массив из Character

Ну вот опять же не понятно, как это всё вяжется с utf-8, где строка это последовательность codepoint’ов переменной длинны, и осуществлять к ней доступ как к массиву не корректно.

а в Character можно класть только символы

Ну в плюсах в любом случае есть static_cast, который решит проблему того, что какое-то число не является символом. Думаю, что в аде тоже есть подобный каст. Сам язык без проблем позволяет заменить char на enum class, к которому просто так ничего не скастуешь. Можно даже на struct { char val; } заменить, и всё будет преобразовываться.

Просто это нафиг никому не надо и я впервые вообще слышу о таких проблемах. Тем более у меня таковых никогда не возникало.

В общем при желании в плюсах можно так же, просто желания ни у кого не возникает.

Я бы вообще из строк убрал итераторы произвольного доступа, т.к. с utf-8 и utf-16 (utf-32 можно считать, что можно) они только к ошибкам приводят, а добавлял их только для кодировок с фиксированным размером. Но это сломает обратную совместимость и мозг програмистов, так что этого, разумеется, не бдует.

Ivan_qrt ★★★★★
()
Ответ на: комментарий от fsb4000

Как будто на «голом железе» не может быть кучи. Тогда давайте думать о железе, в котором нету и стека. Лови железные транзисторы и ни в чем себе не отказывай!

Аргументы «голое железо» обычно лезут именно из тех, кто железа никогда и не видел.

@Dr64h, не обижайся, но твои доводы про строки и как они должны быть реализованы в этом треде — полная лажа. Вылезай из Ада-мирка!

filosofia
()
Ответ на: комментарий от fsb4000

В чём проблема использовать std::string на голом железе?

При очень большом желании можно, но придётся всё равно делать свой аллокатор, а в ситуациях, когда можно обойтись без него char[] на стёке + string_view удобнее.

Во-первых сразу понятно где что выделено, во-вторых при аккуратном подходе можно не переживать по поводу ошибок выделения и сразу рассчитать необходимые ресурсы, что с отдельным аллокатором будет сложнее.

К проблемам Dr64h это разумеется, не имеет никакого отношения.

Ivan_qrt ★★★★★
()
Ответ на: комментарий от fsb4000

такого нам не надо. класс FixedString пишется ручками за 10 минут, чтобы потом писать в виде:

FixedString<512> str;
str = "yasya";
str += " sidorov";

просто не вcе испытывают наслаждение от этих аллокаторов-шмаллокаторов, а любят жить проще.

alysnix ★★★
()
Последнее исправление: alysnix (всего исправлений: 1)
Ответ на: комментарий от fsb4000

Ну в принципе можно и так, просто это чуть менее очевидно, чем явный char[] + string_view поверх (при желании).

Ну и потыкав pmr https://gcc.godbolt.org/z/K6jcT97dM он начал бросать bad_alloc при размере 512 байт, которого явно достаточно (на деле и при 1700 байтах почему-то бросает).

В общем с его поведением разбираться надо, а с char[] всё сразу понятно.

Ivan_qrt ★★★★★
()
Ответ на: комментарий от Dr64h

Там суть такая что грубо говоря String, это массив из Character, а в Character можно класть только символы и массивы это именно массивы, а не замаскированные указатели.

Ну прям вау, я впечатлён. Открою секрет - в плюсах можно на коленках накостылить тип Character и операции над ним любые, строковые литералы этого типа и не реализовывать смешанную арифметику с целыми. Почему же никто не делает, наверное лишь ты один вкусил прелесть божественных строк.

Я сильно сомневаюсь, что Ada умеет utf-8 полностью, с такими примитивами это вряд ли возможно. В попытке выкатить решение для «дурака» получилась недоподелка, которая сломается на первом модификаторе. Да и utf-8 - дерьмо, которое делали наркоманы и всунули в него иероглифы.

kvpfs ★★
()
Ответ на: комментарий от Ivan_qrt

unsynchronized_pool_resource видимо преалоцирует некоторые чанки которые потом будет раздавать.

с monotonic_buffer_resource такого нет, но он не переиспользует память, https://gcc.godbolt.org/z/7va8Ybf8r

можно поиграть с pmr::pool_options, так получается снизить требования к минимальному объему: https://gcc.godbolt.org/z/jrW8asfW8

fsb4000 ★★★★★
()
Ответ на: комментарий от Ivan_qrt

Я не гуру по кодировкам и не пользовался UTF (не было необходимости). Думаю здесь есть более подробный ответ.

Если прям нужно работать с UTF, то для этого есть отдельные продвинутые либы, вот описание к ним:

vss. Вводит свой собственный тип для строк в Юникоде с удобными методами для работы. Его можно использовать для поиска границ символов, кластеров графем, смещений символов в кодировке UTF-8 / UTF-16 и т. д.

matreshka_league. Позволяет оперировать строками через «code points» Юникода. Имеет набор транскодеров для различных систем кодировки (таких как Windows-1251, KOI8-R), поддержку JSON, XML, баз данных, регулярных выражений, движка шаблонов XML и т. д.

И вот ещё справочник по кодировкам откопал.

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

Там есть атрибуты типа, выглядит это примерно так:

number : Integer := 100500;

-- Атрибут 'Image превращает число в строку
Put_Line ("Var contain: " & number'Image);

-- "Var contain: 100500"

Сам язык без проблем позволяет заменить char на enum class, к которому просто так ничего не скастуешь. Можно даже на struct { char val; } заменить, и всё будет преобразовываться.

Так я к тому и веду, что почему бы не избавится от лишнего костылинга и использовать нормльное изкоробочное решение с конкатенацией, диапазонами и прочими прелестями.

Dr64h ★★★
()