English 中文(简体)
In Place rotation C++ Practice
原标题:

I have a working rotating function going for my "items" int array. The code below gets it done, except that im transferring values out unnecessarily. Im trying to acheive the "inplace" rotation. What I mean by that is where the ptrs would increment or decrement instead of grabbing values out of the array..By which I need to "up" the efficiency level in that way for this method..Any Suggestions?

void quack::rotate(int nRotations)
{
 if ( count <= 1 ) return;
 else  // make sure our ptrs are where we want them.
 {
  intFrontPtr = &items[0].myInt;
  intBackPtr  = &items[count-1].myInt;
 }
 for (int temp = 0; nRotations != 0;)
 {
  if ( nRotations > 0 )
  {
     temp = *intFrontPtr;
    *intFrontPtr = *intBackPtr;
    *intBackPtr  = temp; // Connect temps for the rotation
   --intBackPtr; // Move left [...<-] into the array
  }
  else if ( nRotations < 0 ) 
  {
   temp = *intBackPtr;
   *intBackPtr  = *intFrontPtr;
   *intFrontPtr = temp; // Connect temps for the rotation
   ++intFrontPtr; // Move right [->...] into the array
  }
  if ( intBackPtr  == &items[0].myInt  || 
    intFrontPtr == &items[count-1].myInt ) 
  {
   intFrontPtr = &items[0].myInt; 
   intBackPtr  = &items[count-1].myInt; // need to re-set
   if ( nRotations > 0 ) nRotations--;  // Which ways did we rotate?
   else nRotations++;
  }
 }
 }

Oh yes, Im trying to practice c++ and know their are many functions floating around that are programmed to do this already...Im trying to "build my own". I think i ve got it down syntactically, but the efficiency is always where i struggle. As, a novice, I would greatly appreciate critisim towards this aspect..

问题回答

There is an old trick for rotating elements in an array (I first saw it in Programming Pearls)

Say you want to rotate an array to the left by three elements.

First reverse the first three elements, next reverse the remaining elements, and then reverse the entire array.

Starting Array:
1 2 3 4 5 6 7

After reversing the first three elements
3 2 1 4 5 6 7

After reversing the remaining elements
3 2 1 7 6 5 4

Finally reverse the entire array to get the final rotated array
4 5 6 7 1 2 3

Reversing portions of the array can be done in place so you don t need any extra memory.

You can leave the data in place, and have a "base index" member to indicate where the array should start. You then need to use this to adjust the index when accessing the array. The array itself should be private, and only accessed through accessor functions that do the adjustment. Something like this:

class quack
{
public:
    explicit quack(int size) : items(new Item[size]), size(size), base(0) {}
    ~quack() {delete [] items;}

    void rotate(int n)      {base = (base + n) % size;}
    Item &operator[](int i) {return items[(base + i) % size];}

private:
    quack(quack const&) = delete;          // or implement these if you want
    void operator=(quack const&) = delete; // the container to be copyable

    Item *items;
    int   size;
    int   base;
};

although I d call it something like RotatableArray, rather than quack.

As usual, if you really have to physically rotate the elements, the correct answer for C++ would be to use std::rotate, which does exactly what you want to do.

If you have to implement it manually (as a practice assignment), take a look at these slides for algorithms from John Bentley s "Programming Pearls".

doing the rotations one by one is really not the way to go. If you are doing anything more than 2 or 3 rotations it gets really slow really quick.

edit: as a final thought... putting the elements in a (double) linked looped list (so the final element points to the first), would require for a rotate to only move the head pointer a few elements. (The head pointer being a pointer to indicate which element in the looped list is the beginning).

this is by far the quickest (and easiest) way to do a rotate on a list of elements

Really the way to do it is to use indexes instead of pointers.

int to = 0;
int from = (to + nRotations) % count;
if (to == from)
    return;

for (int i=0; i < count; i++) {
   swap(from, to);
   from = advance(from);
   to = advance(to);
}

// ...
static inline int advance(int n, int count) { return (n + 1) % count; }

I may have an alternate solution to rotating the array inline. Rather than the old trick of reversing sets of elements, as proposed earlier, this approach works as follows:

Initialization:

(Note q = amount to shift left, n = length of array)

  1. Determine the first source element, which is located at x1=q%n
  2. The destination element is at x2=0
  3. char, ch1, is the ar[x1] element
  4. char, ch2, is the ar[x2] element

