diff --git a/libs/input/KeyCharacterMap.cpp b/libs/input/KeyCharacterMap.cpp
index 7a379f5..d571917 100644
--- a/libs/input/KeyCharacterMap.cpp
+++ b/libs/input/KeyCharacterMap.cpp
@@ -43,7 +43,6 @@
 // Enables debug output for mapping.
 #define DEBUG_MAPPING 0
 
-
 namespace android {
 
 static const char* WHITESPACE = " \t\r";
@@ -86,75 +85,7 @@
 
 // --- KeyCharacterMap ---
 
-KeyCharacterMap::KeyCharacterMap(const std::string& filename)
-      : mType(KeyboardType::UNKNOWN), mLoadFileName(filename) {}
-
-KeyCharacterMap::KeyCharacterMap(const KeyCharacterMap& other)
-      : mType(other.mType),
-        mLoadFileName(other.mLoadFileName),
-        mLayoutOverlayApplied(other.mLayoutOverlayApplied),
-        mKeysByScanCode(other.mKeysByScanCode),
-        mKeysByUsageCode(other.mKeysByUsageCode) {
-    for (size_t i = 0; i < other.mKeys.size(); i++) {
-        mKeys.add(other.mKeys.keyAt(i), new Key(*other.mKeys.valueAt(i)));
-    }
-}
-
-KeyCharacterMap::~KeyCharacterMap() {
-    clear();
-}
-
-bool KeyCharacterMap::operator==(const KeyCharacterMap& other) const {
-    if (mType != other.mType) {
-        return false;
-    }
-    if (mLoadFileName != other.mLoadFileName) {
-        return false;
-    }
-    if (mLayoutOverlayApplied != other.mLayoutOverlayApplied) {
-        return false;
-    }
-    if (mKeys.size() != other.mKeys.size() ||
-        mKeysByScanCode.size() != other.mKeysByScanCode.size() ||
-        mKeysByUsageCode.size() != other.mKeysByUsageCode.size()) {
-        return false;
-    }
-
-    for (size_t i = 0; i < mKeys.size(); i++) {
-        if (mKeys.keyAt(i) != other.mKeys.keyAt(i)) {
-            return false;
-        }
-        const Key* key = mKeys.valueAt(i);
-        const Key* otherKey = other.mKeys.valueAt(i);
-        if (key->label != otherKey->label || key->number != otherKey->number) {
-            return false;
-        }
-    }
-
-    for (size_t i = 0; i < mKeysByScanCode.size(); i++) {
-        if (mKeysByScanCode.keyAt(i) != other.mKeysByScanCode.keyAt(i)) {
-            return false;
-        }
-        if (mKeysByScanCode.valueAt(i) != other.mKeysByScanCode.valueAt(i)) {
-            return false;
-        }
-    }
-
-    for (size_t i = 0; i < mKeysByUsageCode.size(); i++) {
-        if (mKeysByUsageCode.keyAt(i) != other.mKeysByUsageCode.keyAt(i)) {
-            return false;
-        }
-        if (mKeysByUsageCode.valueAt(i) != other.mKeysByUsageCode.valueAt(i)) {
-            return false;
-        }
-    }
-
-    return true;
-}
-
-bool KeyCharacterMap::operator!=(const KeyCharacterMap& other) const {
-    return !(*this == other);
-}
+KeyCharacterMap::KeyCharacterMap(const std::string& filename) : mLoadFileName(filename) {}
 
 base::Result<std::shared_ptr<KeyCharacterMap>> KeyCharacterMap::load(const std::string& filename,
                                                                      Format format) {
@@ -220,10 +151,6 @@
 void KeyCharacterMap::clear() {
     mKeysByScanCode.clear();
     mKeysByUsageCode.clear();
-    for (size_t i = 0; i < mKeys.size(); i++) {
-        Key* key = mKeys.editValueAt(i);
-        delete key;
-    }
     mKeys.clear();
     mLayoutOverlayApplied = false;
     mType = KeyboardType::UNKNOWN;
@@ -246,30 +173,27 @@
     if (mLayoutOverlayApplied) {
         reloadBaseFromFile();
     }
-    for (size_t i = 0; i < overlay.mKeys.size(); i++) {
-        int32_t keyCode = overlay.mKeys.keyAt(i);
-        Key* key = overlay.mKeys.valueAt(i);
-        ssize_t oldIndex = mKeys.indexOfKey(keyCode);
-        if (oldIndex >= 0) {
-            delete mKeys.valueAt(oldIndex);
-            mKeys.editValueAt(oldIndex) = new Key(*key);
-        } else {
-            mKeys.add(keyCode, new Key(*key));
-        }
+    for (const auto& [keyCode, key] : overlay.mKeys) {
+        mKeys.insert_or_assign(keyCode, key);
     }
 
-    for (size_t i = 0; i < overlay.mKeysByScanCode.size(); i++) {
-        mKeysByScanCode.replaceValueFor(overlay.mKeysByScanCode.keyAt(i),
-                                        overlay.mKeysByScanCode.valueAt(i));
+    for (const auto& [fromScanCode, toAndroidKeyCode] : overlay.mKeysByScanCode) {
+        mKeysByScanCode.insert_or_assign(fromScanCode, toAndroidKeyCode);
     }
 
-    for (size_t i = 0; i < overlay.mKeysByUsageCode.size(); i++) {
-        mKeysByUsageCode.replaceValueFor(overlay.mKeysByUsageCode.keyAt(i),
-                                         overlay.mKeysByUsageCode.valueAt(i));
+    for (const auto& [fromHidUsageCode, toAndroidKeyCode] : overlay.mKeysByUsageCode) {
+        mKeysByUsageCode.insert_or_assign(fromHidUsageCode, toAndroidKeyCode);
     }
     mLayoutOverlayApplied = true;
 }
 
+void KeyCharacterMap::clearLayoutOverlay() {
+    if (mLayoutOverlayApplied) {
+        reloadBaseFromFile();
+        mLayoutOverlayApplied = false;
+    }
+}
+
 KeyCharacterMap::KeyboardType KeyCharacterMap::getKeyboardType() const {
     return mType;
 }
@@ -280,8 +204,8 @@
 
 char16_t KeyCharacterMap::getDisplayLabel(int32_t keyCode) const {
     char16_t result = 0;
-    const Key* key;
-    if (getKey(keyCode, &key)) {
+    const Key* key = getKey(keyCode);
+    if (key != nullptr) {
         result = key->label;
     }
 #if DEBUG_MAPPING
@@ -292,8 +216,8 @@
 
 char16_t KeyCharacterMap::getNumber(int32_t keyCode) const {
     char16_t result = 0;
-    const Key* key;
-    if (getKey(keyCode, &key)) {
+    const Key* key = getKey(keyCode);
+    if (key != nullptr) {
         result = key->number;
     }
 #if DEBUG_MAPPING
@@ -304,9 +228,8 @@
 
 char16_t KeyCharacterMap::getCharacter(int32_t keyCode, int32_t metaState) const {
     char16_t result = 0;
-    const Key* key;
-    const Behavior* behavior;
-    if (getKeyBehavior(keyCode, metaState, &key, &behavior)) {
+    const Behavior* behavior = getKeyBehavior(keyCode, metaState);
+    if (behavior != nullptr) {
         result = behavior->character;
     }
 #if DEBUG_MAPPING
@@ -321,9 +244,8 @@
     outFallbackAction->metaState = 0;
 
     bool result = false;
-    const Key* key;
-    const Behavior* behavior;
-    if (getKeyBehavior(keyCode, metaState, &key, &behavior)) {
+    const Behavior* behavior = getKeyBehavior(keyCode, metaState);
+    if (behavior != nullptr) {
         if (behavior->fallbackKeyCode) {
             outFallbackAction->keyCode = behavior->fallbackKeyCode;
             outFallbackAction->metaState = metaState & ~behavior->metaState;
@@ -342,30 +264,26 @@
 char16_t KeyCharacterMap::getMatch(int32_t keyCode, const char16_t* chars, size_t numChars,
         int32_t metaState) const {
     char16_t result = 0;
-    const Key* key;
-    if (getKey(keyCode, &key)) {
+    const Key* key = getKey(keyCode);
+    if (key != nullptr) {
         // Try to find the most general behavior that maps to this character.
         // For example, the base key behavior will usually be last in the list.
         // However, if we find a perfect meta state match for one behavior then use that one.
-        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
-            if (behavior->character) {
+        for (const Behavior& behavior : key->behaviors) {
+            if (behavior.character) {
                 for (size_t i = 0; i < numChars; i++) {
-                    if (behavior->character == chars[i]) {
-                        result = behavior->character;
-                        if ((behavior->metaState & metaState) == behavior->metaState) {
-                            goto ExactMatch;
+                    if (behavior.character == chars[i]) {
+                        result = behavior.character;
+                        if ((behavior.metaState & metaState) == behavior.metaState) {
+                            // Found exact match!
+                            return result;
                         }
                         break;
                     }
                 }
             }
         }
-    ExactMatch: ;
     }
-#if DEBUG_MAPPING
-    ALOGD("getMatch: keyCode=%d, chars=[%s], metaState=0x%08x ~ Result %d.", keyCode,
-          toString(chars, numChars).c_str(), metaState, result);
-#endif
     return result;
 }
 
@@ -402,11 +320,26 @@
     return true;
 }
 
+void KeyCharacterMap::addKeyRemapping(int32_t fromKeyCode, int32_t toKeyCode) {
+    if (fromKeyCode == toKeyCode) {
+        mKeyRemapping.erase(fromKeyCode);
+#if DEBUG_MAPPING
+        ALOGD("addKeyRemapping: Cleared remapping forKeyCode=%d ~ Result Successful.", fromKeyCode);
+#endif
+        return;
+    }
+    mKeyRemapping.insert_or_assign(fromKeyCode, toKeyCode);
+#if DEBUG_MAPPING
+    ALOGD("addKeyRemapping: fromKeyCode=%d, toKeyCode=%d ~ Result Successful.", fromKeyCode,
+          toKeyCode);
+#endif
+}
+
 status_t KeyCharacterMap::mapKey(int32_t scanCode, int32_t usageCode, int32_t* outKeyCode) const {
     if (usageCode) {
-        ssize_t index = mKeysByUsageCode.indexOfKey(usageCode);
-        if (index >= 0) {
-            *outKeyCode = mKeysByUsageCode.valueAt(index);
+        const auto it = mKeysByUsageCode.find(usageCode);
+        if (it != mKeysByUsageCode.end()) {
+            *outKeyCode = it->second;
 #if DEBUG_MAPPING
             ALOGD("mapKey: scanCode=%d, usageCode=0x%08x ~ Result keyCode=%d.",
                     scanCode, usageCode, *outKeyCode);
@@ -415,9 +348,9 @@
         }
     }
     if (scanCode) {
-        ssize_t index = mKeysByScanCode.indexOfKey(scanCode);
-        if (index >= 0) {
-            *outKeyCode = mKeysByScanCode.valueAt(index);
+        const auto it = mKeysByScanCode.find(scanCode);
+        if (it != mKeysByScanCode.end()) {
+            *outKeyCode = it->second;
 #if DEBUG_MAPPING
             ALOGD("mapKey: scanCode=%d, usageCode=0x%08x ~ Result keyCode=%d.",
                     scanCode, usageCode, *outKeyCode);
@@ -433,72 +366,80 @@
     return NAME_NOT_FOUND;
 }
 
-void KeyCharacterMap::tryRemapKey(int32_t keyCode, int32_t metaState,
-                                  int32_t *outKeyCode, int32_t *outMetaState) const {
-    *outKeyCode = keyCode;
-    *outMetaState = metaState;
+int32_t KeyCharacterMap::applyKeyRemapping(int32_t fromKeyCode) const {
+    int32_t toKeyCode = fromKeyCode;
 
-    const Key* key;
-    const Behavior* behavior;
-    if (getKeyBehavior(keyCode, metaState, &key, &behavior)) {
+    const auto it = mKeyRemapping.find(fromKeyCode);
+    if (it != mKeyRemapping.end()) {
+        toKeyCode = it->second;
+    }
+#if DEBUG_MAPPING
+    ALOGD("applyKeyRemapping: keyCode=%d ~ replacement keyCode=%d.", fromKeyCode, toKeyCode);
+#endif
+    return toKeyCode;
+}
+
+std::pair<int32_t, int32_t> KeyCharacterMap::applyKeyBehavior(int32_t fromKeyCode,
+                                                              int32_t fromMetaState) const {
+    int32_t toKeyCode = fromKeyCode;
+    int32_t toMetaState = fromMetaState;
+
+    const Behavior* behavior = getKeyBehavior(fromKeyCode, fromMetaState);
+    if (behavior != nullptr) {
         if (behavior->replacementKeyCode) {
-            *outKeyCode = behavior->replacementKeyCode;
-            int32_t newMetaState = metaState & ~behavior->metaState;
+            toKeyCode = behavior->replacementKeyCode;
+            toMetaState = fromMetaState & ~behavior->metaState;
             // Reset dependent meta states.
             if (behavior->metaState & AMETA_ALT_ON) {
-                newMetaState &= ~(AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON);
+                toMetaState &= ~(AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON);
             }
             if (behavior->metaState & (AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON)) {
-                newMetaState &= ~AMETA_ALT_ON;
+                toMetaState &= ~AMETA_ALT_ON;
             }
             if (behavior->metaState & AMETA_CTRL_ON) {
-                newMetaState &= ~(AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON);
+                toMetaState &= ~(AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON);
             }
             if (behavior->metaState & (AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON)) {
-                newMetaState &= ~AMETA_CTRL_ON;
+                toMetaState &= ~AMETA_CTRL_ON;
             }
             if (behavior->metaState & AMETA_SHIFT_ON) {
-                newMetaState &= ~(AMETA_SHIFT_LEFT_ON | AMETA_SHIFT_RIGHT_ON);
+                toMetaState &= ~(AMETA_SHIFT_LEFT_ON | AMETA_SHIFT_RIGHT_ON);
             }
             if (behavior->metaState & (AMETA_SHIFT_LEFT_ON | AMETA_SHIFT_RIGHT_ON)) {
-                newMetaState &= ~AMETA_SHIFT_ON;
+                toMetaState &= ~AMETA_SHIFT_ON;
             }
             // ... and put universal bits back if needed
-            *outMetaState = normalizeMetaState(newMetaState);
+            toMetaState = normalizeMetaState(toMetaState);
         }
     }
 
 #if DEBUG_MAPPING
-    ALOGD("tryRemapKey: keyCode=%d, metaState=0x%08x ~ "
-            "replacement keyCode=%d, replacement metaState=0x%08x.",
-            keyCode, metaState, *outKeyCode, *outMetaState);
+    ALOGD("applyKeyBehavior: keyCode=%d, metaState=0x%08x ~ "
+          "replacement keyCode=%d, replacement metaState=0x%08x.",
+          fromKeyCode, fromMetaState, toKeyCode, toMetaState);
 #endif
+    return std::make_pair(toKeyCode, toMetaState);
 }
 
-bool KeyCharacterMap::getKey(int32_t keyCode, const Key** outKey) const {
-    ssize_t index = mKeys.indexOfKey(keyCode);
-    if (index >= 0) {
-        *outKey = mKeys.valueAt(index);
-        return true;
+const KeyCharacterMap::Key* KeyCharacterMap::getKey(int32_t keyCode) const {
+    auto it = mKeys.find(keyCode);
+    if (it != mKeys.end()) {
+        return &it->second;
     }
-    return false;
+    return nullptr;
 }
 
-bool KeyCharacterMap::getKeyBehavior(int32_t keyCode, int32_t metaState,
-        const Key** outKey, const Behavior** outBehavior) const {
-    const Key* key;
-    if (getKey(keyCode, &key)) {
-        const Behavior* behavior = key->firstBehavior;
-        while (behavior) {
-            if (matchesMetaState(metaState, behavior->metaState)) {
-                *outKey = key;
-                *outBehavior = behavior;
-                return true;
+const KeyCharacterMap::Behavior* KeyCharacterMap::getKeyBehavior(int32_t keyCode,
+                                                                 int32_t metaState) const {
+    const Key* key = getKey(keyCode);
+    if (key != nullptr) {
+        for (const Behavior& behavior : key->behaviors) {
+            if (matchesMetaState(metaState, behavior.metaState)) {
+                return &behavior;
             }
-            behavior = behavior->next;
         }
     }
-    return false;
+    return nullptr;
 }
 
 bool KeyCharacterMap::matchesMetaState(int32_t eventMetaState, int32_t behaviorMetaState) {
@@ -537,19 +478,17 @@
         return false;
     }
 
-    for (size_t i = 0; i < mKeys.size(); i++) {
-        const Key* key = mKeys.valueAt(i);
-
+    for (const auto& [keyCode, key] : mKeys) {
         // Try to find the most general behavior that maps to this character.
         // For example, the base key behavior will usually be last in the list.
         const Behavior* found = nullptr;
-        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
-            if (behavior->character == ch) {
-                found = behavior;
+        for (const Behavior& behavior : key.behaviors) {
+            if (behavior.character == ch) {
+                found = &behavior;
             }
         }
-        if (found) {
-            *outKeyCode = mKeys.keyAt(i);
+        if (found != nullptr) {
+            *outKeyCode = keyCode;
             *outMetaState = found->metaState;
             return true;
         }
@@ -701,12 +640,7 @@
             return nullptr;
         }
 
-        Key* key = new Key();
-        key->label = label;
-        key->number = number;
-        map->mKeys.add(keyCode, key);
-
-        Behavior* lastBehavior = nullptr;
+        Key key{.label = label, .number = number};
         while (parcel->readInt32()) {
             int32_t metaState = parcel->readInt32();
             char16_t character = parcel->readInt32();
@@ -716,23 +650,31 @@
                 return nullptr;
             }
 
-            Behavior* behavior = new Behavior();
-            behavior->metaState = metaState;
-            behavior->character = character;
-            behavior->fallbackKeyCode = fallbackKeyCode;
-            behavior->replacementKeyCode = replacementKeyCode;
-            if (lastBehavior) {
-                lastBehavior->next = behavior;
-            } else {
-                key->firstBehavior = behavior;
-            }
-            lastBehavior = behavior;
+            key.behaviors.push_back({
+                    .metaState = metaState,
+                    .character = character,
+                    .fallbackKeyCode = fallbackKeyCode,
+                    .replacementKeyCode = replacementKeyCode,
+            });
         }
+        map->mKeys.emplace(keyCode, std::move(key));
 
         if (parcel->errorCheck()) {
             return nullptr;
         }
     }
+    size_t numKeyRemapping = parcel->readInt32();
+    if (parcel->errorCheck()) {
+        return nullptr;
+    }
+    for (size_t i = 0; i < numKeyRemapping; i++) {
+        int32_t key = parcel->readInt32();
+        int32_t value = parcel->readInt32();
+        map->mKeyRemapping.insert_or_assign(key, value);
+        if (parcel->errorCheck()) {
+            return nullptr;
+        }
+    }
     size_t numKeysByScanCode = parcel->readInt32();
     if (parcel->errorCheck()) {
         return nullptr;
@@ -740,7 +682,7 @@
     for (size_t i = 0; i < numKeysByScanCode; i++) {
         int32_t key = parcel->readInt32();
         int32_t value = parcel->readInt32();
-        map->mKeysByScanCode.add(key, value);
+        map->mKeysByScanCode.insert_or_assign(key, value);
         if (parcel->errorCheck()) {
             return nullptr;
         }
@@ -752,7 +694,7 @@
     for (size_t i = 0; i < numKeysByUsageCode; i++) {
         int32_t key = parcel->readInt32();
         int32_t value = parcel->readInt32();
-        map->mKeysByUsageCode.add(key, value);
+        map->mKeysByUsageCode.insert_or_assign(key, value);
         if (parcel->errorCheck()) {
             return nullptr;
         }
@@ -771,81 +713,46 @@
 
     size_t numKeys = mKeys.size();
     parcel->writeInt32(numKeys);
-    for (size_t i = 0; i < numKeys; i++) {
-        int32_t keyCode = mKeys.keyAt(i);
-        const Key* key = mKeys.valueAt(i);
+    for (const auto& [keyCode, key] : mKeys) {
         parcel->writeInt32(keyCode);
-        parcel->writeInt32(key->label);
-        parcel->writeInt32(key->number);
-        for (const Behavior* behavior = key->firstBehavior; behavior != nullptr;
-                behavior = behavior->next) {
+        parcel->writeInt32(key.label);
+        parcel->writeInt32(key.number);
+        for (const Behavior& behavior : key.behaviors) {
             parcel->writeInt32(1);
-            parcel->writeInt32(behavior->metaState);
-            parcel->writeInt32(behavior->character);
-            parcel->writeInt32(behavior->fallbackKeyCode);
-            parcel->writeInt32(behavior->replacementKeyCode);
+            parcel->writeInt32(behavior.metaState);
+            parcel->writeInt32(behavior.character);
+            parcel->writeInt32(behavior.fallbackKeyCode);
+            parcel->writeInt32(behavior.replacementKeyCode);
         }
         parcel->writeInt32(0);
     }
+    size_t numKeyRemapping = mKeyRemapping.size();
+    parcel->writeInt32(numKeyRemapping);
+    for (auto const& [fromAndroidKeyCode, toAndroidKeyCode] : mKeyRemapping) {
+        parcel->writeInt32(fromAndroidKeyCode);
+        parcel->writeInt32(toAndroidKeyCode);
+    }
     size_t numKeysByScanCode = mKeysByScanCode.size();
     parcel->writeInt32(numKeysByScanCode);
-    for (size_t i = 0; i < numKeysByScanCode; i++) {
-        parcel->writeInt32(mKeysByScanCode.keyAt(i));
-        parcel->writeInt32(mKeysByScanCode.valueAt(i));
+    for (auto const& [fromScanCode, toAndroidKeyCode] : mKeysByScanCode) {
+        parcel->writeInt32(fromScanCode);
+        parcel->writeInt32(toAndroidKeyCode);
     }
     size_t numKeysByUsageCode = mKeysByUsageCode.size();
     parcel->writeInt32(numKeysByUsageCode);
-    for (size_t i = 0; i < numKeysByUsageCode; i++) {
-        parcel->writeInt32(mKeysByUsageCode.keyAt(i));
-        parcel->writeInt32(mKeysByUsageCode.valueAt(i));
+    for (auto const& [fromUsageCode, toAndroidKeyCode] : mKeysByUsageCode) {
+        parcel->writeInt32(fromUsageCode);
+        parcel->writeInt32(toAndroidKeyCode);
     }
 }
 #endif // __linux__
 
-// --- KeyCharacterMap::Key ---
-
-KeyCharacterMap::Key::Key() :
-        label(0), number(0), firstBehavior(nullptr) {
-}
-
-KeyCharacterMap::Key::Key(const Key& other) :
-        label(other.label), number(other.number),
-        firstBehavior(other.firstBehavior ? new Behavior(*other.firstBehavior) : nullptr) {
-}
-
-KeyCharacterMap::Key::~Key() {
-    Behavior* behavior = firstBehavior;
-    while (behavior) {
-        Behavior* next = behavior->next;
-        delete behavior;
-        behavior = next;
-    }
-}
-
-
-// --- KeyCharacterMap::Behavior ---
-
-KeyCharacterMap::Behavior::Behavior() :
-        next(nullptr), metaState(0), character(0), fallbackKeyCode(0), replacementKeyCode(0) {
-}
-
-KeyCharacterMap::Behavior::Behavior(const Behavior& other) :
-        next(other.next ? new Behavior(*other.next) : nullptr),
-        metaState(other.metaState), character(other.character),
-        fallbackKeyCode(other.fallbackKeyCode),
-        replacementKeyCode(other.replacementKeyCode) {
-}
-
-
 // --- KeyCharacterMap::Parser ---
 
 KeyCharacterMap::Parser::Parser(KeyCharacterMap* map, Tokenizer* tokenizer, Format format) :
         mMap(map), mTokenizer(tokenizer), mFormat(format), mState(STATE_TOP) {
 }
 
-KeyCharacterMap::Parser::~Parser() {
-}
-
 status_t KeyCharacterMap::Parser::parse() {
     while (!mTokenizer->isEof()) {
 #if DEBUG_PARSER
@@ -888,9 +795,9 @@
 
             mTokenizer->skipDelimiters(WHITESPACE);
             if (!mTokenizer->isEol() && mTokenizer->peekChar() != '#') {
-                ALOGE("%s: Expected end of line or trailing comment, got '%s'.",
-                      mTokenizer->getLocation().c_str(), mTokenizer->peekRemainderOfLine().c_str());
-                return BAD_VALUE;
+            ALOGE("%s: Expected end of line or trailing comment, got '%s'.",
+                  mTokenizer->getLocation().c_str(), mTokenizer->peekRemainderOfLine().c_str());
+            return BAD_VALUE;
             }
         }
 
@@ -990,17 +897,17 @@
               mapUsage ? "usage" : "scan code", codeToken.c_str());
         return BAD_VALUE;
     }
-    KeyedVector<int32_t, int32_t>& map =
-            mapUsage ? mMap->mKeysByUsageCode : mMap->mKeysByScanCode;
-    if (map.indexOfKey(code) >= 0) {
+    std::map<int32_t, int32_t>& map = mapUsage ? mMap->mKeysByUsageCode : mMap->mKeysByScanCode;
+    const auto it = map.find(code);
+    if (it != map.end()) {
         ALOGE("%s: Duplicate entry for key %s '%s'.", mTokenizer->getLocation().c_str(),
-              mapUsage ? "usage" : "scan code", codeToken.c_str());
+                mapUsage ? "usage" : "scan code", codeToken.c_str());
         return BAD_VALUE;
     }
 
     mTokenizer->skipDelimiters(WHITESPACE);
     String8 keyCodeToken = mTokenizer->nextToken(WHITESPACE);
-    int32_t keyCode = InputEventLookup::getKeyCodeByLabel(keyCodeToken.c_str());
+    std::optional<int> keyCode = InputEventLookup::getKeyCodeByLabel(keyCodeToken.c_str());
     if (!keyCode) {
         ALOGE("%s: Expected key code label, got '%s'.", mTokenizer->getLocation().c_str(),
               keyCodeToken.c_str());
@@ -1011,21 +918,21 @@
     ALOGD("Parsed map key %s: code=%d, keyCode=%d.",
             mapUsage ? "usage" : "scan code", code, keyCode);
 #endif
-    map.add(code, keyCode);
+    map.insert_or_assign(code, *keyCode);
     return NO_ERROR;
 }
 
 status_t KeyCharacterMap::Parser::parseKey() {
     String8 keyCodeToken = mTokenizer->nextToken(WHITESPACE);
-    int32_t keyCode = InputEventLookup::getKeyCodeByLabel(keyCodeToken.c_str());
+    std::optional<int> keyCode = InputEventLookup::getKeyCodeByLabel(keyCodeToken.c_str());
     if (!keyCode) {
         ALOGE("%s: Expected key code label, got '%s'.", mTokenizer->getLocation().c_str(),
               keyCodeToken.c_str());
         return BAD_VALUE;
     }
-    if (mMap->mKeys.indexOfKey(keyCode) >= 0) {
+    if (mMap->mKeys.find(*keyCode) != mMap->mKeys.end()) {
         ALOGE("%s: Duplicate entry for key code '%s'.", mTokenizer->getLocation().c_str(),
-              keyCodeToken.c_str());
+                keyCodeToken.c_str());
         return BAD_VALUE;
     }
 
@@ -1037,31 +944,29 @@
         return BAD_VALUE;
     }
 
-#if DEBUG_PARSER
-    ALOGD("Parsed beginning of key: keyCode=%d.", keyCode);
-#endif
-    mKeyCode = keyCode;
-    mMap->mKeys.add(keyCode, new Key());
+    ALOGD_IF(DEBUG_PARSER, "Parsed beginning of key: keyCode=%d.", *keyCode);
+    mKeyCode = *keyCode;
+    mMap->mKeys.emplace(*keyCode, Key{});
     mState = STATE_KEY;
     return NO_ERROR;
 }
 
 status_t KeyCharacterMap::Parser::parseKeyProperty() {
-    Key* key = mMap->mKeys.valueFor(mKeyCode);
+    Key& key = mMap->mKeys[mKeyCode];
     String8 token = mTokenizer->nextToken(WHITESPACE_OR_PROPERTY_DELIMITER);
     if (token == "}") {
         mState = STATE_TOP;
         return finishKey(key);
     }
 
-    Vector<Property> properties;
+    std::vector<Property> properties;
 
     // Parse all comma-delimited property names up to the first colon.
     for (;;) {
         if (token == "label") {
-            properties.add(Property(PROPERTY_LABEL));
+            properties.emplace_back(PROPERTY_LABEL);
         } else if (token == "number") {
-            properties.add(Property(PROPERTY_NUMBER));
+            properties.emplace_back(PROPERTY_NUMBER);
         } else {
             int32_t metaState;
             status_t status = parseModifier(token.c_str(), &metaState);
@@ -1070,7 +975,7 @@
                       mTokenizer->getLocation().c_str(), token.c_str());
                 return status;
             }
-            properties.add(Property(PROPERTY_META, metaState));
+            properties.emplace_back(PROPERTY_META, metaState);
         }
 
         mTokenizer->skipDelimiters(WHITESPACE);
@@ -1135,7 +1040,7 @@
             } else if (token == "fallback") {
                 mTokenizer->skipDelimiters(WHITESPACE);
                 token = mTokenizer->nextToken(WHITESPACE);
-                int32_t keyCode = InputEventLookup::getKeyCodeByLabel(token.c_str());
+                std::optional<int> keyCode = InputEventLookup::getKeyCodeByLabel(token.c_str());
                 if (!keyCode) {
                     ALOGE("%s: Invalid key code label for fallback behavior, got '%s'.",
                           mTokenizer->getLocation().c_str(), token.c_str());
@@ -1146,12 +1051,12 @@
                           mTokenizer->getLocation().c_str());
                     return BAD_VALUE;
                 }
-                behavior.fallbackKeyCode = keyCode;
+                behavior.fallbackKeyCode = *keyCode;
                 haveFallback = true;
             } else if (token == "replace") {
                 mTokenizer->skipDelimiters(WHITESPACE);
                 token = mTokenizer->nextToken(WHITESPACE);
-                int32_t keyCode = InputEventLookup::getKeyCodeByLabel(token.c_str());
+                std::optional<int> keyCode = InputEventLookup::getKeyCodeByLabel(token.c_str());
                 if (!keyCode) {
                     ALOGE("%s: Invalid key code label for replace, got '%s'.",
                           mTokenizer->getLocation().c_str(), token.c_str());
@@ -1167,7 +1072,7 @@
                           mTokenizer->getLocation().c_str());
                     return BAD_VALUE;
                 }
-                behavior.replacementKeyCode = keyCode;
+                behavior.replacementKeyCode = *keyCode;
                 haveReplacement = true;
 
             } else {
@@ -1180,47 +1085,44 @@
     } while (!mTokenizer->isEol() && mTokenizer->peekChar() != '#');
 
     // Add the behavior.
-    for (size_t i = 0; i < properties.size(); i++) {
-        const Property& property = properties.itemAt(i);
+    for (const Property& property : properties) {
         switch (property.property) {
         case PROPERTY_LABEL:
-            if (key->label) {
-                ALOGE("%s: Duplicate label for key.", mTokenizer->getLocation().c_str());
-                return BAD_VALUE;
-            }
-            key->label = behavior.character;
+                if (key.label) {
+                    ALOGE("%s: Duplicate label for key.", mTokenizer->getLocation().c_str());
+                    return BAD_VALUE;
+                }
+                key.label = behavior.character;
 #if DEBUG_PARSER
-            ALOGD("Parsed key label: keyCode=%d, label=%d.", mKeyCode, key->label);
+                ALOGD("Parsed key label: keyCode=%d, label=%d.", mKeyCode, key.label);
 #endif
             break;
         case PROPERTY_NUMBER:
-            if (key->number) {
-                ALOGE("%s: Duplicate number for key.", mTokenizer->getLocation().c_str());
-                return BAD_VALUE;
+            if (key.number) {
+                    ALOGE("%s: Duplicate number for key.", mTokenizer->getLocation().c_str());
+                    return BAD_VALUE;
             }
-            key->number = behavior.character;
+            key.number = behavior.character;
 #if DEBUG_PARSER
-            ALOGD("Parsed key number: keyCode=%d, number=%d.", mKeyCode, key->number);
+            ALOGD("Parsed key number: keyCode=%d, number=%d.", mKeyCode, key.number);
 #endif
             break;
         case PROPERTY_META: {
-            for (Behavior* b = key->firstBehavior; b; b = b->next) {
-                if (b->metaState == property.metaState) {
+            for (const Behavior& b : key.behaviors) {
+                    if (b.metaState == property.metaState) {
                     ALOGE("%s: Duplicate key behavior for modifier.",
                           mTokenizer->getLocation().c_str());
                     return BAD_VALUE;
-                }
+                    }
             }
-            Behavior* newBehavior = new Behavior(behavior);
-            newBehavior->metaState = property.metaState;
-            newBehavior->next = key->firstBehavior;
-            key->firstBehavior = newBehavior;
-#if DEBUG_PARSER
-            ALOGD("Parsed key meta: keyCode=%d, meta=0x%x, char=%d, fallback=%d replace=%d.",
-                    mKeyCode,
-                    newBehavior->metaState, newBehavior->character,
-                    newBehavior->fallbackKeyCode, newBehavior->replacementKeyCode);
-#endif
+            Behavior newBehavior = behavior;
+            newBehavior.metaState = property.metaState;
+            key.behaviors.push_front(newBehavior);
+            ALOGD_IF(DEBUG_PARSER,
+                     "Parsed key meta: keyCode=%d, meta=0x%x, char=%d, fallback=%d replace=%d.",
+                     mKeyCode, key.behaviors.front().metaState, key.behaviors.front().character,
+                     key.behaviors.front().fallbackKeyCode,
+                     key.behaviors.front().replacementKeyCode);
             break;
         }
         }
@@ -1228,13 +1130,13 @@
     return NO_ERROR;
 }
 
-status_t KeyCharacterMap::Parser::finishKey(Key* key) {
+status_t KeyCharacterMap::Parser::finishKey(Key& key) {
     // Fill in default number property.
-    if (!key->number) {
+    if (!key.number) {
         char16_t digit = 0;
         char16_t symbol = 0;
-        for (Behavior* b = key->firstBehavior; b; b = b->next) {
-            char16_t ch = b->character;
+        for (const Behavior& b : key.behaviors) {
+            char16_t ch = b.character;
             if (ch) {
                 if (ch >= '0' && ch <= '9') {
                     digit = ch;
@@ -1245,7 +1147,7 @@
                 }
             }
         }
-        key->number = digit ? digit : symbol;
+        key.number = digit ? digit : symbol;
     }
     return NO_ERROR;
 }