Is there a container in Boost or C++11 which act as a queue but with unique elements?

Question

I'm looking for a container like std::queue which will add elements (e.g. a custom class with field id of type uint) at the end, but only if that object is not already inside the container.

Two elements of my class are to be considered equal only when id is equal (I have overloaded operator ==).

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

Answer 1

This is called queue with conflation. The 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;
}

A less naive implementation may be merging incoming data with the one in the queue in some non-trivial way (say overwriting) instead of just dropping updates.

Answer 2

In addition to the other answer, here's another example of how you can combine std::set^* and std::queue to form a container with the properties you're looking for.

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_;
};

Use like so:

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

_{* Note: std::set requires that the operator < for the element type is defined.}