Thread: Struct member NAME as parameter to function - how to?

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    22

    Struct member NAME as parameter to function - how to?

    Hello all. My question has to do with lists.

    [LIST EXPLANATION]For the ones who don't know, a list is a set of structs. These structs contain a pointer to the "next" struct, sometimes also to the previous one. There is a special pointer, the head of the lsit, which points to the first element of the list. Thus, all elements can be accesed in such a way: head->next->next->next etc
    [END LIST EXPLANATION]

    I am trying to create an insertion function template for every possible struct that could be a list member. Initially, I was glad to learn about function templates. There is a problem, however. Different structs will have the corresponding next/previous pointers having various names. How can I pass the names of these members into my function's argument in order to use them? I cannot simply pass the members themselves, because the function edits the members that belong not only to the brand new struct I am inserting each time, but also others on the list (most notably, the ones pointed by head, the previous, and the next).

    I had an idea, to use the memory offset of the members in relation to the struct they belong. It really is a headache, void pointers are included, and errors I do get. By the way: I used void pointers in fear that adding the memory offset on them, they would increase in memory offset * sizeof(pointer type) if i gave them a type.

    If I am unclear, or you think it would help, i'll paste my code. Really hope you will enlighten me in an easier way though!

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    One idea that still uses templates is to just create a base node class that contains common things about all nodes, and then make a derived node class that contains the user's data type.

    Code:
    class BaseNode // cast to/used whenever the user data doesn't matter
    {
       protected:
       BaseNode* next, * prev;
       // make an interface, etc
    };
    
    template<typename type> 
    class Node : public BaseNode // to be contained in a list class
    { 
       private:
       type value;
    };
    Something like this works fine.

  3. #3
    [](){}(); manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    *nullptr
    Posts
    2,657
    >you think it would help, i'll paste my code.
    Please do.

    I do not understand what exactly you are trying to do... (If you're trying to make a list containing "completely" different types of nodes...maybe you need a different data structure ? )

  4. #4
    Registered User
    Join Date
    Nov 2011
    Posts
    22
    It is very, VERY fortunate for me that I (think I) DID get it to work. Still, I have questions so that I can both expand my understanding of the language ADN possibly make it look neater. Here we go):
    Code:
    typedef unsigned long N;
    template <typename LMT,typename KT>
    /*1)No failsafe check of duplicates.
    2)template function for various struct types
    3)LMT: List Member Type
    4)KT: keytype
    5)DLL=Double Linked List*/
    void list_insert(LMT* &head, LMT* &temp, KT &key, LMT* &next, bool DLL=false, LMT* &prev=0)
    {
        N next_offset=(N)&next - (N)temp;
        N key_offset= (N)&key  - (N)temp;
        N prev_offset=(N)&prev - (N)temp;
        LMT** sniper;//points the next/previous of external structs
         if(!head||key < *(KT*)((N)head+key_offset)) //new head
         {
                               next=head;
                               if(DLL)
                               {
                                   prev=0;
                                   if(head)
                                   {
                                        sniper=(LMT**)((N)head+prev_offset);
                                        *sniper=temp;
                                   }
                               }
                               head=temp;
         }
         else
         {
             LMT* aux=head;
             LMT** aux_next=(LMT**)((N)aux+next_offset);
             while(*aux_next&&         (*(KT*)((N)*aux_next+key_offset) < key)            )
             {
                     aux=*aux_next;//Find previous
                     aux_next=(LMT**)((N)aux+next_offset);
             }
             next=(LMT*)*aux_next;
             if(DLL)
             {
                    prev=(LMT*)aux;
                    if(*aux_next)
                    {
                            sniper=(LMT**)((N)*aux_next+prev_offset);
                            *sniper=temp;
                    }
              }
             *aux_next=temp;
         }
    }
    //a successful instantiation:
    
    typedef struct node * np;//Node Pointer
    struct node
    {
           int key;
           //Addition of variables should add commands to create() and print()
           np prev,next;
    };
    .........
    list_insert<node,int>(head,temp,temp->key,temp->next,1,temp->prev);
    My questions:
    As you see, I calculated the memory offsets of the next, key(this is the sorting element), and previous members of the LMT. Then, in order to access the same members from list members OTHER than temp, eg head->previous, i had to(lines 22-23):
    1) Find its address ie adress of head->previous=address of head + previous_offset
    2) Make a pointer (ie:sniper), whose value is the result of 1). Thus, its type must be pointerto-previous = pointerto-pointerto-LMT
    3) I can now read/write previous/next using *sniper

    ok, it seems to work, but: i have an address. Can't I change its contents more "directly"? I think I tried it and got some not lvalue errors. Can I not somehow change the contents of memory address (pointer+offset_in_bytes) directly? Could I de-reference this thing? As it is or in any type of cast? It is confusing for me.
    Last edited by Lord Asriel; 11-22-2011 at 05:50 AM. Reason: Line note

  5. #5
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I think 90% of the problem is that the user of the class can create his own node implementation for the list. There's no real good reason for that. If the list used the same basic node type all the time (like I showed you in my example) there's really no confusion about where members are located and things like that.

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    22
    First, I have to admit I am not very familiar with classes yet. I understand this can well be answered as "well, be then!". So let me tell you exactly why I started all this and, if your solution still holds, i'll get to know them better

    I am making a sparse array, with intertwining vertical and horizontal lists. Its members are:
    Code:
    struct edge
    {
    int i,j;
    struct edge *next,*prev,*up,*down;
    };
    so, each time i add an item to the sparse array, it has to make one horizontal and one vertical list inserts. On one case it uses i as a key and next/prev as list member pointers, while the other j/up/down. I thought it was ....ugly to have the same code twice, replacing the triplet appropriately. With my current function, i am going to implement:
    Code:
    inserttosparsearray(....)
    {
    list_insert<edge,int>(head,temp,temp->i,temp->next,1,temp->prev);
    list_insert<edge,int>(head,temp,temp->j,temp->down,1,temp->up);
    
    }
    and it can get on with "the user of the class can create his own node implementation for the list". If, however, you think your solution will make it easier/nicer still, give me a bit more information about your class proposition, as much as you want, and i'll find the rest from the tutorials.

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I think the only difference with my implementation in this case is that you would have to add up and down links into the base node class in order to do up/down links in addition to prev/next links.

  8. #8
    Registered User
    Join Date
    Nov 2011
    Posts
    22
    Actually, I will start using your idea white. See where it leads me. Thanks
    Last edited by Lord Asriel; 11-22-2011 at 07:15 AM. Reason: Enlightment

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    22
    OK, so I started implementing whiteflags's idea.
    here's my List.h:
    Code:
    typedef unsigned long list_index_type;
    class DLListNode{
        public:
            class DLListNode *list_next_link,*list_prev_link;
            list_index_type list_index;
    };
    template <typename list_member_type>
    list_member_type* find_edge(list_member_type* &head, list_index_type x)
    {
        if(!head) return 0;//list is nonexistant
        list_member_type* aux=head;
        if(aux->list_index==x) return aux;//head is the result
        while((aux->list_next_link)&&(aux->list_next_link->list_index < x)) aux=aux->list_next_link;//Horizontal scan. Find latest node with less x.
        if(!aux->list_next_link) return 0;//Didn't find it after a horizontal scan, all were less.
        if(aux->list_next_link->list_index > x) return 0;//Didn't find it either, next was greater.
        return aux->list_next_link;//Found it normally
    }
    template <typename list_member_type>
    bool DLListInsert(list_member_type* &head, list_member_type* temp)
    {
         if(find_edge<list_member_type>(head,temp->list_index)) return 1;//Duplicate entry
         if((!head)||(temp->list_index < head->list_index)) //new head
         {
                               temp->list_next_link=head;
                               temp->list_prev_link=0;
                               if(head) head->list_prev_link=temp;
                               head=temp;
         }
         else
         {
             list_member_type* aux=head;
             while((aux->list_next_link)&&(aux->list_next_link->list_index < temp->list_index))
             aux=aux->list_next_link;//Find previous
             temp->list_next_link=aux->list_next_link;
             temp->list_prev_link=aux;
             if(aux->list_next_link) aux->list_next_link->list_prev_link=temp;
             aux->list_next_link=temp;
         }
         return 0;
    }
    and my main.cpp:

    Code:
    #include <iostream>
    #include "List.h"
    using namespace std;
    typedef class node* np;
    class node: public DLListNode
    {
           public:
                int key;
    };
    class node* head=0;
    //np create();
    //void insert(np &head, np temp);
    //void _delete(np &head, int key);
    //void print(np x);
    /*Debug recommendation sequence, use print after each step. Has already been tested and correct.
    Insert 7 to test first element
    Insert 1 to test new head
    Insert 4 to test middle element
    Insert 9 to test last element. It must be now 1-4-7-9.
    Delete in the reverse sequence to test everything: 9,4,1,7.*/
    
    int main()
    {
        int option;
        do
        {
            system("cls");
            cout << "==--Double Linked List--==\n\n\n1.Insert\n2.Delete\n3.Print\n\n0.Exit\n\n\nEnter an option: ";
            cin >> option;
            system("cls");
            switch(option)
            {
                          case 1:
                                //insert(head,create());
                                np temp=new class node;
                                cout << "Enter key of new node: ";
                                cin >> temp->list_index;
                                DLListInsert<node>(head,temp);
                                break;
            }
        }while(option);
    }
    I read that "a pointer to a derived class is type-compatible with a pointer to its base class"[SIC]. Yet, when i complie, I get a single type of error multiple times: invalid conversion from DLListNode* to node*. What is going wrong?
    Last edited by Lord Asriel; 11-22-2011 at 08:37 AM.

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Just use a cast. Even though it is type compatible, that doesn't mean that you can do implicit conversions without the compiler complaining.

  11. #11
    Registered User
    Join Date
    Nov 2011
    Posts
    22
    So the compiler turned into a complainer? LOL sorry I had to add that. Thanks for the help!

  12. #12
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    A DLListNode is not necessarily a node.
    Why do I say that?

    Consider this:
    A Toyota is a car, but is a car a Toyota (always)?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 4
    Last Post: 04-17-2011, 06:36 PM
  2. Array of struct as function parameter
    By rotger in forum C Programming
    Replies: 12
    Last Post: 11-11-2010, 02:33 PM
  3. Passing array of struct as a function parameter
    By desmond5 in forum C Programming
    Replies: 5
    Last Post: 12-04-2007, 11:32 AM
  4. problem returning struct member from function
    By yukster in forum C Programming
    Replies: 6
    Last Post: 08-24-2003, 01:21 PM
  5. passing struct member to function
    By Sargnagel in forum C Programming
    Replies: 2
    Last Post: 01-06-2003, 05:55 PM

Tags for this Thread