Написать функцию swap

@VitekSR · Регистрация: 20.10.2013

Студворк — интернет-сервис помощи студентам

был вот такой код:

C++
1
2
3
4
5
6
7
8
9
10
for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(p[i].pro < p[j].pro)
            {
            swap (p[i], p[j]);
            }
        }
    }

нужно теперь написать функцию swap, вот мои наброски, но почему то ничего не получается, помогите:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for(i = 0; i < n - 1; i++)
    {
        for(j = i + 1; j < n; j++)
        {
            if(p[i].pro < p[j].pro)
            {
                void swap (p[i].pro, p[j].pro);
                int t = p[i].pro;
                p[i].pro = p[j].pro;
                p[j].pro = t;
            }
        }
    }

ValeryS · 26.03.2014, 17:35

Сообщение от gazlan

Попробуйте обменять два равных значения.

a=5 b=5
a=a^b 5^5=0
b=a^b 0^5=5
a=a^b 0^5=5

попробовал

Добавлено через 1 минуту
с минусами плюсами
a=a+b; 5+5=10
b=a-b; 10-5=5
a=a-b; 10-5=5

@gazlan · 26.03.2014, 17:58

Сообщение от ValeryS

попробовал

Угу. Запамятовал. Это не будет работать, если оба аргумента разделяют тот же самый адрес.

ValeryS · 26.03.2014, 18:21

Сообщение от gazlan

Это не будет работать, если оба аргумента разделяют тот же самый адрес.

а зачем их тогда менять

@gazlan · 26.03.2014, 18:35

Эта ситуация возможна, когда обмениваются элементы некоторого набора. Поэтому при использования XOR Swap() обязательна проверка на несовпадение адресов. Ссылку с ходу не дам, но парочка громких фэйлов, связанная с использованием этого трюка в DB точно была.

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

@DrOffset · 26.03.2014, 18:59

Вариант с прибитым гвоздями xor (или аналогичный) на современных машинах самый дурацкий. Т.к. вносит прямую зависимость операций, что препятствует эффективному параллельному выполнению внутри конвейера. Т.е. при мизерном выигрыше в памяти получаем замедление выполнения. Еще не стоит забывать, что обменивать так можно только целые числа. И еще, рекомендую чаще смотреть на ассемблерный код, который генерит ваш компилятор, не исключено, что он уже и так оптимизировал вариант с временной переменной, до варианта с xor. Во многих гайдланах к современным компиляторам к тому же написано, что не стоит заниматься ручной микрооптимизацией кода, т.к. это может заблокировать более эффективную и обширную оптимизацию компилятора.
Все это естественно не касается тех, кто пишет под встроенные системы, или около того. Там свои законы, и там оправданное применение xor-swap может найтись. Однако это не отменяет профилирования, а значит доказательства того, что именно этот вариант выигрывает по скорости в нашей задаче.
Юзать такое решение по-умолчанию, не очень хорошая идея, но знать про него безусловно полезно.

Tulosba · 26.03.2014, 19:17

Сообщение от DrOffset

но знать про него безусловно полезно.

В первую очередь полезно знать про нежелательность преждевременных оптимизаций, о чем уже, собственно, было сказано выше.
А варианты с ксорами сродни использованию сдвигов вместо деления/умножения на степень двойки. Часто они рассматриваются новичками как некоторое "хакерского" решение (которое якобы должно работать быстрее) без понимания сути происходящего.

ValeryS · 26.03.2014, 19:57

Сообщение от DrOffset

Еще не стоит забывать, что обменивать так можно только целые числа.

это почему еще

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void swapD(long long *a, long long *b)
{
*a=*a^*b;
*b=*a^*b;
*a=*a^*b;
}
 
void swapF(int *a, int *b)
{
*a=*a^*b;
*b=*a^*b;
*a=*a^*b;
}
.........................
float fA=10E30f;
float fB=10E-30f;
 
double dA=10E30;
double dB=10E-30;
 
 
swapD((long long*)&dA,(long long*)&dB);
swapF((int*)&fA,(int*)&fB);

