How to get the following prefix in C ++?

Question

Given the sequence (for example, the string "Xa"), I want to get the next prefix in lexicographic order (for example, "Xb"). The next of "aZ" should be "b"

A motivating use case when this feature is useful is described here .

As I don't want to reinvent the wheel, I wonder if there is any function in C ++ STL or boost that can help to easily define this common function? If not, do you think this feature might be useful?

Notes

• Even if the examples are strings, the function should work for any sequence.
• The lexicographic order must be a parameter of the function template.

From the answers, I conclude that in C ++ / Boost there is nothing that could help to easily define this common function, and also that this function is too specific to be offered for free. I will use a common next_prefix, after which I will ask if you find it useful.

I accepted the only answer that gives some hints on how to do this, even if the proposed implementation is not general.

Answer 1

I'm not sure I understand the semantics by which you want to convert a string, but maybe something like the following might be the starting point for you. The code will increment the sequence as if it were a sequence of digits representing a number.

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

, , , ? , bool?

, , " char , char", - , char , (, , upper_bound char, char).

" char , char" , " " . , , .

Answer 4

, .

, , , , . . ( " "?)

, , . , 127 ( ), , - .

Answer 5

, , , .

Use whatever sorting function you want to use over the entire list of characters you want to include, and then just use this as an ordering. Find the index of the current character, and you can easily find the previous and next characters. Only advance the rightmost character if it does not flip, then move the next character to the left.

In other words, you can reinvent the wheel like 10 lines of Python. Probably less than 500 lines of C ++. :)