Extending std::unordered_set<> for use with std::stack<>

Question

My problem: I want to use std::stack<std::pair<int,int>, std::unordered_set<std::pair<int,int>>

or std::stack<coords, std::unordered_set<coords>> for short

I would like to know if it is possible to extend std::unordered_set<> such that it will function with no issues inside of std::stack<>. Beyond that I would like to know if it is even worth the effort, without divulging the actual end use. I just mean for the benefits of using an unordered_set would it be more efficient to design my own template with the necessary methods rather than extend the existing unordered_set to meet requirements?

Edit: Normally I would delete a negative question, but I feel as though this may end up being helpful to some other poor soul who has misunderstood the std::unordered_set. Then again I am not dead yet, so I may very well delete this yet.

Edit 2: The answer from AndreyT below helped for figuring out why std::stack<std::pair<int,int>, std::unordered_set<std::pair<int,int>> can't be a thing. I switch to jxh's answer because it essentially implemented one and is close to what I ended up using.

Answer 1

As already explained in a different answer, an unordered set is not a suitable container for the stack interface, as the supplied container is supposed to provide the ordering semantics. An unordered set does not provide ordering semantics, as indicated by its name.

It seems that what you want is a LIFO data structure, but you want to be able to find a particular element in that data structure in O(1), and manipulate it (I guess find and remove it).

The best you can probably do is your own data structure that has a stack using a list, and an unordered map of coordinates to iterators into that list.

class MyFunkyStack {
    std::list<coord> list_;
    std::stack<coord, std::list<coord>> stack_;
    std::unordered_map<coord, std::list<coord>::iterator> map_;
    //...

    MyFunkyStack () : list_(), stack_(list_), map_() {}

    coord top () const { return stack_.top(); }

    void push (coord c) {
        stack_.push(c);
        map_[c] = list_.end() - 1;
    }

    void pop () { erase(top()); }

    void erase (coord c) {
        std::unordered_map<coord, std::list<coord>::iterator>::iterator i;
        if ((i = map_.find(c)) == map_.end()) return;
        list_.erase(i->second);
        map_.erase(i);
    }

    //...

};

With apologies to the B-52's:
^{_{If you see an old log line buried in the archived syslog that says: / "15 MB in the Hash Stack" / Hash Stack, yeah, yeah // I'm downloading an open source project. / Looking for the hash-ay able-tay! / Compile the hash table today. // I got me a tar-ball, it's too big for e-mail. / And we're downloading it for my Hash Stack. // I got me a compiler, it optimizes plenty, / So hurry up and get your build box ready! // The Hash Stack is a little weird container that we made together. / Hash Stack, baby (a Hash Stack baby!) // Hash Stack, baby, Hash Stack! / Hash Stack, baby, Hash Stack! // (Hash, baby, that's where it's at.) / (Hash, baby, that's where it's at.) // License (ooh!) is open source dudes! / Cause sharing's cool for the Hash Stack. // It's just a small class, with just a few fields. / It's a weird funky stack, and kind of a hack. // Doesn't need destructor. / Doesn't need assignment. / Doesn't need move or copy. / Doesn't need assignment. // The Hash Stack is a little weird container that we made together. / Hash Stack, baby (a Hash Stack baby!) // (Hash, baby, that's where it's at.) / (Hash, baby, that's where it's at.) // Typing and a-mousing, / Thinking and a-coding, / Wearing next to nothing, / Because I'm working at home (yeah). // The Hash Stack compiles! / The Hash Stack compiles! // The Hash Stack compiles, / While other stacks are still just / Arrays, and arrays, and arrays, and arrays! // Other stacks just pushing, other stacks just popping, baby! / Last ones queued up are the first ones to get out. // Other stacks just pushing, other stacks just popping, baby! / A weird funky stack! / A weird funky stack! // While I compile (dependencies are stale), I send an e-mail! // I launch a new "make", reniced at -20, / So hurry up, and get your build box ready! // The Hash Stack is a little weird container that we made together. / Hash Stack, baby (a Hash Stack baby!) // Hash Stack, baby, Hash Stack! / Hash Stack, baby, Hash Stack! // (Hash, baby, that's where it's at, yeah.) / (Hash, baby, that's where it's at.) // Test, test, test, still no core, baby. / Try a few more cases, baby / Test, test, test, still no core, baby. / What's your test plan? // Test, test, test, still no core, baby. / Try a few more cases, sugar / Test, test, test, still no core, baby. / What's your test plan? // Test, test, test, still no core, baby. / (Try a few more cases.) / Test, test, test, still no core, baby. // Test, test! (Got a core, baby!) / Test, test! (Got a core!) / Test, test! (Got a core, baby!) / Test, test! // You did what? / Reproduced, blocker! // Hash Stack, baby, Hash Stack! / (Hash, baby, that's where it's at, yeah.) / (Hash, baby, that's where it's at.) // Hash, baby, Hash Stack! / Typing and a-mousing, / Thinking and a-coding, / On the Hash Stack.}}