Container templates and constancy of elements

[Stewart Gordon]

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.

In Java and D1, it seems you just have to go on trust if you want your container to accept 
key types other than strict value types.  But can we do better in D2 - short of forcing 
the key type to be immutable, which would hinder the container's usefulness?

But it seems D2 has taken one step in that general direction by automatically 
tail-consting the key type of an AA.  But it doesn't stop modifications to the key through 
mutable references to the data.  And if the key is of class type, you can still modify the 
object, since D2 conflates constancy of an object reference with constancy of the object 
itself.  This is in itself silly.  Really, D should have tail-const built in for stuff 
like this.  OK, so there's Rebindable, but I've found it to be a PITA when trying to do 
generic programming with it, as well as leading to this AA key anomaly because it isn't a 
built-in feature.


I suppose there are a few possibilities for what constancy to apply to elements of a data 
structure to which changes might affect the structure's integrity:

(a) force the type to be tail-const if it's an array, otherwise don't add any constancy
(b) force the type to be tail-const if it's an array, or fully const if it's a class
(c) force the type to be tail-immutable if it's an array, otherwise don't add any constancy
(d) force the type to be tail-immutable if it's an array, or fully immutable if it's a class
(e) don't add any constancy, but just rely on trust


Currently, AAs implement (a).  (d) guarantees that changes to the data that mess up the 
data structure will never happen, at least if the programmer doesn't bypass the const 
system.  (e) is the route D1 and Java are forced to take.  Am I right in thinking that 
sets and maps in the C++ STL take the same path?


Anyway, what are people's thoughts on the right way to go here?

Stewart.