c++ - Boost 或 C++11 中是否有一个容器充当队列但具有独特的元素？

Question

我正在寻找像 std::queue 这样的容器，它将添加元素(例如，一个自定义类，其字段 id 类型为 uint) 最后，但仅如果该对象尚未在容器内。

只有当 id 相等时(我重载了运算符 ==)，我的类的两个元素才被认为是相等的。

C++11 或 Boost 中是否存在这样的容器？

Answer 1

这被称为混合队列。天真的实现是使用这样的东西:

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

一个不太天真的实现可能是以某种重要的方式(比如覆盖)将传入的数据与队列中的数据合并，而不是仅仅丢弃更新。