C++ replace multiple strings in a string in a single pass

user_364847 0
Viewed 9410

Given the following string, "Hi ~+ and ^*. Is ^* still flying around ~+?"

I want to replace all occurrences of "~+" and "^*" with "Bobby" and "Danny", so the string becomes:

"Hi Bobby and Danny. Is Danny still flying around Bobby?"

I would prefer not to have to call Boost replace function twice to replace the occurrences of the two different values.

str-replace boost c++ string
6 Answers

Very late answer but none of answers so far give a solution.

With a bit of Boost Spirit Qi you can do this substitution in one pass, with extremely high efficiency.

#include <iostream>
#include <string>
#include <string_view>
#include <map>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted.hpp>

namespace bsq = boost::spirit::qi;

using SUBSTITUTION_MAP = std::map<std::string, std::string>;//,std::string>;

template <typename InputIterator>
struct replace_grammar
    : bsq::grammar<InputIterator, std::string()>
{
    replace_grammar(const SUBSTITUTION_MAP& substitution_items)
        : replace_grammar::base_type(main_rule)
        {
            for(const auto& [key, value] : substitution_items) {
                replace_items.add(key,value);
            }
            
            main_rule = *( replace_items [( [](const auto &val,  auto& context) {
                auto& res = boost::fusion::at_c<0>(context.attributes);
                res += val;  })]
                |
                bsq::char_ 
                [( [](const auto &val,  auto& context) {
                    auto& res = boost::fusion::at_c<0>(context.attributes);
                    res += val;  })] );
        }

private :
    bsq::symbols<char, std::string> replace_items;
    bsq::rule<InputIterator, std::string()> main_rule;

};


std::string replace_items(std::string_view input, const SUBSTITUTION_MAP& substitution_items)
{
    std::string result;
    result.reserve(input.size());
  
    using iterator_type = std::string_view::const_iterator;
    
    const replace_grammar<iterator_type> p(substitution_items);

    if (!bsq::parse(input.begin(), input.end(), p, result))
        throw std::logic_error("should not happen");

    return result;

}

int main()
{
    std::cout << replace_items("Hi ~+ and ^*. Is ^* still flying around ~+?",{{"~+", "Bobby"} , { "^*", "Danny"}});
}

The qi::symbol is essentially doing the job you ask for , i.e searching the given keys and replace with the given values. https://www.boost.org/doc/libs/1_79_0/libs/spirit/doc/html/spirit/qi/reference/string/symbols.html

As said in the doc it builds behind the scene a Ternary Search Tree, which means that it is more efficient that searching n times the string for each key.

user_87248820
Related