This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

 
  Template List Class
  Submitted by



Disclaimer: I cannot be held responsible for any faults or errors caused by or resident in this code. Introduction: The code I now am posting is a template list class. It's very similar to the STL template list class, the major difference is that this list is only singly linked (unidirectional), furthermore the use of iterators with this list class is a bit different. The main difference in usage (compared with STL::list) is the way the iterators work -- you can't reverse with iterators from the jsh::list class and if you want a constant iterator you use const iterator -- not const_iterator -- note the absence of the underscore. One defecite with this is that you cannot pass a const iterator& to a function and expect it not to change the element of a the list pointed to by the iterator, the eaisy soulution to this is of course to use a const iterator (no reference). The memory usage of an iterator is very small and the copy constructor just takes nominal time. The functions that are implemented for this list class are these (note that many STL functions are not present): 
name			speed			usage
[constructor]		constant/fast		[constructor]
[copy constructor]	variable/medium	        [copy constructor]
[destructor]		variable/mediem	        [destructor]
[operator=]		variable/medium	        [operator=]
push_front		~constant/fast		put argument at front
push_back		~constant/fast		put argument at back
pop_front		~constant/fast		remove front element
begin			constant/fast		get iterator of first element
end			constant/fast		get iterator of last element
front			constant/fast		get first value
back			constant/fast		get last value
size			constant/fast		get number of elements stored
empty			constant/fast		is list empty? true/false
clear			variable/medium	        remove all elements of list
remove		        variable/slow		remove all elements with value equal to argument
erase			variable/slow		remove element pointed to by argument
insert			variable/slow		put second argument before first argument
insert_after*		variable/slow		put second argument after first
swap			constant/fast		swap list with argument
reverse		        variable/medium	        reverse order of elements
(* == not an STL function)



Here is a sample program showing the usage of the jsh::list class.

#include <stdio.h
#include <conio.h
#include "List.h"

void print(const jsh::list<int& list);


int main()
{
	printf("processing...\n");
	jsh::list<int list;
	jsh::list<int list2;
	//add various values to lists
	list.push_back(0);
	list.push_back(1);
	list.push_back(0);
	list.push_back(3);
	list.push_back(4);
	list.push_back(1);
	list.push_back(0);
	list.push_back(5);
	list2.push_back(6);
	list2.push_back(7);
	list2.push_back(8);
	list.push_front(-4);
	list.remove(0);
	list.remove(5);
	list.remove(45);
	jsh::list<int::iterator it = list.begin();//make an iterator
	//do various operations with iterator
	while (!list.empty())
	{
		if (*it == 4) list.erase(it);
		if (*it == 3) (*it)++;
		if (*it == 1) list.insert(it, 2);
		if (it == list.end()) break;
		it++;
	}
	print(list);
	printf("swapping...\n");
	list.swap(list2);
	print(list);
	printf("reversing...\n");
	list.reverse();
	print(list);
	printf("press any key to exit!");
	getch();
	return false;
}


void print(const jsh::list<int& list)
{
	//a constant iterator cannot be used to modify contents of a list

	const jsh::list<int::iterator it = list.begin();
	for (int i = 0; i < list.size(); i++, it++) printf("%d\n", *it);
}



If you have any questions or comments regarding the code you can send me a mail at jesper@atrad.se.

Download Associated File: templateListClass.h (7,048 bytes)

/*
  Simple unidirectional list class.
  Copyright (c) 2003, Jesper qvist

  [comments]
  You may use this code for any purpose, provided that you maintain
  this copyright notice.

  [created] 2003-02-28
  [updated] 2003-03-24
*/

#ifndef _jsh_list_h
#define _jsh_list_h

namespace jsh{

template <class _t>
class list
{
	struct _node
	{
		_t _value;
		_node* _next;

		_node() {}
		_node(const _node& _a) {*this = _a;}
		_node& operator=(const _node& _a) {_value = _a._value;_next = _a._next;}
		~_node() {}
	};
	_node* _front;
	_node* _back;
	unsigned int _size;

public:
	list<_t>(): _front(NULL), _back(NULL), _size(0) {}
	list<_t>(const list<_t>& _a): _front(NULL), _back(NULL), _size(0) {*this = _a;}
	list<_t>& operator=(const list<_t>& _a){
		clear();
		_node* _tmp = _a._front;
		while (true){
			if (_tmp == NULL) return *this;
			push_back(_tmp->_value);
			_tmp = _tmp->_next;}}
	~list<_t>() {clear();}

	class iterator
	{
		friend class list<_t>;
	protected:
		mutable _node* _pointer;

		const iterator& operator--() const {/*NOT a bidirectional iterator*/}
		const iterator operator--(int) const {/*NOT a bidirectional iterator*/}
		iterator& operator--() {/*NOT a bidirectional iterator*/}
		iterator operator--(int) {/*NOT a bidirectional iterator*/}

	public:
		iterator(): _pointer(NULL) {}
		iterator(const iterator& _a) {*this = _a;}
		iterator(_node*const& _a): _pointer(_a) {}
		~iterator() {}

		const iterator& operator=(const iterator& _a) const {_pointer = _a._pointer;return *this;}
		const iterator& operator=(const _node*const& _a) const {_pointer = _a;return *this;}
		const iterator& operator=(_node*& _a) {_pointer = _a;return *this;}

