c++ - 在 LLVM libc++ 中找到的 string::find 中实现的算法(及其复杂性)是什么？

Question

在随 Xcode 分发的 LLVM libc++(适用于 C++ 11)的 string::find 方法中实现的算法(及其复杂性)是什么？我找不到任何关于它的文档并且遵循库标题并不是很容易。谁能帮忙？

Answer 1

这是他们的 basic_string的 find (只发布了一个过载):

template<class _CharT, class _Traits, class _Allocator>
typename basic_string<_CharT, _Traits, _Allocator>::size_type
basic_string<_CharT, _Traits, _Allocator>::find(const value_type* __s,
                                                size_type __pos,
                                                size_type __n) const _NOEXCEPT
{
    _LIBCPP_ASSERT(__n == 0 || __s != nullptr, "string::find(): received nullptr");
    return _VSTD::__str_find<value_type, size_type, traits_type, npos>
        (data(), size(), __s, __pos, __n);
}

可以看出，这只是分派(dispatch)给辅助函数 __str_find ，它执行一些简单的检查，然后调用辅助函数 __search在 <algorithm> :

template<class _CharT, class _SizeT, class _Traits, _SizeT __npos>
_SizeT _LIBCPP_CONSTEXPR_AFTER_CXX11 _LIBCPP_INLINE_VISIBILITY
__str_find(const _CharT *__p, _SizeT __sz, 
       const _CharT* __s, _SizeT __pos, _SizeT __n) _NOEXCEPT
{
    if (__pos > __sz || __sz - __pos < __n)
        return __npos;
    if (__n == 0)
        return __pos;
    const _CharT* __r = 
        _VSTD::__search(__p + __pos, __p + __sz,
                        __s, __s + __n, _Traits::eq,
                        random_access_iterator_tag(), random_access_iterator_tag());
    if (__r == __p + __sz)
        return __npos;
    return static_cast<_SizeT>(__r - __p);
}

值得注意的是 __search也是std::search调用的函数:

template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>
inline _LIBCPP_INLINE_VISIBILITY
_ForwardIterator1
search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
       _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred)
{
    return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type>
                         (__first1, __last1, __first2, __last2, __pred,
                          typename std::iterator_traits<_ForwardIterator1>::iterator_category(),
                          typename std::iterator_traits<_ForwardIterator2>::iterator_category());
}

执行__search本身是相当标准的，如果 !_LIBCPP_UNROLL_LOOPS 有一个手动展开的循环为零。您可以在 <algorithm> 中找到它上面链接的标题。