quote:Original post by Sneftel
hmm, yeah. Well, really what you should do is throw an exception, since there''s nothing you could reasonably return to indicate an error. However, if you want you could do:
return *((T*)0);
!
operator[] on linked lists
!
If the [] operator contains a static iterator, then it''s OK. Also, this operator should test whether the target index is closer to the head, the tail, or the iterator. Thus, the reason for the operator to exist is to hide this functionality.
--------------------------------------
I am the master of stories.....
If only I could just write them down...
--------------------------------------
I am the master of stories.....
If only I could just write them down...
Author
If anyone still cares, 
I''ve implemented an iterator class, unfortunatly I think it makes the code look worse but it''s an improvement in speed over []. I like Nathaniel Hammen''s idea. I''m no big O notation whiz. Would this make change it from O(n) to O(n/2)? as the worse case would be the iterator is at the head or tail and the index is in the middle of the list? Or would it still be O(n) with a smaller constant? Either way, It seems better than iterating from the head until the index is reached.
I''ve implemented an iterator class, unfortunatly I think it makes the code look worse but it''s an improvement in speed over []. I like Nathaniel Hammen''s idea. I''m no big O notation whiz. Would this make change it from O(n) to O(n/2)? as the worse case would be the iterator is at the head or tail and the index is in the middle of the list? Or would it still be O(n) with a smaller constant? Either way, It seems better than iterating from the head until the index is reached.
quote:Original post by aaron_dsYeah, I can tell. O(n) = O(n/2) = O(c*n) where c is a constant. Or even, O(n^2+n) = O(n^2).
I''m no big O notation whiz. Would this make change it from O(n) to O(n/2)?
FWIW, many suggest that overloading the operator(unsigned int) is more agreeable than operator[] since it can be expanded to operator(uint, uint) for two dimensional lists, and operator[] cannot. I subscribe to this philosophy.
I hear (read?) everyone say (write?) that to find list[x] in a linked list, you need to loop over every element until you have i=x, and that this is very slow.
Yes, this method is very slow, but it doesn't mean that list[x] should be slow. I think one could create a pretty fast lookup-mechanism for finding list[x] in a linked list.
What if the first element of a linked list contains a pointer to the element with index = length/2? And that element contains a pointer to index = length/4 and index = length * 3/4? Wouldn't it produce a much faster list[x]?
And what if the list-structure had an easy caching mechanism? What if it had an integer with the last used index, and a pointer to that element? Wouldn't finding list[x+1] be much faster?
I hope this doesn't seem too stupid.
[edited by - Tommy Carlier on April 7, 2004 5:01:17 AM]
Yes, this method is very slow, but it doesn't mean that list[x] should be slow. I think one could create a pretty fast lookup-mechanism for finding list[x] in a linked list.
What if the first element of a linked list contains a pointer to the element with index = length/2? And that element contains a pointer to index = length/4 and index = length * 3/4? Wouldn't it produce a much faster list[x]?
And what if the list-structure had an easy caching mechanism? What if it had an integer with the last used index, and a pointer to that element? Wouldn't finding list[x+1] be much faster?
for(int i=0; i<list.length; i++) v = list[i].value;for(element=list.first; element<=list.last; element=element.next) v = element.value;I hope this doesn't seem too stupid.
[edited by - Tommy Carlier on April 7, 2004 5:01:17 AM]
quote:What if the first element of a linked list contains a pointer to the element with index = length/2? And that element contains a pointer to index = length/4 and index = length * 3/4? Wouldn''t it produce a much faster list[x]?
If all the elements contained such pointers then you could get logarithmic access. I''d be loathe to call the resultant structure a linked list though. It would look much more like a threaded tree of some kind.
quote:And what if the list-structure had an easy caching mechanism? What if it had an integer with the last used index, and a pointer to that element? Wouldn''t finding list[x+1] be much faster?
No faster than with an iterator.
quote:If the [] operator contains a static iterator, then it''s OK.
But that''s a fundamentally bad design decision anyway. It means you can''t iterate over the list in two places and that even multithreaded reads (which would otherwise be safe) need to be synchronized.
quote:True, but perhaps that''s because the STL isn''t being consistent. I mean, one of the first ''gotchas'' people learn when using the STL is "never use size() to test for an empty container". Why? Because, while size() SHOULD be a constant-time operation it CAN be a linear-time operation on SOME list implementations.
In the original 1998 standard, no, it couldn''t be a linear-time operation -- the performance constraints were simply impossible (list.size() must be constant time, and so must list.splice() even for splicing partial lists, which cannot be done). The 2003 standard may fix this, I don''t remember.
This is unfortunate, but I''m not sure that anything can be done about it. list.size() (unlike indexed access) could at least be constant time on average, which though a weaker constraint is still better than forcing people to use std::distance(l.begin(), l.end()) every time.
Further, the size of a list is a property it has -- it does not require the invention of bogus indices.
quote:So why make size() for a list but not operator[]?
Because it can offer better performance guarantees than a non-member could.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
