Given n standard C++ STL maps, can I merge them?
STL maps are stored in a data structure which is effectively sorted by key, typically some kind of binary search tree. BSTs have the property that finding the smallest key and finding the next larger key are both amortised O(1) (assuming you can find a node's children in constant time). 

So doing your merge is similar to merging n sorted arrays, which has complexity $N log n$, where $N$ is the total number of elements in all the arrays. (Sorting the concatenation of all the arrays is $O(N log N)$, which is both practically and theoretically slower.

A simple $O(N log n)$ algorithm is to repeatedly do the following until only one array is left:


Divide the arrays into two $n/2$ pairs. If there is an odd number of arrays, one array is treated as though it were paired with an empty array.
Merge each pair into a single array using the standard merge algorithm, which involves iterating through both arrays in parallel. 


The total number of elements scanned in each iteration is at most $N$. (It will be slightly less because the merge procedure combines two elements with the same key, so that the next iteration will involve fewer elements. But $O(N)$ is an acceptable estimate.)

Since the number of trees is halved each time, it will take $\lceil log_2 n\rceil$ iterations to reduce the number of groups to one. So the he total time is the product of the number of iterationss and the total number of elements scanned, which is $O(N log n)$.