I assume when you say "erase last element", you mean "erase oldest element".
I wouldn't use a string for times, use a date/time type instead (like unix timestamp). Then they'll be sorted by time, instead of lexicographically, and you can myLocations.erase(myLocations.begin()), since the oldest would always be at the beginning.
Even better, use a boost::circular_buffer<std::pair<timetype, LocationStruct>>, and use std::lower_bound to find elements by time. This will automatically remove the oldest for you, and has the same logorithmic complexity on finding an element by time. It's also faster when adding data. It's pretty much win all around for your situation. If you really want to avoid boost, then a std::deque fits your needs best, and gives great performance, but if you already have a working map, then staying with a std::map is probably best.
Here's how to do the find in a deque:
typedef ???? timetype; typedef std::pair<Timetype, LocationStruct> TimeLocPair typedef std::deque<TimeLocPair> LocationContainer; typedef std::deque<TimeLocPair>LocationContainer::const_iterator LocationIterator; bool compareTimeLocPair(const TimeLocPair& lhs, const TimeLocPair& rhs) {return lhs.first < rhs.first;} LocationIterator find(const LocationContainer& cont, timetype time) { TimeLocPair finder(time, LocationStruct()); LocationIterator it = std::lower_bound(cont.begin(), cont.end(), finder, compareTimeLocPair); if (it == cont.end() || it->first != time) return cont.end(); return it; }