CODEWITHSUNDEEP
c++vector
Y2theZ
Y2theZ

Reputation: 10412

Rotating a vector (array)

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?

Upvotes: 9

Views: 20696

Answers (6)

Chioke Aarhus
Chioke Aarhus

Reputation: 485

James Kanze suggested a fantastic answer of using the following code snippet to rotate individual elements. To rotate x amount of items, simply put the below code into a loop.

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

If you CAN use the standard rotate function, that'll be your best choice, however. The code below is again rotating x number of items, see the CPP docs about rotate, and they even provide code examples showing Left & Right rotation. :)

    // simple rotation to the left
    std::rotate(vec.begin(), vec.begin() + x, vec.end());
  
    // simple rotation to the right
    std::rotate(vec.rbegin(), vec.rbegin() + x, vec.rend());

Upvotes: 1

Lakshya Punhani
Lakshya Punhani

Reputation: 293

for making [1,2,3] to [2,3,1] here is the code

vector<int> Solution::rotateArray(vector<int> &A, int B) {
  vector<int> ret; 
  for (int i = 0; i < A.size(); i++) {
    ret.push_back(A[(i + B) % A.size()]);
  }
  return ret; 
}

here A is [1,2,3] and B is 1 to shift 1 position

Upvotes: 0

Mike Seymour
Mike Seymour

Reputation: 254751

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.

Upvotes: 5

James Kanze
James Kanze

Reputation: 154047

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.)

Upvotes: 9

R. Martinho Fernandes
R. Martinho Fernandes

Reputation: 234654

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());

Upvotes: 22

ecatmur
ecatmur

Reputation: 157484

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

Upvotes: 1

Related Questions