🔒 Locked

operator[] on linked lists

Started by aaron_ds Apr 3, 2004 at 6:44 PM 51 replies 4.1k views

Original Post

Apr 3, 2004 at 6:44 PM

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.

Sneftel

Apr 3, 2004 at 6:48 PM

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

Sneftel

Apr 3, 2004 at 7:01 PM

In most of the literature I''ve seen it''s called the "arrow operator".

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

aaron_ds

Apr 3, 2004 at 7:10 PM

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. :-/

Sneftel

Apr 3, 2004 at 7:27 PM

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

aaron_ds

Apr 3, 2004 at 7:47 PM

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.

Sneftel

Apr 3, 2004 at 7:49 PM

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

aaron_ds

Apr 3, 2004 at 7:58 PM

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.

Sneftel

Apr 3, 2004 at 8:16 PM

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

aaron_ds

Apr 3, 2004 at 8:28 PM

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!

Sneftel

Apr 4, 2004 at 1:10 AM

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

mattnewport

Apr 4, 2004 at 4:50 AM

quote:

return *((T*)0);

That is the devil's code.

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

Jingo

Apr 4, 2004 at 5:49 AM

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.

CGameProgrammer

Apr 4, 2004 at 6:01 AM

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( );

_{-- 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]

Enokh

Apr 4, 2004 at 7:32 AM

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]

smart_idiot

Apr 4, 2004 at 7:37 AM

I agree, writing *((T*)0); is a Bad Thing™.

Willm

Apr 4, 2004 at 8:07 AM

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.

DrPizza

Apr 4, 2004 at 8:12 AM

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.

Willm

Apr 4, 2004 at 9:03 AM

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?

Enokh

Apr 4, 2004 at 9:16 AM

If you need to find the middle of a given linked list then you should have used a vector for that specific problem.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.