C ++, левый / правый поворот std :: list

Question

Есть ли способ использовать std::rotate для списка

std::list<int> v = { 0,7, 1,2 };

так как эти левые / правые повороты

std::rotate(v.begin(), v.begin() + 1, v.end());
std::rotate(v.rbegin(), v.rbegin() + 1, v.rend());

работа для вектора?

std::vector<int> v = { 0, 7, 1, 2 };

Один из возможных способов - скопировать список в вектор

std::vector<int> u{ std::begin(v), std::end(v) };

и наоборот, но я нашел его слишком «длинным» ... Прямое вращение списка приводит к следующим ошибкам:

Error   C2672   'std::rotate': no matching overloaded function found    
Error   C2676   binary '+':  std::_List_iterator<std::_List_val<std::_List_simple_types<_Ty>>>' does not define this operator or a conversion to a type acceptable to the predefined operator

Спасибо за вашу помощь.

Answer 1

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

void rot_slow( std::list<Item>& seq )
{
    std::rotate( seq.begin(), next( seq.begin() ), seq.end() );
}

Однако эта логика, использующая std::rotate, использует O (n) операции обмена.

Это излишне неэффективно. Если вы хотите повернуть все элементы списка, это сложность O (n²). Это быстро становится очень медленным.

Вместо этого просто склейте первый элемент в конце списка:

void rot_fast( std::list<Item>& seq )
{
    seq.splice( seq.end(), seq, seq.begin() );
}

Используется 0 обменов предметов, сложность O (1).

Answer 2

Единственная синтаксическая проблема с вызовом

 std::rotate(v.begin(), v.begin() + 1, v.end());

означает, что std::list итераторы не моделируют итераторы с произвольным доступом , но двунаправленные итераторы . Следовательно, вы не можете добавлять или вычитать целые значения из них. Вместо этого звоните std::rotate вот так

std::rotate(v.begin(), std::next(v.begin()), v.end());
std::rotate(v.rbegin(), std::next(v.rbegin()), v.rend());

Здесь std::next увеличивает ваш итератор, независимо от того, какую концепцию он замышляет. Вот почему иногда лучше использовать его в первую очередь (в вашем случае, когда используется std::vector), так как он добавляет один уровень косвенности по сравнению с someIterator + 1, где вы жестко связываете требование произвольного доступа.