473,545 Members | 305 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Delete from a std::set in amortized constant time

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?
Jun 12 '07 #1
33 5522
desktop <ff*@sss.comwri tes:
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 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)
Jun 12 '07 #2
On 6/12/07 4:00 PM, in article f4**********@ne ws.net.uni-c.dk, "desktop"
<ff*@sss.comwro te:
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?
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

Jun 12 '07 #3
Dave Steffen wrote:
desktop <ff*@sss.comwri tes:
>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 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.

But you still need to do the following re balancing that can take O(lg
n) time
Jun 12 '07 #4

On 6/12/07 4:26 PM, in article f4**********@ne ws.net.uni-c.dk, "desktop"
<ff*@sss.comwro te:
Dave Steffen wrote:
>desktop <ff*@sss.comwri tes:
>>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 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.

But you still need to do the following re balancing that can take O(lg
n) time
But the amortized time for rebalancing an RB tree is O(1) - in another
words, a constant amount of time. So the C++ Standard's performance
requirements for deleting an item from a set can be met by implementing the
set with an RB tree.

Greg

Jun 13 '07 #5
Greg Herlihy wrote:
>

On 6/12/07 4:26 PM, in article f4**********@ne ws.net.uni-c.dk, "desktop"
<ff*@sss.comwro te:
>Dave Steffen wrote:
>>desktop <ff*@sss.comwri tes:

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 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.
But you still need to do the following re balancing that can take O(lg
n) time

But the amortized time for rebalancing an RB tree is O(1) - in another
words, a constant amount of time. So the C++ Standard's performance
requirements for deleting an item from a set can be met by implementing the
set with an RB tree.

Greg
The delete version in In Introduction To Algorithms by Thomas Cormen is
the version that takes a pointer to an element (not a key that first has
to be found).

But I can't see how you can avoid the O (lg n ) time since the
subroutine 'tree-successor' has a running time equal to the height of
the tree.
Jun 13 '07 #6
Greg Herlihy wrote:
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.
And the algorithm somehow manages to rebalance the tree in amortized
constant time?
Jun 13 '07 #7
On Jun 13, 1:00 am, desktop <f...@sss.comwr ote:
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.
No it doesn't. It says that the complexity is "amortized
constant". And in §21.1/2, it says clearly that "All of the
complexity requirements in this clause are stated solely in
terms of the number of operations on the contained objects."
I would expect that erase(q) requires one call to the destructor
of the object, and that is it. Which definitely makes it O(1);
I don't even know why there is an "amortized" in there.

The standard never makes any requirements with regards to time.
In a very real way, it can't; there are too many variables
involved that are beyond the control of the implementation.

--
James Kanze (GABI Software, from CAI) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jun 13 '07 #8
James Kanze wrote:
On Jun 13, 1:00 am, desktop <f...@sss.comwr ote:
>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.

No it doesn't. It says that the complexity is "amortized
constant". And in §21.1/2, it says clearly that "All of the
complexity requirements in this clause are stated solely in
terms of the number of operations on the contained objects."
I would expect that erase(q) requires one call to the destructor
of the object, and that is it. Which definitely makes it O(1);
I don't even know why there is an "amortized" in there.
Ok so when erase(p) is said to be amortized constant they exclude the
time used to re balance the tree which would result in logarithmic time.
Jun 13 '07 #9
desktop wrote:
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?
You don't read carefully enough.
According to the standard the function erase(T value) has log(N)
complexity where N is the number of elements. This function requires
searching.

And the function erase(iterator it) has constant complexity because
it doesn't require searching.

--
it's mail not fail
Jun 13 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

26
1514
by: Michael Klatt | last post by:
I am trying to write an iterator for a std::set that allows the iterator target to be modified. Here is some relvant code: template <class Set> // Set is an instance of std::set<> class Iterator { public : typedef typename Set::value_type T; typedef typename Set::iterator SetIterator; Iterator(Set& container, const SetIterator& it);
7
2639
by: ma740988 | last post by:
The position returned via the STL std::set container never made much sense to me. When you insert elements within the container, the position returned - via find - does not reflect the actual position of the value within the container. std::string - for instance - does. How then do I get the actual position of the value when using std::set?...
8
11107
by: gipsy boy | last post by:
I've got a std::set with a custom comparator. When I add things, it puts them in the right place. When I change these objects (and I can tell they are effectively changed), the set doesn't 'auto-sort' with these changes. How can I do this? I store pointers in the set, but the comparator compares the contents of these pointers. -- - gipsy...
1
5053
by: Joe Gottman | last post by:
What are the advantages and disadvantages of the tree-based std::set versus the hash-based tr1::unordered_set? set advantages: 1) iterators remain valid after insert and erase (except for iterators to the erased element). 2) Sets can be compared using operator== or operator<. The STL set functions, (set_union, set_intersection, etc),...
10
7531
by: danibe | last post by:
I never had any problems storing pointers in STL containers such std::vector and std::map. The benefit of storing pointers instead of the objects themselves is mainly saving memory resources and performance (STL containers hold *copies* of what's passed to them via the insert() method). However, I am not sure how to accomplish that using...
12
3496
by: Marcus Kwok | last post by:
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...
26
7168
by: Lionel B | last post by:
Hi, Anyone know if the Standard has anything to say about the time complexity of size() for std::set? I need to access a set's size (/not/ to know if it is empty!) heavily during an algorithm and was thus wondering whether I'd be better off tracking the size "manually" or whether that'd be pointless. Thanks,
7
2573
by: desktop | last post by:
In the C++ standard page 472 it says that you can construct a std::set in linear time if the constructor gets a sorted sequence of elements. But how is this possible when insert takes logarithmic time? Should the time not be nlgn where n is the number of elements?
15
4126
by: desktop | last post by:
If I have a sorted std::list with 1.000.000 elements it takes 1.000.000 operations to find element with value = 1.000.000 (need to iterator through the whole list). In comparison, if I have a std::set with 1.000.000 element it will only take approx lg 1.000.000 = 20 operations! Can it really be true that the difference is a factor of...
0
7464
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7396
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7656
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
7805
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7413
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
5968
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
0
4943
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3449
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
1
1874
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.