merging sorted collection with map

I have n (let's say three) sorted key-value collections. The easiest way to merge them is to use std::map. Simple. However, because there are sorted, worth considering is to iterate through one collection and insert pair from the second collection in proper place, not using map::insert, which always will have O(n log n). So it seems to me that best for this situation will be using std::list with std::pair. I have also considered using std::vector with some maping keys on indexes and merging collections using new vector, however it will be more complicated.

Is this way of thinking have sense? Or is there any efficient way to use map in such task.

Thank You.