Как получить следующий префикс в C ++?

Question

Учитывая последовательность (например, строку "Xa"), я хочу получить следующий префикс в лексикографическом порядке (то есть "Xb"). Следующий из "aZ" должен быть "b"

Мотивирующий случай использования, где эта функция полезна, описан здесь .

Поскольку я не хочу изобретать велосипед, мне интересно, есть ли какая-либо функция в C ++ STL или boost, которая может помочь легко определить эту универсальную функцию? Если нет, то думаете ли вы, что эта функция может быть полезна?

Примечания

• Даже если примеры являются строками, функция должна работать для любой последовательности.
• Лексикографический порядок должен быть параметром шаблона функции.

Из ответов я делаю вывод, что в C ++ / Boost нет ничего, что могло бы помочь легко определить эту универсальную функцию, а также что эта функция слишком специфична, чтобы предлагать ее бесплатно. Я реализую универсальный next_prefix, и после этого я буду запрашивать, считаете ли вы его полезным.

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

Answer 1

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

template<typename Bi, typename I>
bool increment(Bi first, Bi last, I minval, I maxval)
{
    if( last == first ) return false;
    while( --last != first && *last == maxval ) *last = minval;
    if( last == first && *last == maxval ) {
        *last = minval;
        return false;
    }
    ++*last;
    return true;
}

Может быть, вы хотите добавить перегрузку с функциональным объектом или перегрузку или специализацию для примитивов. Пара примеров:

string s1("aaz");
increment(s1.begin(), s1.end(), 'a', 'z');
cout << s1 << endl;     // aba

string s2("95");
do {
    cout << s2 << ' ';  // 95 96 97 98 99
} while( increment(s2.begin(), s2.end(), '0', '9') );
cout << endl;

Answer 2

Это кажется настолько конкретным, что я не могу понять, как это получится в STL или Boost.

Answer 3

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

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

Другими словами, изобретать велосипед - это как 10 строк Python. Вероятно, менее 500 строк C ++. :)

Answer 4

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

Лексикографические заказы, в частности, имеют тенденцию быть только частичными, например, в случае нечувствительности к регистру или диакритической значимости. Поэтому ваш конечный продукт будет недетерминированным или, в лучшем случае, произвольным. («Всегда выбирайте минимальную цифровую кодировку»?)

В любом случае, если вы принимаете компаратор в качестве входных данных, единственный способ преобразовать его в операцию приращения - это сравнить текущее значение со всеми остальными в символьном пространстве. Это может сработать, если 127 значений очень мало (таблица, отсортированная компаратором, быстро решит проблему) или может быть слишком медленной, если вы используете какой-либо другой тип символа.

Answer 5

Когда вы говорите, что заказ является параметром шаблона, что, по вашему мнению, будет передано? Компаратор, который принимает два символа и возвращает bool?

Если это так, то это немного страшно, потому что единственный способ найти «наименее символ, превышающий мой текущий символ» - это отсортировать все символы, найти текущий результат в результате и сделайте шаг вперед (или на самом деле, если некоторые символы могут сравниваться равными, используйте upper_bound с вашим текущим символом, чтобы найти первый большой символ).

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