From -5434611709427160917 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,bc82bd0900b8b4ac X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 2000-12-20 12:43:02 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: brangdon@cix.compulink.co.uk (Dave Harris) Newsgroups: comp.std.c++ Subject: Re: Feature Request: Fast "find" for sorted random access containers Date: Wed, 20 Dec 2000 20:42:44 GMT Organization: BT Internet Approved: Fergus Henderson , moderator of comp.std.c++ Message-ID: References: Reply-To: brangdon@cix.compulink.co.uk X-Trace: mail2news.demon.co.uk 977344974 mail2news:9609 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) Lines: 49 Xref: supernews.google.com comp.std.c++:3051 remove.haberg@matematik.su.se (Hans Aberg) wrote (abridged): > 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. Conditional jumps are usually more efficient than indirect ones, so "if" statements can be more efficient than "switch" statements if the "switch" is implemented that way. In practice a small "switch" like: switch (c) { case less_than: /* */ break; case equals: /* */ break; case greater_than: /* */ break; } will probably be implemented by "if" statements anyway, so you don't gain anything. Indeed, you may find that the compiler generates a default case since the range of the enum includes a 4th value. Also you may find a comparison against -1 is marginally more expensive than a sign-test. Quite often it is natural for a comparison function to return < 0. For example: struct S { int x; int y; }; int compare( const S &a, const S &b ) { if (a.x != b.x) return a.x - b.x; return a.y - b.y; } (You have to watch for overflow, of course.) If we return compare_t instead we'd have to add extra conditional jumps. Dave Harris, Nottingham, UK | "Weave a circle round him thrice, brangdon@cix.co.uk | And close your eyes with holy dread, | For he on honey dew hath fed http://www.bhresearch.co.uk/ | And drunk the milk of Paradise." --- [ 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. ]