Here's a fixed x3 grammar that comes a lot closer to your hand rolled "parser":

const auto key     = +~char_(':');
const auto value   = *(char_ - "\r\n");

const auto header = key >> ':' >> value >> "\r\n";
const auto map    = *header >> "\r\n";

Of course, it's still more strict and more robust. Also, don't call it with a space skipper, since your hand-rolled parser doesn't do that either.

Here's the performance measurements on my box:

Statistics that's 2.5µs vs. 3.5µs on average.

Full Code

Using http://nonius.io for robust benchmarking:

#include <iostream>
#include <string>
#include <map>
#include <nonius/benchmark.h++>

#include <boost/spirit/home/x3.hpp>
#include <boost/fusion/adapted/std_pair.hpp>

using header_map = std::map<std::string, std::string>; 

namespace parser
{
    namespace x3 = boost::spirit::x3;
    using x3::char_;

    const auto key     = +~char_(':');
    const auto value   = *(char_ - "\r\n");

    const auto header = key >> ':' >> value >> "\r\n";
    const auto map    = *header >> "\r\n";
}


template <typename It>
void parseHeader(It& iter, It end, header_map& map)
{
    std::string key;
    std::string value;

    It last = iter;
    bool inKey = true;
    while(iter+1 != end)
    {
        if(inKey && *(iter+1)==':')
        {
            key.assign(last, iter+1);
            iter+=3;
            last = iter;
            inKey = false;
        }
        else if (!inKey && *(iter+1)=='\r' && *(iter+2)=='\n')
        {
            value.assign(last, iter+1);
            map.insert({std::move(key), std::move(value)});
            iter+=3;
            last = iter;
            inKey = true;
        }
        else if (inKey && *(iter)=='\r' && *(iter+1)=='\n') 
        {
            iter+=2;
            break;
        }
        else
        {
            ++iter;
        }
    }
}

static auto const str = [] {
    std::string tmp;
    const std::size_t headerCount = 20;
    for(std::size_t i = 0; i < headerCount; ++i)
    {
        std::string num = std::to_string(i);
        tmp.append("key" + num + ": " + "value" + num + "\r\n");
    }
    tmp.append("\r\n");
    return tmp;
}();

NONIUS_BENCHMARK("manual", [](nonius::chronometer cm) {

    cm.measure([]() {
        auto iter = str.cbegin();
        auto end = str.cend();

        header_map header;
        parseHeader(iter, end, header);
        assert(header.size() == 20);
        return header.size();
    });
})

NONIUS_BENCHMARK("x3", [](nonius::chronometer cm) {

    cm.measure([] {
        auto iter = str.cbegin();
        auto end = str.cend();

        header_map header;
        parse(iter, end, parser::map, header);
        assert(header.size() == 20);
        return header.size();
    });
})

#include <nonius/main.h++>

I'm using gcc 5.4 and Boost 1.61