Sign in to follow this  

Making LinkList Class Using Pointers.

This topic is 4838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello I am trying to make a Link List Class with void pointers. I am using void pointers because each Node can be a different class but they all should link together. Also I want the link list class to know what the head is so I decided to have a static void pointer called Head. I have it static because every node has the same head so it would make sense for the head to be a static void pointer. My problem is that I get this linking error when I compile my program. Link List error LNK2020: unresolved token (0A000010) ?Head@LinkList@@2PAXA Link List fatal error LNK1120: 1 unresolved externals Here is the code any help would be most welcome.
#include <iostream>
#include <new>
#include <stdio.h>
using namespace std;
class LinkList
{

  public:
  template <class X> X *CreateObject(X Head);
  template <class X> X *FindEndObject(X *Node);
  template <class X> void AddToLinkList(X *Adding,void *LastObject);
  template <class X> void MakeNewObject(X NewThing);
  void *Next;
  static void *Head;

};
class Player
{
 public:
 LinkList Node;
 char Face[20];
};

int main(int argc, char *argv[])
{
   Player Frank;
   Frank.Node.Head = &Frank;

}

template <class X> X *LinkList::CreateObject(X Head)
{
  X *Sample = new X;
  return Sample;
  
}

template <class X> X *LinkList::FindEndObject(X *Node)
{
    X* tmpRoom = static_cast<X*>(Node);
    while(tmpRoom->Next)
    {
      tmpRoom = static_cast<X*>(tmpRoom->Next);
    }
    return tmpRoom;
}

template <class X> void LinkList::AddToLinkList(X *Adding,void *LastObject)
{
  X* Temp = reinterpret_cast<X*>(LastObject);
  Temp->Next = Adding;
}

template <class X> void LinkList::MakeNewObject(X NewThing)
{
  AddToLinkList(CreateObject(NewThing),FindEndObject(Next));

}

Fruny - added code tag. [Edited by - Fruny on September 12, 2004 2:18:56 PM]

Share this post


Link to post
Share on other sites
The thing is that the LinkList class will also be used for another group of classes. Like class Food,Eq,Money will be in one link list and another class Room,Store etc.. will be in another link list. And I want the LinkList class to be used to create many link list. That is why I have them as Templates and using void pointers. Because I never know what class the node will be and that their will be different type of classes in one link list so I didnt think they was any other way to solve my problem.

Share this post


Link to post
Share on other sites
first you've declared a class/static member you have not defined it yet so outside of the class just add:


void* LinkList::Head(0);


Secondly if you really need a list of void pointers you would be better of using the standard library list.

thirdly there are probably a million better ways you could do to avoid such a thing because every time you add an element you've lost its type and you can't guarantee to cast it back to the proper type when needed so you can't for example release the memory you've allocated on the heap properly.

Share this post


Link to post
Share on other sites
How would I use the standard library to solve this problem? I never seen anything in it that would help me besides using vectors. And I heard some where their is a serious down fall to using vectors something like it takes alot more memory. And these link list will be 1000 plus long so there will already be alot of meomory being used.

Share this post


Link to post
Share on other sites
How would I use the standard library to solve this problem? I never seen anything in it that would help me besides using vectors.

There is a std::list class template.

And I heard some where their is a serious down fall to using vectors something like it takes alot more memory.

std::vector does over-allocate to allow you to add elements without requiring an allocation every time, but it is not a "serious downfall".

And these link list will be 1000 plus long so there will already be alot of meomory being used.

1000+ elements is not a lot. Unless your objects are tiny, the linked list overhead: two pointers per list object and two pointers per element (it is a doubly-linked list) is not worth losing sleep over.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
How would I use the standard library to solve this problem? I never seen anything in it that would help me besides using vectors.

There is a std::list class template.

And I heard some where their is a serious down fall to using vectors something like it takes alot more memory.

std::vector does over-allocate to allow you to add elements without requiring an allocation every time, but it is not a "serious downfall".

And these link list will be 1000 plus long so there will already be alot of meomory being used.

1000+ elements is not a lot. Unless your objects are tiny, the linked list overhead: two pointers per list object and two pointers per element (it is a doubly-linked list) is not worth losing sleep over.


i'll like to add to that, once you done that and profiled your code and you really do find a performance issue then you can customize STL containers you can give it a custom allocator type, as pointers & smart pointers are small objects & there the same size then you could write or use a pre-written pooled allocator for the container of pointers.

Share this post


