Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
VitekSR
0 / 1 / 0
Регистрация: 20.10.2013
Сообщений: 233
26.03.2014, 14:26     Написать функцию swap #1
был вот такой код:
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;
            }
        }
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.03.2014, 14:26     Написать функцию swap
Посмотрите здесь:

C++ Написать функцию, которая могла бы передать значение в другую функцию
C++ Напишите функцию Swap(a, b), аргументами которой могут быть числа любого типа
Создать функцию SWAP, преобразующую заглавные буквы передаваемой ей строки в строчные и наоборот C++
C++ Написать функцию, которая вычисляет объем и площадь поверхности параллелепипеда, описать функцию IsSquare(K)
не могу разобраться как написать функцию сортировки и исправить функцию добавления в стек C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
26.03.2014, 17:35     Написать функцию swap #21
Цитата Сообщение от 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
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
26.03.2014, 17:58     Написать функцию swap #22
Цитата Сообщение от ValeryS Посмотреть сообщение
попробовал
Угу. Запамятовал. Это не будет работать, если оба аргумента разделяют тот же самый адрес.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
26.03.2014, 18:21     Написать функцию swap #23
Цитата Сообщение от gazlan Посмотреть сообщение
Это не будет работать, если оба аргумента разделяют тот же самый адрес.
а зачем их тогда менять
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
26.03.2014, 18:35     Написать функцию swap #24
Эта ситуация возможна, когда обмениваются элементы некоторого набора. Поэтому при использования XOR Swap() обязательна проверка на несовпадение адресов. Ссылку с ходу не дам, но парочка громких фэйлов, связанная с использованием этого трюка в DB точно была.

И, к слову, "наивный" метод с третьей переменной, обычно, эффективнее.
DrOffset
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
26.03.2014, 18:59     Написать функцию swap #25
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вариант с прибитым гвоздями xor (или аналогичный) на современных машинах самый дурацкий. Т.к. вносит прямую зависимость операций, что препятствует эффективному параллельному выполнению внутри конвейера. Т.е. при мизерном выигрыше в памяти получаем замедление выполнения. Еще не стоит забывать, что обменивать так можно только целые числа. И еще, рекомендую чаще смотреть на ассемблерный код, который генерит ваш компилятор, не исключено, что он уже и так оптимизировал вариант с временной переменной, до варианта с xor. Во многих гайдланах к современным компиляторам к тому же написано, что не стоит заниматься ручной микрооптимизацией кода, т.к. это может заблокировать более эффективную и обширную оптимизацию компилятора.
Все это естественно не касается тех, кто пишет под встроенные системы, или около того. Там свои законы, и там оправданное применение xor-swap может найтись. Однако это не отменяет профилирования, а значит доказательства того, что именно этот вариант выигрывает по скорости в нашей задаче.
Юзать такое решение по-умолчанию, не очень хорошая идея, но знать про него безусловно полезно.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
26.03.2014, 19:17     Написать функцию swap #26
Цитата Сообщение от DrOffset Посмотреть сообщение
но знать про него безусловно полезно.
В первую очередь полезно знать про нежелательность преждевременных оптимизаций, о чем уже, собственно, было сказано выше.
А варианты с ксорами сродни использованию сдвигов вместо деления/умножения на степень двойки. Часто они рассматриваются новичками как некоторое "хакерского" решение (которое якобы должно работать быстрее) без понимания сути происходящего.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
26.03.2014, 19:57     Написать функцию swap #27
Цитата Сообщение от 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
6460 / 3834 / 885
Регистрация: 30.01.2014
Сообщений: 6,629
26.03.2014, 20:02     Написать функцию swap #28
Цитата Сообщение от ValeryS Посмотреть сообщение
а это я так, выпендриваюсь
Зря. Потому что в стандартах С и С++ совершенно не гарантируется, что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые. Но по стандарту твой код - UB.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
26.03.2014, 20:11     Написать функцию swap #29
Цитата Сообщение от DrOffset Посмотреть сообщение
Потому что в стандартах С и С++ совершенно не гарантируется,
сошлюсь на Я. Гашека "Похождение бравого солдата Швейка"
"Много что не разрешается, но допускается"
Цитата Сообщение от DrOffset Посмотреть сообщение
что указатель будет целым числом. И это работает только потому, что на x86 указатели - целые.
а где ты указатели увидел?
я беру адрес и интерпретирую его содержимое по другому
UB. там может быть из за несовпадения размеров плавающих и целочисленных
DrOffset
26.03.2014, 20:18
  #30

