"Hans Aberg" <remove.haberg@matematik.su.se> wrote
>
> The std associative containers (like std::map) have an insert function
> where one can indicate a suggestion of where the search can start, but
> there is no such corresponding "find" function.
>
> [comp.std.c++] Why is there no such function in the standard?

For insert() the only way to get the O(1) benefit is to have the member
function.  You can't get it from outside the class.

For find() you can get the O(1) benefit by externally incrementing or
decrementing the hint and doing the compare yourself.

I'd hate to suggest that the library interface is minimal.  However if you
can do something without adding to the interface, it is somewhat less likely
that the interface will be extended.

Of course if there is an algorithm that works only with knowledge of the
data structure ...


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <CIjf7.186$Hn3.78514@nnrp3.sbc.net>, Bill Wade
<wrwade@swbell.net> wrote:
>> The std associative containers (like std::map) have an insert function
>> where one can indicate a suggestion of where the search can start, but
>> there is no such corresponding "find" function.
>> ... Why is there no such function in the standard?

>For insert() the only way to get the O(1) benefit is to have the member
>function.  You can't get it from outside the class.

>For find() you can get the O(1) benefit by externally incrementing or
>decrementing the hint and doing the compare yourself.

As you note, the standard only indicates a O(1) complexity for the insert,
in which case it is useless to have a similar function for find.

I just tacitly assumed the complexity would be O(log n), where n is the
distance between the guess and the correct iterator (or the size of the
container, but with a smaller complexity constant).

The insert function is clearly constructed for adjacent inserts and
nothing else.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

In article <3B7547AC.3F88BBBC@worldnet.att.net>, "Bruce G. Stewart"
<bruce.g.stewart@worldnet.att.net> wrote:
>For the example problem you provided, finding the longest prefix of a
>given string, (if I understand your requirement correctly,) it would
>seem reasonable to use upper-bound, and then examine the element before
>the position that was found.

This does not work:

Suppose the container has the strings "ab", "abd", and "abf", and the
input string is "abe". Then upper_bound will return an iterator to "abf",
and the string before that is "abd", whereas the correct answer is the
string before that, "ab". Then one will have to step backwards even
further, at best in linear time, even though it is simpler to do it using
lower_bound, stepping forwards, also in linear time.

So I still think that the correct method is to successively check longer
strings, using the old iterators as suggestions for a new search.

Then logarithmic time ought to be possible if std::map had search
functions with iterator suggestions.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Hans Aberg wrote:
>
> In article <3B7547AC.3F88BBBC@worldnet.att.net>, "Bruce G. Stewart"
> <bruce.g.stewart@worldnet.att.net> wrote:
> >For the example problem you provided, finding the longest prefix of a
> >given string, (if I understand your requirement correctly,) it would
> >seem reasonable to use upper-bound, and then examine the element before
> >the position that was found.
>
> This does not work:
>
> Suppose the container has the strings "ab", "abd", and "abf", and the
> input string is "abe". Then upper_bound will return an iterator to "abf",
> and the string before that is "abd", whereas the correct answer is the
> string before that, "ab". Then one will have to step backwards even
> further, at best in linear time, even though it is simpler to do it using
> lower_bound, stepping forwards, also in linear time.
>
> So I still think that the correct method is to successively check longer
> strings, using the old iterators as suggestions for a new search.
>
> Then logarithmic time ought to be possible if std::map had search
> functions with iterator suggestions.

Sorry, I confused myself.

In any event, the implementations of map that I have seen use some form
of balanced trees. I guess the algorithm could walk up the tree until
the hint node is to the left, then search that subtree. It's more
reasonable than I thought at first.


If you end up doing repeated probing for various sized prefixes of
sizeable strings, and there is a strong probability that a prefix of
considerable size will be found, it might improve things to probe for
half the string, then 1/4 or 3/4 depending on what's found, etc. That
way, the number of probes will be O(lg length). OTOH, if you expect the
prefixes to be very short, that obviously won't help. I am drifting off
topic, so I will stop now.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

[Replies can zip out one of the newsgroups, depending on which question
you answer.]

The std associative containers (like std::map) have an insert function
where one can indicate a suggestion of where the search can start, but
there is no such corresponding "find" function. Two questions:

[comp.std.c++] Why is there no such function in the standard?
[comp.lang.c++.moderated] What is the suggested workaround?

An example where I think such a "find" function might be useful is if one
has a map where the keys are strings, and given an input stream wants to
find the longest match among the keys in that map. One then reads a
character one-by-one, and applies lower_bound, and if the so found
iterator is not right the so found iterator is the guess for the next try.
One does not want to apply lower_bound in every new try, as that is too
inefficient.

  Hans Aberg      * Anti-spam: remove "remove." from email address.
                  * Email: Hans Aberg <remove.haberg@member.ams.org>
                  * Home Page: <http://www.matematik.su.se/~haberg/>
                  * AMS member listing: <http://www.ams.org/cml/>

      [ Send an empty e-mail to c++-help@netlab.cs.rpi.edu for info ]
      [ about comp.lang.c++.moderated. First time posters: do this! ]

[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]
[ Note that the FAQ URL has changed!  Please update your bookmarks.     ]

Hans Aberg wrote:
>
> [Replies can zip out one of the newsgroups, depending on which question
> you answer.]
>
> The std associative containers (like std::map) have an insert function
> where one can indicate a suggestion of where the search can start, but
> there is no such corresponding "find" function. Two questions:
>
> [comp.std.c++] Why is there no such function in the standard?
> [comp.lang.c++.moderated] What is the suggested workaround?

>From the description of insert, it appears that the "hint" argument is
meant to be implemented in the following manner: "test whether the
inserted element belongs in the position after the hint iterator. If it
does, insert it there and return. Otherwise, proceed as if no hint had
been given."

In the case of find, one can easily accomplish this by comparing the
search key with the item after the hint, and only calling "find" if that
test fails.

For the example problem you provided, finding the longest prefix of a
given string, (if I understand your requirement correctly,) it would
seem reasonable to use upper-bound, and then examine the element before
the position that was found.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]