Jump to content
  • Advertisement
Sign in to follow this  
kingpinzs

Linked list questions in c++

This topic is 2704 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

I am working on a very simple linear single linked list in c++

My question is how can I make a class that can take either {1,2,3....n+1} data types?

For example
I want to creat a list that takes int as the data type
using the same class but differnt program I want to use the list to take strings and int as data types with out having to make 2 seprate lists.

list<int>
list<string,int>

I am using templates so any data type can be used

Share this post


Link to post
Share on other sites
Advertisement
Just to be sure: you want to be able to create a list where, for example, the first element is a string, the next is an int, the next might be a double, and then a float, and so on?

The usual way of doing this is to first think carefully about the behaviour you expect of each type you want to store in the list. Then create a polymorphic base class with virtual functions that represent the distillation of that behaviour. For example, if all you want to be able to do is display the elements to an ostream, your list's node might be something like this:


struct node
{
node() : next(0) { }
virtual ~node() { }
virtual std::ostream &display(std::ostream &out) const = 0;
// maybe other virtual functions here, too e.g. clone()

node *next;
};


and you'd also have a template class that inherits from 'node' and happens to implement the display() function for the given type:


template<typename T>
struct typed_node : node
{
typed_node(const T &data) : data(data) { }
virtual std::ostream &display(std::ostream &out) const { return out << data; }

T data;
};


Finally, the method that adds a function to your list would be a template method:


template<typename T>
void list::push_back(const T &data)
{
node *n = new typed_node<T>(data);
// TODO: adjust pointers in list s.t. n is at the end
// ...
}


Other alternatives include:

1. not having the 'next' element in the node base class and use an std::list<node*> instead.
2. std::list<boost::any>
3. std::list<boost::variant>
4. use Python or another dynamically typed language (to a certain degree, this is what the above system is simulating anyway)

Share this post


Link to post
Share on other sites

Why not make a structure which contains int and string and store that?

That doesn't really fit the OP's requirements (among other thing, the OP wants to use templates).

Share this post


Link to post
Share on other sites

[quote name='CzarKirk' timestamp='1298207008' post='4776652']
Why not make a structure which contains int and string and store that?

That doesn't really fit the OP's requirements (among other thing, the OP wants to use templates).
[/quote]

You can still have a template. When you want only int, use only int. But if you want a single list which can store both ints and strings, use a struct as the template parameter that holds both types but only use one of them. There will be a few bytes of wasted space but not the end of the world.

Share this post


Link to post
Share on other sites
not really what I was meaning. the linked list needs a string and a int in the same node. and uses class's not structs. The template is going to allow what verible tpe can be used but how can you use more then one without making more then one list.

Share this post


Link to post
Share on other sites

not really what I was meaning. the linked list needs a string and a int in the same node.

So what's the problem? Create a small data type containing both a string and an int.


and uses class's not structs.
[/quote]
The difference between a class and a struct is probably smaller than you think. Use 'class' instead of 'struct' if you want. My example code didn't because it would have involved more boilerplate.


The template is going to allow what verible tpe can be used but how can you use more then one without making more then one list.
[/quote]

struct data_pair
{
data_pair() : s(), i(0) { }
std::string s;
int i;
};

std::list<data_pair> mylist;


Or use std::pair:


typedef std::pair<std::string, int> data_pair;
std::list<data_pair> mylist;



EDIT: so re-examining your initial question:
My question is how can I make a class that can take either {1,2,3....n+1} data types?[/quote]
This is tricky without variadic templates (coming to C++ soon, but not quite there yet). You'd have to use something commonly called type-lists or look at some of the stuff in boost::mpl and boost::fusion (which is quite advanced and not for the timid).

But! Why do you want to do this? There might be a better way.

Share this post


Link to post
Share on other sites
is there a way to use

struct user
{
string name;
int id;
};

as the data type for a linked list?

the class for the linked list looks like this

template <class Item>

class node
{
public:
typedef Item value_type;

node(const value_type& init_data = value_type(),const node* init_link = NULL)
{
data_field = init_data; link_field = init_link;
}
void set_data(const value_type& new_data){data_field = new_data;}
void set_link(node* new_link) {link_field = new_link;}

value_type data() const{return data_field;}

const node* link() const{return link_field;}
node* link() {return link_field;}
protected:
private:
value_type data_field;
node *link_field;
};


Share this post


Link to post
Share on other sites
If your class is written correctly it should be able to accept such user defined types as template arguments. Have you tried it?

But why not just use std::list or std::vector?

Share this post


Link to post
Share on other sites
becuase I need to learn the data structures and the best way to do it is create the data structure from scratch first.

Second I did try it and it errors out.

I am just not sure how to call it.

user p ;
p.name = "ted";
p.id =12;
node<user> *head_ptr;
node<user> *tail_ptr;

node<user> r;

head_ptr = NULL;
tail_ptr = NULL;

I have tryed
head_ptr = p;

and
r = new node<user>(p)

and I get error
no match for 'operator=' in 'r = (operator new(12u), (<statement>, ((node<user>*)<anonymous>)))'|
candidate is: node<user>& node<user>::operator=(const node<user>&)|
In constructor 'node<Item>::node(const value_type&, const node<Item>*) [with Item = user, value_type = user, node<Item> = node<user>]':|


so I have no idea ho to make a struct the template data to pass to my linked list class

I kno I can just change the linked list class to take the string and int but I need it to be more genral then that.

Not sure of any other way to do that.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!