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
