我使用地图< MyStruct,I *> MAP1 ;.显然,我的总应用程序时间的9％用于那里.具体在我的一个主要功能的一条线上.地图不是很大(< 1k几乎总是,< 20是常见的). 有没有可以使用的替代实现？我想我不应该写我自己,但如果我认为这是一个好主意,我可以. 附加信息：我总是在添加元素之前检查.如果存在密钥,我需要报告一个问题.比起一点,我将使用地图大量的查找,不会添加任何更多的元素.
解决方法
首先,您需要了解地图是什么,您正在做的操作代表什么. std :: map是一个平衡的二叉树,查找将采用O(log N)操作,每个操作都是密钥的比较加上大多数情况下可以忽略的一些额外的值(指针管理).插入大致相同的时间来定位插入点,加上新节点的分配,实际插入到树中并重新平衡.复杂度再次为O(log N),尽管隐藏常数较高.
当您尝试在插入之前确定地图中的一个密钥是否导致查找的费用,如果它不成功,则定位插入点的成本相同.您可以通过使用std :: map :: insert来返回一个与迭代器和一个布尔的对话框来告诉您插入是否实际发生或元素已经存在的额外成本.
除此之外,您需要了解比较键的成本是多少,这不是问题所在(MyStruct只能容纳一个或一千个),这是您需要考虑的因素.
最后,地图可能不是您需要的最有效的数据结构,您可能需要考虑使用预期定时插入的std :: unordered_map(哈希表)(如果哈希函数是不可怕),或者对于小型数据集,即使是可以使用二进制搜索来定位元素的简单有序数组(或std :: vector)(这将减少分配次数,代价是更昂贵的插入,但如果持有的类型足够小,可能值得)
一如往常的表现,衡量,然后尝试了解时间花在哪里.另请注意,根据您的应用程序,在特定功能或数据结构中花费的10％的时间可能很多或几乎没有.例如,如果您的应用程序只是执行查找和插入数据集,并且只需要10％的cpu,您就可以在其他地方进行优化.
