我应该如何使用带有 unordered_set 的队列作为底层容器

Question

我有一个包含一组std::pair<int, int>的数据结构。我需要此数据结构的两个重要属性：

我可以快速检查集合成员。
先进先出

因此，作为一个拥有 cppreference.com 的 C++ 初学者，我选择了 std::queue<std::unordered_set<PointUV, pointUVHash>> frontierPointsUV{};，其中我有 typedef std::pair<int, int> PointUV;，并且我在下面的附录中包含了 PointUVHash 的实现。

我的问题是

这是满足上述 2 个要求的明智方法吗？
如何检查集成员资格？我已尝试 frontierPointsUV.c.contains 设置成员资格，但出现“没有成员”错误。
如何压入和弹出（或插入和擦除）？我尝试在任一容器上调用这些修饰符都没有成功。

附录 - 哈希实现

struct pointUVHash final
{
  // This is a safe hashing function for pointUV because we only ever expect it to have 0 or positive ints
  // in ranges well under 2**16
  int operator()(const PointUV &p) const
  {
    return int(p.first) + (int(p.second) << 16);
  }
};

Answer 1

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

你想要的是保留两个数据结构in-sync，例如一个 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; }
};

我使函数语义在某种程度上接近队列或双端队列提供的语义，例如在空队列上调用 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;
    }
};

我应该如何使用带有 unordered_set 的队列作为底层容器

How should I use a queue with an unordered_set as the underlying container

c++

stl

c++-standard-library