笔者介绍：姜雪伟，IT公司技术合伙人，IT高级讲师，CSDN社区专家，特邀编辑，畅销书作者，国家专利发明人;已出版书籍：《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。
相信很多开发者在游戏开发中都会用到List表，用于存储数据或者对象。估计也有很多人对它的实现并不清楚，只是会用而已。学习知识不能仅限于表面，如果抱着只是会用，时间长了对自己的技能提升没有任何帮助不进则退，相信大家都学过侯捷先生的书，它编写的C＋＋都是底层的实现。作为开发者来说，如果对知识的掌握只限于表面，长久下去把自己就废了。因为现在引擎都封装的非常完善，其实这样做的后果就是引擎的关键技术只是掌握在少数人手中，大部分开发者都是逻辑程序员，一直要依附于人家才能生活，这样很可悲的，作为开发者的我们更应该自己主动的去学习。这样即使引擎有问题，自己也可以轻松解决。本章主要是给读者介绍关于List的封装，List是链表，表是有结点组成的，链表的遍历可以使用迭代器实现，这些就组成了链表的封装。首先看看迭代器的定义：
/// the list iterator class Iterator
{
public:
/// default constructor
Iterator();
/// constructor
Iterator(Node* node);
/// copy constructor
Iterator(const Iterator& rhs);
/// assignment operator
const Iterator& operator=(const Iterator& rhs);
/// equality operator
bool operator==(const Iterator& rhs) const;
/// inequality operator
bool operator!=(const Iterator& rhs) const;
/// pre-increment operator
const Iterator& operator++();
/// post-increment operator
Iterator operator++(int);
/// pre-decrement operator
const Iterator& operator--();
/// post-increment operator
Iterator operator--(int);
/// bool operator
operator bool() const;
/// safe -> operator
TYPE* operator->() const;
/// safe dereference operator
TYPE& operator*() const;
private:
friend class List<TYPE>;
/// access to node
Node* GetNode() const;
Node* node;
};
迭代器中还有Node结点指针，下面把节点Node的类定义实现如下所示：
class Node { friend class List; friend class Iterator; /// constructor Node(const TYPE& v); /// destructor ~Node(); /// set pointer to next node void SetNext(Node* n); /// get pointer to next node Node* GetNext() const; /// set pointer to previous node void SetPrev(Node* p); /// get pointer to previous node Node* GetPrev() const; /// get value reference TYPE& Value(); Node* next; Node* prev; TYPE value; };
链表有自己的类型，前后指针这些操作都放在链表中，整个List表的实现的完整代码如下所示：
template<class TYPE> class List{private: class Node;public: class Iterator; /// constructor List(); /// copy constructor List(const List<TYPE>& rhs); /// destructor ~List(); /// assignment operator void operator=(const List<TYPE>& rhs); /// return true if the list is empty bool IsEmpty() const; /// get number of elements in list (slow) SizeT Size() const; /// clear list void Clear(); /// add contents of other list to this list void AddList(const List<TYPE>& l); /// add element after given element Iterator AddAfter(Iterator iter, const TYPE& e); /// add element before given element Iterator AddBefore(Iterator iter, const TYPE& e); /// add element to beginning of list Iterator AddFront(const TYPE& e); /// add element to end of list Iterator AddBack(const TYPE& e); /// remove first element of list TYPE RemoveFront(); /// remove last element of list TYPE RemoveBack(); /// remove given element TYPE Remove(Iterator iter); /// get first element TYPE& Front() const; /// get last element TYPE& Back() const; /// get iterator to first element Iterator Begin() const; /// get iterator past the last element Iterator End() const; /// find element in array (slow) Iterator Find(const TYPE& e, Iterator start) const; /// the list iterator class Iterator { public: /// default constructor Iterator(); /// constructor Iterator(Node* node); /// copy constructor Iterator(const Iterator& rhs); /// assignment operator const Iterator& operator=(const Iterator& rhs); /// equality operator bool operator==(const Iterator& rhs) const; /// inequality operator bool operator!=(const Iterator& rhs) const; /// pre-increment operator const Iterator& operator++(); /// post-increment operator Iterator operator++(int); /// pre-decrement operator const Iterator& operator--(); /// post-increment operator Iterator operator--(int); /// bool operator operator bool() const; /// safe -> operator TYPE* operator->() const; /// safe dereference operator TYPE& operator*() const; private: friend class List<TYPE>; /// access to node Node* GetNode() const; Node* node; };private: /// a node in the list class Node { friend class List; friend class Iterator; /// constructor Node(const TYPE& v); /// destructor ~Node(); /// set pointer to next node void SetNext(Node* n); /// get pointer to next node Node* GetNext() const; /// set pointer to previous node void SetPrev(Node* p); /// get pointer to previous node Node* GetPrev() const; /// get value reference TYPE& Value(); Node* next; Node* prev; TYPE value; }; Node* front; Node* back;};//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::Node::Node(const TYPE& val) : next(0), prev(0), value(val){ // empty}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::Node::~Node(){ #if NEBULA3_BOUNDSCHECKS n_assert(0 == this->next); n_assert(0 == this->prev); #endif}//------------------------------------------------------------------------------/***/template<class TYPE>voidList<TYPE>::Node::SetNext(Node* n){ this->next = n;}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::Node*List<TYPE>::Node::GetNext() const{ return this->next;}//------------------------------------------------------------------------------/***/template<class TYPE>voidList<TYPE>::Node::SetPrev(Node* p){ this->prev = p;}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::Node*List<TYPE>::Node::GetPrev() const{ return this->prev;}//------------------------------------------------------------------------------/***/template<class TYPE>TYPE&List<TYPE>::Node::Value(){ return this->value;}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::Iterator::Iterator() : node(0){ // empty}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::Iterator::Iterator(Node* n) : node(n){ // empty}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::Iterator::Iterator(const Iterator& rhs) : node(rhs.node){ // empty}//------------------------------------------------------------------------------/***/template<class TYPE>const typename List<TYPE>::Iterator&List<TYPE>::Iterator::operator=(const Iterator& rhs){ if (&rhs != this) { this->node = rhs.node; } return *this;}//------------------------------------------------------------------------------/***/template<class TYPE>boolList<TYPE>::Iterator::operator==(const Iterator& rhs) const{ return (this->node == rhs.node);}//------------------------------------------------------------------------------/***/template<class TYPE>boolList<TYPE>::Iterator::operator!=(const Iterator& rhs) const{ return (this->node != rhs.node);}//------------------------------------------------------------------------------/***/template<class TYPE>const typename List<TYPE>::Iterator&List<TYPE>::Iterator::operator++(){ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->node); #endif this->node = this->node->GetNext(); return *this;}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::Iterator::operator++(int){ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->node); #endif Iterator temp(this->node); this->node = this->node->GetNext(); return temp;}//------------------------------------------------------------------------------/***/template<class TYPE>const typename List<TYPE>::Iterator&List<TYPE>::Iterator::operator--(){ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->node); #endif this->node = this->node->GetPred(); return *this;}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::Iterator::operator--(int){ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->node); #endif Iterator temp(this->node); this->node = this->node->GetPred(); return temp;}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::Iterator::operator bool() const{ return (0 != this->node);}//------------------------------------------------------------------------------/***/template<class TYPE>TYPE*List<TYPE>::Iterator::operator->() const{ #if NEBULA3_BOUNDSCHECKS n_assert(this->node); #endif return &(this->node->Value());}//------------------------------------------------------------------------------/***/template<class TYPE>TYPE&List<TYPE>::Iterator::operator*() const{ #if NEBULA3_BOUNDSCHECKS n_assert(this->node); #endif return this->node->Value();}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::Node*List<TYPE>::Iterator::GetNode() const{ return this->node;}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::List() : front(0), back(0){ // empty}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::List(const List<TYPE>& rhs) : front(0), back(0){ this->AddList(rhs);}//------------------------------------------------------------------------------/***/template<class TYPE>List<TYPE>::~List(){ this->Clear();}//------------------------------------------------------------------------------/***/template<class TYPE>voidList<TYPE>::operator=(const List<TYPE>& rhs){ this->Clear(); this->AddList();}//------------------------------------------------------------------------------/***/template<class TYPE>boolList<TYPE>::IsEmpty() const{ return (0 == this->front);}//------------------------------------------------------------------------------/***/template<class TYPE>SizeTList<TYPE>::Size() const{ Iterator iter; SizeT size = 0; for (iter = this->Begin(); iter != this->End(); iter++) { size++; } return size;}//------------------------------------------------------------------------------/***/template<class TYPE>voidList<TYPE>::Clear(){ while (this->back) { this->RemoveBack(); }}//------------------------------------------------------------------------------/***/template<class TYPE>voidList<TYPE>::AddList(const List<TYPE>& rhs){ Iterator iter; for (iter = rhs.Begin(); iter != rhs.End(); iter++) { this->AddBack(*iter); }}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::AddAfter(Iterator iter, const TYPE& e){ Node* node = n_new(Node(e)); if (0 == iter.GetNode()) { #if NEBULA3_BOUNDSCHECKS n_assert((0 == this->front) && (0 == this->back)); #endif this->front = node; this->back = node; } else { if (iter.GetNode() == this->back) { this->back = node; } if (0 != iter.GetNode()->GetNext()) { iter.GetNode()->GetNext()->SetPrev(node); } node->SetNext(iter.GetNode()->GetNext()); iter.GetNode()->SetNext(node); node->SetPrev(iter.GetNode()); } return Iterator(node);}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::AddBefore(Iterator iter, const TYPE& e){ Node *node = n_new(Node(e)); if (0 == iter.GetNode()) { #if NEBULA3_BOUNDSCHECKS n_assert((0 == this->front) && (0 == this->back)); #endif this->front = node; this->back = node; } else { if (iter.GetNode() == this->front) { this->front = node; } if (0 != iter.GetNode()->GetPrev()) { iter.GetNode()->GetPrev()->SetNext(node); } node->SetPrev(iter.GetNode()->GetPrev()); iter.GetNode()->SetPrev(node); node->SetNext(iter.GetNode()); } return Iterator(node);}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::AddFront(const TYPE& e){ return this->AddBefore(this->front, e);}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::AddBack(const TYPE& e){ return this->AddAfter(this->back, e);}//------------------------------------------------------------------------------/***/template<class TYPE>TYPEList<TYPE>::Remove(Iterator iter){ #if NEBULA3_BOUNDSCHECKS n_assert(iter.GetNode()); #endif Node* node = iter.GetNode(); if (node->GetPrev()) { node->GetPrev()->SetNext(node->GetNext()); } if (node->GetNext()) { node->GetNext()->SetPrev(node->GetPrev()); } if (node == this->front) { this->front = node->GetNext(); } if (node == this->back) { this->back = node->GetPrev(); } node->SetNext(0); node->SetPrev(0); TYPE elm = node->Value(); n_delete(node); return elm;}//------------------------------------------------------------------------------/***/template<class TYPE>TYPEList<TYPE>::RemoveFront(){ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->front); #endif return this->Remove(this->front);}//------------------------------------------------------------------------------/***/template<class TYPE>TYPEList<TYPE>::RemoveBack(){ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->back); #endif return this->Remove(this->back);}//------------------------------------------------------------------------------/***/template<class TYPE>TYPE&List<TYPE>::Front() const{ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->front); #endif return this->front->Value();}//------------------------------------------------------------------------------/***/template<class TYPE>TYPE&List<TYPE>::Back() const{ #if NEBULA3_BOUNDSCHECKS n_assert(0 != this->back); #endif return this->back->Value();}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::Begin() const{ return Iterator(this->front);}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::End() const{ return 0;}//------------------------------------------------------------------------------/***/template<class TYPE>typename List<TYPE>::IteratorList<TYPE>::Find(const TYPE& e, Iterator start) const{ for (; start != this->End(); start++) { if (*start == e) { return start; } } return 0;}
学习代码是非常枯燥的，但是知道了它内部的实现原理，使用起来才会更顺手。自己尝试封装一下，再去实现某个小功能，坚持下去，对引擎也会有所了解的。