All o'One Data Structure

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <list>

struct Node
{
   int frequency;
   std::unordered_set<std::string> keys;
};

class AllOne
{
public:
   AllOne()
   {
   }

   void inc(std::string key)
   {
      // two cases:
      // Case A1: key is not in our data structure
      if (_stringToNode.count(key) == 0)
      {
         // we need to insert it to the first node.
         // two cases:
         // Case A2: node with freq = 1 is not present:
         if (_listOfRecords.empty() || _listOfRecords.front().frequency > 1)
            _listOfRecords.push_front({.frequency = 1, .keys = {key}});
         // Case B2: node with freq = 1 is present:

         else
            _listOfRecords.front().keys.insert(key);

         // update map that maps this key to the iterator
         _stringToNode[key] = _listOfRecords.begin();
      }
      // Case B1: key is in our data structure
      else
      {
         // obtain the key:
         auto it = _stringToNode[key];
         int currentFrequency = it->frequency;
         // add to the new list one next to it
         auto itNext = std::next(it);
         // Insertion two cases:
         // Case A3: the next node does not exist yet
         if (itNext == _listOfRecords.end())
         {
            _listOfRecords.push_back({.frequency = currentFrequency + 1, .keys = {key}});
            itNext = std::next(it); // update the itNext
         }

         // Case B3: next node exists
         else
            itNext->keys.insert(key);

         // remove from current unordered_set the key
         it->keys.erase(key);
         // update the unordered_map about where the key is right now
         _stringToNode[key] = itNext;
         // Removal two cases:
         // Case A4: it's not the only key in the unordered_set:
         if (it->keys.size() == 0)
         {
            _listOfRecords.erase(it);
         }
         // Case B4: it's the only key in the unordered_set: do nothing
      }
   }

   void dec(std::string key)
   {
      // Assumption - we know that it is guaranteed that key exists in the data structure before the decrement!
      // first obtain the node that contains unordered_set that contains key:
      auto it = _stringToNode[key];
      auto itPrev = (it != _listOfRecords.begin()) ? std::prev(it) : _listOfRecords.end();

      int currentFrequency = it->frequency;

      // case A1: need to remove that key
      if (currentFrequency == 1)
      {
         _stringToNode.erase(key);
      }
      // case B1: no need to remove that node but move it one node left
      else
      {
         // Case A3: Need to add new node before current Node
         if (itPrev == _listOfRecords.end() ||
             itPrev->frequency != currentFrequency - 1)
         {
            _listOfRecords.insert(it, {.frequency = currentFrequency - 1, .keys = {key}});
            itPrev = std::prev(it); // update itPrev
         }
         // Case B3: No need to add new node BEFORE current node
         else
         {
            itPrev->keys.insert(key);
         }
         // on both cases, update the unordered_map to keep track of where is the key at
         _stringToNode[key] = itPrev;
      }
      // removal from old node:

      it->keys.erase(key);
      // Case A2: need to remove that node
      if (it->keys.size() == 0)
         _listOfRecords.erase(it);

      // Case B2: no need to remove that node
      // do nothing
   }

   std::string getMaxKey()
   {
      if (_listOfRecords.size() == 0)
         return "";
      return *(_listOfRecords.rbegin()->keys.begin());
   }

   std::string getMinKey()
   {
      if (_listOfRecords.size() == 0)
         return "";
      return *(_listOfRecords.begin()->keys.begin());
   }

private:
   std::unordered_map<std::string, std::list<Node>::iterator> _stringToNode;
   std::list<Node> _listOfRecords;
};

int main()
{
   AllOne allOne;
   allOne.inc("a");
   allOne.inc("b");
   allOne.inc("b");
   allOne.inc("b");
   allOne.inc("b");

   allOne.dec("b");
   allOne.dec("b");
   std::cout << "allOne.getMaxKey() = " << allOne.getMaxKey() << std::endl; // return "b"
   std::cout << "allOne.getMinKey() = " << allOne.getMinKey() << std::endl; // return "a"
   allOne.dec("b");
   allOne.dec("b");
   std::cout << "allOne.getMaxKey() = " << allOne.getMaxKey() << std::endl; // return "b"
   std::cout << "allOne.getMinKey() = " << allOne.getMinKey() << std::endl; // return "a"
}