From 3794600023975542404 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,bc82bd0900b8b4ac X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 2000-12-19 02:45:05 PST Path: supernews.google.com!sn-xit-02!supernews.com!router1.news.adelphia.net!cyclone.news.idirect.com.MISMATCH!newsfeed.direct.ca!look.ca!dispose.news.demon.net!demon!news.demon.co.uk!demon!mail2news.demon.co.uk!not-for-mail From: remove.haberg@matematik.su.se (Hans Aberg) Newsgroups: comp.std.c++ Subject: Re: Feature Request: Fast "find" for sorted random access containers Date: Tue, 19 Dec 2000 10:44:07 GMT Organization: Mathematics Approved: Fergus Henderson , moderator of comp.std.c++ Message-ID: References: X-Trace: mail2news.demon.co.uk 977222657 mail2news:25404 mail2news mail2news.demon.co.uk X-Complaints-To: abuse@demon.net X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) NNTP-Posting-Date: 18 Dec 2000 21:51:33 GMT Lines: 70 Xref: supernews.google.com comp.std.c++:3027 In article , Herb Sutter wrote: >I don't disagree that this is a good idea, but they already exist -- >binary_search, lower_bound, upper_bound, and equal_range. They do what you >want, but they're even slicker, to wit: On these one does not get to know if the iterator is the element sought, probably great if the idea is to keep the list sorted, and one only want to find the place where to insert new elements; but otherwise, one will have to throw in an extra equality test with these. >The nice thing about these functions is that they behave as you want them to >if the iterators are indeed random-access, but if you happen to supply >forward or bidirectional iterators the algorithms will automatically switch >to linear mode. Interestingly, in both cases they always use O(logN) >comparisons -- the only thing that depends on the iterator category is O(N) >vs. O(logN) steps through the range. For some reason, one has not bothered implementing +, - on containers such as list and their iterators with respect to the iterator difference_type; if one had done that, this feature would have been automatic. That is, one could have written template ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value) { iterator_traits::difference_type len = last - first, half; ForwardIterator middle; while (len > 0) { middle = first + len / 2; if (*middle < value) { first = middle + 1; len = len - half - 1; } else len = half; } return first; } also for say lists. -- While at it, I think that comparison functions should return a value in a type { less_than, equal, greater_than } which could be equal t { -1, 0, 1 }. Right now there seems to be two types of comparison functions: First those like string::compare which one does not get to know which value they return, only >0 or <0, which means that they cannot be used directly in a switch statement. And second the STL comparisons functions which does not allow one to determine equality in one comparison. It is a bit inconsistent. Hans Aberg * Anti-spam: remove "remove." from email address. * Email: Hans Aberg * Home Page: * AMS member listing: --- [ 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. ]