Archived

This topic is now archived and is closed to further replies.

aaron_ds

operator[] on linked lists

Recommended Posts

For the purpose of learning I''ve been working on a linked_list class. The linked list contains various methods, and a pointer to the head and a pointer to the tail which point to node objects. Each node has a pointer to data. Both linked_list and node are templated to hold any kind of data. Yes, I know the std exists. No, I don''t want to use it instead. I like learning how things work and creating something on my own. I will probably use it later, but for now, I would like to knwo how something like this works. Anyways. I''ve overloaded the subscript operator. I was hoping to get a more intuitive use out of the linked list. But using [] actually makes things more confusing. Its obvious I''m not implementing it correctly.
template <typename T>
T& LINKED_LIST<T>::operator[] (int subscript){
    if(subscript>members)
        return NULL;
    long start = 0;
    NODE<T>*  cur_node=head;
    while(start!=subscript){
	cur_node=cur_node->next;
	start++;
    }
    return cur_node->data;
}
I would like to return the data of the node, rather than the node itself as to create a layer of transparency. To use it, I have to use i=(&(*uvpoly_list)[n])->somememberofdata; Alas. VERY counter-intuitive. I''ve tried googleing "operator[]" However, all symbols are left out of searches so im limited to searching ''subscript operator'' I would search for operator-> but I have no idea what its name even is. :-/ Sorry for the long post. I tend to explain too much. Maybe someone can point me in the right direction. Thanks in advance.

Share this post


Link to post
Share on other sites
You shouldn''t return NULL there. It won''t work if 0 can''t be converted to type T. Instead, return T(). Other than that, it looks like you should just be able to do

LINKED_LIST<int> myList;
// fill myList, and then
myList[3] = 5;

What problems do you have with that syntax?


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
the -> is a pointer dereference operator or an indirection operator, depending on who is doing the talking. I think the second is the proper term.

Share this post


Link to post
Share on other sites
In most of the literature I''ve seen it''s called the "arrow operator".


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Sneftel: using ''return T();'' nor ''return NULL;'' will compile.
error when using ''return T();'' Reference initialized with ''int'', needs lvalue of type ''int'' in function LINKED_LIST::operator[](int) at line 143;

using return NULL; yeilds the same error message. :-/

Share this post


Link to post
Share on other sites
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);


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Sneftel:

template <typename T>
T& LINKED_LIST<T>::operator[] (int subscript){
if(subscript>members)
return *((T*)0);
long start = 1;
NODE<T>* cur_node=head;
while(start<subscript){
cur_node=cur_node->next;
start++;
}
if(cur_node)
return *cur_node->data;
else
return *((T*)0);
}

now works. I dont beleive the index operator was at fault.
LINKED_LIST myList;
// fill myList, and then
myList[3] = 5;

The example now works. However, in my original code my linked_list is created by using something to the effect of LINKED_LIST* myList = new LINKED_LIST;
I do believe I will need to overload a few more operators in order to achieve the desired effect.

Share this post


Link to post
Share on other sites
If you''re declaring it as a pointer then you are SOL with respect to getting the subscript operator to work on it. You''ll just have to do (*myListPtr)[3] = 5. Why are you declaring it as a pointer, anyway?


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
To tell you the truth. I don''t know. I''ve never been formally trained in programming. In no tutorial nor book I''ve read has the topic of relevant pointer usage been discussed. It''s always been some dumb example that just shows How to use them, not why someone would want to.
The noteable exception is passing an object to a function via pointer. Other than that, I really don''t know when to and when not.

I guess its back to the books for me.

Share this post


Link to post
Share on other sites
Are you kidding? You just showed off one of the most notable uses of pointers, namely linked lists. If there''s one thing that pointers are useful for, it''s linked lists. You''re doing pretty well so far, as far as I can tell.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
oye, lol. Well, i guess my question should have been this: when is it adventagous and disadvantagous to use a pointer to a linked list class.

disadvantage #1 operator[] is crap when linked_list is a pointer.

Thanks for all your help so far!

Share this post


Link to post
Share on other sites
It''s not really ever advantageous, except for more general situations independent of the datatype. Consider this, though: suppose you wanted to pass a linked list as an argument into a function. You could pass it by value, but when you pass an argument by value, it makes a copy of it. That would mean copying the entire linked list--or, since I doubt you''ve implemented the copy constructor, would erroneously copy the list itself but still refer to the old nodes, causing insidious and hard-to-find errors. Instead, if you passed in a pointer to the linked list, you''d be able to access the same list that the parent function was using, without any copying done.

Now, in fact this is more a C reason to use pointers, since in C++ references have mostly eclipsed them. Still, you asked.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
quote:
Original post by mattnewport
quote:
return *((T*)0);   


That is the devil''s code.

[edited by - mattnewport on April 4, 2004 5:52:12 AM]



It''s also undefined behavior, dereferencing a null pointer, that is.

Share this post


Link to post
Share on other sites
You could fake it like this:

template <typename T>
struct LIST_PTR
{
LINKED_LIST<T>* Node;

inline LINKED_LIST<T>* operator = ( LINKED_LIST<T>* N )
{
return (Node = N);
}

inline T& operator [] ( int I )
{
return (*Node)[I];
}

inline operator LINKED_LIST<T>* ( )
{
return Node;
}
};


EDIT: So it'll be used like:

LIST_PTR<int> List = new LINKED_LIST<int>;
List[0] = 5;

~CGameProgrammer( );

Screenshots of your games or desktop captures -- Upload up to four 1600x1200 screenshots of your projects, registration optional. View all existing ones in the archives..

[edited by - CGameProgrammer on April 4, 2004 7:04:24 AM]

Share this post


Link to post
Share on other sites
Long version: Listen, overloading the [] operator for a linked list just doesn't make sense. Vectors and Linked Lists have various functions implemented in the std because it makes sense to implement those specific functions to those specific containers. A Vector is contingious in memory as you prolly know and that's why it's faster iterating through it as opposed to a linked list, where each cell can be in god knows where, and thus while iterating through the list, the computer constantly has to jump around in order to find the next cell in the list. That's why the [] operator is implemented in the std:vector and not in the std:list, because it takes advantage of a virtue of the vector container type. Bjarn Stroustrup explains this idea much better than I can in his book The C++ Programming Language 3rd Edition.

Short version: Use a vector ;-)


[edited by - Enokh on April 4, 2004 8:33:32 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Enokh
Long version: Listen, overloading the [] operator for a linked list just doesn''t make sense. Vectors and Linked Lists have various functions implemented in the std because it makes sense to implement those specific functions to those specific containers. A Vector is contingious in memory as you prolly know and that''s why it''s faster iterating through it as opposed to a linked list, where each cell can be in god knows where, and thus while iterating through the list, the computer constantly has to jump around in order to find the next cell in the list. That''s why the [] operator is implemented in the std:vector and not in the std:list, because it takes advantage of a virtue of the vector container type. Bjarn Stroustrup explains this idea much better than I can in his book The C++ Programming Language 3rd Edition.

Short version: Use a vector ;-)



The [] operator may not be implemented in std:list, but there are perfectly justifiable reasons to add it to a list class. I''m also one of those crazy mavericks that likes to roll their own collection classes. I use the [] operator mainly for syntactical sugar. Combined with negative indexing it makes for elegant code. eg List[0] gets the first element (head), List[-1] gets the last (tail).

As long as you are aware that [] isn''t a trivial operation for lists, it is a good idea IMHO.

Share this post


Link to post
Share on other sites
quote:
The [] operator may not be implemented in std:list, but there are perfectly justifiable reasons to add it to a list class.

No there aren''t.

quote:
I''m also one of those crazy mavericks that likes to roll their own collection classes.

This does not surprise me.

Share this post


Link to post
Share on other sites
quote:
Original post by DrPizza
quote:
The [] operator may not be implemented in std:list, but there are perfectly justifiable reasons to add it to a list class.

No there aren''t.

quote:
I''m also one of those crazy mavericks that likes to roll their own collection classes.

This does not surprise me.



Unless you give me a good reason why not, I''ll assume you are just obsessed with dogma and unable to think for yourself.

How would you find the element in the centre of a given list?

Share this post


Link to post
Share on other sites
If you need to find the middle of a given linked list then you should have used a vector for that specific problem.

Share this post


Link to post
Share on other sites
quote:
Original post by Enokh
If you need to find the middle of a given linked list then you should have used a vector for that specific problem.


You may not always have the choice. Consider that you have been given a list of elements in sorter order, and you are required to calculate the mean value.

Have you ever needed to find the second to last, or third to list element in a list? Sure you can do it without the [] operator, but what can be simpler than this..

List[-2] Second to last

List[-3] Third to last

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
try snippets.org

here are the links to some very good linked lists code.

http://cpp.snippets.org/snip_lister.php?fname=list.hpp

http://cpp.snippets.org/snip_lister.php?fname=list.cpp

Share this post


Link to post
Share on other sites
In my case, I implemented the [] operator for readability''s sake. It has been stressed countless times in these forums that readability is a prime goal of the programmer. If I can look back months later and understand a section of code BECAUSE I used the [] operator, then I''ve gained something.
My code used to look like this

for(NODE<POLYGON>* poly_cur= polygon_list->head; poly_cur!=NULL; poly_cur=poly_cur->next){
i=poly_cur->data;
}

and now it looks like this

for(int n=0; n<polygon_list->members; n++){
//do things like:

k=polygon_list[n];
}

Personally, I like the second. It''s simply more readable.

(Both just examples, I know they dont do much)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
aaron_ds, pursuing readability is no good if it harms performance a lot and helps readability only little. In your case, it turns an O(N) algorithm into O(N^2) one. Now you''ll be able to look back at your old code months later and say to yourself "Doh, what was I thinking!" That''s not a great achievement

Share this post


Link to post
Share on other sites