Loop on i=0 to n-1, where n = length of array

  1. Overwrite the destination element, ar[x2] with ch1
  2. Set ch1 = ch2
  3. Set x1 = x2
  4. Set x2 = x2 - q
  5. If x2 is negative due to the above subtraction, add n to it
  6. ch2 = ar[x2]

The following may help explain how this works.

Example, rotate to the left by 2 characters:

a b c d e f g

c d e f g a b

x1    ch1    x2    ch2
2     c      0     a
0     a      5     f
5     f      3     d
3     d      1     b
1     b      6     g
6     g      4     e
4     e      2     c

As you can see, this requires no more than n iterations, so it is linear time algorithm that also rotates inline (requires no additional storage other than the few temporary variables).

Here is a function that implements the above algorithm so you can try it out:

void rotate(char *ar, int q)
{
    if (strlen(ar) < 2)
    {
        return;
    }

    if (q <= 0)
    {
        return;
    }

    char ch1;
    char ch2;
    int x1;
    int x2;
    int i;
    int n;

    n = strlen(ar);

    q %= n;

    if (q == 0)
    {
        return;
    }

    x1 = q;
    ch1 = ar[x1];
    x2 = 0;
    ch2 = ar[x2];

    for (i=0;i<n;i++)
    {
        ar[x2] = ch1;
        ch1 = ch2;

        x1 = x2;

        x2 -= q;

        if (x2 < 0)
        {
            x2 += n;
        }

        ch2 = ar[x2];
    }
}

Here s one that I got by modifying the code here:

template<class It>
It rotate(It begin, It const middle, It end)
{
    typename std::iterator_traits<It>::difference_type i = 0, j;
    if (begin != middle && middle != end)
    {
        while ((i = std::distance(begin, middle)) !=
               (j = std::distance(middle,   end)))
        {
            It k = middle;
            std::advance(
                k,
                std::max(typename std::iterator_traits<It>::difference_type(),
                j - i));
            std::swap_ranges(k, end, begin);
            if (i > j) { std::advance(begin, j); }
            else { std::advance(end, -i); }
        }
    }
    return std::swap_ranges(middle - i, middle, middle);
}

Here is code for sdtom solution

void rotateArray(int arr[], int low, int high)
{
    while  (low<high) {
        int temp = arr[low];
        arr[low]=arr[high];
        arr[high]=temp;
        low++;
        high--;
    }
}
void rotate (int arr[], int k,int uperLimit)
{
    rotateArray(arr,0,k);
    rotateArray(arr,k+1,uperLimit-1);
    rotateArray(arr,0,uperLimit-1);

}

https://stackoverflow.com/q/17119000/2383578 : This is somewhat similar to what is discussed here. Rotating the array by a particular amount.

There are many ways to do array rotation by d places.

  1. Block swap algorithm.
  2. Juggling Algorithm.
  3. Reversal Algorithm.

The link below is from Programming Pearls pdf. Check this out. Explained very clearly with code.

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf





相关问题
Undefined reference

I m getting this linker error. I know a way around it, but it s bugging me because another part of the project s linking fine and it s designed almost identically. First, I have namespace LCD. Then I ...

C++ Equivalent of Tidy

Is there an equivalent to tidy for HTML code for C++? I have searched on the internet, but I find nothing but C++ wrappers for tidy, etc... I think the keyword tidy is what has me hung up. I am ...

Template Classes in C++ ... a required skill set?

I m new to C++ and am wondering how much time I should invest in learning how to implement template classes. Are they widely used in industry, or is this something I should move through quickly?

Print possible strings created from a Number

Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...

typedef ing STL wstring

Why is it when i do the following i get errors when relating to with wchar_t? namespace Foo { typedef std::wstring String; } Now i declare all my strings as Foo::String through out the program, ...

C# Marshal / Pinvoke CBitmap?

I cannot figure out how to marshal a C++ CBitmap to a C# Bitmap or Image class. My import looks like this: [DllImport(@"test.dll", CharSet = CharSet.Unicode)] public static extern IntPtr ...

Window iconification status via Xlib

Is it possible to check with the means of pure X11/Xlib only whether the given window is iconified/minimized, and, if it is, how?

热门标签