Key and Value should be stored separately. Keeping them in a Pair was convenient for iteration, but since the value is typically the one you want to access, storing it in its own container will allow it to be correctly aligned without wastage added by the key, as well as allowing both keys and values to only be pulled into cache when needed (assuming that the vector of each stores them sequentially in memory, as currently happens with the pairs). I don't mind breaking STL compatibility somewhat here (though it could be emulated if need be).
Some improvements to both of these containers:
Map & Set:
Map: