'How to best design MaxStack in C++ with reverse iterators?
I have done some C++ but haven't used much iterators. I am trying to implement a solution for MaxStack in leetcode using iterators. https://leetcode.com/problems/max-stack/
Following was the initial implementation I came up with, which I believe is intuitive. Then, I then learnt push_back() and erase() functions of vector<list<int>::iterator> don't work with reverse iterators (like rbegin()). As a workaround, I got this working by just inserting elements at the front of the list (as opposed to pushing back as in provided implementation) so that all iterators I'll work with are forward iterators. That said, I'd like to know what's the most elegant / intuitive way to do this with reverse iterators? I learnt converting reverse iterators to forward iterators is a messy affair.
class MaxStack {
public:
list<int> dll;
map<int, vector<list<int>::iterator>> mp;
MaxStack() {
}
void push(int x) {
dll.push_back(x);
mp[x].push_back(dll.rbegin());
}
int pop() {
int num = dll.back();
auto itr = mp[num].back();
mp[num].pop_back();
if (mp[num].empty()) {
mp.erase(num);
}
dll.pop_back();
return num;
}
int top() {
return dll.back();
}
int peekMax() {
auto itr = mp.rbegin();
return (*itr).first;
}
int popMax() {
auto itr = mp.rbegin();
int num = (*itr).first;
auto& vec = (*itr).second;
auto delItr = vec.back();
vec.pop_back();
if (vec.empty()) {
mp.erase(num);
}
dll.erase(delItr);
return num;
}
};
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|
