Как работает next_permutation в С++?

В гугле забанили?

Ну так скачайте исходники gcc и найдите там как реализовано, в отличии от всяких там непосредственно кодов компилятора, исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.

p.s. кодю на C++ уже как 3-й год наверное, в т.ч. по основной работе, активно юзаю STL, а о такой штуке как next_permutation даже и не слышал :)

Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator<

А в этом случае состояние описывается упорядоченностью элементов и хранить отдельно его не нужно.

исходные коды STL библиотеки, в реализации от GCC читаются легко, непренуждённо и увлекатльно.

Вот совсем нет. Стиль оформления кода у них настолько чудовищный, что исходники читаются только чуть лучше, чем никак.

Поведение функции соотвествует следующей перестановки только в том случае, если все элементы разные в соответствии с operator<

Я только пытаюсь понять функцию, но на cppreference пример переставляет строку std::sort("aba"):

aab
aba
baa

реализации от GCC читаются легко, непренуждённо и увлекатльно

Тонко

Если на значения самих элементов не смотреть, а смотреть на них как на индексированные чёрные ящики - то перестановок не 3, а 6:

123
aab

132
aba

213
aab

231
aba

312
baa

321
baa

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

А, понял. Спасибо за разьяснение.

текущее поведение будет большим сюрпризом

Ну там сразу декларируется лексикографичность(?) операции:

• next_permutation - generates the next greater lexicographic permutation of a range of elements
• prev_permutation - generates the next smaller lexicographic permutation of a range of elements

как работает next_permutation в С++?

Вычисляет следующую перестановку.

Зачем этой функции нужны два итератора?

Чтобы получить начало и конец последовательности.

Где она хранит состояние между вызовами.

Нигде не хранит.

Вычисляет следующую перестановку.

Каким образом?

Чтобы получить начало и конец последовательности.

Почему ему не хватает только ссылки на последовательность?

Нигде не хранит.

Как он тогда узнаёт, что текущая перестановка уже была и нужно вычислить новую?

https://ru.wikipedia.org/wiki/Алгоритм_Нарайаны

Спасибо.

Почему ему не хватает только ссылки на последовательность?

Потому, что в C++ последовательность принято определять двумя итераторами, указывающими на начало и на конец.

Чтобы получить начало и конец последовательности.

Почему ему не хватает только ссылки на последовательность?

Две причины:

• Итераторы в С++ (по крайней мере стандартные) не знают о «размере» контейнера (они могут только перемещаться по контейнеру без проверки границ).
• Весь STL спроектирован на итераторах, чтоб можно было проводить операции и на части контейнера. А понятие «range» появится в STL только в С++20.

Как он тогда узнаёт, что текущая перестановка уже была и нужно вычислить новую?

std::next_permutation делает лексикографическую перестановку (согласно operator < или соотвентствующего компаратора). Т.е. состояние перестановки == порядок значений последовательности.