更少的恒定时间迭代需要更多的时间- c++编译器依赖？

文章/答案/技术大牛

发布

1回答

c++、g++、profiling

我想在我的课上演示使用预排序概率进行采样可以缩短执行时间。在下面的代码中，sample()函数是主要的工具。相同的随机变量分布以两种形式存储:未排序的概率(数组p和x)和排序的概率(数组p1和x1) -请参阅main()函数。counter变量计算循环迭代次数。结果:在使用(p,x)输入的情况下，sample()花费的mush时间是使用(p1, x1)的两倍，但所用的执行时

浏览 7提问于2020-03-02得票数 1

1回答

Unordered_Map查找时间

performance、hashmap、hashtable、unordered-map、multimap

C++库(包括unordered_map和multimap)中的内置映射和集合要求find函数(用于查找特定元素)使用迭代器来遍历元素。C++参考站点声称使用这些数据结构查找元素需要平均恒定的时间，就像常规的哈希表一样。但是，在找到元素之前，迭代器不是必须遍历整个列表，使平均时间为O(n)吗？

浏览 1提问于2014-08-23得票数 6

回答已采纳

1回答

为什么std::map有双向迭代器类型吗？

std、stdmap、listiterator

我现在正在研究不同类型的迭代器。我看过std::map有bidirectional迭代器。std::set，std::list也有这种类型的迭代器。为什么它们不是random access迭代器？

浏览 4提问于2019-02-04得票数 0

回答已采纳

8回答

关于迭代器顺序的c++* std::map问题*

c++、map、iterator

我是一个C++新手，正在尝试使用一个映射，这样我就可以对find()方法进行恒定时间的查找。请让我知道。编辑:感谢您让我知道map::find()不是恒定

浏览 1提问于2010-03-23得票数 10

4回答

关于递增迭代器的困惑

c++、iterator

graph.begin(); cout << *++it; // True } 为什么编译器在执行it + 1和++it不应该返回相同的值吗？

浏览 29提问于2021-08-18得票数 4

回答已采纳

2回答

在Python语言中可以将字典视为C++中的地图

c++、python

在Python语言中可以将字典视为C++中的地图需要一些好的观点或链接到好的资源。谢谢!

浏览 3提问于2011-03-31得票数 0

回答已采纳

2回答

C++ STL中hash_set::size()的复杂度是多少？

c++、stl

它依赖于实现吗？SGI规范不能保证任何东西。

浏览 1提问于2009-08-14得票数 0

回答已采纳

1回答

O (n / 2)的运行时间复杂度

algorithm、time-complexity

假设我有一个算法，它将返回数组中间的数字。for (int i = 0; i < nums.length; i++) {} 最坏的情况总是O (n / 2没有比这更糟糕的情况了。但是为什么我们只是得出它是O(n)的结论呢？

浏览 1提问于2016-10-26得票数 6

1回答

要求编译器发出无分支/恒定时间代码。

c++、c、gcc、clang、secure-coding

在密码学中，任何依赖秘密数据(例如私钥)的代码都必须在恒定时间内执行，以避免。这可能需要在查看程序集输出时一遍又一遍地重写代码，直到一个神奇的咒语使编译器满意为止--这可能在编译器和编译器之间发生变化，或者当新版本出现时。总的来说，这在两方面都是糟糕的情况:编译器编写人员必须从混淆的代码中推断出意图，将其转换为简单得多的指令序列；而开发人员必须编写这样模糊

浏览 2提问于2021-07-10得票数 3

6回答

创建通用哈希表- C++

.net、c++、algorithm、hashtable

.NET框架有一个Dictionary<TKey，TValue>类，它作为哈希表实现，并在恒定时间内提供数据检索(O(1))。我正在C++中寻找类似的实现。我知道std：：地图，但在这个数据检索需要对数时间。在C++中是否有任何良好的哈希表实现可以在恒定时间内检索数据？ int h

浏览 9提问于2009-10-08得票数 3

回答已采纳

2回答

OpenMP和STL样式的

c++、stl、for-loop、openmp

我正在尝试将我的程序与openMP并行化。该程序大量使用STL迭代器。=N.end(); ++n){};error: invalid controlling predicateg++ -O0 -g3 -Wall -c -fmessage-length=0 -fopenmp -MMD -MP

浏览 0提问于2011-01-26得票数 10

回答已采纳

3回答

类对象、数组或数组

