Finding Key in std::unordered_map with custom key

Question

I'm currently creating a custom std::unordered_map declaration with my custom key:

class BASE_DLLSPEC ClientKey
{
  private:
    // this is always true initially until we call SetClientId
    bool emptyId;

    // both of these are guaranteed to be unique
    QString m_connectId; // ip:port format
    QString m_clientId;  // {Uuid} format
    // ----------

  public:
    ClientKey(const QString& connectId = "", const QString& clientId = "") :
      emptyId(true), m_connectId(connectId), m_clientId(clientId)
    { }

    void SetClientId(const QString& clientId)
    {
      m_clientId = clientId;
      emptyId    = false;
    }

    const QString& GetConnectId() const { return m_connectId; }
    const QString& GetClientId() const { return m_clientId; }

    bool operator==(const ClientKey& other) const
    {
      int comp1 = QString::compare(m_connectId, other.GetConnectId());
      int comp2 = QString::compare(m_clientId, other.GetClientId());

      return (comp1 == 0) ||
             (!emptyId && comp2 == 0);
    }
};

struct BASE_DLLSPEC ClientKeyHash
{
  std::size_t operator()(const ClientKey& key) const
  {
    std::string connectId = key.GetConnectId().toStdString();
    std::string clientId  = key.GetClientId().toStdString();

    std::size_t h1 = std::hash<std::string>()(connectId);
    std::size_t h2 = std::hash<std::string>()(clientId);
    return h1 ^ (h2 << 1);
  }
};

struct BASE_DLLSPEC ClientKeyEqual
{
  bool operator()(const ClientKey& lhs, const ClientKey& rhs) const
  {
    return lhs == rhs;
  }
};

typedef std::unordered_map<ClientKey,
                           ClientPtr,
                           ClientKeyHash,
                           ClientKeyEqual> ClientMap;

I'm having difficulties finding a particular key during my iteration. For some reason my client object is never located when I pass in a key for lookup.

ClientKey key = Manager::ClientKey(connectId);
ClientManager& clientManager = Manager::ClientManager::GetInstance();
ClientMap::const_iterator clientIter = clientManager.GetClients().find(key);

Even if the key has already been inserted, clientIter is always pointing to the end iterator position. Do you think this is related to having to re-create these ClientKey values on the stack and then passing them into the map for look-up, or do I have a problem elsewhere? Thank you for the clarification and insight.

I don't see you implementing a hash function for your client key and that's most likely the problem. See this answer: http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key — Timo Geusch, Jul 13 '16 at 04:45
It looks like you allow keys that compare equal to have different hashes. This cannot possibly work. — n. m. could be an AI, Jul 13 '16 at 05:09

Aconcagua · Accepted Answer · 2016-07-13T05:53:31.610

At first, some considerations to the emptyId field (do not consider invalid formats - which, by the way, is not checked by you either):

ClientKey k0("hello", "world");
ClientKey k1("hello");
k1.SetClientId("world");

Is there any particular reason that the emtpyId flag should be different for k0 and k1? I personally would say:

The flag is implemented incorrectly.
It is redundant, you get the same information via m_clientId.empty().

Now the reason for failure:

Consider again k0 and k1, but without SetClientId having been called on k1:

ClientKey k0("hello", "world");
ClientKey k1("hello");

Imagine k0 has been inserted in the map, and with k1 you try to find it. What will happen? k1 produces another hash key than k0, and the map will look at a different bucket than where k0 resides at - and will not find anything.

What I think you want to achieve is having several clients for the same connection id and being able to iterate over these for a given connection id. So you might prefer std::unordered_multimap<std::string, ClientPtr> (where the string parameter represents the connection id). You will get all clients for a given connection id via equal_range then, and your class ClientKey gets obsolete.

That is indeed the reason I was encountering this problem. Thank you very much. I initially pass in just the connectId with an empty clientId where I do the find. Followed by if it's a new client setting the clientId. So on re-iteration the clientId is always empty, and in it's current state the hash will utilize the clientId as well on the find. — m11hut, Jul 13 '16 at 06:00

score 0 · Answer 2 · answered Jul 13 '16 at 06:10

Your code allows that the following will return true:

ClientKey k1("hello", "world");
ClientKey k2("hello", "");
return k1 == k2;

However, your hash is based on the combination of connectId and clientId.

unordered_map::find does not do an exhaustive search of the map, instead it looks in the bucket for the given hash and compares just the entries in the bucket.

You are generating your test key with just connectId, so it is looking in the bucket for ClientKey(connectId, "") rather than the bucket for ClientKey(connectId, someOtherValue).

You should consider making the hash based exclusively on connectId.

Lastly, note your constructor:

ClientKey(const QString& connectId = "", const QString& clientId = "") :
  emptyId(true), m_connectId(connectId), m_clientId(clientId)
{ }

If I write:

ClientKey ck("hello");

should emptyId really be true?

Finding Key in std::unordered_map with custom key

2 Answers2