Where can I find the full implementation of std::string::find()?

Question

I'm looking to find out why it is that every single implementation of a string searching algorithm I've written so far is quite a bit worse than the one provided by std::string.

Not only is it better, but it seems to perform in constant time (by constant I mean it varies very little depending on the size of the string and/or substring) regardless of whether I've split the load among threads.

Here be my compiler:

g++ (Ubuntu 4.8.1-2ubuntu1~12.04) 4.8.1
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

So far, I've managed to dig up basic_string.tcc located in /usr/include/c++/4.8.1/bits, which yields this for std::string::find:

template<typename _CharT, typename _Traits, typename _Alloc>
    typename basic_string<_CharT, _Traits, _Alloc>::size_type
    basic_string<_CharT, _Traits, _Alloc>::
    find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT
    {
        size_type __ret = npos;
        const size_type __size = this->size();
            if (__pos < __size)
            {
                const _CharT* __data = _M_data();
                const size_type __n = __size - __pos;
                const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
                if (__p)
                __ret = __p - __data;
            }
        return __ret;
    }

The only thing I'm missing at the moment is found on this line:

const _CharT* __p = traits_type::find(__data + __pos, __n, __c);

So does anyone have any idea where I might find the implementation of traits_type::find?

Answer 1

I've found:

• a general one,
• one for char,
• one for wchar_t,
• one for char16_t,
• and one for char32_t.

The char/wchar_t ones just call the C (builtin) functions, and I notice now they could optimize one of the char16_t/char32_t ones using the same specialization as wchar_t which should be the same size as one of these two types on most platforms.