Сдвиг элементов в массиве 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

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

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

Answer 2

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

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

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

Answer 5

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

#include <algorithm>

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

Answer 6

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

Это также довольно эффективно.

// 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 7

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

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

Например,

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

Например, допустим, мы хотим повернуть abcdefg вправо на 2

abcde fg -> перевернуть все -> gf edcba -> перевернуть две части -> fg abcde

P.S. Слайды для этой главы «Программирование жемчуга». Обратите внимание, что в экспериментах Бентли приведенный выше алгоритм оказывается весьма эффективным (среди трех протестированных).

Answer 8

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