STL：从A到B的自然数集
我想将集合中从 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) 时间内完成此操作？
谢谢
I want to add natural numbers from A to B in a set. Currently I am inserting each and every number from A to B, one by one in the set like this,
set<int> s;
for(int j=A; j<=B; j++)
s.insert(j);
But it takes O(n) time (here n = (B - A)+1). Is there any pre-defined way in STL to do it in O(1) time?
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
分配内存来保存 n 个数字总是至少在 O(n) 内，所以我认为你不走运。
Allocating memory to hold n number is always going to be in at least O(n) so I think you're out of luck.
从技术上讲，我相信这是
O(n log n)，因为set.insert函数是log n。我认为O(n)是您能做的最好的事情，但为此您需要使用未排序的容器，例如vector或list。Technically I believe this is
O(n log n)because theset.insertfunction islog n.O(n)is the best you can do I think but for that you would need to use an unsorted container like avectororlist.不会。用连续值填充容器所需的最短时间是
O(n)时间。No. The shortest amount of time it takes to fill a container with sequential values is
O(n)time.使用 STL set 容器，您永远不会获得 O(1) 时间。您可以通过使用 set(InputIterator f, InputIterator l, const key_compare& comp) 构造函数并传入在给定整数范围内迭代的自定义迭代器来减少运行时间。这可能运行得更快（取决于 stl 实现、编译器等）的原因是您正在减少调用堆栈深度。在您的代码片段中，您从 .insert() 调用一路向下到实际插入，然后返回每个整数。使用备用构造函数，您的增量操作将向下移动到执行插入的帧中。如果您的编译器无法内联增量操作，则增量操作现在可能会产生函数调用的开销。不过，在采取这种方法之前，您应该对此进行基准测试。如果您的 stl 实现具有 .insert() 的浅调用堆栈，则速度可能会更慢。
但一般来说，如果您需要一组连续范围的整数，则可以通过实现一个专门的集合类来获得巨大的性能提升，该集合类只能存储和比较每个集合的上限和下限。
With the STL set container you will never get O(1) time. You may be able to reduce the running time by using the
set(InputIterator f, InputIterator l, const key_compare& comp)constructor and passing in a custom iterator that iterates over the given integer range. The reason this may run faster (depends on stl implementation, compiler, etc) is that you are reducing the call stack depth. In your snippet, you go all the way down from your .insert() call to the actual insertion and back for each integer. Using the alternate constructor, your increment operation is moved down into the frame in which the insertion is performed. The increment operation would now have the possible overhead of a function call if your compiler can't inline it. You should benchmark this before taking this approach though. It may be slower if your stl implementation has a shallow call stack for .insert().In general though, if you need a set of a contiguous range of integers, you could see massive performance gains by implementing a specialized set class that can store and compare only the upper and lower bounds of each set.
O(1)仅适用于默认构造函数。O(n)用于复制构造函数和使用迭代器插入排序序列。O(log n!)使用迭代器插入未排序的序列。O(1)is only true for default constructor.O(n)for the copy constructors and sorted sequence insertion using iterators.O(log n!)for unsorted sequence insertion using iterators.好吧，如果您想完全开箱即用，您可以设计一个针对此任务自定义的“延迟加载”数组。基本上，在访问时，如果先前未设置该值，它将确定正确的值。
这将允许设置为 O(1) （假设初始化“先前未设置”标志本身为 O(1)），但不会加快整体操作 - 它只会将时间分散到其余的时间上运行（总体上可能需要更长的时间）。
Well, if you want to complately out of the box, you could design a "lazy-loaded" array, custom to this task. Basically, upon access, if the value had not been previously set, it would determine the correct value.
This would allow the setup to be O(1) (assuming inintialize the "not previously set" flags is itself O(1)), but wouldn't speed up the overall operation -- it would just scatter that time over the rest of the run (It would probably take longer overall).