c++ - 在 C++ 中，用另一个字符串替换字符串中所有出现的子字符串的最快方法是什么？

Question

我正在寻找最有效(就“最快”而言)的方法来用另一个字符串替换字符串中所有出现的子字符串。到目前为止，我想出的只是:

std::string StringReplaceAll(const std::string &cstSearch, const std::string &cstReplace, const std::string &cstSubject)
{
    if(cstSearch.length() > cstSubject.length() || cstSearch == cstReplace || cstSubject.empty() || cstSearch.empty() || cstSubject.find(cstSearch) == std::string::npos)
    {
        return cstSubject;
    }

    std::ostringstream                                  ossReturn;
    std::string::const_iterator                         ci(cstSubject.cbegin());
    const std::string::const_iterator::difference_type  ciFindSize(std::distance(cstSearch.cbegin(), cstSearch.cend()));

    for(std::string::const_iterator ciNow; (ciNow = std::search(ci, cstSubject.cend(), cstSearch.cbegin(), cstSearch.cend())) != cstSubject.cend(); ci = ciNow)
    {
        std::copy(ci, ciNow, std::ostreambuf_iterator<char> (ossReturn));
        std::copy(cstReplace.cbegin(), cstReplace.cend(), std::ostreambuf_iterator<char> (ossReturn));
        std::advance(ciNow, ciFindSize);
    }

    std::copy(ci, cstSubject.cend(), std::ostreambuf_iterator<char> (ossReturn));

    return ossReturn.str();
}

...这对我的需要来说太慢了(!!!):-(

期待向你们学习!

Answer 1

首先，我会使用 std::string 而不是 std::ostringstream 来构建提高结果； std::ostringstream 用于格式化，没有格式化在这里完成。除此之外，您基本上拥有正确的算法；使用 std::search 查找下一个应该更换。我会使用 while 循环来做一些事情更具可读性，这给出了:

std::string
replaceAll( std::string const& original,
            std::string const& before,
            std::string const& after )
{
    std::string retval;
    std::string::const_iterator end     = original.end();
    std::string::const_iterator current = original.begin();
    std::string::const_iterator next    =
            std::search( current, end, before.begin(), before.end() );
    while ( next != end ) {
        retval.append( current, next );
        retval.append( after );
        current = next + before.size();
        next = std::search( current, end, before.begin(), before.end() );
    }
    retval.append( current, next );
    return retval;
}

(注意使用 std::string::append 会比使用快std::copy;字符串知道它必须添加多少，并且可以调整相应的字符串。)

之后，捕获特殊情况将是微不足道的无需替换，立即返回初始字符串；那里使用 std::string::reserve 可能会有一些改进出色地。 (如果 before 和 after 长度相同，retval.reserve( original.size() ) 是一个明显的胜利。即使他们没有，这可能是一场胜利。至于先计算换人次数，然后精确计算最终尺寸，我不知道。你必须用你的实际用例进行测量以找出答案。)