CODEWITHSUNDEEP
c++algorithmlistvectorrotation
justik
justik

Reputation: 4275

C++, left/right rotation of std::list

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.

Upvotes: 3

Views: 2347

Answers (2)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145419

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.

Upvotes: 11

lubgr
lubgr

Reputation: 38315

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.

Upvotes: 6

Related Questions