Circular shifting
-
guys, is there a function in C++ that shifts the elements of an array? lets say that i have an array of 20 elemetns and i need to shift it by one element to the right, then the last element should become the first and the first one will be the second and so on.....am not sure if its called circular shift or rotation or something like that. sorry if there is no function, then how would you go about it? you need to save memory and processing time on small controllers.. thanks!!!
-
guys, is there a function in C++ that shifts the elements of an array? lets say that i have an array of 20 elemetns and i need to shift it by one element to the right, then the last element should become the first and the first one will be the second and so on.....am not sure if its called circular shift or rotation or something like that. sorry if there is no function, then how would you go about it? you need to save memory and processing time on small controllers.. thanks!!!
Hi, AFAIK there is no such function available in the standard libraries. The operation should be called rotation. A buffer that gets used from 0 till dim-1 then back to 0 etc is called a circular buffer. Are you sure you need to move the data around, a circular buffer is used for many purposes (e.g. between a producer and a consumer, using a put and a get pointer); circular buffers may be optimized by using a dimension that equals a power of two (so you dont need to test for wrapping around, you simply mask away the overflowing bit). If you must move the data over an arbitrary shift amount, you could use an existing copy function twice: -once for the part that moves to the right, and once for the part that moves to the left; since source and destination overlap, you would need a temp buffer for one of the moves. Moving over only one position only needs one memcpy or similar, and one temp variable. :)
Luc Pattyn [My Articles]
-
guys, is there a function in C++ that shifts the elements of an array? lets say that i have an array of 20 elemetns and i need to shift it by one element to the right, then the last element should become the first and the first one will be the second and so on.....am not sure if its called circular shift or rotation or something like that. sorry if there is no function, then how would you go about it? you need to save memory and processing time on small controllers.. thanks!!!
If U want to save memory and processing time,U should not shift the entire array. Instead U can have a variable say idxStart.It must be first set to ZERO. If U want to shift to the right do like this: idxStart=(--idxStart+arrayLength)%arrayLength; While referring the array elements always refer like: for(i=0;i<arrayLength;i++) cout<Regards, Arun Kumar.A
-
guys, is there a function in C++ that shifts the elements of an array? lets say that i have an array of 20 elemetns and i need to shift it by one element to the right, then the last element should become the first and the first one will be the second and so on.....am not sure if its called circular shift or rotation or something like that. sorry if there is no function, then how would you go about it? you need to save memory and processing time on small controllers.. thanks!!!
// CommandLine.cpp : Defines the entry point for the console application. // #include "StdAfx.h" #include #include // for 'std::rotate' and 'std::copy' #include // for 'ostream_iterator' int main() { using namespace std; int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int *pOnePastEnd = numbers + sizeof(numbers)/sizeof(numbers[0]); cout << "Before rotate:" << endl; copy(numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; // Rotate left. rotate(numbers, numbers+1, pOnePastEnd); cout << "After rotate left:" << endl; copy(numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; // Rotate right. rotate(numbers, pOnePastEnd-1, pOnePastEnd); cout << "After rotate right:" << endl; copy(numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; return 0; } Steve
-
Hi, AFAIK there is no such function available in the standard libraries. The operation should be called rotation. A buffer that gets used from 0 till dim-1 then back to 0 etc is called a circular buffer. Are you sure you need to move the data around, a circular buffer is used for many purposes (e.g. between a producer and a consumer, using a put and a get pointer); circular buffers may be optimized by using a dimension that equals a power of two (so you dont need to test for wrapping around, you simply mask away the overflowing bit). If you must move the data over an arbitrary shift amount, you could use an existing copy function twice: -once for the part that moves to the right, and once for the part that moves to the left; since source and destination overlap, you would need a temp buffer for one of the moves. Moving over only one position only needs one memcpy or similar, and one temp variable. :)
Luc Pattyn [My Articles]
std::rotatefrom <algorithm>.Steve
-
// CommandLine.cpp : Defines the entry point for the console application. // #include "StdAfx.h" #include #include // for 'std::rotate' and 'std::copy' #include // for 'ostream_iterator' int main() { using namespace std; int numbers[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int *pOnePastEnd = numbers + sizeof(numbers)/sizeof(numbers[0]); cout << "Before rotate:" << endl; copy(numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; // Rotate left. rotate(numbers, numbers+1, pOnePastEnd); cout << "After rotate left:" << endl; copy(numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; // Rotate right. rotate(numbers, pOnePastEnd-1, pOnePastEnd); cout << "After rotate right:" << endl; copy(numbers, pOnePastEnd, ostream_iterator(cout, " ")); cout << endl; return 0; } Steve
Thank you all for all the responses.. much appreciated.. I think i'll go with Arun's method of changing the index. Steve, i got a question.. how do i know about the functions in a library? dumb question, sorry! but not evrything is mentioned in the documentation. oh, yeah and thanks for the code...
-
Thank you all for all the responses.. much appreciated.. I think i'll go with Arun's method of changing the index. Steve, i got a question.. how do i know about the functions in a library? dumb question, sorry! but not evrything is mentioned in the documentation. oh, yeah and thanks for the code...
I read a book on the STL. You could also look through the <algorithm> header file. C++ programmers should get acquainted with STL. I also recommend studying the Boost libraries.
Steve
-
I read a book on the STL. You could also look through the <algorithm> header file. C++ programmers should get acquainted with STL. I also recommend studying the Boost libraries.
Steve
will do.... thanks man. I've just started with C++. from engineering days, am used to matlab.. but i think its always good to add other languages too..
-
Thank you all for all the responses.. much appreciated.. I think i'll go with Arun's method of changing the index. Steve, i got a question.. how do i know about the functions in a library? dumb question, sorry! but not evrything is mentioned in the documentation. oh, yeah and thanks for the code...
Sorry to butt in here, but I'd recommend the book "The C++ Standard Template Library: A Tutorial and Reference" by Josuttis for exactly that purpose. There are several chapters you can skim and get a good sense pretty quickly as to what's in the STL, without being bored to tears. It also has lots of good examples and discussions and things like that. I've looked into a couple books in the past, trying to do exactly what you're talking about, and that one towers over the rest, IMHO. Excellent stuff.