代码之家 › 专栏 › 技术社区 › Ravi Gupta

STL:从A到B的一组自然数

performance stl c++

Ravi Gupta · 技术社区 · 14 年前

我想把A到B的自然数相加。目前我正在插入从A到B的每个数字,像这样一个一个地插入集合中,

set<int> s;
for(int j=A; j<=B; j++)
    s.insert(j);

但这需要 O(n) n = (B - A)+1 ). 在STL中有没有预定义的方法来做呢 O(1)

6 回复 | 直到 14 年前

stimms 14 年前

bshields 14 年前

从技术上说我相信这是 O(n log n) set.insert 功能是 log n . O(n) vector 或 list .

In silico 14 年前

O(n) 时间。

dvogel 14 年前

使用STL集合容器,您永远不会得到O(1)时间。您可以通过使用 set(InputIterator f, InputIterator l, const key_compare& comp) 构造函数,并传入在给定整数范围内迭代的自定义迭代器。这可能运行得更快(取决于stl实现、编译器等)的原因是您正在减少调用堆栈深度。在代码片段中,从.insert()调用一直向下到实际插入,然后返回每个整数。使用替代构造函数,您的增量操作将向下移动到执行插入的帧中。如果编译器不能内联,增量操作现在可能会有函数调用的开销。不过,在采用这种方法之前,您应该先对其进行基准测试。如果stl实现对.insert()有一个浅调用堆栈,则速度可能较慢。

但是,一般来说,如果需要一组连续的整数,则可以通过实现一个专门的set类来获得巨大的性能提升,该类只能存储和比较每个集合的上下界。

cpx 14 年前

O(1)
O(n) 对于复制构造函数和使用迭代器的排序序列插入。
O(log n!)

James Curran 14 年前

好吧,如果你想完全开箱即用,你可以设计一个“延迟加载”数组,为这个任务定制。基本上,在访问时,如果之前没有设置该值,它将确定正确的值。

推荐文章

Julia · 矢量中相加为总和S的值的数量

1 年前

Codeforces Fan · 如何在c中的STL集合中添加lambda函数或执行自定义操作++

2 年前

C_Rod · 在模板方法中确定STL容器中项目的数据类型

2 年前

quantumwell · 将空向量放入std::map()

6 年前

BugShotGG · 如何正确地将托洛尔()应用于C中的德语大写字母,,á++

6 年前

GreyCat · C++参数类型,用于接受适用于基于范围的for循环的所有序列

6 年前

OutOfBound · 对未初始化内存使用算法的优点

6 年前

Adrian · 在容器、PTR和对象不可修改的情况下,如何传递unique\u ptr的容器?

6 年前

xskxzr · 为什么std::unordered\u set会重新刷新,即使负载系数限制没有打破?

6 年前

DarthRubik · 在使用列表删除之后,迭代器如何不无效

6 年前