class AllOne
{
private:
class Node
{
public:
string str;
int num;
Node(string s, int n)
{
str = s;
num = n;
}
friend bool operator<(const Node &a, const Node &b)
{
if (a.num != b.num)
return a.num < b.num;
else
return a.str < b.str;
}
friend bool operator>(const Node &a, const Node &b)
{
if (a.num != b.num)
return a.num > b.num;
else
return a.str > b.str;
}
friend bool operator==(const Node &a, const Node &b)
{
return a.num == b.num && a.str == b.str;
}
};
unordered_map<string, int> ump;
set<Node> st;
unordered_map<string, set<Node>::iterator> stump;
public:
AllOne() {
}
void inc(string key)
{
if (ump.find(key) == ump.end())
ump.insert(pair(key, 1));
else
{
ump[key]++;
st.erase(stump[key]);
stump.erase(key);
}
auto iter = st.insert(Node(key, ump[key]));
stump[key] = iter.first;
}
void dec(string key)
{
if (ump.find(key) != ump.end())
{
if (ump[key] == 1)
{
ump.erase(key);
st.erase(stump[key]);
stump.erase(key);
}
else
{
ump[key]--;
st.erase(stump[key]);
stump.erase(key);
auto iter = st.insert(Node(key, ump[key]));
stump[key] = iter.first;
}
}
}
string getMaxKey()
{
if (ump.empty())
return "";
return (--st.end())->str;
}
string getMinKey()
{
if (ump.empty())
return "";
return st.begin()->str;
}
};
四、运行结果