std::iostream is going to be hopelessly slow, but I would like to point out that -O3 is more appropriate for templated C++ code.

It seems that the two hot spots are the std::string constructor (unsurprisingly) and the vector constructor.

Making string faster is not easy. I would check that gcc is configured to use C++11 strings with the small string optimization and not the older C++03 compatible refcounted string. Writing your own string or a custom allocator are options, but probably overkill for the problem.

The vector constructor is more surprising. It is possible that -O3 could help a bit there. Wrapping the map iterators with std::move_iterator would also avoid a lot of string copies.