Index: lldb/include/lldb/DataFormatters/FormattersContainer.h
===================================================================
--- lldb/include/lldb/DataFormatters/FormattersContainer.h
+++ lldb/include/lldb/DataFormatters/FormattersContainer.h
@@ -65,8 +65,49 @@
 template <typename KeyType, typename ValueType> class FormatMap {
 public:
   typedef typename ValueType::SharedPointer ValueSP;
-  typedef std::map<KeyType, ValueSP> MapType;
+  // A ValueSP wrapper to track its lifetime and remove it from 'm_age' during
+  // its destruction.
+  class ValueTracker {
+  private:
+    typedef std::list<std::pair<const KeyType, ValueTracker> *> AgeType;
+    void Destroy() {
+      if (m_age_iterator != m_age.end())
+        m_age.erase(m_age_iterator);
+    }
+
+  public:
+    typedef ValueSP payload_type;
+    ValueTracker(payload_type payload, AgeType &age)
+        : m_payload(std::move(payload)), m_age(age), m_age_iterator(age.end()) {
+    }
+    void Initialize(typename AgeType::iterator age_iterator) {
+      Destroy();
+      lldbassert(&(*age_iterator)->second == this);
+      m_age_iterator = age_iterator;
+    }
+    ValueTracker(ValueTracker &&other)
+        : m_payload(std::move(other.m_payload)), m_age(other.m_age),
+          m_age_iterator(other.m_age_iterator) {
+      lldbassert(m_age_iterator == m_age.end());
+    }
+    ValueTracker &operator=(ValueTracker &&other) {
+      std::swap(m_payload, other.m_payload);
+      return *this;
+    }
+    ~ValueTracker() { Destroy(); }
+    const payload_type &payload() const { return m_payload; }
+
+  private:
+    payload_type m_payload;
+    AgeType &m_age;
+    typename AgeType::iterator m_age_iterator;
+
+    DISALLOW_COPY_AND_ASSIGN(ValueTracker);
+  };
+  typedef std::map<KeyType, ValueTracker> MapType;
   typedef typename MapType::iterator MapIterator;
+  typedef std::list<std::pair<const KeyType, ValueTracker> *> AgeType;
+  typedef typename AgeType::iterator AgeIterator;
   typedef std::function<bool(const KeyType &, const ValueSP &)> ForEachCallback;
 
   FormatMap(IFormatChangeListener *lst)
@@ -79,7 +120,17 @@
       entry->GetRevision() = 0;
 
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
-    m_map[std::move(name)] = entry;
+    MapIterator iter = m_map.find(name);
+    if (iter != m_map.end())
+      iter->second = ValueTracker(entry, m_age);
+    else {
+      auto inserted =
+          m_map.emplace(std::move(name), ValueTracker(entry, m_age));
+      assert(inserted.second);
+      iter = inserted.first;
+    }
+    m_age.push_front(&*iter);
+    iter->second.Initialize(m_age.begin());
     if (listener)
       listener->Changed();
   }
@@ -107,7 +158,7 @@
     MapIterator iter = m_map.find(name);
     if (iter == m_map.end())
       return false;
-    entry = iter->second;
+    entry = iter->second.payload();
     return true;
   }
 
@@ -117,7 +168,7 @@
       MapIterator pos, end = m_map.end();
       for (pos = m_map.begin(); pos != end; pos++) {
         const KeyType &type = pos->first;
-        if (!callback(type, pos->second))
+        if (!callback(type, pos->second.payload()))
           break;
       }
     }
@@ -135,10 +186,10 @@
       if (end == iter)
         return ValueSP();
     }
-    return iter->second;
+    return iter->second.payload();
   }
 
-  // If caller holds the mutex we could return a reference without copy ctor.
+  // If caller holds the mutex we could return a reference without the copying.
   KeyType GetKeyAtIndex(size_t index) {
     std::lock_guard<std::recursive_mutex> guard(m_map_mutex);
     MapIterator iter = m_map.begin();
@@ -153,10 +204,13 @@
   }
 
 protected:
+  AgeType m_age;
+  // 'm_map' must be destructed first as its element dtor accesses 'm_age'.
   MapType m_map;
   std::recursive_mutex m_map_mutex;
   IFormatChangeListener *listener;
 
+  const AgeType &age() const { return m_age; }
   MapType &map() { return m_map; }
 
   std::recursive_mutex &mutex() { return m_map_mutex; }
@@ -173,7 +227,9 @@
   typedef typename BackEndType::MapType MapType;
   typedef typename MapType::iterator MapIterator;
   typedef typename MapType::key_type MapKeyType;
-  typedef typename MapType::mapped_type MapValueType;
+  typedef typename MapType::mapped_type::payload_type MapValueType;
+  typedef typename BackEndType::AgeType AgeType;
+  typedef typename AgeType::const_iterator AgeConstIterator;
   typedef typename BackEndType::ForEachCallback ForEachCallback;
   typedef typename std::shared_ptr<FormattersContainer<KeyType, ValueType>>
       SharedPointer;
@@ -295,11 +351,11 @@
                 RegularExpression *dummy) {
     llvm::StringRef key_str = key.GetStringRef();
     std::lock_guard<std::recursive_mutex> guard(m_format_map.mutex());
-    MapIterator pos, end = m_format_map.map().end();
-    for (pos = m_format_map.map().begin(); pos != end; pos++) {
-      const RegularExpression &regex = pos->first;
+    AgeConstIterator pos, end = m_format_map.age().cend();
+    for (pos = m_format_map.age().cbegin(); pos != end; pos++) {
+      const RegularExpression &regex = (*pos)->first;
       if (regex.Execute(key_str)) {
-        value = pos->second;
+        value = (*pos)->second.payload();
         return true;
       }
     }
@@ -313,7 +369,7 @@
     for (pos = m_format_map.map().begin(); pos != end; pos++) {
       const RegularExpression &regex = pos->first;
       if (regex.GetText() == key.GetStringRef()) {
-        value = pos->second;
+        value = pos->second.payload();
         return true;
       }
     }