使用boost::algorithm库进行字符串擦除和字符串替换

boost::algorithm库相对于std::string的erase和replace方法的好处就在于，可以做擦除第一个，第二个，最后一个，第N个的操作。
代码很简单，直接上代码，
CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
project(lexical_cast)

add_definitions(-std=c++14)

include_directories("/usr/local/include")
link_directories("/usr/local/lib")
file( GLOB APP_SOURCES ${CMAKE_CURRENT_SOURCE_DIR}/*.cpp)
foreach( sourcefile ${APP_SOURCES} )
    file(RELATIVE_PATH filename ${CMAKE_CURRENT_SOURCE_DIR} ${sourcefile})
    string(REPLACE ".cpp" "" file ${filename})
    add_executable(${file} ${sourcefile})
    target_link_libraries(${file} boost_filesystem boost_regex boost_thread boost_system boost_serialization pthread boost_chrono)
endforeach( sourcefile ${APP_SOURCES} )

main.cpp

#include <boost/algorithm/string/erase.hpp>
#include <boost/algorithm/string/replace.hpp>

#include <iostream>
#include <string>

// 名称空间简化，重命名
namespace ba = boost::algorithm;

const std::string str = "Hello, hello, dear reader.";

// 擦除字符串中特定字符的例子
void erasing_examples() {
    std::cout << "\n erase all copy   :" << ba::erase_all_copy(str, ",");
    std::cout << "\n erase first copy :" << ba::erase_first_copy(str, ",");
    std::cout << "\n erase last copy  :" << ba::erase_last_copy(str, ",");
    std::cout << "\n ierase all copy  :" << ba::ierase_all_copy(str, "hello");
    std::cout << "\n ierase nth copy  :" << ba::ierase_nth_copy(str, ",", 1);
}

void replacing_examples() {
    std::cout << "\n replace all copy   :" << ba::replace_all_copy(str, ",", "!");
    std::cout << "\n replace first copy :" << ba::replace_first_copy(str, ",", "!");    
    std::cout << "\n replace head copy  :" << ba::replace_head_copy(str, 6, "Whaaaaaaaaaaa!");
}

int main(int argc, char* argv[]) {
    erasing_examples();
    replacing_examples();
}

程序输出如下，

图片.png

可以简单关注下boost::algorithm::erase_all_copy函数的实现，其他的实现以此类推。

boost::algorithm::erase_all_copy

template<typename SequenceT, typename RangeT>
        inline SequenceT erase_all_copy( 
            const SequenceT& Input,
            const RangeT& Search )
        {
            // 调用 find_format_all_copy
            return ::boost::algorithm::find_format_all_copy( 
                Input, 
                ::boost::algorithm::first_finder(Search),
                ::boost::algorithm::empty_formatter(Input) );
        }

find_format_all_copy调用 detail::find_format_all_copy_impl,
find_format_all_copy_impl调用::boost::algorithm::detail::find_format_all_copy_impl2，

看一下这个函数的实现，重点看我写注释那两句

  template< 
                typename OutputIteratorT,
                typename InputT,
                typename FinderT,
                typename FormatterT,
                typename FindResultT,
                typename FormatResultT >
            inline OutputIteratorT find_format_all_copy_impl2(
                OutputIteratorT Output,
                const InputT& Input,
                FinderT Finder,
                FormatterT Formatter,
                const FindResultT& FindResult,
                const FormatResultT& FormatResult )
            {       
                typedef BOOST_STRING_TYPENAME 
                    range_const_iterator<InputT>::type input_iterator_type; 

                typedef find_format_store<
                        input_iterator_type, 
                        FormatterT,
                        FormatResultT > store_type;

                // Create store for the find result
                store_type M( FindResult, FormatResult, Formatter );

                // Initialize last match
                input_iterator_type LastMatch=::boost::begin(Input);

                // Iterate through all matches
                while( M )
                {
                    // Copy the beginning of the sequence
                    Output = std::copy( LastMatch, M.begin(), Output );
                    // Copy formatted result
                    Output = std::copy( ::boost::begin(M.format_result()), ::boost::end(M.format_result()), Output );

                    // Proceed to the next match
                    // LastMatch=M.end()
                   // 说明LastMatch记录了上一次找到的字符串的结束位置
                   // 例如  在 hello, hello, deal reader这个串中，查找hello
                   // 第一次找到hello后， M.end()所在的位置就是第一个hello之后的 ","所在位置
                   // 这个","的index是  5 
                    LastMatch=M.end();    
                    M=Finder( LastMatch, ::boost::end(Input) );
                }

                // Copy the rest of the sequence
                Output = std::copy( LastMatch, ::boost::end(Input), Output );

                return Output;
            }

再关注一下 Finder函数的实现，
使用的是 ::boost::algorithm::first_finder

 template<typename RangeT>
        inline detail::first_finderF<
            BOOST_STRING_TYPENAME range_const_iterator<RangeT>::type,
            is_equal>
        first_finder( const RangeT& Search )
        {
            // first_find构造了一个仿函数，first_finderF
            return 
                detail::first_finderF<
                    BOOST_STRING_TYPENAME 
                        range_const_iterator<RangeT>::type,
                        is_equal>( ::boost::as_literal(Search), is_equal() ) ;
        }

重点查看一下first_finderF的 operator()(iterater begin, iterator end)操作符重载,
看注释就可以，

  // Operation
                template< typename ForwardIteratorT >
                iterator_range<ForwardIteratorT>
                operator()(
                    ForwardIteratorT Begin,
                    ForwardIteratorT End ) const
                {
                    typedef iterator_range<ForwardIteratorT> result_type;
                    typedef ForwardIteratorT input_iterator_type;
                  
                    // 和上面的分析一致，
                    // 如果这里是第一次hello匹配完的位置，
                   // 那么hello, hello, dear reader变成
                   //  hello, dear reader
                   // begin指向第二个hello前面的空格
                   // end指向字符串末尾，也就是最后reader的r后面

                    for(input_iterator_type OuterIt=Begin;
                        OuterIt!=End;
                        ++OuterIt)
                    {
                        // Sanity check
                        if( boost::empty(m_Search) )
                            return result_type( End, End );
                    
                        input_iterator_type InnerIt=OuterIt;
                        // m_Search是要查找的字符串，
                        // 在父串中查找子串， 
                       search_iterator_type SubstrIt=m_Search.begin();
                        for(;
                            InnerIt!=End && SubstrIt!=m_Search.end();
                            ++InnerIt,++SubstrIt)
                        {
                            // 如果查找过程中遇到不相等，说明未匹配到子串
                            // 退出匹配过程
                            if( !( m_Comp(*InnerIt,*SubstrIt) ) )
                                break;
                        }

                        // Substring matching succeeded
                        // 如果匹配到子串结束
                        // 说明匹配到子串
                       // 返回当前子串的iterator_range<iterator<const char*>, iterator<const char*>>对象
                        if ( SubstrIt==m_Search.end() )
                            return result_type( OuterIt, InnerIt );
                    }

                    return result_type( End, End );
                }

所以boost::algorithm库的子串擦除算法其实也就是逐个子串匹配。
如果父串的长度为m, 子串的长度为n
那么这种匹配的时间复杂度为 m*n。