Is there a container in Boost or C ++ 11 that works as a queue, but with unique elements?

Question

I am looking for a type container std::queuethat will add elements to the end (for example, a custom class with a idtype field uint), but only if this object is not already inside the container.

Two elements of my class are considered equal only when idequal (I overloaded the operator ==).

Does such a container exist in C ++ 11 or perhaps in Boost?

Answer 1

This is called queue with conflation. A naive implementation is to use something like this:

std::set<your_key_t> unique;
std::queue<your_data_t> q;

void enqueue(your_data_t x) {
    if (unique.insert(x.key).second) {
        q.push(std::move(x));
    }
}

your_data_t dequeue(your_data_t dflt) {
    if (!q.empty()) {
        your_data_t x = std::move(q.front()); q.pop();
        unique.erase(q.front().key);
        return x;
    }
    else return dflt;
}

(, ), .

Answer 2

, , std::set ^* std::queue, , .

template <typename T>
class QueueUnique {
public:
    void push(T t) {
        if (set_.insert(t).second) {
            queue_.push(std::move(t));
        }
    }
    T& front() { return queue_.front(); }
    T& back() { return queue_.back(); }
    typename std::set<T>::size_type size() { return set_.size(); }
    /* More functions */
private:
    std::set<T> set_;
    std::queue<T> queue_;
};

:

QueueUnique<int> q;
q.push(1);
q.push(1);
q.push(2);
q.push(3);
q.push(1);

std::cout << "Size: " << q.size() << std::endl;   // Size: 3
std::cout << "Front: " << q.front() << std::endl; // Front: 1
std::cout << "Back: " << q.back() << std::endl;   // Back: 3

< > * : std::set , < . >