Container templates and constancy of elements

[Ali Çehreli]

On 03/14/2012 12:24 PM, H. S. Teoh wrote:
 > On Wed, Mar 14, 2012 at 06:51:54PM +0000, Stewart Gordon wrote:
 >> With some containers, such as lists and trees (binary search trees
 >> aside), it doesn't matter if the elements can change state, since
 >> the data structure remains well-formed.
 >>
 >> However, with others, such as sets and AAs, it's desirable if the
 >> keys don't mutate.  Any operations on them won't work right if there
 >> are keys in the wrong hash slots or out of order (depending on the
 >> underlying data structure) because they have changed since being put
 >> into the container.  Of course, this doesn't apply to _values_ in an
 >> AA, since these can safely mutate.
 >
 > IMO, AA keys should be *implicitly* immutable. That is, when you declare
 > something like:
 >
 > 	int[ubyte[]] x;
 >
 > then the key type of x should be immutable(ubyte)[], not ubyte[].

Yes, the internally stored copy of the key should be immutable(ubyte[]). 
Please note the difference from yours, but I guess that extra protection 
is just to protect the developers from themselves by avoiding mutating 
the key in the implementation.

But the conceptual key type of the AA should be const(ubyte[]). The 
reason is, a const parameter is welcoming: It says "I accept both 
mutable and immutable as arguments". On the other hand, an immutable 
parameter is restricting: It says "I demand only immutable as argument".

The following opIndex accepts  keys of five different types of immutability:

class SingleElementAA
{
     immutable(uint[]) key;
     int value;

     ref int opIndex(const(uint[]) key)
     {
         return value;
     }
}

void main()
{
     auto aa = new SingleElementAA();

     uint[] mutable;
     immutable(uint)[] element_immutable;
     immutable(uint[]) all_immutable;
     enum uint[] enum_immutable = [ 1 ];

     aa[mutable] = 42;
     aa[element_immutable] = 43;
     aa[all_immutable] = 44;
     aa[enum_immutable] = 45;
     aa[[0, 1]] = 42;          // literal key
}

Ali