Есть ли способ перебирать префиксы std::string? (Для использования с алгоритмами, включающими std::lower_bound) ⇐ C++

[Anonymous]

У меня есть довольно сложная проблема, которую я хочу найти элегантное решение с помощью C++. (Вплоть до C++ 23 или, возможно, даже C++ 26.)
Позвольте мне сначала описать, что я ищу:

• Я хочу иметь возможность перебирать std::string, но вместо того, чтобы перебирать его обычным способом, я хочу перебирать префиксы строки переменной длины
• Я хочу сделать это, используя std::string_view, а не постоянно создавать копии частей строки
• Я хочу объединить это с std::lower_bound, чтобы выполнить поиск некоторого условия с помощью алгоритма логарифмического времени — O(log(N))

У меня есть решение, которое я добавлю в конце. Но это немного «неудобно».
Это похоже на std::ranges::enumerate_view. Моя идея состоит в том (и я не совсем уверен, как это сделать) создать итератор из std::string, который вместо того, чтобы выдавать символы строки или пары символов с индексами, выдает подстроки в виде std::string_view, начиная с первого символа и заканчивая некоторой переменной длиной внутри строки.
Это немного сложно описать. Так что эскиз может помочь.
Представьте, что у меня есть такой поиск:

Код: Выделить всё

std::string my_string = "hello world";

const auto something = std::lower_bound(
prefix_view_iterator(my_string).begin(),
prefix_view_iterator(my_string).end(),
target_value,
lambda
);

Я ищу некоторое условие, где лямбда(элемент) >= target_value, где element — это префикс std::string_view от индекса 0 до некоторого индекса переменной my_string.
Пример: поиск hello_world может происходить примерно так:

Код: Выделить всё

hello_
hello_wor
hello_w
hello_wo # condition met, exit here

Вышеуказанное — всего лишь набросок.
Это все немного абстрактно, поэтому, возможно, я смогу сделать ситуацию более конкретной с помощью рабочего примера.
Следующий код работает, но это не очень элегантное решение. Я попробую скопировать это из окна редактора рядом со мной, пожалуйста, простите за незначительные синтаксические ошибки. Просто чтобы объяснить проблему более конкретно.

Код: Выделить всё

std::size_t find_maximum_length_which_fits_within(
const std::string& line,
const std::size_t width_in_pixels
) {

const auto lambda = [&line](const auto& index, const auto& width_in_pixels) -> bool {

// Convert the end index to a substring view (prefix view)
const auto substring_view = std::string_view(
line.data(),
line.data() + index
);

// Convert the prefix to a length in pixels
const auto length_in_pixels = calculate_length_in_pixels(substring_view);

// Does this number of pixels fit on screen?
return length_in_pixels < width_in_pixels;
};

// Convert a std::string into a sequence of index values so that we can iterate
// over the elements of the string as substrings created from numerical indices
const auto index_it = std::views::iota(0, line.size());

const auto end_it = std::lower_bound(
index_it.begin(),
index_it.end(),
width_in_pixels,
lambda
);

const auto end_index = *end_it;
return end_index;
}

Что это делает?

• Он использует std::lower_bound для управления алгоритмом поиска условия, когда некоторая функция строкового префикса f(prefix) >= width_in_pixels.

• Код: Выделить всё

  f(prefix)

  описывается лямбдой в приведенном выше коде.
• Эта лямбда-функция выполняет следующие действия:
• преобразует конечный индекс в строковый префикс в виде std::string_view
• вычисляет длину этого префикса в пикселях
• Проверьте, соответствует ли эта длина в пикселях некоторому максимальному значению, описанному в width_in_pixels

Предлагает ли стандартная библиотека что-то вроде префиксного итератора? Казалось бы, это самый простой способ решить эту проблему. Я полагаю, что альтернативой было бы создание собственного итератора, который реализует итерацию префикса.

Подробнее здесь: https://stackoverflow.com/questions/798 ... orithms-in