Link to post
Share on other sites
If I used the std::list is there a way the list can contain unknown class types? Or should I just make a list of void pointers and just store the address in the list I guess it would be pretty much the same thing and the fact that I am only storing addresses there shouldnt be any memory problem.

Share this post


Link to post
Share on other sites
It doesn't make much sense to store "unknown class types". In general, people store pointers to some common base class (not void*!) and rely on polymorphism.

And yes, there can be memory problems: there are situations where a single object can have multiple addresses! Converting between types in the object's hierarchy will fix the address as required, but converting to/from a void* will not.

Share this post


Link to post
Share on other sites
A list that can contain items of different unknown types at the same time. Basically the reason I am doing this is because I am making a console game and I want to be some kind of list that holds all the information of a player inventory. But there are many items that can be in a player inventory like Food, Weapon, Equipment, Money etc.. Each classes are different but they all need to go in the player inventory list. Each classes are totally different besides basic things like Name,Description and weight. But besides that they have nothing in common. So that is why I need a list that can hold the information of several different classes at the same time.

Share this post


Link to post
Share on other sites
Well, then your types are related - they all are types of things that can go in an inventory. You will have to give them a common base class (InventoryItem ?) and make a list of pointers to that class.

And before you ask - type fields are evil.

Share this post


Link to post
Share on other sites
If I store what kind of class each class is in a string for example string ClassType = "Room"; so if I want to use the void pointer I would then check to see what it ClassType is and when it matches I convert the void pointer to the proper class using
reinterpret_cast. I would be able to convert the void pointer to the correct object because I would then know what kind of object it is.

Share this post


Link to post
Share on other sites
As I said, type fields are evil. And reinterpret_cast is a cast of last resort, you know...


class Item
{
public:
virtual ~Item() {}

virtual void ShowInventoryLine() = 0;
};

class Armor : public Item
{
void ShowInventoryLine() { /* ... */ }
void SomeArmorFunction() { /* ... */ }
};

class Weapon : public Item
{
void ShowInventoryLine() { /* ... */ }
void SomeWeaponFunction() { /* ... */ }
};

std::list<Item*> inventory;
inventory.push_back(new Armor);
inventory.push_back(new Weapon);

...

std::list<Item*>::iterator itor;
for(itor = inventory.begin(); itor != inventory.end(); ++itor)
(*itor)->ShowInventoryLine();

...

for(itor = inventory.begin(); itor != inventory.end(); ++itor)
if( Armor* armor = dynamic_cast<Armor*>(*itor) )
armor->SomeArmorFunction();
else if ( Weapon* weapon = dynamic_cast<Weapon*> )(*itor) )
weapon->SomeWeaponFunction();
else WhatShouldIDoWithThatCrap(*itor);



With virtual functions, the compiler itself keeps track of the type of the object (the hidden virtual function table pointer effectively acts as a type field).

The latter part of the code (the tests on dynamic_cast) falls into the category of capability queries, which are sometimes unavoidable but are often the sign of a design problem - and they make adding new types complicated, since you have to add new if statements everywhere.

Containers of unrelated types are not a great idea --- to go back to your last post (as of the time of this writing), why would you want to mix Rooms with Weapons in a single container, knowing that you will have to separate them again to use them at all?

Share this post


Link to post
Share on other sites
Rooms are not going to be in the same list. There will be different type of Rooms like Shops,DeathTrap, etc.. that will be in a list. And then there will be another list of Items like Weapons,Food,Money etc... So Rooms and Items will not be in the same list.

Share this post


Link to post
Share on other sites
Ok, so what is the purpose of each list?

Generally, when you do have a list (or some other kind of container), that means you are going to walk down and do some common operation on each element. You have to figure out what those operations are going to be, and use that to define the base type that you are going to use for the list elements.

For example, in the case of your inventory list, you will have inventory items, that can be looked at, equipped, used ...

Share this post


Link to post
Share on other sites
Obey Fruny. Obey your overlord.

All praise be to Cthulu.

Though really, I must agree with Fruny here. I was at a similar debate once, I went with defining a base Node interface that was implemented by all sorts of objects.

I still dont see why you are making this so complicated. How about just have a ListNode class that has prev, next pointers to other ListNode classes, and that stores the data along with the metadata you need to describe the data it is holding?

Share this post


Link to post
Share on other sites
I guess the fact that I dont know much about the STL or LinkList is why I am probably not doing things the /right/ way. I am going to read up on something I didn't quite understand from the code Funy provided and from others post. Lack of knowledge is probably the reason this Thread is lasting so long with this same problem.

Share this post


Link to post
Share on other sites

This topic is 4838 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this