Protobuf did not support maps for a long time. In practice using a list of key/value pairs works fine for most use cases. Sending the message over the wire is obviously always O(n); if you need fast inserts/lookups in code, then it usually makes sense to convert to and from the appropriate in-memory data structure for that purpose.
That said, I think maps are a fine feature for a serialization format to have. But, I haven't gotten around to adding them in Cap'n Proto because I have yet to hit a use case where I wasn't happy with a list of key/value pairs.
For what it's worth, I like them primarily because I don't mind using proto-generated objects as pieces passed around the stack (at least at higher levels of the stack). I lose consistency if I can do that for some objects, but am required to convert objects if they would need a mapping type.
It follows sorta the same reason that Clojure became a fairly widely used lisp – mapping types are extremely common in real world programs. Having them supported first class makes a lot of common tasks quicker to get through.
No, you're right. The canonical way to store a map in capnp is to use a List<Pair<key, value>>. Personally it doesn't bother me that much (mostly from an aesthetic standpoint) because it is not meant as an in-memory, working data structure.
What does bother me is that in the above generic type, "key" and "value" must be pointer types (i.e. non-scalar). The reasons are not unreasonable but it's definitely obnoxious in practice.
Protobuf has disadvantages, but mapping types are something I frequently make use of. losing out on them is a big deal