4
\$\begingroup\$

The tricky thing was keeping copies of list iterators in a tree map and managing both together. I'm not handling invalid input cases (like popping an empty stack) in this code. I am following Google C++ style guide. Any advice and feedback would be appreciated!

// A Max Stack data structure which supports the push/pop LIFO operations
// of a stack and allows removal of the largest number
class MaxStack {
    // Doubly linked list serving as a stack
    list<int> dll_;
    // Tree map mapping user added values to iterator references in the
    // doubly linked list
    map<int, vector<list<int>::iterator>, std::greater<int>> bst_;

public:
    // Push element into the data structures
    // - Push to the end of doubly linked list
    // - Push the iterator from the doubly linked list to the vector
    //   corresponding to the key of the input number
    void Push(int x) {
        dll_.push_back(x);
        if (bst_.find(x) == bst_.end()) {
            bst_[x] = vector<list<int>::iterator>();
        }
        bst_[x].push_back(std::prev(dll_.end()));
    }
    
    // Pop from the top of the stack and remove the corresponding iterator
    // from the map
    int Pop() {
        int val = *(dll_.rbegin());
        auto to_delete = *(bst_[val].rbegin());
        dll_.erase(to_delete);
        bst_[val].pop_back();
        // Remove the key from the map if nothing is left
        if (bst_[val].empty()) {
            bst_.erase(val);
        }
        return val;
    }
    
    int Top() {
        return *(dll_.rbegin());
    }
    
    int PeekMax() {
        return bst_.begin()->first;
    }
    
    // Remove one instance of the largest element in the tree map
    // and the corresponding node in the doubly linked list.
    // If there are multiple largest elements, remove the most recently
    // added one.
    int PopMax() {
        int val = bst_.begin()->first;
        auto to_delete = *(bst_[val].rbegin());
        dll_.erase(to_delete);
        bst_[val].pop_back();
        // Remove the key from the map if nothing is left
        if (bst_[val].empty()) {
            bst_.erase(val);
        }
        return val;
    }
};
```
\$\endgroup\$
3
  • \$\begingroup\$ Any particular reason you need this data structure? \$\endgroup\$ Commented Dec 8, 2022 at 9:01
  • \$\begingroup\$ Useful in situations where there are 2 types of consumers: Consumers who prefer reading the most recent messages first and consumers who prefer reading the most important item first. This could apply in a "trending stories" processing system. \$\endgroup\$ Commented Dec 8, 2022 at 10:37
  • \$\begingroup\$ but wouldn't it usually be the case that the different type of consumers are not supposed to interfere with each other? At most mark an element as "read" so that the other consumer type would have the option to skip if desired. Performance on average should be faster. \$\endgroup\$ Commented Dec 8, 2022 at 13:15

2 Answers 2

Reset to default
2
\$\begingroup\$

Don't use the using namespace std; directive. It should be std::list, not just list.

Don't tend to name your variables for their types because types denote how we store data, not what data we store.

We can simplify Push method.

void Push(int x) {
    dll_.push_back(x);        
    bst_[x].push_back(std::prev(dll_.end()));
}

Method map::operator[] inserts empty vector for us if x does not exist.

And to make the intent clearer,

void Push(int x) {
    auto it = dll_.insert(std::end(dll_), x);
    bst_[x].push_back(it);
}

To get the last vector element, use vector::back().

auto to_delete = bst_[val].back();

bst_[val] used frequently in Pop. I would replace it with an alias to make things look more concise

int Pop() {
    int val = *(dll_.rbegin());
    auto& entries = bst_[val];
    dll_.erase(entries.back());
    entries.pop_back();
    if (entries.empty())
        bst_.erase(val);
    return val;
}

We can optimize Pop* methods a bit.

int Pop() {
    int val = *(dll_.rbegin());
    dll_.pop_back(); // to_delete always points to the last element
    if (auto& entries = bst_[val]; entries.size() == 1) // shortcut for unique elements
        bst_.erase(val);
    else
        entries.pop_back();
    return val;
}

int PopMax() {
    auto it = std::begin(bst_);
    int val = it->first;
    auto& entries = it->second;
    dll_.erase(entries.back());
    if (entries.size() == 1)
        bst_.erase(it); // reuse iterator
    else
        entries.pop_back();
    return val;
}

We can optimize memory usage by replacing the vector of iterators with corresponding std::stack. Stack is an adapter for std::deque which acquires memory sparingly in compare to vector.

\$\endgroup\$
2
\$\begingroup\$

In addition to panik's answer:

Choice of containers

std::list and std::map can work here, but especially if you are storing small values like ints and iterators, these add a lot of overhead. For a stack you could use a std::deque, just like std::stack does, and instead of using a std::map to implement a queue sorted on priority, you could use a std::vector and use std::push_heap() and std::pop_heap, just like std::priority_queue does.

Note that having the priority queue be a map from int to a vector of iterators is not necessary. You could store just a std::set of std::list::iterators, and provide a custom comparator function so it sorts the iterators based on the values they point to. That will make popping from the stack a bit harder, but it would save some memory.

Make it a template

What if you want to store doubles instead of ints? Or maybe std::strings? It would be nice to make your class a template so it works for any type of data. It's quite easy:

template<typename T>
class MaxSatck {
    std::list<T> dll_;
    std::map<T, std::vector<std::list<T>::iterator>, std::greater<T>> bst_;
    …
};

Once you do this, you should start paying attention to how you pass parameters to functions and how you return values; while for ints it doesn't matter, for larger types you might want to pass using r-value references so values can be moved. For PeekMax() you could return a const reference.

Make it look like an STL container

The standard library has lots of containers, and they all have a very similar interface. That means that if you have learned to use one container, it's easy to use other containers. It also makes it easy to change the code from using one container to another, without having to change all the lines of code touching that container. There are also lots of algorithms that can work on those containers.

If you make your container look and act as similar as possible to the STL, then it will make your container easier to use for other programmers, makes it easy to use as a drop-in replacement for existing containers, and it might even be possible to run some of the algorithms on your container.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks a lot! The only thing I couldn't understand how a priority queue could take the place of the tree map I've used because this problem requires finding and sometimes removing elements that are in the middle when pop is called. If I use a priority queue (implemented as a vector), searching and removing in the middle would take O(n) time instead of O(logn) \$\endgroup\$ Commented Dec 9, 2022 at 4:05
  • 1
    \$\begingroup\$ Some people tested and found that priority_queue is not necessarily faster than map and can be even slower. \$\endgroup\$ Commented Dec 9, 2022 at 5:25
  • \$\begingroup\$ It does depend on the access patterns, how big your stack is typically going to be, and whether you want to optimize for speed or memory usage. Indeed, you cannot use std::stack and std::priority_queue directly in your code, but my goal was to show you could use the techniques these container adapters use to implement your stack and queue. \$\endgroup\$ Commented Dec 9, 2022 at 6:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.