From -5398222146942661216 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: f78e5,bc82bd0900b8b4ac X-Google-Attributes: gidf78e5,public X-Google-ArrivalTime: 2000-12-21 07:15:03 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: Thu, 21 Dec 2000 15:14:04 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 977411656 mail2news:19443 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: 76 Xref: supernews.google.com comp.std.c++:3056 remove.haberg@matematik.su.se (Hans Aberg) wrote (abridged): > > Indeed, you may find that the compiler generates a default case > > since the range of the enum includes a 4th value. > > One reason for having a type ordering = { less, equal, greater } is > that such switch staments can be fully checked [...] No. That is what I just said doesn't work. The reason is that enums have a range which includes unnamed values. From Stroustrup's C++PL: The range of an enumeration holds all the enumeration values rounded up to the nearest larger binary power minus 1. The range goes down to 0 if the smallest enumerator is non-negative and to the nearest lesser negative binary power if the smallest enumerator is negative. This defines the smallest bit-field capable of holding the enumerator values. This means the range is always a power of 2; we cannot have a range of just 3 values. Thus: enum order { less_than = -1, equal_to = 0, greater_than = 1 }; order x = order(-2); assert( x == -2 ); // OK. This is portable and well-defined. -2 belongs to the range even though it isn't a named value. Switch statements cannot assume that order expressions will never be -2. > There are no jumps needed, if the CPU has an instruction to extract the > sign of an int. -- I do not know if that is common though. I would write it as: order compare( const S &a, const S &b ) { if (a.x != b.x) return (a.x < b.x) ? less_than : greater_than; if (a.y != b.y) return (a.y < b.y) ? less_than : greater_than; return equal_to; } I should think the conditional operators would become jumps on most platforms. I would be surprised if any compiler got rid of the second "if". Although the full compare() would be useful in some algorithms, much of the time it would be used like: if (compare( a, b ) == less_than) ... in which case the straight-forward: bool operator<( const S &a, const S &b ) { return (a.x == b.x) ? (a.y < b.y) : (a.x < b.x); } will be maximally efficient, especially if it can be inlined. This is what the STL uses. I wouldn't be surprised if a good optimiser could reduce the common subexpressions even in the 3-way case. 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. ]