STL set question

[jpalecek]

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

 

[Victor Bazarov]

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

 

[homsan toft]

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)

 

[Daniel Kay]

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();
}
}

 

[Daniel Kay]

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();
}
}

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

 

[jpalecek]

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