Container insertion and removal

[Fawzi Mohamed]

I am coming late into this discussion, some comments:

I like a duck typing approach whenever possible, and don't need runtime 
adaptability (which seems to be in line with others)

different container have different trade offs, and switching between 
them should be a design choice

Generic algorithm in my opinion are useful to easily (and with little 
well tested code) give a wise range interface to several containers.
They should not "forbid" special implementation of some algorithms in a 
container.
To have a common interface one can always use a trampoline function, 
that looks for the specialized implementation in various places.
I know that in theory one should be able to write specialized templates 
instead, but in practice I have often encountered bugs and strange 
behavior, in container implementation seems much cleaner to me

Different containers have different "threadsafeness". Normally some 
subset of operations is threadsafe, but mixing in other might break it. 
This in my opinion *must* be documented, for example one should not 
have to look to the source to know if addition of an element to an AA 
breaks a foreach loop or not.
Threadsafeness has a cost, in general non threadsafe structures are 
faster, so it makes sense to have them (especially thinking that often 
even in the non threadsafe structures one can use a subset of 
operations concurrently without problems.
There is a large class of structures that *are* threadsafe, these have 
some beautiful properties, and are very useful to know. A very good 
review of them (I don't say introduction because the book is quite 
advanced) is "Purely Functional Data Structures" by Chris Okasaki. In 
these structures the values read are always the same, but lazy 
evaluation might be used to transform amortized cost in non amortized 
cost.

I had already spoken about these back during the const discussion, 
because I would have liked that these structures were "immutable" and 
usable by pure functions, which meant a slighlty different thing from 
immutable. Some casting might be used to implement them, if one assumes 
that casting a mutable structure to immutable and modifying it later is 
doable (no compiler optimization on immutable disallow it, this could 
be done even just for a special "thunk" that contain a lazy function 
that will produce the value). Anyway that is another discussion.

For the current discussion the important thing is that yes, there are 
fully threadsafe structures, and it would be useful to have them, but 
in general they have a slightly larger cost.
Not safe structures are also useful as they are faster, in general in 
the documentation one expects to find which operations are safe and 
which not.
The minima baseline typically is that just reading is threadsafe, 
modifications in general aren't and might invalidate all pointers to 
the structure.
Exceptions to this should be clearly stated, for example appending to 
an array can be made threadsafe without a large cost, whereas insertion 
(if the update of an element is not atomic) cannot.

If D really wants to go after multithreading it makes sense to offer as 
many safe structures as possible, and in any case clearly document the 
non threadsafeness of the others.

it might make sense to give "safe" interfaces (I would say basically 
just reading without updates), but one cannot expect to really express 
all threadsafeness of a container though interfaces, because that would 
be too complicated and then one would end up with one container per 
interface without much gain.

Fawzi