Help with Template

[eboyd]

I'm trying to learn how to better use templates. I've given myself a very straightforward assignment:

Create a linked-list template class.

What I'm wondering is if i have a private class for the Node and friend classes for the List and Iterator, which class/es need to be templated?


For clarification:

Code: Select all

class Node{
    friend class Iterator;
    friend class List;
    Node* next;
    type data;
}

class List, etc.
class Iterator, etc.

If "type data" is what I want templated, does only Node need to be a template? Or do they all need to be templated?[/code]

[os64dev]

write out the code and it will become clear.

Code: Select all

template<typename T>
class Node {
    friend class Iterator;
    friend class List;
    Node * next;
    T data;
};

now the problem for the iterator class is that you need to secify the type because Node<int> is something different then Node<char> and this i think is already the answer to your question. For a proper implementation of list look into the STL or BOOST libraries. They might be daunting at first glance but explain a lot.

[eboyd]

I see the func()s but can you point me to the headers? I'm under the impression that the STL List uses a public struct Node to encapsulate the <type>data.

There's a million ways to make a linked-list. I would like to keep Node a private class (hence the friends). My iterator class won't be quite like the STL iterator, mine will really just be overloaded operators allowing for things like myList++ to advance.

Really, I hardly ever overload operators, but Candy's convinced me to look into templates and the STL, and realistically I guess I should get used to writing re-usable code. I'm used to writing functions like:

Code: Select all

object* get_obj(){ return some_pointer; }

But I guess that's not going to help someone who expects an overloaded assignment operator, iterators, etc.

[Candy]

I see the func()s but can you point me to the headers? I'm under the impression that the STL List uses a public struct Node to encapsulate the <type>data.

There's no point in making the node class public. You can never pass any of its pointers to the outside world since you only use iterators for that. Make it a private inner class.

There's a million ways to make a linked-list. I would like to keep Node a private class (hence the friends). My iterator class won't be quite like the STL iterator, mine will really just be overloaded operators allowing for things like myList++ to advance.

Hardly a million, I suspect only a few thousand if you include very odd schemes; about a dozen practical ones. These include the array list (list based on array, usually slow), the singly linked list and the doubly linked list. My personal default is the singly linked list since it's not much more complex than a doubly linked one, very efficient with space and easy to make generic.STL's list is by definition a doubly linked list but most implementations also provide an slist.

Really, I hardly ever overload operators, but Candy's convinced me to look into templates and the STL, and realistically I guess I should get used to writing re-usable code. I'm used to writing functions like:

Code: Select all

object* get_obj(){ return some_pointer; }

But I guess that's not going to help someone who expects an overloaded assignment operator, iterators, etc.

Woo! I convinced somebody!

Reusable code is infinitely more usable than normal code, especially because it's reusable. More importantly (which most people forget - I'm not in it to cut time) is that reusable code is used a lot more, tested much more thoroughly and therefore much more reliable.

At work people are used to just reimplement the list when you hit another location since it's a bit of work to make a generic one and it doesn't really pay off directly. I've added a generic one to the fray, making it a total of a few hundred implementations of a list. At least 10% of these contain an error, which almost never shows. Half of them is pure code duplication.

[eboyd]

Oh, I totally agree that a public Node is retarded. I've just seen many implementations that way. In school we were taught to use inheritance. However, a lot of people around here seem to feel poopoo towards inheritance in gerneral.

Really, what's the difference between:

Code: Select all

class Node{
    protected:
         Node* next;
         type data;
};
class List:public Node{
    private:
         Node* head;
};

and...

Code: Select all

class Node{
    Node* next;
    type data;
    friend class List;
};
class List{
    private:
        Node* head;
};

Advantages/Disadvantages of either way?

[Candy]

Code: Select all

class Node{
    protected:
         Node* next;
         type data;
};
class List:public Node{
    private:
         Node* head;
};

and...

Code: Select all

class Node{
    Node* next;
    type data;
    friend class List;
};
class List{
    private:
        Node* head;
};

Advantages/Disadvantages of either way?

The first requires you to make node public and exposes your inner data. The latter requires a friend declaration, which is equally bad.

Code: Select all

template <typename T>
class list {
    class entry {
      public:
        T item;
        entry *next, *prev;
    };
    entry *head, *tail;
public:
    // interface
};

