使用自定义密钥在 std::unordered_map 中查找密钥

Question

我目前正在使用自定义密钥创建自定义 std::unordered_map 声明：

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;

我在迭代过程中很难找到特定的键。出于某种原因，当我传递一个用于查找的键时，我的客户端对象从未被定位。

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

即使key已经插入，clientIter也始终指向结束迭代器位置。您认为这是否与必须在堆栈上重新创建这些 ClientKey 值然后将它们传递到映射中进行查找有关，还是我在其他地方有问题？感谢您的澄清和见解。

Answer 1

首先，对 emptyId 字段的一些注意事项（不考虑无效格式 - 顺便说一句，您也没有检查）：

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

是否有任何特殊原因导致 k0 和 k1 的 emtpyId 标志应该不同？我个人会说：

标志实现不正确。
这是多余的，你通过m_clientId.empty()获得相同的信息。

现在失败原因：

再次考虑 k0 和 k1，但没有在 k1 上调用 SetClientId：

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

假设 k0 已插入地图中，并且使用 k1 尝试找到它。会发生什么？ k1 生成另一个哈希键而不是 k0，并且映射将查看与 k0 所在的不同的桶 - 并且不会找到任何东西。

我认为您想要实现的是让多个客户端使用相同的连接 ID，并能够针对给定的连接 ID 迭代这些客户端。所以你可能更喜欢 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 那么你的 class ClientKey 就过时了。

Answer 2

您的代码允许以下内容 return 为真：

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

但是，您的哈希是基于 connectId 和 clientId 的组合。

unordered_map::find 不会对映射进行详尽搜索，而是在存储桶中查找给定的哈希值并比较只是存储桶中的条目。

您仅使用 connectId 生成测试密钥，因此它正在查找 ClientKey(connectId, "") 的存储桶而不是 ClientKey(connectId, someOtherValue) 的存储桶。

您应该考虑完全基于 connectId.

进行散列

最后，请注意您的构造函数：

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

如果我写：

ClientKey ck("hello");

emptyId真的应该是真的吗？

使用自定义密钥在 std::unordered_map 中查找密钥

Finding Key in std::unordered_map with custom key

c++

unordered-map