在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() )则是明显的胜利.即使他们没有,也可能是胜利.至于首先计算替换的数量,然后精确计算最终大小,我不知道.你'我们必须根据您的实际用例来衡量.)