Jos*_*osh 6 c++ algorithm search vector data-structures
我正在编写一个与MySQL数据库连接的电子邮件应用程序.我有两个表来源我的数据,其中一个包含取消订阅,另一个是标准用户表.截至目前,我正在创建一个指向电子邮件对象的指针向量,并且最初将所有未订阅的电子邮件存储在其中.然后我有一个标准的SQL循环,我在其中检查电子邮件是否在取消订阅向量中,然后将其添加到全局发送电子邮件向量中.我的问题是,有更有效的方法吗？我必须在我的系统中搜索每个电子邮件的unsub向量,最多50K不同.有更好的搜索结构吗？而且,一个更好的结构来维护一个独特的价值集合？如果它已经包含它,那么它可能会简单地丢弃该值？
如果您的C++标准库实现支持它,请考虑使用a std::unordered_set 或a std::hash_set.
您也可以使用std::set,但其开销可能更高(这取决于为对象生成哈希的成本与多次比较两个对象的成本).
如果你确实使用了基于节点的容器,set或者unordered_set你也可以获得这样的优势:与从a中删除相比,删除元素相对便宜vector.
像这样的任务(设置操作)最好留给执行它们的MEANT - 数据库!
例如:
SELECT email FROM all_emails_table e WHERE NOT EXISTS (
SELECT 1 FROM unsubscribed u where e.email=u.email
)
如果您想要一个算法,您可以通过检索电子邮件列表和取消订阅列表作为ORDERED列表来快速完成此操作.然后,您可以浏览电子邮件列表(已订购),当您这样做时,您可以沿着取消订阅列表滑行.这个想法是你向前移动1个具有"最大"当前元素的列表.这个算法是O(M + N)而不是O(M*N)就像你当前的那个
或者,您可以执行哈希映射,该映射从未订阅的电子邮件地址映射到1.然后,您find()在该映射上进行调用,正确的哈希实现对于每个查找都是O(1).遗憾的是,C++中没有Hash Map标准 - 请参阅现有实现的SO问题(有一些想法,有SGI的STL hash_map和Boost和/或TR1 std::tr1::unordered_map).
该帖子的一条评论表明它将被添加到标准中:"考虑到这一点,C++标准库技术报告引入了无序关联容器,这些容器是使用哈希表实现的,现在它们已被添加到工作中C++标准草案."