diff --git a/libs/binder/LazyServiceRegistrar.cpp b/libs/binder/LazyServiceRegistrar.cpp
index f064bd7..dc9482c 100644
--- a/libs/binder/LazyServiceRegistrar.cpp
+++ b/libs/binder/LazyServiceRegistrar.cpp
@@ -53,13 +53,14 @@
 
     struct Service {
         sp<IBinder> service;
+        std::string name;
         bool allowIsolated;
         int dumpFlags;
     };
     /**
-     * Map of registered names and services
+     * Number of services that have been registered.
      */
-    std::map<std::string, Service> mRegisteredServices;
+    std::vector<Service> mRegisteredServices;
 };
 
 bool ClientCounterCallback::registerService(const sp<IBinder>& service, const std::string& name,
@@ -67,24 +68,20 @@
     auto manager = interface_cast<AidlServiceManager>(
                     ProcessState::self()->getContextObject(nullptr));
 
-    bool reRegister = mRegisteredServices.count(name) > 0;
-    std::string regStr = (reRegister) ? "Re-registering" : "Registering";
-    ALOGI("%s service %s", regStr.c_str(), name.c_str());
+    ALOGI("Registering service %s", name.c_str());
 
     if (!manager->addService(name.c_str(), service, allowIsolated, dumpFlags).isOk()) {
         ALOGE("Failed to register service %s", name.c_str());
         return false;
     }
 
-    if (!manager->registerClientCallback(name, service, this).isOk()) {
-        ALOGE("Failed to add client callback for service %s", name.c_str());
-        return false;
+    if (!manager->registerClientCallback(name, service, this).isOk())
+    {
+      ALOGE("Failed to add client callback for service %s", name.c_str());
+      return false;
     }
 
-    if (!reRegister) {
-        // Only add this when a service is added for the first time, as it is not removed
-        mRegisteredServices[name] = {service, allowIsolated, dumpFlags};
-    }
+    mRegisteredServices.push_back({service, name, allowIsolated, dumpFlags});
 
     return true;
 }
@@ -122,11 +119,10 @@
     for (; unRegisterIt != mRegisteredServices.end(); ++unRegisterIt) {
         auto& entry = (*unRegisterIt);
 
-        bool success = manager->tryUnregisterService(entry.first, entry.second.service).isOk();
-
+        bool success = manager->tryUnregisterService(entry.name, entry.service).isOk();
 
         if (!success) {
-            ALOGI("Failed to unregister service %s", entry.first.c_str());
+            ALOGI("Failed to unregister service %s", entry.name.c_str());
             break;
         }
     }
@@ -141,8 +137,7 @@
         auto& entry = (*reRegisterIt);
 
         // re-register entry
-        if (!registerService(entry.second.service, entry.first, entry.second.allowIsolated,
-                             entry.second.dumpFlags)) {
+        if (!registerService(entry.service, entry.name, entry.allowIsolated, entry.dumpFlags)) {
             // Must restart. Otherwise, clients will never be able to get a hold of this service.
             ALOGE("Bad state: could not re-register services");
         }