Neil Conway wrote:

Gaetano Mendola <[EMAIL PROTECTED]> writes:

Why instead of reinvent the whell not use, or at least do a "C" port of
stl::list ?

Because (a) implementing a linked list is pretty trivial (b) the only
difficult part is getting the semantics / API right. I don't see how
std::list would help with (b), and (a) negates the benefit of
importing the code from elsewhere.

We'd also have to gut std::list, since we wouldn't be able to make use
of C++ templates.

That said, if you know of any specific techniques from std::list
implementations that would be useful, please let me know.

An interesting think that stl::list do is to never do an "if" branch during an insert/remove phase, an stl::list is a struct with a Master Node:

struct node
    void* value;
    node* next;
    node* prev;

struct list { node* master_node; };

here respect your proposal a node is saved.

an empty list is initialized with:

master_node = [ ... create a node ... ]
master_node->next = master_node;
master_node->prev = master_node;

and the insertion phase sound like:

AddHead(list *l, node *e)
   node *where = l->master_node->next;
   e->next = where;
   e->prev = where->prev;

   where->prev->next = e;
   where->prev = e;

AddTail(list *l, node *e)
   node *where = l->master_node;
   e->next = where;
   e->prev = where->prev;

   where->prev->next = e;
   where->prev = e;

now is very late here ( 04:17 AM ) so I wrote the wrong code ( not checked ) but show the idea of avoid "if".

PS: My 2 cents: I don't like too much have the lenght inside the list

Why not?

What if you will never call the size() on a list doing massive insert ? May be we need two list, depending on the way we are going to use it?

I'm too much C++ oriented and another very weak argument is: for the
same reason that STL (at least in gcc) doesn't have it:

may be the third point not apply to us.

Gaetano Mendola

---------------------------(end of broadcast)--------------------------- TIP 4: Don't 'kill -9' the postmaster

Reply via email to