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!

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.

>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 ? )

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.

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.

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.

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.

Actually, I will start using your idea white. See where it leads me. Thanks :)

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?

Just use a cast. Even though it is type compatible, that doesn't mean that you can do implicit conversions without the compiler complaining.

So the compiler turned into a complainer? LOL sorry I had to add that. Thanks for the help!

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)?