Index: clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.cpp
===================================================================
--- clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.cpp
+++ clang-tools-extra/clang-tidy/misc/IncludeCleanerCheck.cpp
@@ -106,7 +106,11 @@
   const SourceManager *SM = Result.SourceManager;
   const FileEntry *MainFile = SM->getFileEntryForID(SM->getMainFileID());
   llvm::DenseSet<const include_cleaner::Include *> Used;
-  std::vector<MissingIncludeInfo> Missing;
+  using SymRef = include_cleaner::SymbolReference;
+  auto Cmp = [](const SymRef &Left, const SymRef &Right) {
+    return Left.Target.name() < Right.Target.name();
+  };
+  std::map<SymRef, include_cleaner::Header, decltype(Cmp)> Missing{Cmp};
   llvm::SmallVector<Decl *> MainFileDecls;
   for (Decl *D : Result.Nodes.getNodeAs<TranslationUnitDecl>("top")->decls()) {
     if (!SM->isWrittenInMainFile(SM->getExpansionLoc(D->getLocation())))
@@ -135,7 +139,7 @@
              if (!Satisfied && !Providers.empty() &&
                  Ref.RT == include_cleaner::RefType::Explicit &&
                  !shouldIgnore(Providers.front()))
-               Missing.push_back({Ref, Providers.front()});
+               Missing.try_emplace(Ref, Providers.front());
            });
 
   std::vector<const include_cleaner::Include *> Unused;
@@ -181,9 +185,9 @@
 
   tooling::HeaderIncludes HeaderIncludes(getCurrentMainFile(), Code,
                                          FileStyle->IncludeStyle);
-  for (const auto &Inc : Missing) {
+  for (const auto &[SymRef, Header] : Missing) {
     std::string Spelling =
-        include_cleaner::spellHeader({Inc.Missing, *HS, MainFile});
+        include_cleaner::spellHeader({Header, *HS, MainFile});
     bool Angled = llvm::StringRef{Spelling}.starts_with("<");
     // We might suggest insertion of an existing include in edge cases, e.g.,
     // include is present in a PP-disabled region, or spelling of the header
@@ -192,9 +196,9 @@
     if (auto Replacement =
             HeaderIncludes.insert(llvm::StringRef{Spelling}.trim("\"<>"),
                                   Angled, tooling::IncludeDirective::Include))
-      diag(SM->getSpellingLoc(Inc.SymRef.RefLocation),
+      diag(SM->getSpellingLoc(SymRef.RefLocation),
            "no header providing \"%0\" is directly included")
-          << Inc.SymRef.Target.name()
+          << SymRef.Target.name()
           << FixItHint::CreateInsertion(
                  SM->getComposedLoc(SM->getMainFileID(),
                                     Replacement->getOffset()),
Index: clang-tools-extra/test/clang-tidy/checkers/misc/include-cleaner.cpp
===================================================================
--- clang-tools-extra/test/clang-tidy/checkers/misc/include-cleaner.cpp
+++ clang-tools-extra/test/clang-tidy/checkers/misc/include-cleaner.cpp
@@ -15,3 +15,5 @@
 // CHECK-MESSAGES: :[[@LINE-1]]:6: warning: no header providing "std::string" is directly included [misc-include-cleaner]
 int FooBarResult = foobar();
 // CHECK-MESSAGES: :[[@LINE-1]]:20: warning: no header providing "foobar" is directly included [misc-include-cleaner]
+int FooBarResult2 = foobar();
+// CHECK-MESSAGES-NOT: :[[@LINE-1]]: