C语言中的通用数组元素交换 [英] Universal array element swap in C

问题描述

现在我已经意识到，在我的许多代码中，我将拥有2或3个这样的函数:

I've realized now that in many of my codes, I will have 2 or 3 functions like this:

void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

每个都有自己的指针类型.我想知道的是，例如，是否有一种方法可以交换数组的两个元素，而与数组类型无关?

Each with their own pointer type. What I'm wondering is, if there is a way to swap two elements of an array, for example, regardless of the array type?

推荐答案

是的，但是您必须告诉swap代码元素的大小:

Yes, but you have to tell the swap code how big the elements are:

void generic_swap(void *v1, void *v2, size_t size)
{
    char temp[size];
    memmove(temp, v1, size);
    memmove(v1, v2, size);
    memmove(v2, temp, size);
}

这为临时空间使用了VLA(可变长度数组-C99的功能和C11的可选功能).本地数组temp的大小在运行时由功能参数size控制.如果您不信任用户不要请求交换数兆字节的数据，则可以改用动态内存分配，或者仅在大小大于1 KB时才使用动态内存分配.

This uses a VLA (variable length array — a feature of C99 and an optional feature of C11) for the temporary space. The size of the local array, temp, is controlled at runtime by the function parameter size. If you don't trust your users not to request swapping multiple megabytes of data, you can use dynamic memory allocation instead, or only use dynamic memory allocation if the size is bigger than, say, 1 kilobyte.

要么:

void generic_swap(void *v1, void *v2, size_t size)
{
    size_t chunk = (size > 1024) ? 1024 : size;
    size_t offset = 0;
    char *s1 = v1;
    char *s2 = v2;
    char  temp[chunk];
    while (size > 0)
    {
        size_t length = (size > chunk) ? chunk : size;
        memmove(temp, s1 + offset, length);
        memmove(s1 + offset, s2 + offset, length);
        memmove(s2 + offset, temp, length);
        size -= length;
        offset += length;
    }
}

或者:

void generic_swap(void *v1, void *v2, size_t size)
{
    void *v3 = malloc(size);
    if (v3 != 0)
    {
        memmove(v3, v1, size);
        memmove(v1, v2, size);
        memmove(v2, v3, size);
        free(v3);
    }
}

循环版本避免了动态内存分配的开销，并且不会比在三个操作中全部复制慢得多.可以使用多种方法来调整循环代码—另请参见 rici 发表的评论，介绍了其他优化方法，如果您发现交换代码是瓶颈. 您可以自由选择小于1024字节的大小. 64或128也可能是可行的，并且您不一定在功能中需要VLA.

The loop version avoids the overhead of dynamic memory allocation, and won't be much slower than copying it all in three operations. There are various ways that could be used to tune the looping code — see also the comments by rici about other ways in which you can optimize that if you find that the swapping code is a bottleneck. You're at liberty to choose a smaller size than 1024 bytes; 64 or 128 might be feasible too, and you don't necessarily need a VLA in the function.

交换两个整数:

int i = 37;
int j = 99;

swap_generic(&i, &j, sizeof(i));

交换两个char数组:

char data[80] = "A tabloid writer's nightmare on steroids";
char info[80] = "Obsequiousness will get you nowhere fast";

swap_generic(data, info, sizeof(data));

等请注意，数组必须具有相同的大小，或者更准确地说，您指定的大小必须是较小的数组的大小，以确保安全.

Etc. Note that the arrays need to be the same size — or, more accurately, the size you specify needs to be the size of the smaller of the arrays to be safe.

如果您乐于危险地生活，则可以使用memcpy()代替memmove()-尽管在这种情况下危险是有限的. (如果与自己交换对象，则会调用未定义的行为.否则，这是安全的.)使用memmove()始终有效；使用memcpy()通常有效.我更喜欢总是"而不是大部分".

You can use memcpy() instead of memmove() if you are happy to live dangerously — though the danger is limited in this context. (If you swap an object with itself, you invoke undefined behaviour. Otherwise, it is safe.) Using memmove() always works; using memcpy() usually works. I prefer 'always' to 'mostly'.

例如，使用

