Boost.Xpressive FTW

This message recently came over the boost-users mailing list:

Subject: [Boost-users] best tool in Boost for (massive) string
         replacement?
From: alfC (alfredo.correa_at_[hidden])
Date: 2010-09-23 18:11:20 

With all the tools available in Boost and coming from a
different backgroup is hard for me to choose what is the best
tool in Boost to do a massive string replacement.

The problem I have is the following, I have a map of replaced
and replacing strings

std::map<std::string, std::string> rep;
rep["alpha"] = "a";
rep["beta"] = "b";
...

let's say about 100 of these. And I have an input/output file
(few thousand lines) were I would like to do all this
replacements. What is the best tool in boost to do this,
Spirit, Regex, tokenizer, StringAlgorithm?

My only approach so far is Regex and the implementation is
very crude. I read the file line by line and do a loop over
the replacement keys for each line. It is not even
exploiting the fact that I have a map of replacements
(compared to an array of replacements). It seems very slow.

(Yes, it is like a 'sed' unix command replacement but with
hundreds of replacement strings)

Thank you,
Alfredo

Here was my answer:

Subject: Re: [Boost-users] best tool in Boost for (massive)
         string replacement?
From: Eric Niebler (eric_at_[hidden])
Date: 2010-09-25 21:04:56 

None of the above. Use Boost.Xpressive. The complete solution
is below:

    #include <map>
    #include <string>
    #include <iostream>
    #include <boost/xpressive/xpressive_static.hpp>
    #include <boost/xpressive/regex_actions.hpp>
    using namespace std;
    using namespace boost::xpressive;

    int main()
    {
        std::map<std::string, std::string> rep;
        rep["alpha"] = "a";
        rep["beta"] = "b";
        rep["gamma"] = "g";
        rep["delta"] = "d";

        local<std::string const *> pstr;
        sregex const rx = (a1 = rep)[pstr = &a1];

        std::string str("alpha beta gamma delta");
        std::cout << regex_replace(str, rx, *pstr)
                  << std::endl;
    }

The regex (a1 = rep) takes the keys in the rep map and builds
a search trie (http://en.wikipedia.org/wiki/Trie) out of them.
When the trie matches, the attribute a1 receives the value
associated with the matching key. The semantic action
[pstr = &a1] assigns the address of the value to the local
variable pstr.

The call to regex_replace uses the lambda expression *pstr as
the replacement.

With Boost.Xpressive, the solution is short and efficient. If we instead call the version of regex_replace that writes to an output iterator, we can do the replacement with only one or two dynamic allocations (used internally by xpressive for holding backreferences and such). Another victory for embedded DSLs.