dcollections 1.0 and 2.0a beta released

[Steven Schveighoffer]

On Mon, 24 May 2010 16:07:22 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 05/24/2010 01:49 PM, Steven Schveighoffer wrote:
>> On Mon, 24 May 2010 12:27:10 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>>> A pointer to the end element would be required for both appending and
>>>> back().
>>>
>>> This further erodes my confidence. Size needs to be maintained _and_ a
>>> pointer to the last element must be maintained. For many uses, all of
>>> this stuff is unnecessary overhead.
>>
>> You make it sound like incrementing a counter and changing a pointer are
>> incredibly slow operations :)
>
> They are. Ask Walter for a good example.

Actually, I realize that pointing to the end node isn't good enough,  
because once you remove that node, there is no way to get to the previous  
node without traversing the list again.

So slist cannot implement the List interface, you were right.

>> The overhead of storage is minimal
>> compared to the elements of the list, which do not contain said  
>> overhead.
>
> I'm talking containers of lists here.

I was more talking about the ratio of elements to lists.  For example, the  
Hash implementation uses the same link list nodes as elements in its  
table, and generally a hash has very few elements per list, so overhead on  
the list head would be too much.  On top of that, a LinkList has its own  
allocator, meaning each one consumes a large chunk of data assuming you  
will be adding lots of elements to it.

So maybe we need to refine the implementation building blocks that back  
the dcollections classes so they are useable in special situations where  
performance is critical.  It actually would be pretty trivial to define  
SLink as a specialization of dcollections' Link struct, and that would  
essentially give you a lot of functionality in terms of your ideal list  
type.

>> Which may be acceptable to you if you
>> want the bleeding fastest speed available. There will always be tailored
>> code crafted to be as fast as possible for some specific design and
>> dcollections and your slist just won't fit the bill.
>
> Except that the set is considerably smaller for a well-designed slist.

The set of problems that an slist solves is also considerably smaller.   
Having that backwards capability enables more algorithms.

-Steve