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

Question

我有一个包含一组 std::pair 的数据结构。我需要这个数据结构有两个重要的属性：

• 我可以快速检查集合成员资格。
• 因此

，作为一名使用 cppreference.com 的 C++ 初学者，我选择了 std::queue> 。 frontierPointsUV{}; 其中我有 typedef std::pair; PointUV; 我在下面的附录中包含了 PointUVHash 的实现。

我的问题是，

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

附录 - 哈希实现

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

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

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

不管怎样，这样的事情应该可以解决问题：

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; > 和 unordered_map, 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;
    }
};