how should I implement this list?

[bearophile]

Bedros:

> I have a node of struct { ulong mask; ulong value};
>
> now I need to create a list and insert that node; but first I 
> don't need duplicates, so, I first check if node already exists 
> in list.
>
> I also need to traverse the list, and remove a node
>
> currently I'm using dynamic array in D, but it's not efficient; 
> is there a better way to do the following
>
> insert with no duplicates
> remove
> traverse
> find
>
> I read about containers in D, but the documentation is 
> confusing; and not sure if container implementation is mature.
>
> BTW, my code will generate 100s of millions of nodes, and each 
> node on average is used once or twice then removed

Is the average number of items in the whole data structure 
constant? How much do you have to transverse the data structure 
(beside finding the duplications)? During such transversal do you 
need to display items in some order?

Your needs are special, so I think you will have to try several 
different data structures before finding the best one. Generally 
linked lists are slow in transversals, have less cache coherence, 
and give troubles to the GC making it work slowly.

A possible data structure for your needs is some kind of array of 
pointers to short fixed sized arrays that also keep a count of 
how many items each of them keeps, and keep them in a freelist. 
But first try something simpler, like a dynamic array with 
periodic holes, like on library shelves.

Bye,
bearophile