diff --git a/libbacktrace/BacktraceMap.cpp b/libbacktrace/BacktraceMap.cpp
index 0e31495..0f1ae11 100644
--- a/libbacktrace/BacktraceMap.cpp
+++ b/libbacktrace/BacktraceMap.cpp
@@ -40,9 +40,10 @@
 
 void BacktraceMap::FillIn(uintptr_t addr, backtrace_map_t* map) {
   ScopedBacktraceMapIteratorLock lock(this);
-  for (BacktraceMap::const_iterator it = begin(); it != end(); ++it) {
-    if (addr >= it->start && addr < it->end) {
-      *map = *it;
+  for (auto it = begin(); it != end(); ++it) {
+    const backtrace_map_t* entry = *it;
+    if (addr >= entry->start && addr < entry->end) {
+      *map = *entry;
       return;
     }
   }
diff --git a/libbacktrace/UnwindStackMap.cpp b/libbacktrace/UnwindStackMap.cpp
index 9ac0a0b..836a774 100644
--- a/libbacktrace/UnwindStackMap.cpp
+++ b/libbacktrace/UnwindStackMap.cpp
@@ -71,8 +71,19 @@
   if (map_info == nullptr) {
     return;
   }
-  unwindstack::Elf* elf = map_info->GetElf(process_memory_, true);
-  map->load_bias = elf->GetLoadBias();
+  map->load_bias = map_info->GetLoadBias(process_memory_);
+}
+
+uint64_t UnwindStackMap::GetLoadBias(size_t index) {
+  if (index >= stack_maps_->Total()) {
+    return 0;
+  }
+
+  unwindstack::MapInfo* map_info = stack_maps_->Get(index);
+  if (map_info == nullptr) {
+    return 0;
+  }
+  return map_info->GetLoadBias(process_memory_);
 }
 
 std::string UnwindStackMap::GetFunctionName(uintptr_t pc, uintptr_t* offset) {
diff --git a/libbacktrace/UnwindStackMap.h b/libbacktrace/UnwindStackMap.h
index bc432e7..2f63655 100644
--- a/libbacktrace/UnwindStackMap.h
+++ b/libbacktrace/UnwindStackMap.h
@@ -42,6 +42,8 @@
   const std::shared_ptr<unwindstack::Memory>& process_memory() { return process_memory_; }
 
  protected:
+  uint64_t GetLoadBias(size_t index) override;
+
   std::unique_ptr<unwindstack::Maps> stack_maps_;
   std::shared_ptr<unwindstack::Memory> process_memory_;
 };
diff --git a/libbacktrace/backtrace_offline_test.cpp b/libbacktrace/backtrace_offline_test.cpp
index 0a1f33d..0935660 100644
--- a/libbacktrace/backtrace_offline_test.cpp
+++ b/libbacktrace/backtrace_offline_test.cpp
@@ -171,10 +171,12 @@
   testdata += android::base::StringPrintf("pid: %d tid: %d\n", getpid(), arg.tid);
   // 2. Dump maps
   for (auto it = map->begin(); it != map->end(); ++it) {
-    testdata += android::base::StringPrintf(
-        "map: start: %" PRIxPTR " end: %" PRIxPTR " offset: %" PRIxPTR " load_bias: %" PRIxPTR
-        " flags: %d name: %s\n",
-        it->start, it->end, it->offset, it->load_bias, it->flags, it->name.c_str());
+    const backtrace_map_t* entry = *it;
+    testdata +=
+        android::base::StringPrintf("map: start: %" PRIxPTR " end: %" PRIxPTR " offset: %" PRIxPTR
+                                    " load_bias: %" PRIxPTR " flags: %d name: %s\n",
+                                    entry->start, entry->end, entry->offset, entry->load_bias,
+                                    entry->flags, entry->name.c_str());
   }
   // 3. Dump registers
   testdata += android::base::StringPrintf("registers: %zu ", sizeof(arg.unw_context));
diff --git a/libbacktrace/backtrace_test.cpp b/libbacktrace/backtrace_test.cpp
index 9911e74..890ab3f 100644
--- a/libbacktrace/backtrace_test.cpp
+++ b/libbacktrace/backtrace_test.cpp
@@ -857,6 +857,34 @@
 
 static bool map_sort(map_test_t i, map_test_t j) { return i.start < j.start; }
 
+static std::string GetTestMapsAsString(const std::vector<map_test_t>& maps) {
+  if (maps.size() == 0) {
+    return "No test map entries\n";
+  }
+  std::string map_txt;
+  for (auto map : maps) {
+    map_txt += android::base::StringPrintf("%" PRIxPTR "-%" PRIxPTR "\n", map.start, map.end);
+  }
+  return map_txt;
+}
+
+static std::string GetMapsAsString(BacktraceMap* maps) {
+  if (maps->size() == 0) {
+    return "No map entries\n";
+  }
+  std::string map_txt;
+  for (const backtrace_map_t* map : *maps) {
+    map_txt += android::base::StringPrintf(
+        "%" PRIxPTR "-%" PRIxPTR " flags: 0x%x offset: 0x%" PRIxPTR " load_bias: 0x%" PRIxPTR,
+        map->start, map->end, map->flags, map->offset, map->load_bias);
+    if (!map->name.empty()) {
+      map_txt += ' ' + map->name;
+    }
+    map_txt += '\n';
+  }
+  return map_txt;
+}
+
 static void VerifyMap(pid_t pid) {
   char buffer[4096];
   snprintf(buffer, sizeof(buffer), "/proc/%d/maps", pid);
@@ -875,12 +903,20 @@
   std::unique_ptr<BacktraceMap> map(BacktraceMap::Create(pid));
 
   // Basic test that verifies that the map is in the expected order.
-  ScopedBacktraceMapIteratorLock lock(map.get());
-  std::vector<map_test_t>::const_iterator test_it = test_maps.begin();
-  for (BacktraceMap::const_iterator it = map->begin(); it != map->end(); ++it) {
-    ASSERT_TRUE(test_it != test_maps.end());
-    ASSERT_EQ(test_it->start, it->start);
-    ASSERT_EQ(test_it->end, it->end);
+  auto test_it = test_maps.begin();
+  for (auto it = map->begin(); it != map->end(); ++it) {
+    ASSERT_TRUE(test_it != test_maps.end()) << "Mismatch in number of maps, expected test maps:\n"
+                                            << GetTestMapsAsString(test_maps) << "Actual maps:\n"
+                                            << GetMapsAsString(map.get());
+    ASSERT_EQ(test_it->start, (*it)->start) << "Mismatch in map data, expected test maps:\n"
+                                            << GetTestMapsAsString(test_maps) << "Actual maps:\n"
+                                            << GetMapsAsString(map.get());
+    ASSERT_EQ(test_it->end, (*it)->end) << "Mismatch maps in map data, expected test maps:\n"
+                                        << GetTestMapsAsString(test_maps) << "Actual maps:\n"
+                                        << GetMapsAsString(map.get());
+    // Make sure the load bias get set to a value.
+    ASSERT_NE(static_cast<uint64_t>(-1), (*it)->load_bias) << "Found uninitialized load_bias\n"
+                                                           << GetMapsAsString(map.get());
     ++test_it;
   }
   ASSERT_TRUE(test_it == test_maps.end());
diff --git a/libbacktrace/include/backtrace/BacktraceMap.h b/libbacktrace/include/backtrace/BacktraceMap.h
index d078392..4ae68dd 100644
--- a/libbacktrace/include/backtrace/BacktraceMap.h
+++ b/libbacktrace/include/backtrace/BacktraceMap.h
@@ -30,6 +30,7 @@
 #endif
 
 #include <deque>
+#include <iterator>
 #include <string>
 #include <vector>
 
@@ -61,6 +62,49 @@
 
   virtual ~BacktraceMap();
 
+  class iterator : public std::iterator<std::bidirectional_iterator_tag, backtrace_map_t*> {
+   public:
+    iterator(BacktraceMap* map, size_t index) : map_(map), index_(index) {}
+
+    iterator& operator++() {
+      index_++;
+      return *this;
+    }
+    iterator& operator++(int increment) {
+      index_ += increment;
+      return *this;
+    }
+    iterator& operator--() {
+      index_--;
+      return *this;
+    }
+    iterator& operator--(int decrement) {
+      index_ -= decrement;
+      return *this;
+    }
+
+    bool operator==(const iterator& rhs) { return this->index_ == rhs.index_; }
+    bool operator!=(const iterator& rhs) { return this->index_ != rhs.index_; }
+
+    const backtrace_map_t* operator*() {
+      if (index_ >= map_->size()) {
+        return nullptr;
+      }
+      backtrace_map_t* map = &map_->maps_[index_];
+      if (map->load_bias == static_cast<uintptr_t>(-1)) {
+        map->load_bias = map_->GetLoadBias(index_);
+      }
+      return map;
+    }
+
+   private:
+    BacktraceMap* map_ = nullptr;
+    size_t index_ = 0;
+  };
+
+  iterator begin() { return iterator(this, 0); }
+  iterator end() { return iterator(this, maps_.size()); }
+
   // Fill in the map data structure for the given address.
   virtual void FillIn(uintptr_t addr, backtrace_map_t* map);
 
@@ -89,14 +133,6 @@
   virtual void LockIterator() {}
   virtual void UnlockIterator() {}
 
-  typedef std::deque<backtrace_map_t>::iterator iterator;
-  iterator begin() { return maps_.begin(); }
-  iterator end() { return maps_.end(); }
-
-  typedef std::deque<backtrace_map_t>::const_iterator const_iterator;
-  const_iterator begin() const { return maps_.begin(); }
-  const_iterator end() const { return maps_.end(); }
-
   size_t size() const { return maps_.size(); }
 
   virtual bool Build();
@@ -114,6 +150,8 @@
  protected:
   BacktraceMap(pid_t pid);
 
+  virtual uint64_t GetLoadBias(size_t /* index */) { return 0; }
+
   virtual bool ParseLine(const char* line, backtrace_map_t* map);
 
   pid_t pid_;