diff --git a/clang/include/clang/Tooling/Inclusions/HeaderIncludes.h b/clang/include/clang/Tooling/Inclusions/HeaderIncludes.h
--- a/clang/include/clang/Tooling/Inclusions/HeaderIncludes.h
+++ b/clang/include/clang/Tooling/Inclusions/HeaderIncludes.h
@@ -14,6 +14,7 @@
 #include "clang/Tooling/Inclusions/IncludeStyle.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
+#include <list>
 #include <unordered_map>
 
 namespace clang {
@@ -97,7 +98,8 @@
   // Map from include name (quotation trimmed) to a list of existing includes
   // (in case there are more than one) with the name in the current file. <x>
   // and "x" will be treated as the same header when deleting #includes.
-  llvm::StringMap<llvm::SmallVector<Include, 1>> ExistingIncludes;
+  // std::list is used for pointers stability (see IncludesByPriority)
+  llvm::StringMap<std::list<Include>> ExistingIncludes;
 
   /// Map from priorities of #include categories to all #includes in the same
   /// category. This is used to find #includes of the same category when
diff --git a/clang/unittests/Tooling/HeaderIncludesTest.cpp b/clang/unittests/Tooling/HeaderIncludesTest.cpp
--- a/clang/unittests/Tooling/HeaderIncludesTest.cpp
+++ b/clang/unittests/Tooling/HeaderIncludesTest.cpp
@@ -51,6 +51,15 @@
   EXPECT_EQ(Expected, insert(Code, "\"a.h\""));
 }
 
+TEST_F(HeaderIncludesTest, RepeatedIncludes) {
+  std::string Code;
+  for (int i = 0; i < 100; ++i) {
+    Code += "#include \"a.h\"\n";
+  }
+  std::string Expected = Code + "#include \"a2.h\"\n";
+  EXPECT_EQ(Expected, insert(Code, "\"a2.h\""));
+}
+
 TEST_F(HeaderIncludesTest, NoExistingIncludeWithDefine) {
   std::string Code = "#ifndef A_H\n"
                      "#define A_H\n"