[eboyd]

Candy, you make me feel like some hapless fool fumbling around with lines of code like I don't have a clue in the world!

Thanks for the advice though, I'll give it a whirl!

[eboyd]

BTW, what's the difference in templates between <class T> and <typename T>?

[pcmattman]

BTW, what's the difference in templates between <class T> and <typename T>?

Nothing. "typename" is probably easier to understand, though.

If you all want a linked list template class (that is really simple) I can post it.

[eboyd]

I'd like to take a ganders at it!

[pcmattman]

LinkedList.hpp:

Code: Select all

/***************************************************************************\
 * The Mattise Kernel														*
 * Copyright 2007 Matthew Iselin											*
 * Licensed under the GPL													*
 *																			*
 * LinkedList.hpp															*
 *																			*
 * Easy-to-use linked list class for any type.								*
 *																			*
\***************************************************************************/

//--------------- Includes ---------------//

// These are dependent on your system...

#include <iostream>
#include <stdio.h>

//--------------- Class Definition ---------------//

/**
	The CLinkedList class basically is a shell around a certain data
	type. It allows linked lists to be created for any data type,
	hence saving coding time.
**/

// main class
template< class _T > class CLinkedList
{
	public:

		// initializes the list
		CLinkedList();

		// destroys all data in the list
		~CLinkedList();

		// dumps the list
		void Dump();

		// clears the list
		void Clear();

		// inserts data at the given offset, shifting everything else
		int Insert( _T, int );

		// pushes data onto the end of the list
		int Push( _T );

		// pops data off the end of the list
		_T Pop();

		// gets data from the list
		_T Get( int );

		// deletes an item
		void Delete( int );
		
		// retrieves the size
		int Size();
		
		// gets data using a random-access operator
		_T operator [] ( int i );

	private:

		// the list type
		struct myType
		{
			_T data;
			struct myType* next;
			struct myType* prev;
		};

		// the start of the list
		struct myType start;
		
		// size of the list
		int size;
};

template< class _T > CLinkedList<_T>::CLinkedList()
{
	// set the next and prev fields of start to null
	start.next = start.prev = (struct myType*) NULL;
	
	// there are no elements yet
	size = 0;
}

template< class _T > CLinkedList<_T>::~CLinkedList()
{
	// clear the list, free the memory
	Clear();
}

template< class _T > int CLinkedList<_T>::Size()
{
	// return the size
	return size;
}

template< class _T > void CLinkedList<_T>::Dump()
{
	// iterate through the list, displaying information about each item

	// running pointer
	struct myType* curr = start.next;

	// running accumulator
	unsigned int i = 0;

	// dump each item
	while( curr != (struct myType*) NULL )
	{
		// print it - this may not be a really good idea :D
		cout << "LIST[" << i++ << "]: " << curr->data << endl;

		// get the next pointer
		curr = curr->next;
	}
}

template< class _T > int CLinkedList<_T>::Push( _T d )
{
	// find the end of the list, then append the data

	// running pointers
	struct myType* prev, *curr = &start;

	// wait until curr is null
	while( curr != (struct myType*) NULL )
	{
		// save the current pointer
		prev = curr;

		// load the next one
		curr = curr->next;
	}

	// check that the one we want to add to isn't null
	if( prev == (struct myType*) NULL )
	{
		// fail!
		return -1;
	}

	// safe, so append - we need to make a structure first
	struct myType* m = (struct myType*) malloc( sizeof( struct myType ) );
	m->prev = prev;
	m->next = (struct myType*) NULL;
	m->data = d;

	// fill it in
	prev->next = m;
	
	// one more element
	size++;

	// success!
	return size-1;
}

template< class _T > _T CLinkedList<_T>::Pop()
{
	// find the end of the list, and remove it after saving its data

	// running pointers
	struct myType* prev, *curr = &start;

	// wait until curr is null
	while( curr != (struct myType*) NULL )
	{
		// save the current pointer
		prev = curr;

		// load the next one
		curr = curr->next;
	}

	// check that prev isn't null
	if( prev == (struct myType*) NULL )
	{
		// return start's data
		return start.data;
	}

	// prev holds the data we want
	_T ret = prev->data;

	// now unlink prev (the previous one's next is NULL)
	prev->prev->next = (struct myType*) NULL;

	// and free the pointer
	free( prev );
	
	// one less element
	size--;

	// return the data
	return ret;
}

