Queue with unique entries in c++

Question

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.

Answer 1

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