如何使用具有unordered_set的队列作为基础容器

队列适配器需要有序的容器（如 deque 或 list）才能工作。在我看来，它也已经过时了，因为它只从底层容器中删除了功能，并没有添加任何实质内容。

您想要的是两个保持同步的数据结构，例如 one 和 one 。看到如何是一个非常简单的类型，这种组合效果最好。如果开始处理更复杂的类型，并且可能希望避免重复的对象和查找，则可以选择将指针存储在其中一个容器中。unordered_set<pair<int, int> >deque<pair<int, int> >pair<int, int>

无论如何，这样的事情应该可以解决问题：

class unique_queue
{
public:
    using value_type = std::pair<int, int>;
private:
    struct hash: private std::hash<int>
    {
        std::size_t operator()(const value_type& value) const noexcept
        {
          if(sizeof(int) >= sizeof(std::size_t)) {
              const std::hash<int>& inthash = *this;
              return inthash(value.first) * 31 + inthash(value.second);
          }
          return static_cast<std::size_t>(value.first)
                << ((sizeof(std::size_t) - sizeof(int)) * CHAR_BIT)
                + static_cast<std::size_t>(value.second);
        }
    };
    using set_type = std::unordered_set<value_type, hash>;
    using queue_type = std::deque<value_type>;

    set_type set;
    queue_type queue;
public:
    bool push(const value_type& value)
    {
        std::pair<set_type::iterator, bool> inserted = set.insert(value);
        if(! inserted.second) // equal value already contained
            return false;
        try {
            queue.push_back(value);
        } catch(...) { // provide exception safety
            set.erase(inserted.first);
            throw;
        }
        return true;
    }
    bool empty() const noexcept
    { return queue.empty(); }

    const value_type& front() const noexcept
    { return queue.front(); }

    void pop() noexcept
    {
        set.erase(front());
        queue.pop_front();
    }
    bool contained(const value_type& value) const noexcept
    { return set.count(value) != 0; }
};

我使函数语义在某种程度上接近队列或 deque 提供的内容，例如，如果在空队列上调用，则未定义的行为。front()

如果希望队列中有多个相等的键，最简单的方法是替换为以跟踪队列中有多少个相等的键。像这样的东西：unordered_set<pair<int, int> >unordered_map<pair<int, int>, size_t>

class set_queue
{
public:
    using value_type = std::pair<int, int>;
private:
    struct hash: private std::hash<int>
    {
        std::size_t operator()(const value_type& value) const noexcept
        {
          if(sizeof(int) >= sizeof(std::size_t)) {
              const std::hash<int>& inthash = *this;
              return inthash(value.first) * 31 + inthash(value.second);
          }
          return static_cast<std::size_t>(value.first)
                << ((sizeof(std::size_t) - sizeof(int)) * CHAR_BIT)
                + static_cast<std::size_t>(value.second);
        }
    };
    using map_type = std::unordered_map<value_type, std::size_t, hash>;
    using queue_type = std::deque<value_type>;

    map_type map;
    queue_type queue;
public:
    bool push(const value_type& value)
    {
        std::pair<map_type::iterator, bool> inserted = map.emplace(value, 0);
        try {
            queue.push_back(value);
        } catch(...) { // provide exception safety
            if(inserted.second)
                map.erase(inserted.first);
            throw;
        }
        inserted.first->second += 1;
        return true;
    }
    bool empty() const noexcept
    { return queue.empty(); }

    const value_type& front() const noexcept
    { return queue.front(); }

    void pop() noexcept
    {
        map_type::iterator refcount = map.find(front());
        assert(refcount != map.end());
        queue.pop_front();
        refcount->second -= 1;
        if(! refcount->second) // last element of same value
            map.erase(refcount);
    }
    std::size_t count(const value_type& value) const noexcept
    {
        map_type::const_iterator found = map.find(value);
        return found == map.end() ? 0 : found->second;
    }
};