quote:Original post by Anonymous Poster
well just whereever he says "node" read it as "iterator", I mean really.

Really what?

Nodes are things used to build certain containers.

Iterators are things to move through certain containers.

Replacing "node" with "iterator" will change what he wrote completely, and it would change it to something other than what he intended.

They have different properties -- nodes store things and have two pointers, iterators don''t store anything, have unknown internal construction, and a few members to provide pointer-like semantics. One cannot simply replace "node" with "iterator" in what he wrote.

An iterator can''t be used to steal nodes, because the iterator shouldn''t provide access to the node (i.e. won''t let you unlink it from one chain and link it onto another).

quote:So he''s just removing one object from a list and inserting it into another. It is just that he is doing it more efficiently.

The point is, his list absolutely should not expose nodes, ever.

quote:I don''t know the STL list that well (I prefer vectors, maps, and the other containers)

It isn''t a question of which you prefer, it''s a question of which is correct.

quote:but doesn''t it have a splice function or something?

Yes.

And it quite probably will be implemented by unlinking nodes from one list and putting them in the other -- which will provide the same ultimate result as the StealNode function but without exposing Nodes.

quote: If it took a range of iterators and you throw a remove algo in, you''d probably be able to get what he is doing.

Probably.

quote:As to the allocators, don''t allocators do the equivilent of overloading new? Since nodes store the object in the node itself allocators have no relevance and thus cannot be used in an implementation, unless the implementation doesn''t store the object in the node, but wouldn''t that be less efficient?

It''d be a pointer dereference and a memory allocation less efficient; I don''t think it''s forbidden, though; the standard generally specifies only the properties of the interface, not the implementation.

char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/

quote:Original post by Anonymous Poster
but what I mean is that he is using node to mean both implementation and interface.

But this is very distinct from what the STL uses iterators for. Iterators are *not* a part of the implementation (that is to say, iterators are categorically not nodes, and do not do any node-like things). One cannot use iterators as nodes, and one cannot use nodes as iterators. They''re used for different things.

quote:It is a vocabulary issue. The STL specifies an interface based around something called an iterator with the two most important operations being ++ and *. His list specifies an interface based around something called a node with the two most important operations being ->=next (arrow equals isn''t an operator but probably should be)

To do what?

quote:and .element. He just calls them nodes. If all iterators were called nodes they''d still be iterators. He could change his implementation and still call things nodes, well actually he can''t because he''s not using functions (overloaded operators) to traverse and get at the element, but the point that I''m trying to make is that calling them nodes is no big deal.

The POINT is that nodes and iterators are fundamentally different, and that exposing users of the list to nodes is fundamentally wrong. Calling them Nodes *is* a big deal, because it implies certain things about their function.

quote:What he is saying is that a combined remove and insert operator would be useful. The STL could have it too, just operating on iterators. The signature might be something like this: move_from_to(iter begin, iter end, iter target);

The STL can''t have something like that, because it can''t remove iterators from a container without having access to that container. This is why std::list::splice() requires a reference to the other list -- without it, it can''t remove the elements it''s stealing.

If the STL exposed _nodes_ this would no longer be required -- nodes could be unhooked from one list and joined onto the other *without* requiring access to the list itself. Iterators do not permit this, because iterators do not expose the implementation details. They provide access to the elements within the list, but nothing more than that. There''s no way to tell an iterator "detach from that container and reattach yourself to this container".

char a[99999],*p=a;int main(int c,char**V){char*v=c>0?1[V]:(char*)V;if(c>=0)for(;*v&&93!=*v;){62==*v&&++p||60==*v&&--p||43==*v&&++*p||45==*v&&--*p||44==*v&&(*p=getchar())||46==*v&&putchar(*p)||91==*v&&(*p&&main(0,(char**)(--v+2))||(v=(char*)main(-1,(char**)++v)-1));++v;}else for(c=1;c;c+=(91==*v)-(93==*v),++v);return(int)v;}  /*** drpizza@battleaxe.net ***/