双方向チェーンテーブルのC++クラステンプレート実装
11447 ワード
ヘッダファイル:
実装ファイル:
テストファイル:
/*****************************************************************************
* doublelist.h
*
* Double List.
*
* This class template includes a smart pointer supporting "*", "++", "--",
* "==" and "!=" operations, which makes it easy to implement the frequently
* used operations, such as "is empty", "make empty", "begin", "end", "fornt",
* "back", "push front", "push back", "pop front", "pop back", "insert",
* "erase" and so on.
*
* Zhang Ming, 2009-10
*****************************************************************************/
#ifndef DOUBLELIST_H
#define DOUBLELIST_H
#include <iostream>
namespace itlab
{
/**
* List Node
*/
template <typename Type>
struct Node
{
Type data;
Node<Type> *prev;
Node<Type> *next;
Node( const Type &d=Type(), Node<Type> *p=NULL, Node<Type> *n=NULL )
: data(d), prev(p), next(n)
{ }
};
// class Node
/**
* List Iterator
*/
template <typename Type> class DList;
template <typename Type>
class ListItr
{
friend class DList<Type>;
public:
ListItr();
ListItr( Node<Type> *p );
~ListItr();
inline Type& operator*();
inline const Type& operator*() const;
inline ListItr& operator++();
inline ListItr operator++( int );
inline ListItr& operator--();
inline ListItr operator--( int );
inline bool operator==( const ListItr &rhs ) const;
inline bool operator!=( const ListItr &rhs ) const;
private:
Node<Type> *current;
};
// class ListItr
/**
* Double List
*/
template <typename Type>
class DList
{
public:
DList();
DList( const DList<Type> &rhs );
~DList();
DList<Type>& operator=( const DList<Type> &rhs );
typedef ListItr<Type> Iterator;
typedef const Iterator Const_Iterator;
inline void clear();
inline bool isEmpty() const;
inline int size() const;
inline Iterator begin();
inline Const_Iterator begin() const;
inline Iterator end();
inline Const_Iterator end() const;
inline Type& front();
inline const Type& front() const;
inline Type& back();
inline const Type& back() const;
inline void pushFront( const Type &x );
inline void pushBack( const Type &x );
inline void popFront();
inline void popBack();
Iterator insert( Iterator itr, const Type &x );
Iterator erase( Iterator itr );
Iterator erase( Iterator start, Iterator end );
private:
int listSize;
Node<Type> *head;
Node<Type> *tail;
inline void init();
};
// class DList
#include <doublelist-impl.h>
}
// namespace itlab
#endif
// DOUBLELIST_H
実装ファイル:
/*****************************************************************************
* doublelist-impl.h
*
* Implementation for ListItr and DList class.
*
* Zhang Ming, 2009-10
*****************************************************************************/
/**
* constructors and destructor
*/
template <typename Type>
ListItr<Type>::ListItr()
{
}
template <typename Type>
ListItr<Type>::ListItr( Node<Type> *p ) : current(p)
{
}
template <typename Type>
ListItr<Type>::~ListItr()
{
}
/**
* Overload operations of pointer.
*/
template <typename Type>
inline Type& ListItr<Type>::operator*()
{
return current->data;
}
template <typename Type>
inline const Type& ListItr<Type>::operator*() const
{
return current->data;
}
/**
* Overload operations of "++" and "--".
*/
template <typename Type>
inline ListItr<Type>& ListItr<Type>::operator++()
{
current = current->next;
return *this;
}
template <typename Type>
inline ListItr<Type> ListItr<Type>::operator++( int )
{
ListItr old = *this;
++( *this );
return old;
}
template <typename Type>
inline ListItr<Type>& ListItr<Type>::operator--()
{
current = current->prev;
return *this;
}
template <typename Type>
inline ListItr<Type> ListItr<Type>::operator--( int )
{
ListItr old = *this;
--( *this );
return old;
}
/**
* Overload comparison operations.
*/
template <typename Type>
inline bool ListItr<Type>::operator==( const ListItr &rhs ) const
{
return current == rhs.current;
}
template <typename Type>
inline bool ListItr<Type>::operator!=( const ListItr &rhs ) const
{
return !( *this == rhs );
}
/**
* constructors and destructor
*/
template< typename Type >
inline void DList<Type>::init()
{
listSize = 0;
head = new Node<Type>;
tail = new Node<Type>;
head->next = tail;
tail->prev = head;
}
template< typename Type >
DList<Type>::DList()
{
init();
}
template< typename Type >
DList<Type>::DList( const DList &rhs )
{
init();
*this = rhs;
}
template< typename Type >
DList<Type>::~DList()
{
clear();
delete head;
delete tail;
}
/**
* assigning operator
*/
template< typename Type >
DList<Type>& DList<Type>::operator=( const DList &rhs )
{
if( this == &rhs )
return *this;
clear();
for( Iterator itr=rhs.begin(); itr!=rhs.end(); ++itr )
pushBack( *itr );
return *this;
}
/**
* Make the list empty.
*/
template< typename Type >
inline void DList<Type>::clear()
{
while( !isEmpty() )
popFront();
}
/**
* If the list is empty, return true.
*/
template< typename Type >
inline bool DList<Type>::isEmpty() const
{
return size() == 0;
}
/**
* Return the size of list.
*/
template< typename Type >
inline int DList<Type>::size() const
{
return listSize;
}
/**
* Get the beginning iterator of the list.
*/
template< typename Type >
inline typename DList<Type>::Iterator DList<Type>::begin()
{
return Iterator( head->next );
}
template< typename Type >
inline typename DList<Type>::Const_Iterator DList<Type>::begin() const
{
return Iterator( head->next );
}
/**
* Get the ending iterator of the list.
*/
template< typename Type >
inline typename DList<Type>::Iterator DList<Type>::end()
{
return Iterator( tail );
}
template< typename Type >
inline typename DList<Type>::Const_Iterator DList<Type>::end() const
{
return Iterator( tail );
}
/**
* Get the front element of the list.
*/
template< typename Type >
inline Type& DList<Type>::front()
{
return *begin();
}
template< typename Type >
inline const Type& DList<Type>::front() const
{
return *begin();
}
/**
* Get the back element of the list.
*/
template< typename Type >
inline Type& DList<Type>::back()
{
return *--end();
}
template< typename Type >
inline const Type& DList<Type>::back() const
{
return *--end();
}
/**
* Push an element from the front of the list.
*/
template< typename Type >
inline void DList<Type>::pushFront( const Type &x )
{
insert( begin(), x );
}
/**
* Push an element from the back of the list.
*/
template< typename Type >
inline void DList<Type>::pushBack( const Type &x )
{
insert( end(), x );
}
/**
* Pop an element from the front of the list.
*/
template< typename Type >
inline void DList<Type>::popFront()
{
erase( begin() );
}
/**
* Push an element from the back of the list.
*/
template< typename Type >
inline void DList<Type>::popBack()
{
erase( --end() );
}
/**
* Insert an element into list at the position pointed by "itr".
*/
template< typename Type >
typename DList<Type>::Iterator DList<Type>::insert( Iterator itr,
const Type &x )
{
Node<Type> *p = itr.current;
p->prev = p->prev->next = new Node<Type>( x, p->prev, p );
listSize++;
return Iterator( p->prev );
}
/**
* Erase an element pointed by "itr".
*/
template< typename Type >
typename DList<Type>::Iterator DList<Type>::erase( Iterator itr )
{
Node<Type> *p = itr.current;
Iterator tmp( p->next );
p->prev->next = p->next;
p->next->prev = p->prev;
listSize--;
delete p;
return tmp;
}
/**
* Erase elements from "start" to "end" of the list .
*/
template< typename Type >
typename DList<Type>::Iterator DList<Type>::erase( Iterator start,
Iterator end )
{
for( Iterator itr = start; itr != end; )
itr = erase( itr );
return end;
}
テストファイル:
/*****************************************************************************
* dlist_test.cpp
*
* Double list class testing.
*
* Zhang Ming, 2009-10
*****************************************************************************/
#include <iostream>
#include <string>
#include <doublelist.h>
using namespace std;
using namespace itlab;
template <typename Type>
void printList( const DList<Type> &dl )
{
if( dl.isEmpty() )
cout << " The list is empty!" << endl;
typename DList<Type>::Iterator itr = dl.begin();
while( itr != dl.end() )
cout << " " << *itr++ << endl;
cout << endl;
}
int main()
{
string name;
DList<string> dl;
dl.pushBack( "Zhang Ming" );
dl.pushBack( "Zhang Zong" );
printList( dl );
dl.pushFront( "Yu Kai" );
dl.pushFront( "Yu Zong" );
printList( dl );
dl.popFront();
dl.popFront();
printList( dl );
dl.popBack();
printList( dl );
DList<string>::Iterator itr = dl.begin();
dl.insert( itr, "Yu Kai" );
printList( dl );
dl.insert( dl.end(), "Yu Zong" );
printList( dl );
cout << " The first element in the list is: " << dl.front() << endl;
cout << " The last element in the list is: " << dl.back() << endl;
cout << endl;
dl.erase( dl.begin() );
dl.erase( --dl.end() );
printList( dl );
DList<string>::Const_Iterator citr = dl.begin();
cout << " " << *citr << endl;
cout << endl;
dl.clear();
printList( dl );
return 0;
}