Ответ 1
Редактировать:
Поскольку контекст не задан, неясно, вызывает ли ваш код std::swap() или другой алгоритм swap(a,b), например
T tmp = a; a = b; b = tmp;
Когда a и b являются векторами по 1000 int каждый, это будет копировать все векторные элементы 3 раза. a.swap(b) версия std::swap() для контейнеров, таких как std::vector<T> вместо этого вызывает метод a.swap(b) контейнера, по существу заменяя только указатели динамических данных контейнеров.
Кроме того, для разных типов итераторов реализация std::rotate() может использовать некоторые оптимизации (см. Мой старый, возможно, вводящий в заблуждение ответ ниже).
Caveat: Реализация std::rotate() зависит от реализации. Для разных категорий итераторов могут использоваться различные алгоритмы (например, искать __rotate( в заголовке bits/stl_algo.h GNU g++).
Чтобы сдвинуть n элементов на m=std::distance(first,middle) простой (наивный) алгоритм, такой как m вращений одним элементом, требует O (n * m) операций перемещения или копирования. Но нужны только движения O (n), когда каждый элемент находится непосредственно в его правильном положении, что приводит к (примерно) m раз быстрее алгоритму.
Пример для иллюстрации: Поверните строку s = "abcdefg" тремя элементами:
abcdefg : store 'a' in temporary place
dbcdefg : move s[3] to s[0] (where it belongs in the end, directly)
dbcgefg : move s[6] to s[3]
dbcgefc : move s[9%7] to s[6] (wrapping index modulo container size: 9%7 == 2)
dbfgefc : move s[5] to s[2]
dbfgebc : move s[1] to s[5] (another wrapping around)
defgebc : move s[4] to s[1]
defgabc : move 'a' from temporary place to s[4]
Для n и m с наибольшим общим делителем 1 вы делаете это сейчас. В противном случае вам нужно повторить эту схему n/m время для первых m последовательных элементов (n > m принятых здесь). Этот более сложный алгоритм выполняется намного быстрее.
Для двунаправленных итераторов можно использовать еще один легендарный алгоритм O (3n), называемый "перевернутыми руками". Согласно книге Джона Бентли " Программирование жемчуга", она использовалась в ранних редакторах UNIX для перемещения текста:
Положите руки перед собой, один над другим, палец вверх. Теперь
- Поверните одну руку.
- Поверните другое.
- Поверните оба, подключенных друг к другу.
В коде:
reverse(first, middle);
reverse(middle, last);
reverse(first, last);
Для итераторов с произвольным доступом большие куски памяти могут быть перемещены с помощью swap_ranges() (или memmove() для типов POD).
Микрооптимизация с использованием ассемблерных операций может дать небольшое дополнительное ускорение, это можно сделать поверх алгоритма голодания.
Алгоритмы, использующие последовательные элементы вместо "прыжков вокруг" в памяти, также приводят к меньшему количеству промахов кэш-памяти на современных компьютерных архитектурах.