Будет ли std::swap(vector[0], vector[1]) быстрее, чем vector[1] = vector[0]?

Question

[Никита]

Допустим, что у нас есть вектор из двух элементов. Необходимо заменить значение в первом элементе вектора на значение в нулевом элементе вектора. Что будет хранится после операции в нулевом элементе - не имеет значения. Тогда какой из этих вариантов будет быстрее?

std::swap(vector[0], vector[1]);

vector[1] = vector[0];

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

Answer 1

[Wataru]

В общем случае - будет.
std::swap работает за константу:

Complexity
1) Constant.

Присвоение за линию:

Complexity
1) Linear in the size of *this and other.

Edit: это если присваемые штуки - вектора. Или какие-то большие объекты с семантикой перемещения. Если у вас тупо числа, то одно присвоение будет быстрее swap.

Comments

[Евгений Шатунов]

Никита , попутно не забываем о том, что std::swap по умолчанию реализуется через три перемещения и его семантика заключается в том, чтобы разменять состояния переданных объектов.
В это же время код vector[1] = vector[0]; выполняет единичное копирование, а не перемещение.
Код std::swap(vector[0], vector[1]); не является семантически равнозначным коду vector[1] = vector[0];.

[Евгений Шатунов]

Wataru ,

Присвоение за линию:

Для всего вектора, а не для его элемента. :)

Т.е. не vector[1] = vector[0];, а vector = other_vector;

[Wataru]

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

[Евгений Шатунов]

Wataru, та я сам минут 5 втыкал в вопрос, ловя диссонанс между кодом и словами вопроса.
Автор немного витиевато во второй части описывает свою реальную ситуацию. Он явно полагает что если вектор состоит из миллиона элементов, то переброс из нулевого в полумиллионный элемент будет дороже переброса из нулевого в первый.

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