在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);
}

可以看出,这只是分派到辅助函数__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>上面链接的标题中找到它.