473,289 Members | 1,875 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,289 software developers and data experts.

STL set question

Hello,

I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.

Does somebody know why?

Regards
Jiri Palecek

Jun 1 '06 #1
5 2599
jp******@web.de wrote:
I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.

Does somebody know why?


If I had to guess, I'd say that there was no [perceived] need in it.
Since the set is a sorted container, and is most likely organized as
a directed graph (tree), it is on average no faster to search for
a given item starting from some node than from the root.

You can ask about rationale behind any decision made WRT Standard and
the Library in comp.std.c++.

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Jun 1 '06 #2
jp******@web.de wrote:

I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.

Does somebody know why?


First question should be, why insert with hint?
It's because the (in practice) standard implementation (red-black tree) allows
an optimisation that makes it at best constant time rather than log time
to find the place to insert.
Again, why provide it rather than just plain insert(key)?
I guess because insertion is so often done in batches, and keys to be inserted
are so often pre-sorted (roughly or completely, eg in a file),
so it makes general sense to use the iterator returned from last insert as hint.

Why not find with hint then? The more common use of searches is probably
that they are one-off operations with random input (eg user-provided keys).
There could probably be valid use cases where find with hint would be good
to have, eg to look up a list of two-letter words in a full OED dictionary.
In this case the range you get from lower_bound(firstKey), upper_bound(lastKey)
would not be of much help. But if the batch of keys to find is so small,
the sum of find operations is not so expensive...

So, it may have been deemed that it's not common enough to warrant the extra effort.
Again I'm guessing the reasoning of standard committee without looking at facts.

If you really want to know, Stroustrup's "Design and Evolution of C++" may
provide answers, and is anyway certainly a good read (near top of my reading list)
Hope it helps more than confuses

homsan
(privatdozent of speculative statistics)
Jun 1 '06 #3
jp******@web.de wrote:
Hello,

I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.

Does somebody know why?

Regards
Jiri Palecek


Hello Jiri,

You can use the std:: find algorithm. But I can't say if this is the
best and/or fastest way. The example below won't compile because
SomeObject has some methods missing. It's only meant as a hint.

#include <set>
#include <algorithm>

class SomeObject {
};

void func()
{
std::set<SomeObject> myset;
myset.insert(SomeObject("first"));
myset.insert(SomeObject("second"));
myset.insert(SomeObject("third"));

std::set<SomeObject>::const_iterator iter;
iter = std::find(myset.begin(), myset.end(), SomeObject("second));

if (iter != myset.end()) {
iter->doSomething();
}
}
--
Regards
Daniel Kay
Jun 1 '06 #4
Daniel Kay wrote:
jp******@web.de wrote:
Hello,

I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.

Does somebody know why?

Regards
Jiri Palecek


Hello Jiri,

You can use the std:: find algorithm. But I can't say if this is the
best and/or fastest way. The example below won't compile because
SomeObject has some methods missing. It's only meant as a hint.

#include <set>
#include <algorithm>

class SomeObject {
};

void func()
{
std::set<SomeObject> myset;
myset.insert(SomeObject("first"));
myset.insert(SomeObject("second"));
myset.insert(SomeObject("third"));

std::set<SomeObject>::const_iterator iter;
iter = std::find(myset.begin(), myset.end(), SomeObject("second));

if (iter != myset.end()) {
iter->doSomething();
}
}
--
Regards
Daniel Kay


Sorry, that I wasn't answering your question. I didn't read your post
correctly. I think it's time to go to bed... ;-)

--
Regards,
Daniel Kay
Jun 1 '06 #5

homsan toft wrote:
jp******@web.de wrote:

I know there is a method "insert with hint" int std::set. But there
isn't anything similar for find and erase.

Does somebody know why?
First question should be, why insert with hint?
It's because the (in practice) standard implementation (red-black tree) allows
an optimisation that makes it at best constant time rather than log time
to find the place to insert.
Again, why provide it rather than just plain insert(key)?
I guess because insertion is so often done in batches, and keys to be inserted
are so often pre-sorted (roughly or completely, eg in a file),
so it makes general sense to use the iterator returned from last insert as hint.


I had known that. This is why I asked the question. BTW not only
RB-trees have this property, and I would not call this an optimization,
as the structure and operations are not changed. To be more specific,
almost any structure will let you find a place to insert in O(1) time
provided you have the iterator, but the point is that the rebalancing
phase of the insert AND delete (even when mixed) is amortized
constant time.
Why not find with hint then? The more common use of searches is probably
that they are one-off operations with random input (eg user-provided keys).
There could probably be valid use cases where find with hint would be good
to have, eg to look up a list of two-letter words in a full OED dictionary.
In this case the range you get from lower_bound(firstKey), upper_bound(lastKey)
would not be of much help. But if the batch of keys to find is so small,
the sum of find operations is not so expensive...


Well, I was thinking about other uses. For erase, you could do eg.
set difference (that is A:=A-B) in mostly linear time or
size(B)*log(size(A)), whichever is smaller. For find, you could do
joins of two sets (write all adresses of people whose surnames
are in some set). Also, you could implement the other two in
terms of find with hint and normal insert/erase.

Regards
Jiri Palecek

Jun 2 '06 #6

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

Similar topics

1
by: Mohammed Mazid | last post by:
Can anyone please help me on how to move to the next and previous question? Here is a snippet of my code: Private Sub cmdNext_Click() End Sub Private Sub cmdPrevious_Click() showrecord
3
by: Stevey | last post by:
I have the following XML file... <?xml version="1.0"?> <animals> <animal> <name>Tiger</name> <questions> <question index="0">true</question> <question index="1">true</question> </questions>
7
by: nospam | last post by:
Ok, 3rd or is it the 4th time I have asked this question on Partial Types, so, since it seems to me that Partial Types is still in the design or development stages at Microsoft, I am going to ask...
3
by: Ekqvist Marko | last post by:
Hi, I have one Access database table including questions and answers. Now I need to give answer id automatically to questionID column. But I don't know how it is best (fastest) to do? table...
10
by: glenn | last post by:
I am use to programming in php and the way session and post vars are past from fields on one page through to the post page automatically where I can get to their values easily to write to a...
10
by: Rider | last post by:
Hi, simple(?) question about asp.net configuration.. I've installed ASP.NET 2.0 QuickStart Sample successfully. But, When I'm first start application the follow message shown. ========= Server...
53
by: Jeff | last post by:
In the function below, can size ever be 0 (zero)? char *clc_strdup(const char * CLC_RESTRICT s) { size_t size; char *p; clc_assert_not_null(clc_strdup, s); size = strlen(s) + 1;
56
by: spibou | last post by:
In the statement "a *= expression" is expression assumed to be parenthesized ? For example if I write "a *= b+c" is this the same as "a = a * (b+c)" or "a = a * b+c" ?
2
by: Allan Ebdrup | last post by:
Hi, I'm trying to render a Matrix question in my ASP.Net 2.0 page, A matrix question is a question where you have several options that can all be rated according to several possible ratings (from...
3
by: Zhang Weiwu | last post by:
Hello! I wrote this: ..required-question p:after { content: "*"; } Corresponding HTML: <div class="required-question"><p>Question Text</p><input /></div> <div...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
Hello Experts! I have written a code in MS Access for a cmd called "WhatsApp Message" to open WhatsApp using that very code but the problem is that it gives a popup message everytime I clicked on...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: marcoviolo | last post by:
Dear all, I would like to implement on my worksheet an vlookup dynamic , that consider a change of pivot excel via win32com, from an external excel (without open it) and save the new file into a...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...

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.