		const _t& operator*() const {return _pointer->_value;}
		const _t* operator->() const {return &_pointer->_value;}
		_t& operator*() {return _pointer->_value;}
		_t* operator->() {return &_pointer->_value;}
		const iterator& operator++() const {_pointer = _pointer->_next;return *this;}
		const iterator operator++(int) const {iterator _tmp(*this);++(*this);return _tmp;}
		iterator& operator++() {_pointer = _pointer->_next;return *this;}
		iterator operator++(int) {iterator _tmp(*this);++(*this);return _tmp;}
		bool operator==(const iterator& _a) const {return (_pointer == _a._pointer);}
		bool operator!=(const iterator& _a) const {return (_pointer != _a._pointer);}
		bool operator==(const _node*const& _a) const {return (_pointer == _a);}
		bool operator!=(const _node*const& _a) const {return (_pointer != _a);}
		friend bool operator==(const _node*const& _a, const iterator& _b) {return (_a == _b._pointer);}
		friend bool operator!=(const _node*const& _a, const iterator& _b) {return (_a != _b._pointer);}
	};

	void push_front(const _t& _a);//put value at front
	void push_back(const _t& _a);//put value at back
	void pop_front();//remove front element
	const iterator begin() const {return iterator(_front);}//constant iterator
	iterator begin() {return iterator(_front);}//non-constant iterator
	const _t& front() const {return _front->_value;}//consant reference
	_t& front() {return _front->_value;}//non-constant reference
	const iterator end() const {return iterator(_back);}//constant iterator
	iterator end() {return iterator(_back);}//non-constant iterator
	const _t& back() const {return _back->_value;}//constant reference
	_t& back() {return _back->_value;}//non-constant reference
	unsigned int size() const {return _size;}//size of list
	bool empty() const {return (!_size);}//is list empty?
	void clear() {while (!empty()) pop_front();}//erase all the contents of the list
	void remove(const _t& _a);//remove all elements with values equal to argument
	void erase(iterator& _a);//erases iterator from list
	void insert(iterator& _a, const _t& _b);//insert _b in front of _a
	void insert_after(iterator& _a, const _t& _b);//insert _b after _a
	void swap(list<_t>& _a){//swaps this list with argument
		_node* _tmp;_tmp = _front;_front = _a._front;_a._front = _tmp;
		_tmp = _back;_back = _a._back;_a._back = _tmp;
		unsigned int _tmp2 = _size;_size = _a._size;_a._size = _tmp2;}
	void reverse(){//reverses order of elements
		list<_t> _new;
		while (!empty()){
			_new.push_front(front());
			pop_front();}
		swap(_new);}
};

template <class _t>
void list<_t>::push_front(const _t& _a)
{
	if (!empty())
	{
		_node* _new = new _node;
		_new->_next = _front;
		_front = _new;
	}
	else
	{
		_front = new _node;
		_front->_next = NULL;
		_back = _front;
	}
	_front->_value = _a;
	_size++;
}

template <class _t>
void list<_t>::push_back(const _t& _a)
{
	if (!empty())
	{
		_back->_next = new _node;
		_back = _back->_next;
	}
	else
	{
		_front = new _node;
		_back = _front;
	}
	_back->_value = _a;
	_back->_next = NULL;
	_size++;
}

template <class _t>
void list<_t>::pop_front()
{
	if (empty()) return;
	if (_front == _back)
	{
		delete _front;
		_front = _back = NULL;
	}
	else
	{
		_node* _tmp = _front->_next;
		delete _front;
		_front = _tmp;
	}
	_size--;
}

template <class _t>
void list<_t>::remove(const _t& _a)
{
	_node* _tmp = _front;
	_node* _tmp2 = _tmp;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp->_value == _a)
		{
			if (_tmp == _front)
			{
				pop_front();
				if (empty()) return;
				_tmp = _tmp2 = _front;
				_tmp = _tmp->_next;
			}
			else
			{
				_tmp2->_next = _tmp->_next;
				if (_tmp == _back) _back = _tmp2;
				delete _tmp;
				_tmp = _tmp2->_next;
				_size--;
			}
			continue;
		}
		_tmp2 = _tmp;
		_tmp = _tmp->_next;
	}
}

template <class _t>
void list<_t>::erase(iterator& _a)
{
	_node* _tmp = _front;
	_node* _tmp2 = _tmp;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp == _a)
		{
			if (_tmp == _front)
			{
				pop_front();
				_a = _front;
			}
			else
			{
				_tmp2->_next = _tmp->_next;
				if (_tmp == _back) _back = _tmp2;
				delete _tmp;
				_a = _tmp2->_next;
				_size--;
			}
			return;
		}
		_tmp2 = _tmp;
		_tmp = _tmp->_next;
	}
}

template <class _t>
void list<_t>::insert(iterator& _a, const _t& _b)
{
	_node* _tmp = _front;
	_node* _tmp2 = _tmp;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp == _a)
		{
			if (_tmp == _front)
				push_front(_b);
			else
			{
				_tmp2->_next = new _node;
				_tmp2 = _tmp2->_next;
				_tmp2->_next = _tmp;
				_tmp2->_value = _b;
				_size++;
			}
			return;
		}
		_tmp2 = _tmp;
		_tmp = _tmp->_next;
	}
}

template <class _t>
void list<_t>::insert_after(iterator& _a, const _t& _b)
{
	_node* _tmp = _front;
	while (true)
	{
		if (_tmp == NULL) return;
		if (_tmp == _a)
		{
			if (_tmp == _back)
				push_back(_b);
			else
			{
				_node* _tmp2 = _tmp->_next;
				_tmp->_next = new _node;
				_tmp = _tmp->_next;
				_tmp->_next = _tmp2;
				_tmp->_value = _b;
				_size++;
			}
			return;
		}
		_tmp = _tmp->_next;
	}
}

};

#endif _jsh_list_h

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

 

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.