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:
void
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; }
void
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 struct.
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: http://gcc.gnu.org/ml/gcc-bugs/1998-12/msg00270.html
may be the third point not apply to us.
Regards Gaetano Mendola
---------------------------(end of broadcast)--------------------------- TIP 4: Don't 'kill -9' the postmaster