прекрасно меняется

DrOffset, Tulosba, я с вами полностью согласен
а это я так, выпендриваюсь

@DrOffset · 26.03.2014, 20:02

Сообщение от ValeryS

а это я так, выпендриваюсь

Зря. Потому что в стандартах С и С++ совершенно не гарантируется, что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые. Но по стандарту твой код - UB.

ValeryS · 26.03.2014, 20:11

Сообщение от DrOffset

Потому что в стандартах С и С++ совершенно не гарантируется,

сошлюсь на Я. Гашека "Похождение бравого солдата Швейка"
"Много что не разрешается, но допускается"

Сообщение от DrOffset

что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые.

а где ты указатели увидел?
я беру адрес и интерпретирую его содержимое по другому
UB. там может быть из за несовпадения размеров плавающих и целочисленных

@DrOffset · 26.03.2014, 20:18

Не по теме:

Сообщение от ValeryS

а где ты указатели увидел?

Да, сори - проглядел. Увидел параметры и перещелкнуло :)

@gazlan · 26.03.2014, 20:19

Обсуждение в MSDN: Stupid Coding Tricks

ValeryS · 26.03.2014, 20:22

gazlan,
я так понял что там неоднозначность из-за точек следования
недавно где то тема такая пролетала и именно с такой конструкцией

C++
1
a ^= b ^= a ^= b;

@gazlan · 26.03.2014, 20:29

Сообщение от ValeryS

неоднозначность из-за точек следования

Там еще и интересные комментарии к статье :-)

@Alex5 · 27.03.2014, 16:00

Сообщение от gazlan

Обсуждение в MSDN: Stupid Coding Tricks

"During a lunch interview, ... wrote on a napkin: a ^= b ^= a ^= b;"
("За завтраком... написал на салфетке ..." )

Прочитал 1-ю строчку и подумал, стоит ли читать дальше?

Автор заметки "Stupid Coding Tricks", видимо, плохо понимает, о чём пишет. Он путает
1) порядок выполнения операций ^=
этот порядок задан однозначно, т.к. a ^= b ^= a ^= b; эквивалентно a ^= (b ^= (a ^= b) );
2) порядок вычисления аргументов (сначала a, потом b или наоборот). Здесь, действительно C++ не даёт никаких гарантий.

Добавлено через 1 час 22 минуты
Здесь (см.пример на C++) ( Алгоритм обмена при помощи исключающего ИЛИ ) (см.пример на C++) объясняется, почему неправильна запись x ^= (y ^= (x ^= y));

ValeryS · 27.03.2014, 16:08

Сообщение от Alex5

Здесь (см.пример на C++)

я не могу найти, где то здесь на форуме, месяца два назад,человек писал, что всегда пользовался
вот такой записью

C++
1
a ^= b ^= a ^= b;

и все работало, но стоило изменить аргументы, то ли с указателя на ссылку то ли наоборот, и все рухнуло

@Alex5 · 27.03.2014, 21:22

Сообщение от ValeryS

месяца два назад,человек писал

Да, в начале февраля рассматривалась эта тема:

Сообщение от Pershin

вторая запись перестает работать, если вынести обмен в функцию
Хотелось бы разобраться. Компилятор gcc 4.6.3.

@taras atavin · 14.03.2015, 15:42

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

Добавлено через 2 минуты

Сообщение от gazlan

Попробуйте обменять два равных значения.

C++
1
2
3
a^=b; // Здесь a обнуляется
b^=a; // Ксор с нолём равен второму операнду, b сохраняет значение
a^=b; // Ксор с нолём равен второму операнду, a восстанавливает значение

Добавлено через 1 минуту

Сообщение от gazlan

Угу. Запамятовал. Это не будет работать, если оба аргумента разделяют тот же самый адрес.

Тогда сама задача обмена стоять не должна.

Добавлено через 2 минуты

Сообщение от ValeryS

это почему еще

C++
1
void swapD(long long *a, long long *b)

