c++ - priority_queue - 删除不在顶部的元素

Question

我有 priority_queue。我的函数 delete 在内存消耗和时间方面不是很合理。我见过类似的主题，但它们对我没有帮助。

How to remove element not at top from priority_queue?

STL Priority Queue - deleting an item

我如何删除 log( n ) 上的元素。

我的功能:

1

void deleteFromTimeQueue(const K& key)
            {
                std::priority_queue<Record<K>, std::vector<Record<K>>, Comparator<K>> tmpTimeQueue_;

                while (timeQueue_.size() > 0)
                {
                    Record<K> it = timeQueue_.top();

                    if (it.getKey() == key)
                    {
                        timeQueue_.pop();
                        break;
                    }
                    tmpTimeQueue_.push(it);
                    timeQueue_.pop();
                }

                while (tmpTimeQueue_.size() > 0)
                {
                    Record<K> it = tmpTimeQueue_.top();
                    timeQueue_.push(it);
                    tmpTimeQueue_.pop();
                }
            }

我如何删除没有 tmpTimeQueue_ 的元素？

2

void deleteFromTimeQueue(const K& key)
        {
            std::priority_queue<Record<K>, std::vector<Record<K>>, Comparator<K>> tmpTimeQueue_;

            while (timeQueue_.size() > 0)
            {
                Record<K> it = timeQueue_.top();

                if (it.getKey() == key)
                {
                    timeQueue_.pop();
                    continue;
                }
                tmpTimeQueue_.push(it);
                timeQueue_.pop();
            }
            timeQueue_.swap(tmpTimeQueue_);
        }

1 或 2 哪个更好？

Answer 1

也许使用 LINK-LIST 实现优先级队列是一个不错的理想选择。这样，您就可以搜索该元素并将其删除为普通链接列表。希望这对您有所帮助。