扩展std :: unordered_set <>以与std :: stack <>一起使用

Question

我的问题:我想用 std::stack<std::pair<int,int>, std::unordered_set<std::pair<int,int>>

或std::stack<coords, std::unordered_set<coords>>简称

我想知道是否可以扩展std::unordered_set<>,以便它可以在没有问题的情况下运行std::stack<>.除此之外,我想知道它是否值得付出努力,而不泄露实际的最终用途.我只是意味着使用unordered_set的好处是使用必要的方法设计我自己的模板更有效,而不是扩展现有的unordered_set以满足要求？

编辑:通常我会删除一个否定的问题,但我觉得这可能最终有助于其他一些误解了std :: unordered_set的可怜的灵魂.然后我还没死,所以我可能会删除它.

编辑2:来自AndreyT的答案有助于弄清楚为什么std::stack<std::pair<int,int>, std::unordered_set<std::pair<int,int>>不能成为一件事.我切换到jxh的答案,因为它基本上实现了一个并且接近我最终使用的.

Answer 1

正如在不同的答案中已经解释的那样,无序集合不是堆栈接口的合适容器,因为提供的容器应该提供排序语义.无序集不提供排序语义,如其名称所示.

看起来你想要的是一个LIFO数据结构,但你希望能够在O(1)中找到该数据结构中的特定元素,并对其进行操作(我想找到并删除它).

你可以做的最好的事情是你自己的数据结构,它有一个使用列表的堆栈,以及一个无序的坐标映射到该列表中的迭代器.

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);
    }

    //...

};

向B-52道歉:
^{_{如果你看到一个旧的日志行埋在存档的系统日志中,说:/"哈希堆栈中的15 MB"/哈希堆栈,是的,是的//我正在下载一个开源项目./寻找hash-ay able-tay!/今天编译哈希表.//我给了我一个tar-ball,它对于电子邮件来说太大了./我们正在为我的Hash Stack下载它.//我给了我一个编译器,它优化了很多,/所以快点让你的构建盒准备就绪!// Hash Stack是我们一起制作的一个奇怪的容器./哈希堆栈,宝贝(一个哈希堆栈宝贝!)//哈希堆栈,宝贝,哈希堆栈!/哈希堆栈,宝贝,哈希堆栈!//(哈希,宝贝,这就是它所在的地方.)/(哈希,宝贝,这就是它所在的地方.)//许可证(哦!)是开源的家伙!/导致共享对哈希堆栈很酷.//这只是一个小班,只有几个领域./这是一个奇怪的时髦堆栈,有点像黑客.//不需要析构函数./不需要分配./不需要移动或复制./不需要分配.// Hash Stack是我们一起制作的一个奇怪的容器./哈希堆栈,宝贝(一个哈希堆栈宝贝!)//(哈希,宝贝,这就是它所在的地方.)/(哈希,宝贝,这就是它的所在.)//打字和调动,/思考和 - 编码,/几乎没穿,/因为我在家工作(是的).//哈希堆栈编译!/哈希堆栈编译!//哈希堆栈编译,/其他堆栈仍然只是/数组,数组,数组和数组!//其他堆栈只是推,其他堆栈刚刚弹出,宝贝!排队的最后排队是第一批排队的人.//其他堆栈只是推,其他堆栈刚刚弹出,宝贝!/一个奇怪的时髦堆栈!/一个奇怪的时髦堆栈!//当我编译(依赖是陈旧的)时,我发送一封电子邮件!//我发布了一个新的"make",租用率为-20,/快点,准备你的构建盒!// Hash Stack是我们一起制作的一个奇怪的容器./哈希堆栈,宝贝(一个哈希堆栈宝贝!)//哈希堆栈,宝贝,哈希堆栈!/哈希堆栈,宝贝,哈希堆栈!//(哈希,宝贝,这就是它所在的地方,是的.)/(哈希,宝贝,这就是它所在的地方.)//测试,测试,测试,仍然没有核心,宝贝./尝试几个案例,宝贝/测试,测试,测试,仍然没有核心,宝贝./你的测试计划是什么？//测试,测试,测试,仍然没有核心,宝贝./尝试几个案例,糖/测试,测试,测试,仍然没有核心,宝贝./你的测试计划是什么？//测试,测试,测试,仍然没有核心,宝贝./(再尝试几个案例.)/测试,测试,测试,仍然没有核心,宝贝.// 测试一下!(有一个核心,宝贝!)/测试,测试!(有核心!)/测试,测试!(有一个核心,宝贝!)/测试,测试!// 你做了什么？/转载,拦截!//哈希堆栈,宝贝,哈希堆栈!/(哈希,宝贝,这就是它所在的地方,是的.)/(哈希,宝贝,这就是它所在的地方.)//哈希,宝贝,哈希堆!/键入和调整,/思考和编码,/在哈希堆栈上.}}