在使用Xcode分发的LLVM libc(for C 11)的string :: find方法中实现的算法(及其复杂性)是什么？我找不到任何关于它的文档,并且跟随库标题并不是很容易.有人可以帮忙吗？

解决方法:

这是他们的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,它执行一些简单的检查,然后调用<algorithm>中的辅助函数__search：

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>中找到它.标题链接在上面.