C++ 中的内部实现 std::find

Question

我注意到内部实现的 std::find 中的一些东西让我感到困惑；他们为什么这么做？

\n

std::find(begin,end,...)假设这一行，那么在文件的内部实现中stl_algobase.h，Line:2064是：

\n

\xc2\xa0 \xc2\xa0 \xc2\xa0 typename iterator_traits<_RandomAccessIterator>::difference_type\n\xc2\xa0 \xc2\xa0 __trip_count = (__last - __first) >> 2;\n

\n

这里发生了什么？为什么他们一起做减法然后使用移位运算符？我不明白他们为什么这样做？（抱歉，如果这是初学者的问题。）

\n

Answer 1

这是一种循环展开优化。

auto size = __last - __first;
__trip_count = size / 4; // Instead of >> 2

for(;__trip_count>0; __trip_count--){
  // do 4 sequential tests
  ++first;      ++first;      ++first;      ++first;
}

// The switch takes care of the remaining 0, 1, 2 or 3 checks.

整个实现是

template<typename _RandomAccessIterator, typename _Predicate>
    _GLIBCXX20_CONSTEXPR
    _RandomAccessIterator
    __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Predicate __pred, random_access_iterator_tag)
    {
      typename iterator_traits<_RandomAccessIterator>::difference_type
    __trip_count = (__last - __first) >> 2;

      for (; __trip_count > 0; --__trip_count)
    {
      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;

      if (__pred(__first))
        return __first;
      ++__first;
    }

      switch (__last - __first)
    {
    case 3:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 2:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 1:
      if (__pred(__first))
        return __first;
      ++__first;
      // FALLTHRU
    case 0:
    default:
      return __last;
    }
    }

来自https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_algobase.h#L2059