August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Arcane Jill | On Sat, 07 Aug 2004 20:26:05 +0000, Arcane Jill wrote:
> But we /can/ have our cake and eat it. [SUGGESTION:] Associative arrays don't
> need opCmp(). Honestly, they don't. Why not? - because the only thing AAs
> require is a sort criterion. That sort criterion does not have to be based on <.
> The current implementation of AAs is to sort based on (x < y), but then to have
> Object define < such that (x < y) is implemented as (&x < &y). So why not just
> have the sort criterion for AAs be (&x < &y) instead of (x < y)? If this were
I don't know how the AA algorithm works, but since &x != &y doesn't mean x
!= y, wouldn't using &x < &y not be kosher? In other words,
import AJ's bigint;
Int a = new Int(5);
Int b = new Int(5);
bit[Int] aa;
aa[a] = true;
if (aa[b])
printf("true\n\0");
else
printf("false\n\0");
That should print true, but if the AA is sorted using &a and &b, it could easily print false. Again, I don't know how the algorithm works, so this small example might work using the references, but with larger AAs, what's the point of sorting by a (basically) arbitrary and irrelevant number?
Or am I WAY off base? (If so, please explain)
Instead of using (x < y) I think the hash should be used, this way it can
be overridden by classes, since &x can't be overridden (and I really hope
I'm not wrong about that.)
John
|
August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to teqDruid | In article <pan.2004.08.08.08.43.07.193849@teqdruid.com>, teqDruid says... >That should print true, but if the AA is sorted using &a and &b, it could easily print false. Again, I don't know how the algorithm works, so this small example might work using the references, but with larger AAs, what's the point of sorting by a (basically) arbitrary and irrelevant number? > >Or am I WAY off base? (If so, please explain) No, you're right. Damn! >Instead of using (x < y) I think the hash should be used, this way it can >be overridden by classes, since &x can't be overridden (and I really hope >I'm not wrong about that.) I don't think that would work either, since hash(x) == hash(y) does not imply x == y. (Although obviously using hash() would work for a hashmap). What you need for AAs is a sort function for which precisely one of the following conditions is always true: either (a) x preceeds y; or (b) x == y; or (c) x succeeds y. Using (hash(x)<hash(y)) as the sort criterion would allow a fourth possibility: that (a), (b) and (c) are all simulataneously false. An AA would fall over if that possibility were encountered. So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map. C++ also provides std::hash_map, which requires storable objects to implement the function hash(). I wonder if AAs couldn't simply be re-implemented /as/ a hashmap? That way you don't need a sort criterion at all. It would require hash() to implemented for all storable objects though. Jill |
August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Arcane Jill | Arcane Jill wrote:
> In article <pan.2004.08.08.08.43.07.193849@teqdruid.com>, teqDruid says...
>
>>That should print true, but if the AA is sorted using &a and &b, it could easily print false. Again, I don't know how the algorithm works, so this small example might work using the references, but with larger AAs, what's the point of sorting by a (basically) arbitrary and irrelevant number?
>>
>>Or am I WAY off base? (If so, please explain)
>
> No, you're right. Damn!
>
>>Instead of using (x < y) I think the hash should be used, this way it can
>>be overridden by classes, since &x can't be overridden (and I really hope
>>I'm not wrong about that.)
>
> I don't think that would work either, since hash(x) == hash(y) does not
> imply x == y. (Although obviously using hash() would work for a hashmap).
> What you need for AAs is a sort function for which precisely one of the
> following conditions is always true: either (a) x preceeds y; or (b) x ==
> y; or (c) x succeeds y. Using (hash(x)<hash(y)) as the sort criterion
> would allow a fourth possibility: that (a), (b) and (c) are all
> simulataneously false. An AA would fall over if that possibility were
> encountered.
>
> So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map. C++ also provides std::hash_map, which requires storable objects to implement the function hash().
>
> I wonder if AAs couldn't simply be re-implemented /as/ a hashmap? That way you don't need a sort criterion at all. It would require hash() to implemented for all storable objects though.
>
> Jill
One can see how AAs are implemented by looking at src/phobos/internal/aaA.d It is a hash table with a nifty collision data structure (none of this slow linked-list collision stuff). I bet Walter has been tweaking it for years.
|
August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Arcane Jill | In article <cf5gq2$2uq4$1@digitaldaemon.com>, Arcane Jill says... > > So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map. Basing AAs on the user implemented opCmp is not a good idea, since it's behavior is not defined. I might for example have a group of objects which are all "equal" in the way I want to compare them (opCmp() always 0, opEquals() always true) but which contain entirely different data. The AAs should use the algorithm it already uses, but it should be implemented as part of the AA, not in Object. It's different for std::map, since it's defined and "advertised" as a _sorted_ container, placing certain restrictions on the input type (in the docs.) Also, STL always allows you to specify a custom ordering functor as an optional template parameter, so < and > might not be used at all if you don't want them to. This is a good practice for DTL to follow, btw :) > C++ also provides > std::hash_map, which requires storable objects to implement the function > hash(). The hash containers are not really part of C++, just in the SGI implementation (which gcc uses.) Nick |
August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Walter | In article <cf31k5$223l$2@digitaldaemon.com>, Walter says... > > >"Jarrett Billingsley" <kb3ctd2@yahoo.com> wrote in message news:cf2qfj$1toe$1@digitaldaemon.com... >> personally i don't see what's wrong with >> operator+() , but oh well. > >operator+ doesn't work when you need both the forward and the 'r' versions of an operator overload. Also, opCmp handles <, <=, >, >=. And lastly, opCmp is eminently greppable. > > i'd still prefer operator cmp() and similar. opAnything looks ugly. operator Anything() not (imho). but thats me.. and doesn't really mather |
August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick | "Nick" <Nick_member@pathlink.com> wrote in message news:cf5rd5$75$1@digitaldaemon.com... > In article <cf5gq2$2uq4$1@digitaldaemon.com>, Arcane Jill says... > > > > So I don't have an answer any more. The way that C++ does it (in std::map) is > > that the sort criterion is <, but < is not defined for everything, so if < isn't > > defined, you simply can't store your object in a std::map. > > Basing AAs on the user implemented opCmp is not a good idea, since it's behavior > is not defined. What do you mean by undefined behaviour? > I might for example have a group of objects which are all > "equal" in the way I want to compare them (opCmp() always 0, opEquals() always > true) but which contain entirely different data. The AAs should use the algorithm it already uses, but it should be implemented as part of the AA, not > in Object. Maybe your objects are strange? In most cases my for my classes the two objects are either a<b or a==b (or !(a<b)) > It's different for std::map, since it's defined and "advertised" as a _sorted_ > container, placing certain restrictions on the input type (in the docs.) I like it the way std::map dos things! > Also, > STL always allows you to specify a custom ordering functor as an optional > template parameter, so < and > might not be used at all if you don't want them > to. This is a good practice for DTL to follow, btw :) Yes it is! But what do you think about the subject of removing opCmp and opEquals from Object! They prevent us from writing templates that require these operators because there are default versions of these, and they probbably don't do what the author of the class wants! > > > C++ also provides > > std::hash_map, which requires storable objects to implement the function > > hash(). > > The hash containers are not really part of C++, just in the SGI implementation > (which gcc uses.) > > Nick > > |
August 08, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lars Ivar Igesund | "Lars Ivar Igesund" <larsivar@igesund.net> wrote in message news:cf3ik6$2abe$1@digitaldaemon.com... > Ivan Senji wrote: > > > opCmp shouldn't be discriminated this way! :) > > Ivan's correct. You got my vote. Hooray! Thanks. But: Walter is the one to say if i am correct or not and it seems to me he thinks i am wrong on this subject. :( > > Lars Ivar Igesund |
August 09, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Lars Ivar Igesund | Me too. I dislike the root class having things that derived classes (or their designers) cannot make informed choices on. And a runtime assert is a revolting way to denote that a type should not take part in comparison operations. "Lars Ivar Igesund" <larsivar@igesund.net> wrote in message news:cf3ik6$2abe$1@digitaldaemon.com... > Ivan Senji wrote: > > > opCmp shouldn't be discriminated this way! :) > > Ivan's correct. You got my vote. > > Lars Ivar Igesund |
August 09, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nick | "Nick" <Nick_member@pathlink.com> wrote in message news:cf5rd5$75$1@digitaldaemon.com... > In article <cf5gq2$2uq4$1@digitaldaemon.com>, Arcane Jill says... > > > > So I don't have an answer any more. The way that C++ does it (in std::map) is that the sort criterion is <, but < is not defined for everything, so if < isn't defined, you simply can't store your object in a std::map. > > Basing AAs on the user implemented opCmp is not a good idea, since it's behavior is not defined. I might for example have a group of objects which are all "equal" in the way I want to compare them (opCmp() always 0, opEquals() always true) but which contain entirely different data. The AAs should use the algorithm it already uses, but it should be implemented as part of the AA, not in Object. > > It's different for std::map, since it's defined and "advertised" as a _sorted_ container, placing certain restrictions on the input type (in the docs.) Also, STL always allows you to specify a custom ordering functor as an optional template parameter, so < and > might not be used at all if you don't want them to. This is a good practice for DTL to follow, btw :) Those prototypes are already in. (Just not implemented in most cases.) > > C++ also provides > > std::hash_map, which requires storable objects to implement the function > > hash(). > > The hash containers are not really part of C++, just in the SGI implementation > (which gcc uses.) |
August 09, 2004 Re: [Again] One big isue before 1.0 | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ivan Senji | "Ivan Senji" <ivan.senji@public.srce.hr> wrote in message news:cf3i3d$2a7r$3@digitaldaemon.com... > What is so special about opCmp, (ok it is used in AAs but couldn't compiler report: "this type cann't be used in AA because of the missing opCmp!") Putting it in Object reserves a predictable vtbl[] slot for it. |
Copyright © 1999-2021 by the D Language Foundation