I have a data structure containing a set of std::pair<int, int>. There are two important properties I require for this data structure:

• I can check set membership fast.
• FIFO

So as a C beginner armed with cppreference.com I went for std::queue<std::unordered_set<PointUV, pointUVHash>> frontierPointsUV{}; where I have typedef std::pair<int, int> PointUV; and I include the implementation of PointUVHash in the appendix below.

My questions are

1. Is this a sensible way to meet the 2 requirements above?
2. How do I check set membership? I've tried frontierPointsUV.c.contains for set membership but I get "has no member" errors.
3. How to I push and pop (or insert and erase)? I've been unsuccessful with trying to call these modifiers on either of the containers.

Appendix - Hash implementation

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

CodePudding user response：

The queue adaptor requires an ordered container such as deque or list to work. In my opinion, it is also obsolete as it only removes functionality from the underlying container and doesn't add anything of substance.

What you want is two data structures that are kept in-sync, e.g. one unordered_set<pair<int, int> > and one deque<pair<int, int> >. Seeing how pair<int, int> is a very simple type, this combination works best. If you start handling more complex types where you may want to avoid duplicate objects and lookups, storing pointers in one of the containers may be an option.

Anyway, something like this should do the trick:

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

I've kept the function semantics somewhat close to what queue or deque provide, e.g. undefined behavior if front() is called on an empty queue.

If you want multiple equal keys in your queue, the easiest way is to replace unordered_set<pair<int, int> > with unordered_map<pair<int, int>, size_t> to keep track of how many equal keys are in the queue. Something like this:

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