3

Is there any way how to use std::rotate for the list

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

since these left/right rotations

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

work for the vector?

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

One possible way is to copy the list to the vector

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

and vice versa but I found it too "lengthy"... A direct rotation of the list leads to the following errors:

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

Thanks for your help.

2

2 Answers 2

8

You can't add to std::list iterator since it's not random access. But you can increment it. And that's what std::next does for you:

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

However, this logic, using std::rotate, uses O(n) swap operations.

That's needlessly inefficient. If you want to rotate through all items in the list that's O(n²) complexity. It quickly gets very slow.

Instead just splice the first item in at the end of the list:

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

This uses 0 item swaps, O(1) complexity.

3
  • Somehow I was expecting/hoping that rotate has an overload for list iterators ...
    – Raffi
    Jun 29, 2019 at 23:08
  • This is undefined behaviour. See the standard. The behavior is undefined if other refers to the same object as *this. en.cppreference.com/w/cpp/container/list/splice Aug 9, 2022 at 8:32
  • 1
    @bradgonesurfing: Thanks, but the UB for splicing from self only applies to the overloads with 2 arguments, i.e. attempting to move all of the list into a position in the list (which is generally impossible). It's easy to misunderstand. In fact, at first I corrected the code and wrote: ❝Thanks, you're right, splicing from itself is UB. That was surprising restriction. I've corrected the code to just use a temporary list.❞ Aug 10, 2022 at 9:40
6

The only syntactical issue with the invocation

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

is that std::list iterators don't model random access iterators but bidirectional iterators. Therefore, you can't add or subtract integral values to/from them. Instead, call std::rotate like this

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

Here, std::next increments your iterator, no matter what concept it satifies. That's why it's sometimes better to use it in the first place (in your case, when using a std::vector), as it adds one level of indirection as opposed to someIterator + 1, where you hard-wire the random access requirement.

2
  • I wouldn't call that “the only issue”. By far. Aug 28, 2018 at 9:27
  • @Cheersandhth.-Alf I see your point. "Only" was meant to address the syntactical part of the code. I'll clarify it.
    – lubgr
    Aug 28, 2018 at 9:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.