std::rotate substitute

[bitrex]

I need an implementation of rotate for a microprocessor platform where I
have C++11 compiler but really nothing else available to work with. I'd
like to be able to rotate the elements of a short array of characters of
arbitrary length e.g. ABCD -> BCDA -> CDAB etc.

Something like the following should be good enough, but what's good to
use for "swap"? "algorithm" is a non-starter here, too.

#include <algorithm>

string rotate(string s) {
for (int i = 1; i < s.size(); i++)
swap(s[i-1], s[i]);
return s;
}

[bitrex]

Post by bitrex
I need an implementation of rotate for a microprocessor platform where I
have C++11 compiler but really nothing else available to work with. I'd
like to be able to rotate the elements of a short array of characters of
arbitrary length e.g. ABCD -> BCDA -> CDAB etc.
Something like the following should be good enough, but what's good to
use for "swap"? "algorithm" is a non-starter here, too.
#include <algorithm>
string rotate(string s) {
  for (int i = 1; i < s.size(); i++)
    swap(s[i-1], s[i]);
  return s;
}

Perhaps the old "hack":

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

?

[David Brown]

Post by bitrex

Post by bitrex
I need an implementation of rotate for a microprocessor platform where
I have C++11 compiler but really nothing else available to work with.
I'd like to be able to rotate the elements of a short array of
characters of arbitrary length e.g. ABCD -> BCDA -> CDAB etc.
Something like the following should be good enough, but what's good to
use for "swap"? "algorithm" is a non-starter here, too.
#include <algorithm>
string rotate(string s) {
for (int i = 1; i < s.size(); i++)
swap(s[i-1], s[i]);
return s;
}

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

No. Just.. no.


(Alf has already posted the ideas I had.)

[bitrex]

Post by David Brown

Post by bitrex

Post by bitrex
I need an implementation of rotate for a microprocessor platform where
I have C++11 compiler but really nothing else available to work with.
I'd like to be able to rotate the elements of a short array of
characters of arbitrary length e.g. ABCD -> BCDA -> CDAB etc.
Something like the following should be good enough, but what's good to
use for "swap"? "algorithm" is a non-starter here, too.
#include <algorithm>
string rotate(string s) {
for (int i = 1; i < s.size(); i++)
swap(s[i-1], s[i]);
return s;
}

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

No. Just.. no.
(Alf has already posted the ideas I had.)

Ah, right, memmove! I've definitely got string.h, it's been a long time
since I've had to resort to dusty ol' C...

[Juha Nieminen]

Post by bitrex
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

Which at least in modern architectures is slower than the "naive"
swap.

[Alf P. Steinbach]

Post by bitrex
I need an implementation of rotate for a microprocessor platform where I
have C++11 compiler but really nothing else available to work with. I'd
like to be able to rotate the elements of a short array of characters of
arbitrary length e.g. ABCD -> BCDA -> CDAB etc.

If the microprocessor is 32-bit or better, just use its rotate instruction.

Post by bitrex
Something like the following should be good enough, but what's good to
use for "swap"? "algorithm" is a non-starter here, too.

Don't move data by repeated swapping. For moving, move.

Post by bitrex
#include <algorithm>
string rotate(string s) {
  for (int i = 1; i < s.size(); i++)
    swap(s[i-1], s[i]);
  return s;
}

You want a mutating routine for efficiency, not a function.

Like,

void rotate_buffer( char* buf, int size )
{
// Use memmov for the moving.
}

void rotate( string& s )
{
rotate_buffer( s.data(), s.size() );
}

Cheers & hth.,

- Alf

[Juha Nieminen]

Post by bitrex
string rotate(string s) {
for (int i = 1; i < s.size(); i++)
swap(s[i-1], s[i]);
return s;
}

Why swapping? You are performing tons of unnecessary assignments.
In fact, you are performing twice as many as would be needed.
(For a string of length n, you only need n+1 assignments,
not (n-1)*3 assignments as you are doing there.)