Не по теме:

Цитата Сообщение от ValeryS Посмотреть сообщение
а где ты указатели увидел?
Да, сори - проглядел. Увидел параметры и перещелкнуло

gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
26.03.2014, 20:19     Написать функцию swap #31
Обсуждение в MSDN: Stupid Coding Tricks
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
26.03.2014, 20:22     Написать функцию swap #32
gazlan,
я так понял что там неоднозначность из-за точек следования
недавно где то тема такая пролетала и именно с такой конструкцией
C++
1
a ^= b ^= a ^= b;
gazlan
2867 / 1815 / 272
Регистрация: 27.08.2010
Сообщений: 4,919
Записей в блоге: 1
26.03.2014, 20:29     Написать функцию swap #33
Цитата Сообщение от ValeryS Посмотреть сообщение
неоднозначность из-за точек следования
Там еще и интересные комментарии к статье :-)
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
27.03.2014, 16:00     Написать функцию swap #34
Цитата Сообщение от 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
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
27.03.2014, 16:08     Написать функцию swap #35
Цитата Сообщение от Alex5 Посмотреть сообщение
Здесь (см.пример на C++)
я не могу найти, где то здесь на форуме, месяца два назад,человек писал, что всегда пользовался
вот такой записью
C++
1
a ^= b ^= a ^= b;
и все работало, но стоило изменить аргументы, то ли с указателя на ссылку то ли наоборот, и все рухнуло
Alex5
883 / 618 / 81
Регистрация: 12.04.2010
Сообщений: 1,552
27.03.2014, 21:22     Написать функцию swap #36
Цитата Сообщение от ValeryS Посмотреть сообщение
месяца два назад,человек писал
Да, в начале февраля рассматривалась эта тема:
Цитата Сообщение от Pershin Посмотреть сообщение
вторая запись перестает работать, если вынести обмен в функцию
Хотелось бы разобраться. Компилятор gcc 4.6.3.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
14.03.2015, 15:42     Написать функцию swap #37
Ксор переполняет каждый бит и гарантированно. В данной задаче это не критично, так как переполнение строго парно и исправляет само себя, но беда ксора в неприменимости к большинству типов.

Добавлено через 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
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
14.03.2015, 17:14     Написать функцию swap #38
Цитата Сообщение от 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
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
14.03.2015, 17:54     Написать функцию swap #39
Цитата Сообщение от MrGluck Посмотреть сообщение
реновый вариант. Если менять переменные с одним и тем же адресом он их обнулит.
При совпадении адресов имеет одну переменную и задача обмена её местами просто не может существовать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.03.2015, 18:06     Написать функцию swap
Еще ссылки по теме:

Массив: Описать функцию swap(A,B), меняющую местами максимальные элементы матриц А и В. C++
C++ рекурсия.написать функцию,принимающую указ. на другую функцию, осуществл. некую операцию с переданным х
C++ Чем можно заменить функцию swap?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,057
14.03.2015, 18:06     Написать функцию swap #40
Цитата Сообщение от taras atavin Посмотреть сообщение
А ничего, что полное имя long long вообще то long long int?
вообще то int допускается опускать
long long тоже самое, что и long long int
short тоже самое, что и short int
Цитата Сообщение от taras atavin Посмотреть сообщение
А это только при совпадении размеров. И приведение в данном контексте - грязный хак.
а я где то утверждал обратное?
Цитата Сообщение от ValeryS Посмотреть сообщение
я беру адрес и интерпретирую его содержимое по другому
UB. там может быть из за несовпадения размеров плавающих и целочисленных
Добавлено через 1 минуту
Цитата Сообщение от taras atavin Посмотреть сообщение
Нужны комментарии?
желательно
Yandex
Объявления
14.03.2015, 18:06     Написать функцию swap
Ответ Создать тему
Опции темы

Текущее время: 01:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru