--- a/xpcom/threads/HangAnnotations.cpp
+++ b/xpcom/threads/HangAnnotations.cpp
@@ -1,17 +1,17 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mozilla/HangAnnotations.h"
 
-#include <vector>
+#include <map>
 
 #include "MainThreadUtils.h"
 #include "mozilla/DebugOnly.h"
 #include "nsXULAppAPI.h"
 
 namespace mozilla {
 namespace HangMonitor {
 
@@ -30,22 +30,21 @@ public:
   void AddAnnotation(const nsAString& aName, const nsAString& aData) override;
   void AddAnnotation(const nsAString& aName, const nsACString& aData) override;
   void AddAnnotation(const nsAString& aName, const bool aData) override;
 
   size_t SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const override;
   bool IsEmpty() const override;
   UniquePtr<Enumerator> GetEnumerator() override;
 
-  typedef std::pair<nsString, nsString> AnnotationType;
-  typedef std::vector<AnnotationType> VectorType;
-  typedef VectorType::const_iterator IteratorType;
+  typedef std::map<nsString, nsString> MapType;
+  typedef MapType::const_iterator IteratorType;
 
 private:
-  VectorType  mAnnotations;
+  MapType  mAnnotations;
 };
 
 BrowserHangAnnotations::BrowserHangAnnotations()
 {
   MOZ_COUNT_CTOR(BrowserHangAnnotations);
 }
 
 BrowserHangAnnotations::~BrowserHangAnnotations()
@@ -53,74 +52,69 @@ BrowserHangAnnotations::~BrowserHangAnno
   MOZ_COUNT_DTOR(BrowserHangAnnotations);
 }
 
 void
 BrowserHangAnnotations::AddAnnotation(const nsAString& aName, const int32_t aData)
 {
   nsString dataString;
   dataString.AppendInt(aData);
-  AnnotationType annotation = std::make_pair(nsString(aName), dataString);
-  mAnnotations.push_back(annotation);
+  mAnnotations[nsString(aName)] = dataString;
 }
 
 void
 BrowserHangAnnotations::AddAnnotation(const nsAString& aName, const double aData)
 {
   nsString dataString;
   dataString.AppendFloat(aData);
-  AnnotationType annotation = std::make_pair(nsString(aName), dataString);
-  mAnnotations.push_back(annotation);
+  mAnnotations[nsString(aName)] = dataString;
 }
 
 void
 BrowserHangAnnotations::AddAnnotation(const nsAString& aName, const nsAString& aData)
 {
-  AnnotationType annotation = std::make_pair(nsString(aName), nsString(aData));
-  mAnnotations.push_back(annotation);
+  mAnnotations[nsString(aName)] = nsString(aData);
 }
 
 void
 BrowserHangAnnotations::AddAnnotation(const nsAString& aName, const nsACString& aData)
 {
   nsString dataString;
   AppendUTF8toUTF16(aData, dataString);
-  AnnotationType annotation = std::make_pair(nsString(aName), dataString);
-  mAnnotations.push_back(annotation);
+  mAnnotations[nsString(aName)] = dataString;
 }
 
 void
 BrowserHangAnnotations::AddAnnotation(const nsAString& aName, const bool aData)
 {
   nsString dataString;
   dataString += aData ? NS_LITERAL_STRING("true") : NS_LITERAL_STRING("false");
-  AnnotationType annotation = std::make_pair(nsString(aName), dataString);
-  mAnnotations.push_back(annotation);
+  mAnnotations[nsString(aName)] = dataString;
 }
 
 /**
  * This class itself does not use synchronization but it (and its parent object)
  * should be protected by mutual exclusion in some way. In Telemetry the chrome
  * hang data is protected via TelemetryImpl::mHangReportsMutex.
  */
 class ChromeHangAnnotationEnumerator : public HangAnnotations::Enumerator
 {
 public:
-  explicit ChromeHangAnnotationEnumerator(const BrowserHangAnnotations::VectorType& aAnnotations);
+  explicit ChromeHangAnnotationEnumerator(const BrowserHangAnnotations::MapType& aAnnotations);
   ~ChromeHangAnnotationEnumerator();
 
   virtual bool Next(nsAString& aOutName, nsAString& aOutValue);
 
 private:
   BrowserHangAnnotations::IteratorType mIterator;
   BrowserHangAnnotations::IteratorType mEnd;
 };
 
 ChromeHangAnnotationEnumerator::ChromeHangAnnotationEnumerator(
-                          const BrowserHangAnnotations::VectorType& aAnnotations)
+                          const BrowserHangAnnotations::MapType& aAnnotations)
   : mIterator(aAnnotations.begin())
   , mEnd(aAnnotations.end())
 {
   MOZ_COUNT_CTOR(ChromeHangAnnotationEnumerator);
 }
 
 ChromeHangAnnotationEnumerator::~ChromeHangAnnotationEnumerator()
 {
@@ -145,18 +139,17 @@ bool
 BrowserHangAnnotations::IsEmpty() const
 {
   return mAnnotations.empty();
 }
 
 size_t
 BrowserHangAnnotations::SizeOfIncludingThis(mozilla::MallocSizeOf aMallocSizeOf) const
 {
-  size_t result = sizeof(mAnnotations) +
-                  mAnnotations.capacity() * sizeof(AnnotationType);
+  size_t result = sizeof(mAnnotations);
   for (IteratorType i = mAnnotations.begin(), e = mAnnotations.end(); i != e;
        ++i) {
     result += i->first.SizeOfExcludingThisIfUnshared(aMallocSizeOf);
     result += i->second.SizeOfExcludingThisIfUnshared(aMallocSizeOf);
   }
 
   return result;
 }