From 6841729399156904661 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,bc82bd0900b8b4ac X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 2000-12-20 11:05:04 PST Path: supernews.google.com!sn-xit-02!supernews.com!news-x.support.nl!colt.net!dispose.news.demon.net!demon!news.demon.co.uk!demon!mail2news.demon.co.uk!not-for-mail From: jthill@telus.net (Jim Hill) Newsgroups: comp.std.c++ Subject: Re: Feature Request: Fast "find" for sorted random access containers Date: Wed, 20 Dec 2000 19:04:01 GMT Organization: biological <-- hey! a one-word oxymoron! Approved: Fergus Henderson , moderator of comp.std.c++ Message-ID: <1elxn3k.l6pl5i10qjnnkN%jthill@telus.net> References: X-Trace: mail2news.demon.co.uk 977339048 mail2news:5770 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-Server-Date: 20 Dec 2000 18:55:06 GMT User-Agent: MacSOUP/2.4.6 Lines: 71 Xref: supernews.google.com comp.std.c++:3050 Hans Aberg wrote: > In general one wants to avoid conditional sequences as jumps slows down > the CPU: Typically instructions are piped, and that pipe is broken by a > jump. This is certainly true, but I think you're missing crucial points: the library's complexity requirements are not arbitrary, and interfaces missing from the standard library are (pace idiocies) missing for precisely those non-arbitrary reasons. You wanted +/- on lists. You asked the impossible: look at the complexity requirements. This may seem flippant, but it's not intended to be so: if you can show how to do it, you will become the latest entry on a long list of those who have achieved the impossible and made the mortals look foolish once again. For another take on it, consider this: I see your point on convenience. I've got a "dts" namespace for hacking around, full of interfaces like using std::sort; template void sort( C &c ) { sort(c.begin(),c.end()); } template void sort( C &c, LT < ) { sort(c.begin(), c.end(), lt); } and I don't suppose I'm alone. It'd be nice to be able to use it in published code, because applying algorithms to a complete container is by far the most common usage. I can't, because it's not standard. Grumble..grumble... Right? I don't think so anymore. What it is, is "by far the most common _nonstandard_ usage". Where to stop is always going to be a compromise, and so is always going to be less than completely satisfying. You've found other such compromises. C'est la vie, n'est-ce pas? Both of the above considerations apply to > STL frequently uses a function > compare(x, y) <=> x < y > which takes a bool value. Thus if you only have "compare" available and > want to check that x == y, this must be done by checking that both > compare(x, y) & compare(y, x) are false. I've seen Stepanov's choice of strict weak ordering for the STL's core described as an act of genius. I don't know enough to agree or disagree with that, but I can see their point. Equal for what purpose? The STL supports arbitrary -- more than that, multiple, incompatible arbitrary purposes. When you don't need it, the navigation is decidedly inconvenient. I saw their point when I actually needed such a beast: a container with almost entirely unrelated iterator paths and equivalence relations. It took me days to realize the solution I was working out precisely matched the definitions of a couple of iterator categories. My way: hundreds of lines of code. With iterators, I haven't counted. A handful of declarations and one-liner definitions of the right operators, plus algorithms that look like textbook examples because they might as well be just that. Color me deeply, deeply impressed. My current opinion, for what it's worth, is that the standard library _shouldn't_ provide all those convenience interfaces. The time and thought necessary to implement them provides a tour of the structure that I look forward to taking again at intervals. Jim --- [ 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. ]