diff --git a/src/gn/header_checker.cc b/src/gn/header_checker.cc
index 05c74d6..1ecc90a 100644
--- a/src/gn/header_checker.cc
+++ b/src/gn/header_checker.cc
@@ -5,6 +5,7 @@
 #include "gn/header_checker.h"
 
 #include <algorithm>
+#include <unordered_map>
 
 #include "base/containers/queue.h"
 #include "base/files/file_util.h"
@@ -561,7 +562,7 @@
   // a shortest dependency chain (in reverse order) from search_from to
   // search_for.
 
-  std::map<const Target*, ChainLink> breadcrumbs;
+  std::unordered_map<const Target*, ChainLink> breadcrumbs;
   base::queue<ChainLink> work_queue;
   work_queue.push(ChainLink(search_from, true));
 
@@ -585,7 +586,7 @@
 
     // Always consider public dependencies as possibilities.
     for (const auto& dep : target->public_deps()) {
-      if (breadcrumbs.insert(std::make_pair(dep.ptr, cur_link)).second)
+      if (breadcrumbs.emplace(dep.ptr, cur_link).second)
         work_queue.push(ChainLink(dep.ptr, true));
     }
 
@@ -596,7 +597,7 @@
       // public/private-ness.
       first_time = false;
       for (const auto& dep : target->private_deps()) {
-        if (breadcrumbs.insert(std::make_pair(dep.ptr, cur_link)).second)
+        if (breadcrumbs.emplace(dep.ptr, cur_link).second)
           work_queue.push(ChainLink(dep.ptr, false));
       }
     }