我需要一个具有 O(1) 添加、查找和删除操作的数据结构,用于由客户列表订阅的主题。
它需要支持的一些函数是:isTopicExists、isClientExists、getClientsForTopic、addClientForTopic、removeClientForTopic 和 getTopicsForClient。
给定一个主题名称、一个我们可以假定为唯一的客户端 ID 和客户端指针,最好使用什么数据结构?有哪些实现可用?
最佳答案
HashMap 似乎不是一个坏主意。它的预期复杂度为 O(1),但具有许多冲突的悲观场景可以使您达到 O(n),具体取决于链接的实现方式。对数搜索在这里很难被击败,所以我会选择自平衡二叉搜索树,甚至是 std::map(大多数 STL 实现中的红黑树)。使其更高效的唯一方法是使用 vector (数组),但前提是您的 ID 很小或偏移但彼此靠近。在这里你无法战胜数学。
关于c++ - 客户端主题列表的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6065957/