Сдвиговые элементы в массиве C++

Question

Я разработал метод, называемый «rotate» для моего класса объектов стека. Я сделал то, что если в стеке есть элементы: {0,2,3,4,5,6,7}, мне нужно было бы вращать элементы вперед и назад.

Если мне нужно повернуть вперед на 2 элемента, то мы получим {3,4,5,6,7,0,2} в массиве. И если мне нужно повернуть назад или -3 элемента, то, глядя на исходный массив, это будет {5,6,7,0,2,3,4}

Итак, метод, который я разработал работает отлично. Его просто ужасно неэффективная ИМО. Мне было интересно, могу ли я объединить массив с помощью оператора мод? Или если их бесполезный код повесился вокруг того, что я еще не понял, и так далее.

Я думаю, мой вопрос: как я могу упростить этот метод? например используя меньше код. :-)

void stack::rotate(int r) 
{ 
    int i = 0; 
    while (r > 0) // rotate postively. 
    { 
     front.n = items[top+1].n; 
     for (int j = 0; j < bottom; j++) 
     { 
      items[j] = items[j+1];         
     } 
     items[count-1].n = front.n; 
     r--; 
    } 

    while (r < 0) // rotate negatively. 
    { 
     if (i == top+1) 
     { 
      front.n = items[top+1].n; 
      items[top+1].n = items[count-1].n; // switch last with first 
     } 

     back.n = items[++i].n; // second element is the new back 
     items[i].n = front.n; 
     if (i == bottom) 
     { 
      items[count-1].n = front.n; // last is first 
      i = 0; 
      r++; 
      continue; 
     } 
     else 
     { 
      front.n = items[++i].n; 
      items[i].n = back.n; 
      if (i == bottom) 
      { 
       i = 0; 
       r++; 
       continue; 
      } 
     } 
    } 
} 

Answer 1

Функция rotate ниже, основан на напоминаниях (вы имеете в виду это под «модой» операций?)

Это также весьма эффективное.

// Helper function. 
// Finds GCD. 
// See http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations 
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);} 

// Number of assignments of elements in algo is 
// equal to (items.size() + gcd(items.size(),r)). 
void rotate(std::vector<int>& items, int r) { 
    int size = (int)items.size(); 
    if (size <= 1) return; // nothing to do 
    r = (r % size + size) % size; // fits r into [0..size) 
    int num_cycles = gcd(size, r); 
    for (int first_index = 0; first_index < num_cycles; ++first_index) { 
    int mem = items[first_index]; // assignment of items elements 
    int index = (first_index + r) % size, index_prev = first_index; 
    while (index != first_index) { 
     items[index_prev] = items[index]; // assignment of items elements 
     index_prev = index; 
     index = (index + r) % size; 
    }; 
    items[index_prev] = mem; // assignment of items elements 
    } 
} 

Конечно, если это целесообразно для вас, чтобы изменить структуру данных, как описано в других ответов, вы можете получить более эффективное решение.

Answer 2

Вместо того чтобы перемещать все предметы в вашем стеке, вы можете изменить определение «начало». Имейте индекс, который представляет первый элемент в стеке, 0 в начале, который вы добавляете и вычитаете из использования модульной арифметики всякий раз, когда вы хотите повернуть свой стек.

Обратите внимание, что если вы примете такой подход, вы не должны предоставлять пользователям доступ к вашему базовому массиву (не то, что вы действительно должны в любом случае ...).

Answer 3

Ну, так как это абстракция вокруг массива, вы можете сохранить индекс «нуль» в качестве члена абстракции и индексировать в массив на основе этого абстрактного понятия первого элемента. Грубо ...

class WrappedArray 
{ 
    int length; 
    int first; 
    T *array; 

    T get(int index) 
    { 
    return array[(first + index) % length]; 
    } 

    int rotateForwards() 
    { 
    first++; 
    if (first == length) 
     first = 0; 
    } 
} 

Answer 4

У вас уже есть несколько разумных ответов, но, возможно, еще один не повредит. Моя первая реакция заключалась в том, чтобы сделать ваш стек оберткой вокруг std :: deque, и в этом случае перемещение элемента с одного конца на другое дешево (O (1)).

Answer 5

Что вы здесь, круговой список.
Если вы настаиваете на сохранении элементов в массиве, просто используйте верхнее смещение и размер для доступа. Этот подход делает вставку элементов после того, как вы достигли выделенного размера, дорогого (перераспределение, копирование). Это можно решить, используя двусвязный список (ala std :: list) и итератор, но произвольный доступ в стек будет O (n).

Answer 6

А теперь, обычный «это уже в Boost,» Ответ: Существует Boost.CircularBuffer

Answer 7

Если по какой-то причине вы бы предпочли, чтобы выполнить фактическое физическое вращение элементов массива, вы можете найти несколько альтернативных решений в " «Программирование жемчуга» Джона Бентли (колонка 2, 2.3 Сила примитивов). На самом деле поиск в Интернете для Rotating Algorithms 'Programming Pearls' расскажет вам все. Литеральный подход, который вы используете сейчас, имеет очень мало практического значения.

Если вы предпочитаете сами решить эту проблему, это может помочь попытаться разобраться с проблемой по-разному. Видите ли, «вращение массива» на самом деле то же самое, что «замена двух неравных частей массива». Думая об этой проблеме в последних условиях может привести вас к новым решениям :)

Например,

• Сторнирования подхода. Измените порядок элементов во всем массиве.Затем разворачивайте две части независимо друг от друга. Вы сделали.

Например, предположим, что мы хотим, чтобы повернуть abcdefg вправо на 2

ABCDE fg ->реверс весь ->gf edcba ->поменять местами две части ->fg ABCDE

PS Slides для этой главы «Программирование жемчуга». Заметим, что в экспериментах Бентли вышеуказанный алгоритм оказывается достаточно эффективным (среди трех тестируемых).

Answer 8

Я не понимаю, какие переменные front и back означают, и зачем вам нужно .n. Во всяком случае, это самый короткий код, который я знаю, чтобы повернуть элементы массива, которые также можно найти в книге Бентли.

#include <algorithm> 

std::reverse(array , array + r ); 
std::reverse(array + r, array + size); 
std::reverse(array , array + size);