diff --git a/runtime/base/allocator.h b/runtime/base/allocator.h
index 969f5b9..cea7046 100644
--- a/runtime/base/allocator.h
+++ b/runtime/base/allocator.h
@@ -158,7 +158,7 @@
 
 template<class Key, class T, AllocatorTag kTag, class Compare = std::less<Key>>
 using AllocationTrackingMultiMap = std::multimap<
-    Key, T, Compare, TrackingAllocator<std::pair<Key, T>, kTag>>;
+    Key, T, Compare, TrackingAllocator<std::pair<const Key, T>, kTag>>;
 
 template<class Key, AllocatorTag kTag, class Compare = std::less<Key>>
 using AllocationTrackingSet = std::set<Key, Compare, TrackingAllocator<Key, kTag>>;
diff --git a/runtime/safe_map.h b/runtime/safe_map.h
index 4e62dda..a8b48ee 100644
--- a/runtime/safe_map.h
+++ b/runtime/safe_map.h
@@ -146,7 +146,7 @@
 
 template<class Key, class T, AllocatorTag kTag, class Compare = std::less<Key>>
 class AllocationTrackingSafeMap : public SafeMap<
-    Key, T, Compare, TrackingAllocator<std::pair<Key, T>, kTag>> {
+    Key, T, Compare, TrackingAllocator<std::pair<const Key, T>, kTag>> {
 };
 
 }  // namespace art