从摊销的常量时间中的std :: set中删除 [英] Delete from a std::set in amortized constant time
问题描述
在C ++标准sec 23.1.2表69中，它表示擦除（q），其中q是
a指向元素的指针可以在分摊的常量时间内完成。
我猜这不是最糟糕的情况，因为std :: set实际上是一个红黑的
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is
a pointer to an element can be done in amortized constant time.
I guess that is not worst case since std::set is practically a red-black
tree where insert/delete takes O(lg n) time. Or are there some other
explanation for this complexity?
推荐答案
desktop< ff*@sss.comwrites：
desktop <ff*@sss.comwrites:
在C ++标准sec 23.1.2表69中它表示擦除（q）其中q
是指向元素的指针可以是以摊还的常数时间完成。
我猜这不是最糟糕的情况，因为std :: set实际上是一个
红黑树，其中插入/删除需要O（lg n）时间。或者是否有这种复杂性的其他解释？
？
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q
is a pointer to an element can be done in amortized constant time.
I guess that is not worst case since std::set is practically a
red-black tree where insert/delete takes O(lg n) time. Or are there
some other explanation for this complexity?
IIRC插入需要log n时间，因为你必须搜索正确的
位置才能插入它。
"删除此值"也需要记录时间，因为你必须搜索
来删除它。
在这种情况下，你已经知道要删除什么东西，因为你已经有了b $ b得到了一个迭代器。不需要搜索，只需摆弄
一些内部簿记。
-
Dave Steffen，Ph.D。不服从这个命令！
软件工程师IV - Douglas Hofstadter
Numerica Corporation
dgAsteffen aat dataa dAot us（删除A'给我发邮件） ）
IIRC insert takes log n time, since you have to search for the right
place to insert it.
"Remove this value" also takes log n time, since you have to search
for the thing to delete.
In this case, you already know what thing to delete, since you''ve
got an iterator to it. No searching required, just fiddling with
some internal bookkeeping.
--
Dave Steffen, Ph.D. Disobey this command!
Software Engineer IV - Douglas Hofstadter
Numerica Corporation
dgAsteffen aAt numerica dAot us (remove A''s to email me)
6月12日下午4:00，文章f4**********@news.net.uni-c.dk ，桌面
< ff*@sss.comwrote：
On 6/12/07 4:00 PM, in article f4**********@news.net.uni-c.dk, "desktop"
<ff*@sss.comwrote:
在C ++标准sec 23.1.2表69中它说擦除（q）其中q是
a指向一个元素的指针可以在摊还的常量时间内完成。
我想这不是最坏的情况，因为std： ：set实际上是一个红黑的
树，其中insert / delete占用O（lg n）时间。或者对于这种复杂性还有其他的解释吗？
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is
a pointer to an element can be done in amortized constant time.
I guess that is not worst case since std::set is practically a red-black
tree where insert/delete takes O(lg n) time. Or are there some other
explanation for this complexity?
解释很简单。测量一个节点时，节点的移除时间包括在树中找到要删除的节点所需的时间。
在这种情况下调用set :: erase（）时，不需要花时间搜索要删除的节点（即项目）的
，因为它的位置是
作为参数传递给擦除方法。因此，通过跳过搜索
项目，该项目能够以摊销常数（和
非对数）时间从集合中删除。
Greg
The explanation is simple. The removal time of a node when measured for an
RB tree includes the time needed to find the node to be deleted in the tree.
In this case of a call to set::erase(), no time needs to be spent searching
for the node (that is, the item) to be removed because its location is
passed to the erase method as a parameter. So by skipping the search for the
item, the item is able to be removed from the set in amortized constant (and
not logarithmic) time.
Greg
Dave Steffen写道：
Dave Steffen wrote:
desktop< ff*@sss.comwrites：
desktop <ff*@sss.comwrites:
>在C ++标准sec 23.1.2表69中，它表示擦除（q）其中q
是指向元素的指针可以在分摊的常量时间内完成。
我想这不是最坏的情况，因为std :: set实际上是一个红黑树，其中insert / delete需要O（ lg n）时间。还是对这种复杂性有其他解释吗？
>In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q
is a pointer to an element can be done in amortized constant time.
I guess that is not worst case since std::set is practically a
red-black tree where insert/delete takes O(lg n) time. Or are there
some other explanation for this complexity?
IIRC插入需要记录时间，因为你必须搜索正确的
位置才能插入它。
"删除此值"也需要记录时间，因为你必须搜索
来删除它。
在这种情况下，你已经知道要删除什么东西，因为你已经有了b $ b得到了一个迭代器。不需要搜索，只需摆弄
一些内部簿记。
IIRC insert takes log n time, since you have to search for the right
place to insert it.
"Remove this value" also takes log n time, since you have to search
for the thing to delete.
In this case, you already know what thing to delete, since you''ve
got an iterator to it. No searching required, just fiddling with
some internal bookkeeping.
但是你还需要做以下的重新平衡可以拿O（lg
n）时间
But you still need to do the following re balancing that can take O(lg
n) time
这篇关于从摊销的常量时间中的std :: set中删除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