template< class _T > _T CLinkedList<_T>::Get( int offset )
{
	// loop through the list until we hit either NULL or the offset

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return start.data;

	// return the data
	return curr->data;
}

template< class _T > void CLinkedList<_T>::Delete( int offset )
{
	// loop through the list until we hit either NULL or the offset
	// then unlink it

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return;

	// unlink the item
	if( curr->prev )
		curr->prev->next = curr->next;
	if( curr->next )
		curr->next->prev = curr->prev;
	
	// one less element
	size--;

	// free the memory
	free( curr );
}

template< class _T > int CLinkedList<_T>::Insert( _T d, int offset )
{
	// loop through the list until we hit either NULL or the offset
	// then append data to it

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return -1;

	// create a new item
	struct myType* m = (struct myType*) malloc( sizeof( struct myType ) );
	m->data = d;
	m->next = curr->next;
	m->prev = curr;

	// link it into the list
	curr->next = m;
	
	// one more element
	size++;

	// success!
	return 0;
}

template< class _T > void CLinkedList<_T>::Clear()
{
	// iterate through the list, freeing memory as we go

	// running pointers - never start at 'start' because it isn't heap allocated
	struct myType* savnext, *curr = start.next;

	// delete each item
	while( curr != (struct myType*) NULL )
	{
		// save this one's next
		savnext = curr->next;

		// delete this one
		kfree( curr );

		// get the next pointer
		curr = savnext;
	}

	// and make sure start is setup properly
	start.next = (struct myType*) NULL;
	start.prev = (struct myType*) NULL;
	
	// there are no elements
	size = 0;
}

template< class _T > _T CLinkedList<_T>::operator [] ( int i )
{
	return Get( i );
}

I've used this class in my own OS, and in a game engine I wrote once. If there are any 'jmalloc' or 'kfree' calls left, replace them with 'free' or 'malloc', or whatever function you use to allocate memory.

Edit: Stupid tabs always only ever look good in the editor...

[eboyd]

Maybe Candy can tell me if I'm heading in the right direction
(I'm starting with a singly-linked list to get my feet wet)

Code: Select all

template <typename T> class SList{
    
    public:
        
        SList() : head(0) {}
        
        /*
        Slist(const Slist& src);
       ~Slist();
        
        void pushFront(int);
        void pushBack(int);
        void popFront();
        void popBack();
        void insert();
        void remove();
        T retrieve(int);
        int search(T);
        */
        
    private:
        
        class Node{
            
            int id;
            T data;
            Node *next;
            Node(Node* init) : next(init) {}
            Node(T _dat) : next(0), data(_dat) { assign(); }
            
            void assign(){ this->id = 0; } // This func obviously not written yet
        };
        
        Node *head;
};

[Candy]

Code: Select all

template <typename T> class SList{
    public:
        SList() : head(0) {}
        
        /*
        Slist(const Slist& src);
       ~Slist();
        
        void pushFront(int);
        void pushBack(int);
        void popFront();
        void popBack();
        void insert();
        void remove();
        T retrieve(int);
        int search(T);
        */

You seem to have the signature for push_back, push_front a bit off. They normally take a const T reference. Insert and remove take an iterator (which you don't have, so that's ok) and normally there's an erase function as well.

Given the signature of your retrieve function I think you're making a map, not a list.

Code: Select all

    private:
        class Node{
            int id;
            T data;
            Node *next;
            Node(Node* init) : next(init) {}
            Node(T _dat) : next(0), data(_dat) { assign(); }
            
            void assign(){ this->id = 0; } // This func obviously not written yet
        };
        Node *head;
};

Yep, that appears to be a map. Try not to add the id mechanism yet, just make a plain list of objects.

[eboyd]

I can understand the "const correctness" but why a reference argument?

Code: Select all

void push_front(const T&);  // ?????????

[Colonel Kernel]

I can understand the "const correctness" but why a reference argument?

Code: Select all

void push_front(const T&);  // ?????????

Because T could be a very large type. You wouldn't want to pass 512 byte structures around by value, for example. You already have to make one copy to add it to the list -- there's no need to make extra copies while passing it to push_back().