gcc -O3 -g -std=c11 -Wall -Wextra -Werror -DUSE_GENSWAP_3 swap89.c -o swap89

与 Valgrind 一起运行时，该代码将获得明确的健康证明.

When run with Valgrind, the code gets a clean bill of health.

代码:

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

#if !defined(USE_GENSWAP_1) && !defined(USE_GENSWAP_2) && !defined(USE_GENSWAP_3)
#define USE_GENSWAP_1
#endif

extern void generic_swap(void *v1, void *v2, size_t size);

#ifdef USE_GENSWAP_1
void generic_swap(void *v1, void *v2, size_t size)
{
    char temp[size];
    memmove(temp, v1, size);
    memmove(v1, v2, size);
    memmove(v2, temp, size);
}
#endif

#ifdef USE_GENSWAP_2
void generic_swap(void *v1, void *v2, size_t size)
{
    size_t chunk = (size > 1024) ? 1024 : size;
    size_t offset = 0;
    char *s1 = v1;
    char *s2 = v2;
    char  temp[chunk];
    while (size > 0)
    {
        size_t length = (size > chunk) ? chunk : size;
        memmove(temp, s1 + offset, length);
        memmove(s1 + offset, s2 + offset, length);
        memmove(s2 + offset, temp, length);
        size -= length;
        offset += length;
    }
}
#endif

#ifdef USE_GENSWAP_3
void generic_swap(void *v1, void *v2, size_t size)
{
    void *v3 = malloc(size);
    if (v3 != 0)
    {
        memmove(v3, v1, size);
        memmove(v1, v2, size);
        memmove(v2, v3, size);
        free(v3);
    }
}
#endif

static size_t min_len(size_t x, size_t y) { return (x < y) ? x : y; }

static void dump_long_buffer(const char *tag, size_t length, char buffer[length])
{
    int maxpadlen = strlen(tag) + sizeof(" = ") - 1;
    printf("%s = ", tag);
    size_t offset = 0;
    int padlen = 0;
    while (length > 0)
    {
        int linelen = min_len(length, 80 - maxpadlen - sizeof("[]\n"));
        printf("%*s[%.*s]\n", padlen, "", linelen, buffer + offset);
        offset += linelen;
        length -= linelen;
        padlen = maxpadlen;
    }
}

int main(void)
{
    int i = 37;
    int j = 99;

    printf("i = %d; j = %d\n", i, j);
    generic_swap(&i, &j, sizeof(i));
    printf("i = %d; j = %d\n", i, j);

    char data[80] = "A tabloid writer's nightmare on steroids";
    char info[80] = "Obsequiousness will get you nowhere fast";

    printf("data = [%s]\ninfo = [%s]\n", data, info);
    generic_swap(data, info, sizeof(data));
    printf("data = [%s]\ninfo = [%s]\n", data, info);

    char maxibuff1[2560];
    char maxibuff2[2560];

    for (size_t k = 0; k < sizeof(maxibuff1); k++)
    {
        maxibuff1[k] = k % 64 + '!';
        maxibuff2[k] = 'z' - k % 64;
    }

    /* The aligned output is mostly the result of serendipity */
    dump_long_buffer("maxibuff1", sizeof(maxibuff1), maxibuff1);
    dump_long_buffer("maxibuff2", sizeof(maxibuff2), maxibuff2);
    generic_swap(maxibuff1, maxibuff2, sizeof(maxibuff1));
    dump_long_buffer("maxibuff1", sizeof(maxibuff1), maxibuff1);
    dump_long_buffer("maxibuff2", sizeof(maxibuff2), maxibuff2);

    return 0;
}

样本输出(每种算法的结果相同)

Sample output (the result is the same from each algorithm):

i = 37; j = 99
i = 99; j = 37
data = [A tabloid writer's nightmare on steroids]
info = [Obsequiousness will get you nowhere fast]
data = [Obsequiousness will get you nowhere fast]
info = [A tabloid writer's nightmare on steroids]
maxibuff1 = [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
…
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
maxibuff2 = [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
…
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
maxibuff1 = [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
…
            [zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;]
maxibuff2 = [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]
…
            [!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`]

这篇关于C语言中的通用数组元素交换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！