diff --git a/src/gn/inherited_libraries.cc b/src/gn/inherited_libraries.cc
index 37e0b97..977e97d 100644
--- a/src/gn/inherited_libraries.cc
+++ b/src/gn/inherited_libraries.cc
@@ -10,49 +10,23 @@
 
 InheritedLibraries::~InheritedLibraries() = default;
 
-std::vector<const Target*> InheritedLibraries::GetOrdered() const {
-  std::vector<const Target*> result;
-  result.resize(map_.size());
-
-  // The indices in the map should be from 0 to the number of items in the
-  // map, so insert directly into the result (with some sanity checks).
-  for (const auto& pair : map_) {
-    size_t index = pair.second.index;
-    DCHECK(index < result.size());
-    DCHECK(!result[index]);
-    result[index] = pair.first;
-  }
-
-  return result;
-}
-
 std::vector<std::pair<const Target*, bool>>
 InheritedLibraries::GetOrderedAndPublicFlag() const {
   std::vector<std::pair<const Target*, bool>> result;
-  result.resize(map_.size());
-
-  for (const auto& pair : map_) {
-    size_t index = pair.second.index;
-    DCHECK(index < result.size());
-    DCHECK(!result[index].first);
-    result[index] = std::make_pair(pair.first, pair.second.is_public);
-  }
-
+  result.reserve(targets_.size());
+  for (size_t i = 0; i < targets_.size(); ++i)
+    result.emplace_back(targets_[i], public_flags_[i]);
   return result;
 }
 
 void InheritedLibraries::Append(const Target* target, bool is_public) {
   // Try to insert a new node.
-  auto insert_result =
-      map_.insert(std::make_pair(target, Node(map_.size(), is_public)));
-
-  if (!insert_result.second) {
-    // Element already present, insert failed and insert_result indicates the
-    // old one. The old one may need to have its public flag updated.
-    if (is_public) {
-      Node& existing_node = insert_result.first->second;
-      existing_node.is_public = true;
-    }
+  auto ret = targets_.PushBackWithIndex(target);
+  if (ret.first) {
+    public_flags_.push_back(is_public);
+  } else if (is_public) {
+    // Target already present, if |is_public|, set its flag.
+    public_flags_[ret.second] = true;
   }
 }
 
@@ -60,15 +34,19 @@
                                          bool is_public) {
   // Append all items in order, mark them public only if the're already public
   // and we're adding them publicly.
-  for (const auto& cur : other.GetOrderedAndPublicFlag())
-    Append(cur.first, is_public && cur.second);
+  for (size_t i = 0; i < other.targets_.size(); ++i) {
+    Append(other.targets_[i], is_public && other.public_flags_[i]);
+  }
 }
 
 void InheritedLibraries::AppendPublicSharedLibraries(
     const InheritedLibraries& other,
     bool is_public) {
-  for (const auto& cur : other.GetOrderedAndPublicFlag()) {
-    if (cur.first->output_type() == Target::SHARED_LIBRARY && cur.second)
-      Append(cur.first, is_public);
+  for (size_t i = 0; i < other.targets_.size(); ++i) {
+    const Target* target = other.targets_[i];
+    if (target->output_type() == Target::SHARED_LIBRARY &&
+        other.public_flags_[i]) {
+      Append(target, is_public);
+    }
   }
 }
diff --git a/src/gn/inherited_libraries.h b/src/gn/inherited_libraries.h
index 758e3c9..7a3fc25 100644
--- a/src/gn/inherited_libraries.h
+++ b/src/gn/inherited_libraries.h
@@ -7,10 +7,11 @@
 
 #include <stddef.h>
 
-#include <map>
 #include <utility>
 #include <vector>
 
+#include "gn/unique_vector.h"
+
 class Target;
 
 // Represents an ordered uniquified set of all shared/static libraries for
@@ -30,7 +31,7 @@
 
   // Returns the list of dependencies in order, optionally with the flag
   // indicating whether the dependency is public.
-  std::vector<const Target*> GetOrdered() const;
+  std::vector<const Target*> GetOrdered() const { return targets_.vector(); }
   std::vector<std::pair<const Target*, bool>> GetOrderedAndPublicFlag() const;
 
   // Adds a single dependency to the end of the list. See note on adding above.
@@ -52,16 +53,8 @@
                                    bool is_public);
 
  private:
-  struct Node {
-    Node() : index(static_cast<size_t>(-1)), is_public(false) {}
-    Node(size_t i, bool p) : index(i), is_public(p) {}
-
-    size_t index;
-    bool is_public;
-  };
-
-  using LibraryMap = std::map<const Target*, Node>;
-  LibraryMap map_;
+  UniqueVector<const Target*> targets_;
+  std::vector<bool> public_flags_;
 
   InheritedLibraries(const InheritedLibraries&) = delete;
   InheritedLibraries& operator=(const InheritedLibraries&) = delete;