From: Nathan Myers (ncm-yahoospam_at_[hidden])
Date: 2001-12-28 16:25:17
On Thu, 27 Dec 2001 13:53:27 -0500, "Beman Dawes" <bdawes_at_[hidden]> wrote:
> At 03:55 AM 12/27/2001, Nathan wrote:
>
> >On Wed, 26 Dec 2001 20:05:14 -0500, "Beman Dawes" <bdawes_at_[hidden]> wrote:
> >> Did you consider asserting or throwing on b < e precondition
> >> violations?
> >
> >As a precondition, it is a logical error to insert into the set elements
> >that are already present. The type std::set<> doesn't throw if you try
> >to insert the same element again.
>
> But std::set<> doesn't have a precondition that the element can't already
> be present, and has very well defined (ignore the insert) behavior if it is
> already present.
>
> I understand the reluctance to throw, but what about asserting on any of
> the preconditions where the complexity of testing the precondition is
> minimal? Sure it is just a QOI issue, but it does help users.
In practice the way you use these things is to insert a big range, and then
carve off pieces, returning them when you're finished. You know that a range
isn't included because you know what you have and where you got it.
Testing for b > e, or b >= e, is easy and cheap, but is a very unlikely
error. Checking has_all or !has_any is more likely to catch errors, but
is quite expensive.
> > Passing a range to std::set<> with the
> >iterators reversed does not result in an exception.
>
> No, but an implementation is free to assert on that, if detectable.
Do any?
> >I cannot imagine how client code could respond meaningfully to such an
> >exception.
>
> For precondition violations, asserts are often better that exceptions. But
> there has been past discussion where people pointed out cases where assert
> was desirable in debug builds, but they would like an exception in release
> mode.
Mm, they won't get that from the regular STL components.
What exception would you suggest? I am inclined to std::logic_error.
I have included some code to do the cheaper but less useful checks.
> >> What is the rationale for the insert precondition !has_any(b, e),
> >> and the erase precondition has_all(b, e)? (I'm just curious and
> >> not suggesting that looser preconditions would be better.)
> >
> >The preconditions radically simplify the logic of the insert and erase
> >members. They correspond, logically, to the requirement the same memory
> >not be passed to free() twice. More general functions that don't impose
> >such preconditions must contain a loop. They would be easy to add (along
>
> >with general set union, intersection, and complement-intersection), and I
> >expect that will happen eventually, but they would not be a substitute
> >for the more basic operations.
>
> Understood. You might want to add the above to Rationale or FAQ docs.
I will.
> >> The portion of the license which reads "Permission is granted for
> >> any use free of charge provided..." can be read two ways:
> >> ...
> >
> >I have edited the license to eliminate any ambiguity:
> >
> >// Copyright 2001 by Nathan C. Myers <ncm-nospam_at_[hidden]>.
> >// Permission is granted free of charge for any use provided that (1)
> >// this copyright notice is retained unchanged in its entirety, and
> >// (2) the author is indemnified, held harmless, and released from all
> >// responsibility for any consequences of such use.
> >
> >As I understand it this is the minimal license that allows unrestricted
> >use without exposing me to liability.
>
> Thanks for clarifying the wording.
>
> When first looking at extent_set yesterday, I thought I'd once had a need
> for something similar, but couldn't remember the details. It has now come
> back to me, but the half-open ranges would be a problem.
>
> The problem was a QA audit program for a map database to determine if there
> was overlap in house number ranges for various records representing
> segments of a street.
>
> Thus Bound would be a class named HouseNumber. About 99% of the streets in
> the US have unsigned numeric house numbers. But the other 1% have
> different numbering schemes, with very approximately 200 in common
> use. Thus HouseNumber isn't an integer, but rather a complex class capable
> of dealing with the numbering schemes.
>
> HouseNumber is "assignable, copyable, and equality-comparable, and
> comparable using the Compare operation" but it doesn't have any increment()
> or successor() operations because for some addressing schemes there is no
> valid result possible from such an operation. That means there isn't any
> way to form a half-open range, at least not without changing HouseNumber.
>
> A specific example would be single-character alphabetic house numbers
> running from A to Z. What is the half-open range? Z doesn't have a
> successor.
>
> One solution would be to modify the HouseNumber class to add a successor,
> with a special off-the-end value. That's uncomfortable; why should a type
> which meets the requirements still need modification? There are also some
> schemes with discontinuous (although orderable) schemes; they would be an
> additional headache.
>
> I guess the question this raises is whether or not a half-open range is the
> best way to specify ranges for arbitrary types? It's really natural for
> iterators, but seems unnatural at least for the HouseNumber application.
>
> Are there killer arguments in favor of half-open ranges for extent_set?
It bothered me too that the submitted version cannot represent membership of
MAXINT. I have an implementation of extent_set using closed ranges, but it
requires both successor and predecessor functions (n + 1 and n - 1), which
had seemed to me to limit extent_set<>'s application more than the half-open
ranges. (Either would work fine for my purposes.) Of course, instead of
literally "n + 1", it says "this->succ(n)", invoking an instantiation of
a template argument. That makes the interface a little more complicated.
I have posted the closed-range implementation in the files section, under
the names "extent_set-0.2.tgz" and "extent_set-0_2.zip". See
http://groups.yahoo.com/group/boost/files/extent_set/
It includes tests to ensure that the predecessor and successor functions
never try to generate a value that exceeds the range of the argument type.
Please let me know if you like it better.
Nathan Myers
ncm at cantrip dot org