Есть ли встроенная функция подкачки в C?

Есть ли встроенная функция подкачки в C, которая работает без использования третьей переменной?


person Community    schedule 14.01.2012    source источник


Ответы (10)


Нет.
Встроенная функция подкачки C++: swap(first,second);
Проверьте это: http://www.cplusplus.com/reference/algorithm/swap/

Вы можете использовать это, чтобы поменять местами два значения переменных без использования третьей переменной:

a=a^b;
b=a^b;
a=b^a;

Вы также можете проверить это:

https://stackoverflow.com/questions/756750/своп-значения-двух-переменных-без-использования-третьей-переменной

Как поменять местами без третьей переменной?

person Saiful    schedule 14.01.2012
comment
следует избегать решения с суммой и разностью. С операндами подписанных типов он может переполняться, а знаковые переполнения не определены в C. - person ouah; 14.01.2012
comment
Подкачка C++ не работает как c=a; a=b; b=c;. - person einpoklum; 08.12.2020

Почему вы не хотите использовать третью переменную? Это самый быстрый способ для подавляющего большинства архитектур.

алгоритм замены XOR работает без третьей переменной, но он проблематичен по двум причинам:

  1. Переменные должны быть разными, т.е. swap(&a, &a) не будет работать.
  2. В целом медленнее.

Иногда может быть предпочтительнее использовать своп XOR, если использование третьей переменной приведет к сбросу стека, но обычно вы не в таком положении, чтобы сделать этот вызов.

Чтобы ответить на ваш вопрос напрямую, в стандартном C нет функции подкачки, хотя написать ее было бы тривиально.

person Peter Alexander    schedule 14.01.2012
comment
@delnan: я не пытаюсь утверждать, что производительность важна. Все, что я говорю, это то, что нет причин (включая производительность) не хотеть третью переменную. - person Peter Alexander; 14.01.2012
comment
@delnan: int t = a; a = b; b = t; против a ^= b; b ^= a; a ^= b;. Где это потерянное время? И какая вселенная записывает своп, значительно увеличивая время, необходимое вам для решения проблемы? Это должно быть самая большая проблема, которую я когда-либо видел. - person Peter Alexander; 14.01.2012
comment
@delnan Если вы посмотрите на мой пост, я почти уверен, что моя функция считается независимой от типа, за исключением того, что вы должны указать размер в байтах значений, которые заменяются в качестве третьего аргумента, поэтому я думаю, что это не технически считается, что третья переменная не используется. - person Patrick Roberts; 07.03.2015
comment
XOR Swap — это в основном уловка для программистов на C во встроенных системах, где память драгоценна. - person A. Gille; 08.12.2020

Предполагая, что вам нужен солотив C, а не C++, вы можете сделать его макросом, по крайней мере, используя расширение GCC, чтобы оно было достаточно общим, что-то вроде

 #define SWAP(x,y) do {   \ 
   typeof(x) _x = x;      \
   typeof(y) _y = y;      \
   x = _y;                \
   y = _x;                \
 } while(0)

остерегайтесь таких уловок, как вызовы swap(t[i++],i); чтобы их избежать, используйте адресный оператор &. И вам лучше использовать временное (для целых чисел есть известный и бесполезный трюк с исключающим ИЛИ).

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

person Basile Starynkevitch    schedule 14.01.2012
comment
В чем преимущество использования двух временных переменных вместо одной (скажем, typeof(x) _tmp = x; x = y; y = _tmp; ? - person einpoklum; 28.07.2013
comment
Просто лучшая читаемость и, возможно, более легкая оптимизация компилятором. - person Basile Starynkevitch; 28.07.2013

В стандарте C такой функции нет.

(В C++ используется std::swap().)


Возможно, вам будет полезен макрос из этого вопроса.

person Igor Oks    schedule 14.01.2012

В C нет стандартной функции для замены двух переменных.

Макрос можно написать так:

#define SWAP(T, a, b) do { T tmp = a; a = b; b = tmp; } while (0)

и макрос можно назвать так:

int a = 42;
int b = 2718;

SWAP(int, a, b);

Следует избегать некоторых решений для написания макроса SWAP:

#define SWAP(a, b) do { a = b + a; b = a - b; a = a - b; } while (0)

когда операнды имеют знаковые типы, может произойти переполнение, а подписанное переполнение является неопределенным поведением.

Также следует избегать решения, пытающегося оптимизировать решение XOR, подобное этому:

#define SWAP(a, b) (a ^= b ^= a ^=b)

a изменяется дважды между предыдущей и следующей точкой последовательности, поэтому это нарушает правила точек последовательности и является неопределенным поведением.

person ouah    schedule 14.01.2012
comment
Разве предпочтительнее версия макроса SWAP от @BasileStarynkevitch? - person einpoklum; 28.07.2013
comment
@einpoklum: Нет, потому что не каждый компилятор является GCC, поэтому вы не можете полагаться на расширение GCC, такое как typeof(expr). - person ; 28.07.2013
comment
Мне особенно нравится использование int в качестве первых аргументов макроса. Теперь мы можем утверждать, что у нас есть шаблоны на нашем любимом языке :-) - person paxdiablo; 04.07.2017

Так как вы можете скопировать любое представление объекта в беззнаковый массив символов в C, следующий макрос позволяет вам поменять местами любые два объекта:

