It seems to me it doesn't bring anything noteworthy over std.container.SList. Would anyone miss it if I erased it?

Andrei

Andrei Alexandrescu:

> It seems to me it doesn't bring anything noteworthy over std.container.SList. Would anyone miss it if I erased it?

One linked list is enough.
Can't the heap in std.algorithm be moved to the collections/containers?

Bye,
bearophile

On 05/30/2010 02:01 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> It seems to me it doesn't bring anything noteworthy over
>> std.container.SList. Would anyone miss it if I erased it?
>
> One linked list is enough.

Sounds good.

> Can't the heap in std.algorithm be moved to the collections/containers?

The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.

Andrei

Andrei Alexandrescu:
> Sounds good.

I'd like a single linked one, and a double linked one (but in my opinion in modern programming linked lists are uncommon. In most situations dynamic arrays are better).


> The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.

As usual some pieces of Reality don't perfectly fit our categories :-)
A collection is something able to hold/keep many items. A heap is a data structure, it's one specific organization of data.
They are two different things, it's like the difference between an "array" and a "sorted array", they are two different data structures (because you can't append randomly in the second one), but they are represented with the same collection.
You can map one data structure on different collections.
A "heap struct" (as the one in std.algorithm) is not an algorithm, so std.algorithm is not the right place for it, so it's better to move it elsewhere.

Bye,
bearophile

On 05/30/2010 06:00 PM, bearophile wrote:

> I'd like a single linked one, and a double linked one (but in my opinion in modern programming linked lists are uncommon. In most situations dynamic arrays are better).

I think you just program too much in python <g>

Ellery Newcomer:
> I think you just program too much in python <g>

On modern CPUs most times liked lists are the wrong data structure to use. They are slower, use more memory, can be less handy and less safe. There are few situations where a single/double linked list is better, but they are quite uncommon (for example when you have often to add/remove items from the middle of a sequence and you can find such points quickly, this happens for example in the dancing link algorithm).

Bye,
bearophile

bearophile wrote:

> Ellery Newcomer:
>> I think you just program too much in python <g>
> 
> On modern CPUs most times liked lists are the wrong data structure to use. They are slower, use more memory, can be less handy and less safe. There are few situations where a single/double linked list is better, but they are quite uncommon (for example when you have often to add/remove items from the middle of a sequence and you can find such points quickly, this happens for example in the dancing link algorithm).
> 
> Bye,
> bearophile

Uncommon? Sure, if you don't need the ability to arbitrarily add and remove elements from a container, then a vector type is definitely better than a linked list. However, there are _plenty_ of cases out there where the ability to arbitrarily add and remove elements from a container is a necessity. It depends entirely on the algorithm that you're using and what you're trying to do. Just because you, personally, don't run into many situations where linked lists are needed does not mean that others don't.

Linked lists are a basic, vital data structure in any good container library. True, it's best to prefer vector types when you don't need the specific abilities of a linked list, but that does not mean that the linked list isn't going to be frequently used, just that it shouldn't be used when it isn't needed.

- Jonathan M Davis

Jonathan M Davis:

>Uncommon? Sure, if you don't need the ability to arbitrarily add and remove elements from a container, then a vector type is definitely better than a linked list. However, there are _plenty_ of cases out there where the ability to arbitrarily add and remove elements from a container is a necessity. It depends entirely on the algorithm that you're using and what you're trying to do.<

In many cases the items you have to remove are not so specific, so you can just pop the last item of a dynamic array. The same for adding items.
If you have to remove specific items you often don't need to keep their order, so you can move the last item to the array slot that now is free, and shorten the array length by one. You can take a look here:
http://www.fantascienza.net/leonardo/ar/list_deletions.html
Dynamic arrays can contain references or pointers, so you can swap items around efficiently using their index.
Modern CPUs have two or more cache layers, this means that today following link chains worsens the access pattern inside the cache lines, and pointers need memory that increses cache pressure.
In most of your algorithms you can replace linked lists with *good* dynamic arrays (D ones are not good enough in their append performance) with a general performance and memory improvement. And the code can become simpler.

There are few situations where linked lists are useful, but today they are uncommon. Even if you use linked lists often, this doesn't mean they are the often better than using a dynamic array.

Bye,
bearophile

Andrei Alexandrescu wrote:

> On 05/30/2010 02:01 PM, bearophile wrote:
>> Andrei Alexandrescu:
>>
>>> It seems to me it doesn't bring anything noteworthy over std.container.SList. Would anyone miss it if I erased it?
>>
>> One linked list is enough.
> 
> Sounds good.
> 
>> Can't the heap in std.algorithm be moved to the collections/containers?
> 
> The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.
> 
> Andrei

I would also rather think of heap as the heapify operation, not unlike partition.

On Sun, 30 May 2010 18:33:22 -0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:


> The heap is a tad difficult to tackle. Most of the time you don't want to create a heap, but instead to organize an existing range as a heap. As such, the heap is not always obvious to think of as a container. I'm undecided on how to approach this.

It's easier to think of a heap as a single entity with operations on it.  At least for me anyway.

Most of the time, once you make a range a heap, you want to continue to use it as a heap.  Restricting operations on that range by defining a heap type around it can do this.  Otherwise, you could accidentally do something foolish like sort the range.

-Steve