Зачем нужны функции std::advance, next, prev?

#cpp #итераторы

В стандартной библиотеке С++ есть функции std::advance, std::next, std::prev.
Зачем они нужны и в каких случаях следует их использовать?
    

Ответы

Ответ 1

Функция std::advance появилась ранее функций std::next и std::prev еще в стандарте
C++ 2003, в то время как последние две функции появились в стандарте C++ 2011.

Функция std::advance имеет следующее объявление

template 
void advance(InputIterator& i, Distance n);


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

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

auto next = current;
advance( next, n );


где n - некоторое целое число.

Например, рассмотрим задачу найти максимальный элемент во второй половине элементов
некоторого списка

#include 
#include 
#include 

// ...

std::list lst;

// инициализация списка некоторыми значениями

std::list::iterator it = lst.begin();
std::advance( it, lst.size() / 2 );

it = std::max_element( it, lst.end() );


Так как функция std::advance имеет тип возвращаемого значения void, и она меняет
переданный ей в качестве аргумента итератор, то ее неудобно использовать с алгоритмами.
Требуются дополнительные объявления и предложения кода, чтобы вызвать какой-нибудь
алгоритм. Например, вот как может выглядеть вызов алгоритма std::rotate для списка
с использованием функции std::advance 

#include 
#include 
#include 

// ...

std::list lst;

// инициализация списка некоторыми значениями

std::list::iterator middle = lst.begin();
std::advance( middle, lst.size() / 2 );
std::rotate( lst.begin(), middle, lst.end() );


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

std::advance( middle, -1 );


Из этого предложения трудно сделать вывод, является ли -1 опечаткой или же это значение
действительно выражает намерение программиста.

Такие имена, как prev или next более ясно выражают намерения программиста и делают
код более читабельным.

Поэтому было предложено ввести функции std::prev и std::next в стандарт C++ 2011.
Более того эти функции возвращают итератор, а потому их можно встраивать в вызовы алгоритмов.
Они не изменяют итераторы, на основе которых функции возвращают новые итераторы.

Предыдущий пример вызова алгоритма std::rotate для списка теперь с использованием
этих функций можно записать в одну строчку

#include 
#include 
#include 

// ...

std::list lst;

// инициализация списка некоторыми значениями

std::rotate( lst.begin(), std::next( lst.begin(), lst.size() / 2 ), lst.end() );


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

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

std::vector sequence = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

std::rotate( sequence.begin(), sequence.begin() + sequence.size() / 2, sequence.end() );


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

Значительно лучше будет если даже для итераторов произвольного доступа вы будете
использовать данные обобщенные функции

std::vector sequence = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

std::rotate( sequence.begin(), std::next( sequence.begin(), sequence.size() / 2 ),
sequence.end() );


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

Обе функции std::next и std::prev имеют для второго параметра аргумент по умолчанию:

template 
ForwardIterator next(ForwardIterator x,
typename std::iterator_traits::difference_type n = 1);


template 
BidirectionalIterator prev(BidirectionalIterator x,
typename std::iterator_traits::difference_type n = 1);


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

std::vector v = { /* некоторые значения */ };

auto after_first = std::next( v.begin() );
auto before_last = std::prev( v.end() );


Было бы логичным, чтобы функция std::advance также имела для второго параметра аргумент
по умолчанию. Тогда вместо выражения, как, например,

auto it = v.begin();
std::advance( it, 1 );


можно было бы записать проще

auto it = v.begin();
std::advance( it );


И слово advance в этом случае соответствовало бы своему непосредственному значению.

Мною было сделано такое предложение  по включению в объявление функции std::advance
значения аргумента по умолчанию равного 1 для второго параметра функции.

С данным моим предложением по изменению стандарта C++ относительно функции std::advance
можно ознакомиться по этой ссылке


Ответ 2

Существуют различные категории итераторов, такие как RandomAccessIterator или ForwardIterator.  

Категория итератора определяет какие операции поддерживаются итератором:  


RandomAccessIterator умеет it + n, it += n, ++it, it--, и т.п.; 
BidirectionalIterator может перемещаться только на один элемент:  ++it, it--;
ForwardIterator может перемещаться только вперед: ++it или it++.


Перемещение на несколько элементов

Функции std::advance, std::next и std::prev упрощают перемещение между несколькими
элементами для BidirectionalIterator и более простых категорий итераторов.

iter = std::next(iter, n); // Эквивалентно iter = iter + n;
iter = std::prev(iter, n); // Эквивалентно iter = iter - n;
std::advance(iter, n); // Эквивалентно iter += n;


Для RandomAccessIterator эти функции не дают никаких преимуществ, по этому нет смысла
применять их вместо операторов + или +=.

Перемещение на один элемент

В требованиях к категориям итераторов, операции ++ и -- определены следующим образом:

Выражение | Тип
----------+-----
++r       | X&


Там образом операции ++ и -- определены только для переменных (l-value), и не определены
для r-value значений, например результатов функций. По этому выражение вида ++f() может
не скомпилироваться: 

++std::min_element(first, last) // НЕ РЕКОМЕНДУЕТСЯ: может не скомпилироваться
std::next(std::min_element(first, last)) // OK: next скопирует результат find()
                                         // и вызовет "++" у l-value


В остальных случаях нет никаких причин использовать next и prev вместо ++ и --.