I was thinking along the lines of accessing the mapped value of the current element by returning iteratorName->second once the iterator has reached the index passed into the function (I'll increment an int or unsigned int in a loop to keep track of the index).
That will not work: the elements in a map are effectively sorted by key, not by the order in which they were inserted into the map. Since you have no way to re-construct that order given just the map, you have no way to access the nth element.
Still don't see the point of using a vector or deque here, since a vector is basically a resizable array of a specific type. Why would I be storing map iterators in either one of those types, when I'm only interested in one iterator in the at() function, so that I can access the mapped element at the index passed?
Then you can indeed access the nth element, but it will be relatively slow (linear time). You can still use a vector or deque to speed up access to constant time in this case, except that again the performance characteristic of other operations will be affected, e.g., if you want to insert a new element, you have to do it in linear time instead of O(log n) time, since you may need to insert into somewhere in the middle of the corresponding vector or deque.