#define SWAP(X,Y) \
    do { \
        unsigned char _buf[sizeof(*(X))]; \
        memmove(_buf, (X), sizeof(_buf)); \
        memmove((X),  (Y), sizeof(_buf)); \
        memmove((Y), _buf, sizeof(_buf)); \
    } while (0)

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

person u0b34a0f6ae    schedule 13.01.2013
comment
Любые два объекта? Типа... int x; double y; например? :-) Возможно, вы имели в виду любые два объекта одного и того же типа. - person paxdiablo; 04.07.2017

Есть библиотечная функция C++. Он меняет местами значения двух целочисленных переменных. Например, своп(х, у); поменяет местами значения переменных x и y. Точно так же swap(mat[i][j], mat[j][i]); поменяет местами два значения в матрице mat, а именно значение в строке i, столбце j, и значение в строке j, столбце i.

person Prinavin Govender    schedule 18.09.2014
comment
Библиотечная функция C++ не является ни функцией C, ни встроенной. - person Chris; 18.09.2014

Встроенной функции подкачки нет, но вы можете попробовать это

a = a ^ b;

b = a ^ b;

a = b ^ a;

person Saiful    schedule 27.08.2012

есть std::swap т.к. вообще это зависит от вашего процессора, поддерживает ли он подкачку. есть инструкция под названием «сравнить и поменять местами», но она работает только с типами, которые помещаются в регистр и гарантированно являются атомарными. Существует встроенная реализация сравнения и подкачки (CAS) из gcc он используется для синхронизации реализаций потоков и мьютексов и, вероятно, выходит за рамки ваших целей, поэтому лучше использовать только временную переменную или, если вы действительно застряли на C, вы всегда можете использовать макрос нравится:

#define swap(a,b) a=a^b; \
                  b=a^b; \
                  a=b^a;
person Alexander Oh    schedule 14.01.2012
comment
разве минуту назад не было тега C++? - person Alexander Oh; 14.01.2012
comment
Я думаю, что litb удалил его, потому что вопрос касается C. - person Peter Alexander; 14.01.2012
comment
этого макроса следует избегать. Это неопределенное поведение в C, потому что a изменяется дважды между предыдущей и следующей точкой последовательности. - person ouah; 14.01.2012
comment
@ouah: задействовано 3 точки последовательности ... Так вы уверены, что это неопределенное поведение ?? - person Basile Starynkevitch; 14.01.2012
comment
@BasileStarynkevitch ответ был отредактирован после моего комментария. Он изначально предложил это решение: a^=b^=a^=b; - person ouah; 14.01.2012

Я считаю, что придумал независимую от типа функцию для замены любых двух значений в стандартном C, хотя, поскольку я новичок в этом языке, я мог что-то упустить. Он использует алгоритм подкачки XOR, и я уверен, что его можно было бы еще оптимизировать, но он работает до тех пор, пока два значения указывают на одно и то же количество байтов, указанное третьим аргументом:

void swapn(void *a, void *b, size_t n) {
    if (a == b) {
        return;
    }

    size_t i;
    char *x = (char *)a,
        *y = (char *)b;

    for (i = 0; i < n; i++) {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
        x++;
        y++;
    }
}

Пример использования:

// swap two integers
int x = 5,
    y = 30;

printf("%d\t%d\n", x, y);

swapn(&x, &y, sizeof(int));

printf("%d\t%d\n\n", x, y);

// swap two floats
float a = 9.23f,
    b = 6.83f;

printf("%.2f\t%.2f\n", a, b);

swapn(&a, &b, sizeof(float));

printf("%.2f\t%.2f\n\n", a, b);

// swap two doubles
double p = 4.7539,
    q = 0.9841;

printf("%.4f\t%.4f\n", p, q);

swapn(&p, &q, sizeof(double));

printf("%.4f\t%.4f\n\n", p, q);

// swap two chars
char m = 'M',
    n = 'n';

printf("%c\t%c\n", m, n);

swapn(&m, &n, sizeof(char));

printf("%c\t%c\n\n", m, n);

// swap two strings of equivalent length
char s[] = "Hello",
    t[] = "World";

printf("%s\t%s\n", s, t);

swapn(s, t, sizeof(s));

printf("%s\t%s\n\n", s, t);

Результат:

5   30
30  5

9.23    6.83
6.83    9.23

4.7539  0.9841
0.9841  4.7539

M   n
n   M

Hello   World
World   Hello
person Patrick Roberts    schedule 06.03.2015
comment
Я почти уверен, что трехстороннее xor-назначение является неопределенным поведением, поскольку оно дважды назначает *x без промежуточной точки последовательности. Это легко исправить, но я не понимаю, зачем вообще нужно заморачиваться с xor swap. Это не быстрее, это не проще, это ломается, когда псевдоним двух параметров, и в этой общей реализации из двадцати строк дополнительная переменная даже не является большим кодом. Но это кажется довольно типичным агонистом, я дам вам это. n должно быть size_t. - person ; 07.03.2015
comment
@delnan Я удалил неопределенное поведение и изменил третий аргумент на тип size_t. Что вы подразумеваете под псевдонимом двух параметров? Я считаю, что это обрабатывается начальным оператором if. - person Patrick Roberts; 07.03.2015