Rotating a vector (array)

Question

I am trying to rotate a vector of elements in C++. What I mean by that is that I have a vector<point> I want the last element to become the first.

Example:

[1,2,3] become [3,1,2] then [2,3,1]

For that I tried to do the following:

//Add the last element at index 0
ObjectToRotate.insert(0, ObjectToRotate.at(ObjectToRotate.size()-1));
//Remove Last element
ObjectToRotate.erase(ObjectToRotate.size()-1);

but I get this error:

Error 6 error C2664: 'std::_Vector_iterator<_Myvec> std::vector<Ty>::insert<cv::Point<_Tp>&>(std::_Vector_const_iterator<_Myvec>,_Valty)' : cannot convert parameter 1 from 'int' to 'std::_Vector_const_iterator<_Myvec>'

How can I solve it?

Answer 1

There's a std::rotate algorithm in the standard library:

std::rotate(ObjectToRotate.begin(),
            ObjectToRotate.end()-1, // this will be the new first element
            ObjectToRotate.end());

Answer 2

The recommendations to use std::rotate are, of course, fully correct; using an existing function is always the preferred solution when available. Never the less, it's worth pointing out why your solution didn't work. Containers in the standard library, like std::vector, take position information in the form of iterators, not indexes. The idiomatic way of writing your operation would be:

v.insert( v.begin(), v.back() );
v.erase( std::prev( v.end() ) );

(If you don't have C++11, it's pretty simply to write your own version of prev. Or in the case of vector, you can just write v.end() - 1.)

Answer 3

The arguments to insert and erase are iterators, not indexes:

ObjectToRotate.insert(ObjectToRotate.begin(), ObjectToRotate.back());
ObjectToRotate.pop_back();  // or erase(ObjectToRotate.end()-1), if you prefer

But it may be more efficient to remove the last element first (after taking a copy), to avoid the possibility of reallocation:

auto back = ObjectToRotate.back();
ObjectToRotate.pop_back();
ObjectToRotate.insert(ObjectToRotate.begin(), back);

or to use std::rotate:

std::rotate(ObjectToRotate.begin(), ObjectToRotate.end()-1, ObjectToRotate.end());

If you're doing this a lot, then deque might be a better choice of container, since that allows efficient insertion and removal at both ends. But, if speed is important, make sure you measure and verify that this really is an improvement; if the sequence isn't very large, then the overhead from the more complicated memory layout might make deque slower.

Answer 4

Use std::rotate: http://en.cppreference.com/w/cpp/algorithm/rotate