From 4995258534906872940 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,bc82bd0900b8b4ac X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 2000-12-18 11:01:19 PST Path: supernews.google.com!sn-xit-02!supernews.com!news.infoave.net!skynet.be!dispose.news.demon.net!demon!news.demon.co.uk!demon!mail2news.demon.co.uk!not-for-mail From: Herb Sutter Newsgroups: comp.std.c++ Subject: Re: Feature Request: Fast "find" for sorted random access containers Date: Mon, 18 Dec 2000 19:00:49 GMT Organization: PeerDirect Inc. Approved: Fergus Henderson , moderator of comp.std.c++ Message-ID: References: X-Trace: mail2news.demon.co.uk 977166055 mail2news:20215 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) X-Newsreader: Forte Agent 1.7/32.534 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit NNTP-Posting-Date: Mon, 18 Dec 2000 10:56:22 PST Lines: 35 Xref: supernews.google.com comp.std.c++:3023 remove.haberg@matematik.su.se (Hans Aberg) writes: >Summary: I suggest that the C++ std library is augmented with a >logarithmic time "find" function for use with sorted random access >containers. 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: > By contrast, a random access container in which the elements are known >to be sorted with respect to the comparison function can be searched in >logarithmic time, by successively halving intervals 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. Herb --- Herb Sutter (mailto:hsutter@peerdirect.com) CTO, PeerDirect Inc. (http://www.peerdirect.com) Contributing Editor, C/C++ Users Journal (http://www.cuj.com) --- [ 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. ]