插入std :: set [英] Inserting into std::set
问题描述
我不确定这是否是标准所涵盖的内容，或者
，如果它是我的标准库的实施细节。
我正在将大量数据读入std :: set。 std :: set :: insert（）有一个
重载，它将一个迭代器作为一个提示作为
到新值插入的位置，并且我的实现
（Dinkumware）说如果提示是好的（意味着迭代器在插入的值应该去之前或之后指向
）那么
插入可以在摊还的常数时间而不是对数时间内发生。
我想利用这个事实。我的输入数据应该已按排序顺序排列，因此我认为我可以使用my_set.end（）作为
提示插入（）。这是一个有效的假设，还是这取决于如何实际实现std :: set的
？
-
Marcus Kwok
将''invalid''替换为''net''以回复
I am not sure if this is something that is covered by the Standard, or
if it''s an implementation detail of my Standard Library.
I am reading in a large amount of data into a std::set. There is an
overload for std::set::insert() that takes in an iterator as a hint as
to where the new value should be inserted, and my implementation
(Dinkumware) says that if the hint is good (meaning the iterator points
immediately before or after where the inserted value should go) then the
insertion can happen in amortized constant time rather than logarithmic
time.
I would like to take advantage of this fact. My input data should
already be in sorted order, therefore I think I can use my_set.end() as
the hint to insert(). Is this a valid assumption, or does this depend
on how std::set is actually implemented?
--
Marcus Kwok
Replace ''invalid'' with ''net'' to reply
推荐答案
10月26日星期四2006 18:48:57 +0000（UTC）comp.lang.c ++，
ri ****** @ gehennom.inva lid（Marcus Kwok）写道，
On Thu, 26 Oct 2006 18:48:57 +0000 (UTC) in comp.lang.c++,
ri******@gehennom.invalid (Marcus Kwok) wrote,
>我想利用这个事实。我的输入数据应该已按排序顺序排列，因此我认为我可以使用my_set.end（）作为插入（）的提示。这是一个有效的假设，还是这取决于如何实际实现std :: set？
>I would like to take advantage of this fact. My input data should
already be in sorted order, therefore I think I can use my_set.end() as
the hint to insert(). Is this a valid assumption, or does this depend
on how std::set is actually implemented?
听起来对我有效。但是，我认为我更愿意使用前一个insert（）调用返回的
迭代器。
Sounds valid to me. However, I think that I would prefer to use the
iterator returned by the previous insert() call.
Marcus Kwok写道：
Marcus Kwok wrote:
我不确定这是否是标准涵盖的内容，或者
如果它是一个实现细节我的标准库。
我正在将大量数据读入std :: set。 std :: set :: insert（）有一个
重载，它将一个迭代器作为一个提示作为
到新值插入的位置，并且我的实现
（Dinkumware）说如果提示是好的（意思是迭代器
在插入值之前或之后立即指向
去）那么插入可以在摊销的恒定时间内发生，而不是对数时间。
我想利用这个事实。我的输入数据应该已按排序顺序排列，因此我认为我可以使用my_set.end（）
作为insert（）的提示。这是一个有效的假设，还是这个
取决于std :: set是如何实际实现的？
I am not sure if this is something that is covered by the Standard, or
if it''s an implementation detail of my Standard Library.
I am reading in a large amount of data into a std::set. There is an
overload for std::set::insert() that takes in an iterator as a hint as
to where the new value should be inserted, and my implementation
(Dinkumware) says that if the hint is good (meaning the iterator
points immediately before or after where the inserted value should
go) then the insertion can happen in amortized constant time rather
than logarithmic time.
I would like to take advantage of this fact. My input data should
already be in sorted order, therefore I think I can use my_set.end()
as the hint to insert(). Is this a valid assumption, or does this
depend on how std::set is actually implemented?
为什么不用双手尝试并比较你的程序花费的时间
来形成你的''套餐'' ？
V
-
请在通过电子邮件回复时删除资金'A'
我没有回应最热门的回复，请不要问
Why don''t you try it both ways and compare the time it takes your program
to form your ''set''?
V
--
Please remove capital ''A''s when replying by e-mail
I do not respond to top-posted replies, please don''t ask
Marcus Kwok写道：
[使用插入std :: set时的提示
Victor Bazarov< v。******** @ comacast.netwrote：
Marcus Kwok wrote:
[using a hint when inserting into std::set]
Victor Bazarov <v.********@comacast.netwrote:
为什么你不尝试两种方式并比较你的程序花费的时间
来形成你的''set''？
Why don''t you try it both ways and compare the time it takes your program
to form your ''set''?
好的，所以我测试了我的代码的三个不同版本：一个没有提示
，我使用my_set.end （）作为提示，并且我将使用上一次迭代返回的迭代器作为提示。所有
都非常接近。有趣的是，没有提示的那个实际上是最快的，但是只比使用end（）稍快一点，因为
提示（我会认为它们是相同的，因为我的
计时结果的分辨率）。同样有趣的是使用之前的
插入'迭代器的那个是最慢的，但只有大约3％。
由于时间差异是相当可以忽略不计（也不是因为我同时运行其他进程而确定
），我认为我只会坚持使用简单版本的insert（），因为它是最简单的
。
-
Marcus Kwok
替换''无效''与''net''回复
OK, so I tested three different versions of my code: one where no hint
is supplied, one where I use my_set.end() as the hint, and one where I
use the iterator returned from the previous iteration as the hint. All
of them were pretty close. Interestingly, the one with no hint was
actually the fastest, but only very slightly faster than using end() as
the hint (I will consider them the same due to the resolution of my
timing results). Also interesting was that the one using the previous
insertion''s iterator was the slowest, but only by about 3%.
Since the timing differences are fairly negligible (and also not
definitive since I had other processes running at the same time), I
think I will just stick to the simple version of insert(), since it is
the clearest.
--
Marcus Kwok
Replace ''invalid'' with ''net'' to reply
这篇关于插入std :: set的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
