为什么天真的`iter_swap`可能比`swap`慢得多？

Question

从David Abrahams和Aleksey Gurtovoy的书“C ++ Template Metaprogramming”，我了解到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。

Answer 1

你的iter_swap()通常是次优的，如果它“完全”起作用，并且不是错误的。

1. std::iter_swap()使用swap()代表argument-dependent-lookup是有原因的： 挑选量身定制的实施方案。
2. 此外，后备std::swap()在交换时利用了移动语义，可能消除了您没有使用的昂贵的资源获取。

当然，两者都与琐碎的类型无关。

Answer 2

向量的std::swap是一个常数复杂运算。

复制矢量的复杂性相对于矢量的长度线性增加。

T tmp = *it1调用复制构造函数。 *it1 = *it2和*it2 = tmp调用复制赋值运算符。