Co奶茶怎么样:stl地图性能怎么样(stl map c++)

我使用map<MyStruct, I*> map1;。显然我的总应用程序时间的 9 % 花在那里。特别是在我的一个主要功能的一行。地图不是很大(& lt;1k 几乎总是,& lt;20 是常见的)。

我想我不应该写我自己的,但我可以,如果我认为这是一个好主意。

附加信息:我总是在添加元素之前检查。如果一个键存在,我需要报告一个问题。比点后,我将大量使用 map 进行查找,并且不会添加任何更多的元素。

57

首先,您需要了解映射是什么以及您正在做的操作代表什么。std::map是一个平衡的二叉树,查找将需要O( log N )操作,每个操作都是键的比较以及在大多数情况下可以忽略的一些额外操作(指针管理)。插入花费大致相同的时间来定位插入点,再加上新节点的分配,实际插入到树中的复杂性更高。

当您尝试在插入之前确定一个键是否在映射中时,您将产生查找的成本,如果它不成功,则查找插入点的成本相同。您可以通过使用std::map::insert来避免额外的成本,它返回一个带有迭代器和 bool 的对,告诉您插入是否实际发生或元素是否已经存在。

除此之外,您还需要了解比较密钥的成本有多高,这与问题所显示的不同(MyStruct只能容纳一个int或一千个),这是您需要考虑的。

最后,可能是map不是满足您需求的最有效的数据结构的情况,您可能需要考虑使用std::unordered_map(哈希表)具有预期的常量时间插入(如果哈希函数不是可怕的)或对于小数据集,即使是简单的有序数组(或std::vector),您可以使用二进制搜索来定位它的数量更多

与往常一样,对性能进行测量,然后尝试了解所花费的时间。还要注意,在特定功能或数据结构上花费的时间的 10 % 可能很多,或者几乎没有,这取决于您的应用程序是什么。例如,如果您的应用程序只是在数据集中执行查找和插入,而这只需要 10 % 的 CPU,那么您在其他地方都有很多需要优化的地方!

10

可能会更快,只是做一个insert,并检查pair.secondfalse如果键已经存在:

像这样

if ( myMap.insert( make_pair( MyStruct, I* ) ).second == false)
{
  // report error
}
else
  // inserted new value

...而不是每次都执行find调用。

7

而不是map,你可以尝试unordered_map使用哈希键,而不是树,找到元素。This answer给出了一些提示何时更喜欢unordered_map而不是map

5

这可能是一个很长的镜头,但对于小集合,有时最关键的因素是cache性能。

由于std::map实现了一个红黑树,这是 [AFAIK] 不是很高效的缓存-也许将地图实现为std::vector<pair<MyStruct,I*>>将是一个好主意,并使用二进制搜索 [而不是地图查找],至少它应该是有效的,一旦你开始只查找 [停止插入元素],因为std::vector更适合缓存。

这个因素 [cpu-cache] 通常被忽略并隐藏为大 O 符号中的常量,但对于大型集合,它可能会产生重大影响。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(339)
Sk gaming:UseMethod(“SK”)中的错误:没有适用于“SK”的方法应用于类“character”的对象
上一篇
免费店铺小程序:Java小程序 vs应用程序
下一篇

相关推荐

  • 嵌入式和c++的区别:嵌入式 C++:使用STL还是不 (c++ embeded)

    关于嵌入式和c++的区别的问题,在c++ embeded中经常遇到,我一直是一名嵌入式软件工程师,但通常在 OSI 堆栈的第 3 层或第 2 层。我不是一个真正的硬件人。我通常总是做电信产品,通常是手 / 手机,这通常意味着像 ARM 7 处理器。…

    2024-05-29 01:17:12
    0 62 43
  • C++迭代器是什么:STL C++中的过去迭代器是什么(c++ end)

    关于C++迭代器是什么的问题,在c++ end中经常遇到,任何人都可以解释past-the-end的含义。为什么我们调用end()函数过去结束?…

    2024-05-18 07:27:24
    0 25 22
  • 莲花c-01:lastLogonTimeStamp属性的1601/01/01

    关于莲花c-01的问题,在what is the difference between lastlogon and lastlogontimest中经常遇到,我使用lastLogonTimeStamp跟踪用户上次登录时间,如下代码所示:…

    2024-02-29 08:32:21
    0 91 33
  • 网上报的编程猫课怎么样:stl地图性能怎么样(stl map c++)

    关于网上报的编程猫课怎么样的问题,在stl map c++中经常遇到,我使用map<MyStruct,I*>map1;。显然我的总应用程序时间的 9 % 花在那里。特别是在我的一个主要功能的一行。地图不是很大(& lt;1k 几乎总是,& lt;20 是常见的)。…

    2024-03-06 05:10:08
    0 89 31
  • comeandgetyourlove音乐爱就在你身边

    Come and Get Your Love是一首热门的歌曲,由美国摇滚乐队Redbone演唱。这首歌曲于1974年发行,被收录在他们的专辑《Wovoka》中。歌曲以放克曲风为主,旋律活泼,曲调悠扬,歌词朗朗上口,深受歌迷喜爱。…

    2023-06-29 07:47:31
    0 26 77
  • css预编译器: center;}

    CSS预编译器是一种用于构建CSS的工具,它可以将CSS代码转换为更易于管理和维护的格式。它们可以使CSS代码更加灵活,更易于重用,并且可以帮助开发人员更轻松地组织和管理CSS代码。…

    2023-04-30 05:19:08
    0 31 44
  • python中predict函数参数:如何使用Python的predict函数进行机器学习预测

    示例示例predict函数是scikit-learn中的一个函数,用于预测新样本的输出结果。参数:…

    2023-03-30 08:03:12
    0 25 16
  • codeblocks无法编译运行:Codeblocks无法编译运行的解决方案

    codeblocks无法编译运行的原因可能有很多,下面以一段简单的C语言代码为例,来说明codeblocks无法编译运行的情况。…

    2023-07-11 08:01:55
    0 16 42

发表评论

登录 后才能评论

评论列表(20条)