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

Question

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

5

我注意到在内部实现的std::find中有一些令人困惑的东西；他们为什么要这样做？

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

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

这里发生了什么？为什么他们要相互减去，并使用位移运算符？我不明白他们这样做的原因。(如果这是一个初学者的问题，抱歉。)

- Another HM

2

通常编译器能够将 x / 4 优化为 x >> 2 ... 因此这只是从旧的优化中复制粘贴或者是作者故意混淆。 - Öö Tiib

2

作为一个旁注：标准库经过优化，可以使我们的懒散代码具有良好的性能。参观并查看，但即使您不完全理解，也可以使用它。 - Friedrich

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Captain Giraffe · Accepted Answer

这是某种循环展开优化。

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