Почему наивный `iter_swap` потенциально намного медленнее, чем` swap`? - PullRequest
Новая
       35

Почему наивный `iter_swap` потенциально намного медленнее, чем` swap`?

0 голосов
/ 20 февраля 2019

Из книги Дэвида Абрахамса и Алексея Гуртового "Метапрограммирование шаблонов на С ++" я узнал, что iter_swap (см. Ниже) иногда будет намного медленнее, чем std::swap.Хотя в книге есть какое-то объяснение, я не совсем понял, может кто-нибудь объяснить причину этого более подробно.

template <typename ForwardIt1>
void iter_swap(ForwardIt1 it1, ForwardIt1 it2){
  typedef typename std::iterator_traits<ForwardIt1>::value_type T;
  T tmp = *it1;
  *it1 = *it2;
  *it2 = tmp;
}

template <typename ForwardIt1>
void swap_wrapper(ForwardIt1 it1, ForwardIt1 it2){
  std::swap(*it1, *it2);
}

Применяя их к std::list<std::vector<std::string>>::iterator, я обнаружил, что первое в 10 раз медленнее второго, даже когда размер вектора (все элементы которого представляют собой небольшие строки, длина которых меньше 10) равен всего 10.

Ответы [ 2 ]

0 голосов
/ 20 февраля 2019

std::swap вектора - операция постоянной сложности.

Сложность копирования вектора возрастает линейно по отношению к длине вектора.

T tmp = *it1 вызывает копиюконструктор.*it1 = *it2 и *it2 = tmp вызывают оператор назначения копирования.

0 голосов
/ 20 февраля 2019

Ваш iter_swap() часто является неоптимальным, если он вообще "работает" и не ошибается.

  1. Есть причина std::iter_swap() делегирует swap(), используя :
    Подбор индивидуальных реализаций.

  2. Кроме того, запасной вариант std::swap()использует преимущества семантики перемещения при замене, что потенциально исключает дорогостоящее получение ресурсов, которое вы не использовали.

Конечно, оба эти значения не имеют значения для тривиальных типов.

...