А ничего, что полное имя long long вообще то long long int?

Добавлено через 2 минуты

Сообщение от ValeryS

void swapF(int *a, int *b)

Указатель есть целое специального вида, предназначенное для хранения адреса функции, или другого данного, то есть для хранения номер байта (трайта).

Нужны комментарии?

Добавлено через 1 минуту

Сообщение от ValeryS

swapF((int*)&fA,(int*)&fB);

А это только при совпадении размеров. И приведение в данном контексте - грязный хак.

MrGluck · 14.03.2015, 17:14

Сообщение от MastAKK

par1 = par1^par2;

Хреновый вариант. Если менять переменные с одним и тем же адресом он их обнулит.

А для шаблонов - попробуйте передать в swap пользовательский тип. Не вышло? Всё дело в том, что данный алгоритм подходит только для типов, у которых определён operator^.

Добавлено через 2 минуты
Мой вариант (С++11)

C++
1
2
3
4
5
6
7
template <typename T>
void swap(T &a, T &b)
{
    T tmp(std::move(a));
    a = std::move(b);
    b = std::move(tmp);
}

Стоит отметить, что явно указывать тип у шаблонной функции при вызове не требуется.

@taras atavin · 14.03.2015, 17:54

Сообщение от MrGluck

реновый вариант. Если менять переменные с одним и тем же адресом он их обнулит.

При совпадении адресов имеет одну переменную и задача обмена её местами просто не может существовать.

ValeryS · 14.03.2015, 18:06

Сообщение от taras atavin

А ничего, что полное имя long long вообще то long long int?

вообще то int допускается опускать
long long тоже самое, что и long long int
short тоже самое, что и short int

Сообщение от taras atavin

А это только при совпадении размеров. И приведение в данном контексте - грязный хак.

а я где то утверждал обратное?

Сообщение от ValeryS

я беру адрес и интерпретирую его содержимое по другому
UB. там может быть из за несовпадения размеров плавающих и целочисленных

Добавлено через 1 минуту

Сообщение от taras atavin

Нужны комментарии?

желательно

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

@gazlan 3178 / 1937 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.03.2014, 18:35
	Эта ситуация возможна, когда обмениваются элементы некоторого набора. Поэтому при использования XOR Swap() обязательна проверка на несовпадение адресов. Ссылку с ходу не дам, но парочка громких фэйлов, связанная с использованием этого трюка в DB точно была. И, к слову, "наивный" метод с третьей переменной, обычно, эффективнее. 0

@DrOffset 19501 / 10106 / 2461 Регистрация: 30.01.2014 Сообщений: 17,825
	26.03.2014, 18:59
	Сообщение было отмечено ValeryS как решение Решение Вариант с прибитым гвоздями xor (или аналогичный) на современных машинах самый дурацкий. Т.к. вносит прямую зависимость операций, что препятствует эффективному параллельному выполнению внутри конвейера. Т.е. при мизерном выигрыше в памяти получаем замедление выполнения. Еще не стоит забывать, что обменивать так можно только целые числа. И еще, рекомендую чаще смотреть на ассемблерный код, который генерит ваш компилятор, не исключено, что он уже и так оптимизировал вариант с временной переменной, до варианта с xor. Во многих гайдланах к современным компиляторам к тому же написано, что не стоит заниматься ручной микрооптимизацией кода, т.к. это может заблокировать более эффективную и обширную оптимизацию компилятора. Все это естественно не касается тех, кто пишет под встроенные системы, или около того. Там свои законы, и там оправданное применение xor-swap может найтись. Однако это не отменяет профилирования, а значит доказательства того, что именно этот вариант выигрывает по скорости в нашей задаче. Юзать такое решение по-умолчанию, не очень хорошая идея, но знать про него безусловно полезно. 3

@gazlan 3178 / 1937 / 312 Регистрация: 27.08.2010 Сообщений: 5,131 Записей в блоге: 1
	26.03.2014, 20:19
	Обсуждение в MSDN: Stupid Coding Tricks 0

Написать функцию swap

Решение