diff --git a/clang-tools-extra/clang-tidy/utils/IncludeSorter.h b/clang-tools-extra/clang-tidy/utils/IncludeSorter.h
--- a/clang-tools-extra/clang-tidy/utils/IncludeSorter.h
+++ b/clang-tools-extra/clang-tidy/utils/IncludeSorter.h
@@ -10,7 +10,6 @@
 #define LLVM_CLANG_TOOLS_EXTRA_CLANG_TIDY_INCLUDESORTER_H
 
 #include "../ClangTidyCheck.h"
-#include <string>
 
 namespace clang {
 namespace tidy {
@@ -61,7 +60,8 @@
   /// Mapping from file name to #include locations.
   llvm::StringMap<SourceRangeVector> IncludeLocations;
   /// Includes sorted into buckets.
-  SmallVector<std::string, 1> IncludeBucket[IK_InvalidInclude];
+  SmallVector<llvm::StringMapEntry<SourceRangeVector> *, 1>
+      IncludeBucket[IK_InvalidInclude];
 };
 
 } // namespace utils
diff --git a/clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp b/clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp
--- a/clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp
+++ b/clang-tools-extra/clang-tidy/utils/IncludeSorter.cpp
@@ -134,20 +134,21 @@
                                SourceLocation EndLocation) {
   int Offset = findNextLine(SourceMgr->getCharacterData(EndLocation));
 
+  auto &MapEntry = *IncludeLocations.try_emplace(FileName).first;
   // Record the relevant location information for this inclusion directive.
-  IncludeLocations[FileName].push_back(
+  MapEntry.getValue().push_back(
       SourceRange(HashLocation, EndLocation.getLocWithOffset(Offset)));
-  SourceLocations.push_back(IncludeLocations[FileName].back());
+  SourceLocations.push_back(MapEntry.getValue().back());
 
   // Stop if this inclusion is a duplicate.
-  if (IncludeLocations[FileName].size() > 1)
+  if (MapEntry.getValue().size() > 1)
     return;
 
   // Add the included file's name to the appropriate bucket.
   IncludeKinds Kind =
       determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
   if (Kind != IK_InvalidInclude)
-    IncludeBucket[Kind].push_back(FileName.str());
+    IncludeBucket[Kind].push_back(&MapEntry);
 }
 
 Optional<FixItHint> IncludeSorter::createIncludeInsertion(StringRef FileName,
@@ -174,9 +175,11 @@
       determineIncludeKind(CanonicalFile, FileName, IsAngled, Style);
 
   if (!IncludeBucket[IncludeKind].empty()) {
-    for (const std::string &IncludeEntry : IncludeBucket[IncludeKind]) {
+    for (auto *IncludeMapEntry : IncludeBucket[IncludeKind]) {
+      StringRef IncludeEntry = IncludeMapEntry->getKey();
       if (compareHeaders(FileName, IncludeEntry, Style) < 0) {
-        const auto &Location = IncludeLocations[IncludeEntry][0];
+
+        const auto &Location = IncludeMapEntry->getValue().front();
         return FixItHint::CreateInsertion(Location.getBegin(), IncludeStmt);
       }
       if (FileName == IncludeEntry) {
@@ -185,8 +188,8 @@
     }
     // FileName comes after all include entries in bucket, insert it after
     // last.
-    const std::string &LastInclude = IncludeBucket[IncludeKind].back();
-    SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
+    SourceRange LastIncludeLocation =
+        IncludeBucket[IncludeKind].back()->getValue().back();
     return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
                                       IncludeStmt);
   }
@@ -209,15 +212,15 @@
 
   if (NonEmptyKind < IncludeKind) {
     // Create a block after.
-    const std::string &LastInclude = IncludeBucket[NonEmptyKind].back();
-    SourceRange LastIncludeLocation = IncludeLocations[LastInclude].back();
+    SourceRange LastIncludeLocation =
+        IncludeBucket[NonEmptyKind].back()->getValue().back();
     IncludeStmt = '\n' + IncludeStmt;
     return FixItHint::CreateInsertion(LastIncludeLocation.getEnd(),
                                       IncludeStmt);
   }
   // Create a block before.
-  const std::string &FirstInclude = IncludeBucket[NonEmptyKind][0];
-  SourceRange FirstIncludeLocation = IncludeLocations[FirstInclude].back();
+  SourceRange FirstIncludeLocation =
+      IncludeBucket[NonEmptyKind][0]->getValue().back();
   IncludeStmt.append("\n");
   return FixItHint::CreateInsertion(FirstIncludeLocation.getBegin(),
                                     IncludeStmt);