Using std::set::insert(hint p, e) ("hairy")

[desktop]

I am currently trying to implement std::set::insert(hint p, e).

On this page:

http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4

3 cases are mentioned and if they are fulfilled the new element e can be
inserted in amortized constant time:

# begin(), then the item being inserted should have a key less than all
the other keys in the container. The item will be inserted at the
beginning of the container, becoming the new entry at begin().

# end(), then the item being inserted should have a key greater than all
the other keys in the container. The item will be inserted at the end of
the container, becoming the new entry at end().

# neither begin() nor end(), then: Let h be the entry in the container
pointed to by hint, that is, h = *hint. Then the item being inserted
should have a key less than that of h, and greater than that of the item
preceding h. The new item will be inserted between h and h's predecessor

I the last case it only applies if the key e are less that *h but
greater than --*h corresponding to this example:

4 6 8
--h h

if e = 5 insert between 4 and 6 in amortized constant time.

But what if e = 7 why is it not possible to insert in amortized constant
time between 6 and 8?

 

[Zeppe]

I am currently trying to implement std::set::insert(hint p, e).

On this page:

http://gcc.gnu.org/onlinedocs/libstdc++/23_containers/howto.html#4

3 cases are mentioned and if they are fulfilled the new element e can be
inserted in amortized constant time:

# begin(), then the item being inserted should have a key less than all
the other keys in the container. The item will be inserted at the
beginning of the container, becoming the new entry at begin().

# end(), then the item being inserted should have a key greater than all
the other keys in the container. The item will be inserted at the end of
the container, becoming the new entry at end().

# neither begin() nor end(), then: Let h be the entry in the container
pointed to by hint, that is, h = *hint. Then the item being inserted
should have a key less than that of h, and greater than that of the item
preceding h. The new item will be inserted between h and h's predecessor

I the last case it only applies if the key e are less that *h but
greater than --*h corresponding to this example:

4 6 8
--h h

if e = 5 insert between 4 and 6 in amortized constant time.

But what if e = 7 why is it not possible to insert in amortized constant
time between 6 and 8?

I think the concept expressed in the text you quoted it's simple. If you
provide the insert method with the right position of the element, it's
inserted in constant time. If you don't, it has to find the right
position and it will take log n. if you have e = 7, you have to give the
correct hint (*h = 8) to obtain the speedup.

Regards,

Zeppe

 

[desktop]

I think the concept expressed in the text you quoted it's simple. If you
provide the insert method with the right position of the element, it's
inserted in constant time. If you don't, it has to find the right
position and it will take log n. if you have e = 7, you have to give the
correct hint (*h = 8) to obtain the speedup.

Regards,

Zeppe

But why not just supply hint *h = 6 and check if e > *h and e < *h++ =
8? I don't understand why it only works with leftmost comparisons.

 

[Zeppe]

But why not just supply hint *h = 6 and check if e > *h and e < *h++ =
8? I don't understand why it only works with leftmost comparisons.

Because it would require additional time. The concept is: if you know
the position, give the hint as the position of the smallest bigger node.
Otherwise, a normal correct position search is performed. Of course, the
position that you give is checked for correctness, but it's a small
effort (just one additional comparison).

Regards,

Zeppe

 

[desktop]

Because it would require additional time. The concept is: if you know
the position, give the hint as the position of the smallest bigger node.
Otherwise, a normal correct position search is performed. Of course, the
position that you give is checked for correctness, but it's a small
effort (just one additional comparison).

Regards,

Zeppe

Ok so the reason that you don't both do a "left" (compare with h--) and
"right" (compare with h++) comparison is that it saves time to just make
one of them?

Are these kind of comparisons not made in constant time independently of
the size of the input?

 

[Zeppe]

Ok so the reason that you don't both do a "left" (compare with h--) and
"right" (compare with h++) comparison is that it saves time to just make
one of them?

Are these kind of comparisons not made in constant time independently of
the size of the input?

Sure they are... but constant time is not "no time". Consider that log n
is usually a quite small value... for a 32 items graph log n is 5, which
means that with 5 comparisons the exact position is found with a
classical search. The insert has to do two comparisons when the hint is
supplied. If also the right comparison were done, there will be 3
comparisons... we are approaching the performances for the insertion
without hint!

You may object that the time-saving would be high for high graphs, for
example for 1 million of items log n is around 20. But for one million
of items, if the correct position is not that one that you provided with
the hint, it's very unlikely that it is "around that point" (i.e., on
the left, or two on the left, or two on the right..). If you know where
to insert the node, provide the right position (the first greater node),
otherwise, do not tell anything, it will be faster by itself.

Regards,

Zeppe

 

[desktop]

Sure they are... but constant time is not "no time". Consider that log n
is usually a quite small value... for a 32 items graph log n is 5, which
means that with 5 comparisons the exact position is found with a
classical search. The insert has to do two comparisons when the hint is
supplied. If also the right comparison were done, there will be 3
comparisons... we are approaching the performances for the insertion
without hint!

Very clear explanation, thanks!