用C ++中的唯一条目排队 [英] Queue with unique entries in c++

问题描述

我需要在C或C ++中实现一个包含唯一条目（无重复项）的队列。我正在考虑维护对队列中已经可用的元素的引用，但这似乎效率很低。

I need to implement a queue containing unique entries(no duplicates) in C or C++. I am thinking of maintaining a reference of elements already available in queue but that seems very inefficient.

请告诉我您解决此问题的建议。

Kindly let me know your suggestions to tackle this.

推荐答案

如何跟踪辅助数据的唯一性：

How about an auxiliary data structure to track uniqueness:

std::queue<Foo> q;
std::set<std::reference_wrapper<Foo>> s;

// to add:

void add(Foo const & x)
{
    if (s.find(x) == s.end())
    {
        q.push_back(x);
        s.insert(std::ref(q.back()));  // or "s.emplace(q.back());"
    }
}

或者，也可以颠倒队列的角色并集合：

Or, alternatively, reverse the roles of the queue and the set:

std::set<Foo> s;
std::queue<std::reference_wrapper<Foo>> q;

void add(Foo const & x)
{
    auto p = s.insert(x);       // std::pair<std::set<Foo>::iterator, bool>
    if (s.second)
    {
        q.push_back(std::ref(*s.first));  // or "q.emplace_back(*s.first);"
    }
}

这篇关于用C ++中的唯一条目排队的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！