On Mon, 24 May 2010 16:07:22 -0400, Andrei Alexandrescu
<[email protected]> wrote:
On 05/24/2010 01:49 PM, Steven Schveighoffer wrote:
On Mon, 24 May 2010 12:27:10 -0400, Andrei Alexandrescu
<[email protected]> 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
