c++ - 扩展 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

正如已经在另一个答案中解释的那样，无序集不是堆栈接口(interface)的合适容器，因为提供的容器应该提供排序语义。无序集不提供排序语义，如其名称所示。

看起来你想要的是一个 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 是我们一起制作的一个有点奇怪的容器。/ 哈希堆栈，宝贝(哈希堆栈宝贝!)// 哈希堆栈，宝贝，哈希堆栈!/ 哈希堆栈，宝贝，哈希堆栈!// (哈希，宝贝，这就是它所在的位置。)/ (哈希，宝贝，这就是它所在的位置。)// 许可证(哦!)是开源的伙计们!/ 因为哈希堆栈的共享很酷。// 这只是一个小类(class)，只有几个领域。/ 这是一个奇怪的时髦堆栈，有点像 hack。// 不需要析构函数。/ 不需要赋值。/ 不需要移动或复制。/ 不需要赋值。// Hash Stack 是我们一起制作的一个有点奇怪的容器。/ 哈希堆栈，宝贝(哈希堆栈宝贝!)// (哈希，宝贝，这就是它所在的位置。)/ (哈希，宝贝，这就是它所在的位置。)// 打字和鼠标，/ 思考和编码，/ 几乎什么都没穿，/ 因为我在家工作(是的)。// 哈希堆栈编译!/ 哈希堆栈编译!// 哈希堆栈编译，/ 而其他堆栈仍然只是/ 数组，数组，数组，数组!// 其他堆栈只是插入，其他堆栈只是弹出，宝贝!/ 最后排队的是第一个出去的。// 其他堆栈只是插入，其他堆栈只是弹出，宝贝!/ 一个奇怪的时髦堆栈!/ 一个奇怪的时髦堆栈!// 当我编译时(依赖关系是陈旧的)，我发送了一封电子邮件!// 我发布了一个新的“make”，在 -20 处重新发布，/ 所以快点，准备好你的构建盒!// Hash Stack 是我们一起制作的一个有点奇怪的容器。/ 哈希堆栈，宝贝(哈希堆栈宝贝!)// 哈希堆栈，宝贝，哈希堆栈!/ 哈希堆栈，宝贝，哈希堆栈!// (哈希，宝贝，就是它的位置，是的。)/ (哈希，宝贝，这就是它所在的位置。)// 测试，测试，测试，仍然没有核心，宝贝。/ 多试几个案例，宝贝/ 测试，测试，测试，仍然没有核心，宝贝。/ 你的测试计划是什么？// 测试，测试，测试，仍然没有核心，宝贝。/ 多试几个案例，糖/ 测试，测试，测试，仍然没有核心，宝贝。/ 你的测试计划是什么？// 测试，测试，测试，仍然没有核心，宝贝。/ (多试几个案例。)/ 测试，测试，测试，仍然没有核心，宝贝。// 测试一下! (有一个核心，宝贝!)/ 测试一下! (有一个核心!)/ 测试一下! (有一个核心，宝贝!)/ 测试一下!// 你做了什么？/ 转载，拦截!// 哈希堆栈，宝贝，哈希堆栈!/ (哈希，宝贝，就是它的位置，是的。)/ (哈希，宝贝，这就是它所在的位置。)// 哈希，宝贝，哈希堆栈!/ 打字和鼠标，/ 思考和编码，/ 在哈希堆栈上。