On Sunday 26 September 2010 11:38:35 Joel Christensen wrote: > I normally use D's built in dynamic arrays. but it doesn't work with > adding and removing with the foreach loop (like removing an object from > the list while still going through the list).
I would point out to you that Bearophile seems strongly opposed to linked lists in general and seems to point out to people that arrays and vector/ArrayList types (Array in std.container) are faster on modern hardware whenever they come up. I can only assume that it's one of his pet peeves (we all have them - for instance, I hate it when people use post-increment or pos-decrement for instance when pre-increment or pre-decrement will do), but I don't think that he's necessarily right. Classicly in computer science, if you have a data structure which you're going to be doing a lot of appending to, prepending to, or inserting into, you use a linked list. std.container currently has SList, which is a singly-linked list but no doubly-linked list. However, they don't have random access and they take up more memory than an array or an Array (thanks to all of those prev and next pointers). Bearophile objects to them, I believe, because they aren't a single block of memory and so they harm cache locality, resulting in poorer cache performance from the CPU. He may very well be right (in fact on some level, I'm sure he is), but that's the sort of thing that most people worry about when they find that their data structure has poor performance rather than reacting negatively to any suggestion of using a linked list. Whether using a linked list is the best choice for your application, I don't know, but it is often the case that you can do the job just as well or better with an Array, tree, or hash table, depending on what you're trying to do and how you're trying to do it. However, if you constantly adding and removing from a container (especially if you're doing it anywhere other than the end), and you rely on insertion order (so you can't use a hash table) rather than sorted order (like you would with a tree), then a linked list is likely the best choice. It has cheap insertions and removals. Certainly, in D, I would avoid having lots of appending to and removal from the end of dynamic arrays in your code because the GC isn't efficient enough and that's going to result in a lot of allocations and deallocations, but Array should solve that problem for the most part, since it uses an internal array which is larger than the Array's length so that it can reduce how often reallocation occurs (and if you've removed from the end, then it has more room for adding more to the end, so it shouldn't have the same problem as a built-in array). In any case, from your description of having to remove from the middle of a list would indicate that a linked list is probably the best for what you're doing, but not knowing in detail, I'm obviously not in the best place to judge. - Jonathan M Davis
