Ah, I see. But if you have an "index" object, you could keep the stack in it as well. (I assume that is done in a multiset iterator?)
/ Mirar
Previous text:
2003-01-30 18:41: Subject: Re: hybrid of array & list
No, to insert or remove an element you need to find its parents, all the way to the root node in the worst case. My multiset implementation doesn't store parent pointers, so this is instead done by recording the path on a stack when a node is found. It works fine as long as there's a good order function, which I consider to be the normal case.
If the order function doesn't order some values (or all in this case) then it can only be used to find the right set of unordered elements. Within that set the implementation has to do a linear search while the stack is kept updated appropriately.
/ Martin Stjernholm, Roxen IS