Оптимальный способ выполнения операции сдвига по массиву

Предположим, что у меня есть массив

unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9};

Есть ли способ выполнить операцию переключения на них, а не просто скопировать их все в другой массив. Мы можем легко сделать это, используя связанные списки, но мне было интересно, можем ли мы использовать оператор shift и быстрее работать.

Примечание. Данные в этом вопросе являются лишь примером. Ответ должен быть независимо от данных в массиве.

Ответы

Ответ 1

Если вам нужен круговой сдвиг элементов:

std::rotate(&arr[0], &arr[1], &arr[10]);

... сделает трюк. Вам нужно будет # включить заголовок алгоритма.

Ответ 2

Пока массив модифицируется, вы можете использовать memmove для их смещения (но не ошибочно используйте memcpy, поскольку memcpy не предназначен для перекрывающихся областей):

memmove(&arr[0], &arr[1], sizeof(arr) - sizeof(*arr));

(sizeof (arr) - sizeof (* arr) - это размер в байтах всего, кроме 1 элемента массива).

Ответ 3

Если вы единственный человек с указателем на массив, просто увеличивайте указатель и уменьшайте длину.

Не забудьте сохранить исходный указатель, когда вы его освободите.

Ответ 4

Если вы ищете чистое решение C, вот оно, включая программу драйвера. Это довольно просто: повернуть на n, вы:

  • отмените первые n элементы на месте,
  • отмените оставшиеся элементы на месте и
  • отмените весь массив на месте.

Это требует наличия одного элемента дополнительного хранилища (для реверса).

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

/* print an array */
static void print_array(unsigned char *arr, size_t n, const char *prefix)
{
    size_t i;

    if (prefix) {
        printf("%s: ", prefix);
    }
    for (i=0; i < n; ++i) {
        printf("%02x ", (unsigned int)arr[i]);
    }
    printf("\n");
}

/* reverse 'arr', which has 'narr' elements */
static void reverse(unsigned char *arr, size_t narr)
{
    size_t i;

    for (i=0; i < narr / 2; ++i) {
        unsigned char tmp = arr[i];
        arr[i] = arr[narr-i-1];
        arr[narr-i-1] = tmp;
    }
}

/* rotate 'arr' of size 'narr' by 'shift' */
static void rotate(unsigned char *arr, size_t narr, unsigned long shift)
{
    reverse(arr, shift);
    reverse(arr + shift, narr - shift);
    reverse(arr, narr);
}

/* driver program */
int main(int argc, char *argv[])
{
    unsigned char arr[]= {0,1,2,3,4,5,6,7,8,9,10};
    size_t narr = sizeof arr / sizeof arr[0];
    unsigned long shift = 2;

    if (argc > 1) {
        char *eptr;
        shift = strtoul(argv[1], &eptr, 0);
        if (*eptr || errno == ERANGE) {
            perror("strtoul");
            return EXIT_FAILURE;
        }
    }
    print_array(arr, narr, "before shift");
    rotate(arr, narr, shift);
    print_array(arr, narr, "after shift");
    return EXIT_SUCCESS;
}

Ответ 6

Интересно, возможно, вы должны использовать std:: valarray.