javascript、arrays、json

在迭代过程中哪一个更快？哪一个通过网络需要更少的时间呢？为了在我所说的场景中提供更多的光明，请查看下面的两个选项。Option1Option2 {"0":"A1", "1":

浏览 1提问于2016-12-08得票数 1

2回答

二进制堆与二叉树C++

c++、map、heap、binary-search-tree、priority-queue

对于二进制搜索树和二进制堆上的find_min操作的运行时，我有些困惑。我理解在二进制堆中返回min是一个O(1)操作。我也理解为什么在理论上，返回二进制搜索树中的最小元素是O(log(N))操作。令我惊讶的是，当我阅读C++ STL中的数据结构时，文档指出，将迭代器返回到映射中的第一个元素(与返回最小元素相同)是在恒定的时间内发生的！这不是应该在对数时间内归还吗

浏览 1提问于2014-01-07得票数 1

回答已采纳

1回答

在TreeSet O(1)时间内得到最大的元素？

java、c++、iterator、binary-search-tree、hashset

调用last()将获得最大的元素，但它是O(logN)时间，我知道在C++中，我可以利用迭代器，调用rbegin()是常数时间，当得到最大的元素时，能用Java的TreeSet实现这个恒定的时间吗？C++中的示例代码：s.insert(3);... // say I i

浏览 5提问于2016-06-04得票数 0

回答已采纳

1回答

算法复杂性:在小的有界列表上迭代

time-complexity、computation-theory

我的问题是关于语义的，以及一点关于理论与实践的问题。假设您有一个表，其中的项目可以是任意数量的数字。假设您在表中有一个可见项的数组(屏幕上的项)。可见单元数组的大小受屏幕大小的限制。这是一个已知值。也许它会因设备和屏幕尺寸的不同而不同，但可以肯定的是，它将是一个很小的数字，比如20或更少。现在，如果您要迭代可见项，理论上这是一个线性算法(<em

浏览 1提问于2013-09-05得票数 0

2回答

在C++中，访问未初始化的数组是未指定的行为还是未定义的行为？

c++、unspecified-behavior

例如，在以下代码中：int x = myarray[1];这在类似于数组的数据结构中很有用，但可以在恒定时间内初始化。(对不起，我的阿霍、霍普克罗夫特和尤尔曼的复印件在手边，所以不能查到名字。)

浏览 2提问于2018-04-06得票数 1

回答已采纳

1回答

用于C++中的循环和性能关键应用程序

c++

我试图为性能关键的应用程序编写快速的C++代码，但是我对编译器和编译器实现的了解是有限的。我目前正在使用gcc编译器。因此，我想知道在实践中，写成如下的for循环在性能上是否存在差异{ for( int i = 0

浏览 2提问于2015-05-13得票数 0

回答已采纳

2回答

Deque索引-迭代器转换

c++、iterator、deque

Deque允许在固定时间内按索引访问元素。所以看起来我们可以快速找到元素在内存中的位置。但是，当要获得迭代器(例如，传递到擦除())时，我们需要使begin() +i，这将需要线性时间。能否在恒定时间内转换索引->迭代器？如果不是，索引/创建迭代器的区别是什么？相反的操作是否可能:指向元素/迭代器->索引的指针(不

浏览 3提问于2015-03-07得票数 1

回答已采纳

1回答

大小的时间复杂度是多少？

c++、data-structures、time-complexity、big-o

我正在研究不同STL容器的各种操作的复杂性。通过这个网站上的different question，我找到了这个图表。 website link ? 我注意到这个图表中缺少的一个操作是size操作。我想，如果一个人知道.begin和.end的复杂性，也可以计算出大小的复杂性。但这些也是缺失的。我已经找到了一个类似于我在this问题中寻找的答案，但这个答案是针对Java的，所以它没有涵盖所有的STL容器，并且它只为少数给定的

浏览 36提问于2020-04-23得票数 5

回答已采纳

1回答

shr(7，dest)比shr(1，dest)花费更多的时间吗？

assembly、x86、instructions、hla

我正在学习HLA汇编语言的书籍，汇编语言艺术，第二版。我刚开始学习shr和shl指令，我想知道更多的移位是否比移动更少的时间更长。shr(1，dest)对shr(7，dest)。如果说明的语法不对，我很抱歉。

浏览 4提问于2015-09-06得票数 0

回答已采纳

点击加载更多