While it was 2/12/04 8:52 PM throughout the UK, Sean Kelly sprinkled
little black dots on a white screen, and they fell thus:

<snip>
>> That would make sense if the associative array were implemented as a binary search tree.  But it shouldn't be trying to do this anyway if it can't be sure first that a comparator is defined.
> 
> 
> But the same holds for equality comparison, unless references don't support any other comparison method?

I'm not quite sure what you mean by that.

<snip>
> I was making assumptions.  I figured the back-end would be implemented as some sort of tree structure for efficiency, which wouldn't be compatible with equality comparisons.

I'd expect the typical implementation to be a hash table, if it isn't
going to require the key type to be ordered.

Of course, you could have a hash tree, but I'm not sure if there'd be
much point in that....

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the
unfortunate victim of intensive mail-bombing at the moment.  Please keep
replies on the 'group where everyone may benefit.

Stewart Gordon wrote:
>
> While it was 2/12/04 8:52 PM throughout the UK, Sean Kelly sprinkled
> little black dots on a white screen, and they fell thus:
>
>> But the same holds for equality comparison, unless references don't support any other comparison method?
> 
> I'm not quite sure what you mean by that.

If a reference is roughly equivalent to a pointer then it's possible it could be compared using all the normal numeric methods.  However I think some languages restrict comparisons to equality only as the pointers may reference separate memory spaces.

> I'd expect the typical implementation to be a hash table, if it isn't
> going to require the key type to be ordered.

True.  And in that case it may indeed use equality.


Sean

While it was 2/13/04 4:50 PM throughout the UK, Sean Kelly sprinkled little black dots on a white screen, and they fell thus:

<snip>
> If a reference is roughly equivalent to a pointer then it's possible it could be compared using all the normal numeric methods.  However I think some languages restrict comparisons to equality only as the pointers may reference separate memory spaces.

I don't know much about this, but C and C++ seem to support inequality operations on pointers.  Not sure what would constitute "separate memory spaces".

But that doesn't affect the fact, that surely it should be comparing the objects, not the pointers?

>> I'd expect the typical implementation to be a hash table, if it isn't
>> going to require the key type to be ordered.
> 
> True.  And in that case it may indeed use equality.

Indeed, should use equality.  I can't see any reason that Walter would've copied the eccentric behaviour of STL containers just for the sake of it.  And indeed, I tried defining opCmp but it made no difference.  What would be the point of having an equality operator if you're not going to use it?

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:
>
> I don't know much about this, but C and C++ seem to support inequality operations on pointers.  Not sure what would constitute "separate memory spaces".

By that I meant a pointer to a memory-mapped file vs. a pointer to main memory.  In such cases, a less-than comparison is meaningless.

> But that doesn't affect the fact, that surely it should be comparing the objects, not the pointers?

Yes it should, but apparently that isn't how it's currently working.

>>> I'd expect the typical implementation to be a hash table, if it isn't
>>> going to require the key type to be ordered.
>>
>> True.  And in that case it may indeed use equality.

> Indeed, should use equality.  I can't see any reason that Walter would've copied the eccentric behaviour of STL containers just for the sake of it.

There are some hashlist implementations that use equivalence.  The Dinkumware version is an adaptor on top of a doubly-linked list IIRC.

> And indeed, I tried defining opCmp but it made no difference.  What would be the point of having an equality operator if you're not going to use it?

Agreed.

The associative array code for class objects uses toHash() and opCmp(). See
std\typeinfo\ti_C.d. You'll need to overload opCmp() for your example.

"Ilya Minkov" <minkov@cs.tum.edu> wrote in message news:c0gq82$221f$1@digitaldaemon.com...
> I think it's simply a bug since toHash should be enough.

It isn't because hashes can collide.

Let:

uint[bit[]] avec;
static bit[] bvec = [0b1, 0b0];
++avec[bvec]; // <-- error

:-\

"Walter" <walter@digitalmars.com> wrote in message news:c0kf1m$1psq$3@digitaldaemon.com...
> The associative array code for class objects uses toHash() and opCmp().
See
> std\typeinfo\ti_C.d. You'll need to overload opCmp() for your example.
>

i tried:

class ABC
{
     this(int x,int y, int z)
     {
          a = x;
          b = y;
          c = z;
     }
     override uint toHash()
    {
          return a+b+c;
     }
     int opCmp ( ABC x)
    {
          return this.toHash() - x.toHash();
     }
     int a,b,c;
}

... an leter:

int[ABC] AA;

ABC a111 = new ABC(1,1,1);
ABC b222 = new ABC(2,2,2);
ABC c111 = new ABC(1,1,1);

assert(a111<b222);
assert(!(a111<c111));

AA[a111] = 111;
AA[b222] = 222;

assert(AA.length == 2);

AA[c111] = 111;

assert(AA.length == 2); // this asser fails because there are 3 elements in
associative
//array but there should be only 2!

Am i doing something wrong?

While it was 2/14/04 6:25 AM throughout the UK, Walter sprinkled little black dots on a white screen, and they fell thus:
> The associative array code for class objects uses toHash() and opCmp().

Why, exactly?  Do you implement it as a hash table of binary trees? Surely associative arrays shouldn't be restricted to classes that have an ordering?

Further, is there any rule that if opCmp is defined, it has to be consistent with opEquals?  I haven't found any clarification of this in the spec, and moreover, the Java API at least has a few counterexamples.

> See std\typeinfo\ti_C.d. You'll need to overload opCmp() for your example.

Tried already - please see my dialogue with Sean Kelly (http://www.digitalmars.com/drn-bin/wwwnews?D/23817 et seq).

FWIR, I defined

	int opCmp(IChar c) {
		return toupper(d) - toupper(c.d);
	}

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.

Stewart Gordon wrote:

> While it was 2/14/04 6:25 AM throughout the UK, Walter sprinkled little black dots on a white screen, and they fell thus:
> 
>> The associative array code for class objects uses toHash() and opCmp().
> 
> Why, exactly?  Do you implement it as a hash table of binary trees? Surely associative arrays shouldn't be restricted to classes that have an ordering?

The Dinkumware STL implements hash sets as a hash wrapper around an ordered deque.  I suppose this is one possibility.

> Further, is there any rule that if opCmp is defined, it has to be consistent with opEquals?  I haven't found any clarification of this in the spec, and moreover, the Java API at least has a few counterexamples.

Nope, not required.  In fact 95% of the time when I define equality and comparison in classes they give different results, as I generally want to order classes on a subset of what actually contitutes equality.

>> See std\typeinfo\ti_C.d. You'll need to overload opCmp() for your example.
> 
> Tried already - please see my dialogue with Sean Kelly (http://www.digitalmars.com/drn-bin/wwwnews?D/23817 et seq).

I'll have to try this out myself.  Still haven't gotten around to it.


Sean