笔者介绍：姜雪伟，IT公司技术合伙人，IT高级讲师，CSDN社区专家，特邀编辑，畅销书作者，国家专利发明人;已出版书籍：《手把手教你架构3D游戏引擎》电子工业出版社和《Unity3D实战核心技术详解》电子工业出版社等。
我写过一本关于比较简单的3D游戏引擎的封装，在这里给读者介绍一下，关于商业引擎中的底层封装，很多人可能会问，引擎已经为我们封装好了，拿过来用就可以了，不需要再自己封装了，这个没有错。引擎也是人写的，为什么人家能写，你写不了。难道我们就一直做一个逻辑程序员？虚幻引擎在开发游戏产品时，为了提升在移动端的性能，需要对底层做修改，如果我们对最基本的数据结构都搞不定，谈何修改底层？总之，学习一定要深入进行，不能只浮在表面。接下来的系列文章就是告诉读者，商业引擎的底层是如何封装的，我们自己如何封装类似STL模版中的数据结构，掌握了它们就等于迈出了学习引擎底层的第一步，首先介绍的是Array数组或者说是列表。
使用数组或者列表需要申请内存，内存的申请，释放可以直接调用Memory内存的类，在这里，我们将其封装了一下，封装内容如下所示：
__forceinline void*
operator new(size_t size)
{
return Memory::Alloc(Memory::ObjectHeap, size);
}
__forceinline void*
operator new(size_t size, const std::nothrow_t& noThrow)
{
return Memory::Alloc(Memory::ObjectHeap, size);
}
__forceinline void*
operator new[](size_t size)
{
return Memory::Alloc(Memory::ObjectArrayHeap, size);
}
__forceinline void*
operator new[](size_t size, const std::nothrow_t& noThrow)
{
return Memory::Alloc(Memory::ObjectArrayHeap, size);
}
__forceinline void
operator delete(void* p)
{
Memory::Free(Memory::ObjectHeap, p);
}
__forceinline void
operator delete[](void* p)
{
Memory::Free(Memory::ObjectArrayHeap, p);
}
#endif
#define n_new(type) new type
#define n_new_array(type,size) new type[size]
#define n_delete(ptr) delete ptr
#define n_delete_array(ptr) delete[] ptr
上面就是封装的关于内存存储，new一个空间和删除一个空间，以及一个宏定义。其实封装的意义在于一旦函数出现问题，只要修改对应的接口即可。函数封装中经常使用，一些变量定义，这个一般实用typedef定义。区别的好处是用于区分系统自己的：定义类型如下所示：
typedef unsigned long ulong;typedef unsigned int uint;typedef unsigned short ushort;typedef unsigned char uchar;typedef unsigned char ubyte;typedef int IndexT; // the index typetypedef int SizeT; // the size typestatic const int InvalidIndex = -1;#define N_ARGB(a,r,g,b) ((uint)((((a)&0xff)<<24)|(((r)&0xff)<<16)|(((g)&0xff)<<8)|((b)&0xff)))#define N_RGBA(r,g,b,a) N_ARGB(a,r,g,b)#define N_XRGB(r,g,b) N_ARGB(0xff,r,g,b)#define N_COLORVALUE(r,g,b,a) N_RGBA((uint)((r)*255.f),(uint)((g)*255.f),(uint)((b)*255.f),(uint)((a)*255.f))
接下来开始着手定义Array的内容了，在开发中我们经常使用数组或者说是队列的接口，但是大家都是直接使用系统自带的。系统是如何实现的一概不知，下面就告诉读者如何自己去封装队列。自己封装就要什么都要考虑清楚，比如申请内存，获取队列大小，判断队列是否为空，插入队列元素，重置队列，，填充队列，清除队列，破坏队列，拷贝队列等等。这些接口系统自己的也有，我们自己封装的，对于需求我们可以随意更改。扩展性非常好，性能也是可以保证的。还有我们自己封装的队列并不是固定使用某个类型，对于这样的需求，最好的解决办法是使用模版template，模版的使用在游戏封装中使用的非常广泛，因为它可以做到通用。在这里告诉开发者封装队列，一是可以加深读者对队列的理解，另一个是告诉读者自己封装并不难的，别人能实现的技术，作为我们也是可以实现的。在这里我们分两部分：第一部分是关于Array的定义完整的函数代码如下所示：
template<class TYPE> class Array{public: /// define iterator typedef TYPE* Iterator; /// constructor with default parameters Array(); /// constuctor with initial size and grow size Array(SizeT initialCapacity, SizeT initialGrow); /// constructor with initial size, grow size and initial values Array(SizeT initialSize, SizeT initialGrow, const TYPE& initialValue); /// copy constructor Array(const Array<TYPE>& rhs); /// destructor ~Array(); /// assignment operator void operator=(const Array<TYPE>& rhs); /// [] operator TYPE& operator[](IndexT index) const; /// equality operator bool operator==(const Array<TYPE>& rhs) const; /// inequality operator bool operator!=(const Array<TYPE>& rhs) const; /// convert to "anything" template<typename T> T As() const; /// append element to end of array void Append(const TYPE& elm); /// append the contents of an array to this array void AppendArray(const Array<TYPE>& rhs); /// increase capacity to fit N more elements into the array void Reserve(SizeT num); /// get number of elements in array SizeT Size() const; /// get overall allocated size of array in number of elements SizeT Capacity() const; /// return reference to first element TYPE& Front() const; /// return reference to last element TYPE& Back() const; /// return true if array empty bool IsEmpty() const; /// erase element at index, keep sorting intact void EraseIndex(IndexT index); /// erase element pointed to by iterator, keep sorting intact Iterator Erase(Iterator iter); /// erase element at index, fill gap by swapping in last element, destroys sorting! void EraseIndexSwap(IndexT index); /// erase element at iterator, fill gap by swapping in last element, destroys sorting! Iterator EraseSwap(Iterator iter); /// insert element before element at index void Insert(IndexT index, const TYPE& elm); /// insert element into sorted array, return index where element was included IndexT InsertSorted(const TYPE& elm); /// insert element at the first non-identical position, return index of inclusion position IndexT InsertAtEndOfIdenticalRange(IndexT startIndex, const TYPE& elm); /// test if the array is sorted, this is a slow operation! bool IsSorted() const; /// clear array (calls destructors) void Clear(); /// reset array (does NOT call destructors) void Reset(); /// return iterator to beginning of array Iterator Begin() const; /// return iterator to end of array Iterator End() const; /// find identical element in array, return iterator Iterator Find(const TYPE& elm) const; /// find identical element in array, return index, InvalidIndex if not found IndexT FindIndex(const TYPE& elm) const; /// fill array range with element void Fill(IndexT first, SizeT num, const TYPE& elm); /// clear contents and preallocate with new attributes void Realloc(SizeT capacity, SizeT grow); /// returns new array with elements which are not in rhs (slow!) Array<TYPE> Difference(const Array<TYPE>& rhs); /// sort the array void Sort(); /// do a binary search, requires a sorted array IndexT BinarySearchIndex(const TYPE& elm) const;private: /// destroy an element (call destructor without freeing memory) void Destroy(TYPE* elm); /// copy content void Copy(const Array<TYPE>& src); /// delete content void Delete(); /// grow array void Grow(); /// grow array to target size void GrowTo(SizeT newCapacity); /// move elements, grows array if needed void Move(IndexT fromIndex, IndexT toIndex); static const SizeT MinGrowSize = 16; static const SizeT MaxGrowSize = 65536; // FIXME: big grow size needed for mesh tools SizeT grow; // grow by this number of elements if array exhausted SizeT capacity; // number of elements allocated SizeT size; // number of elements in array TYPE* elements; // pointer to element array};
定义的类型在前面已经给读者封装了，后面就是第二部分，函数实现的内容，这些函数读者可以直接拿去使用，完整的代码如下所示：
template<class TYPE>Array<TYPE>::Array() : grow(8), capacity(0), size(0), elements(0){ // empty}//------------------------------------------------------------------------------/***/template<class TYPE>Array<TYPE>::Array(SizeT _capacity, SizeT _grow) : grow(_grow), capacity(_capacity), size(0){ if (0 == this->grow) { this->grow = 16; } if (this->capacity > 0) { this->elements = n_new_array(TYPE, this->capacity); } else { this->elements = 0; }}//------------------------------------------------------------------------------/***/template<class TYPE>Array<TYPE>::Array(SizeT initialSize, SizeT _grow, const TYPE& initialValue) : grow(_grow), capacity(initialSize), size(initialSize){ if (0 == this->grow) { this->grow = 16; } if (initialSize > 0) { this->elements = n_new_array(TYPE, this->capacity); IndexT i; for (i = 0; i < initialSize; i++) { this->elements[i] = initialValue; } } else { this->elements = 0; }}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Copy(const Array<TYPE>& src){ #if NEBULA3_BOUNDSCHECKS n_assert(0 == this->elements); #endif this->grow = src.grow; this->capacity = src.capacity; this->size = src.size; if (this->capacity > 0) { this->elements = n_new_array(TYPE, this->capacity); IndexT i; for (i = 0; i < this->size; i++) { this->elements[i] = src.elements[i]; } }}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Delete(){ this->grow = 0; this->capacity = 0; this->size = 0; if (this->elements) { n_delete_array(this->elements); this->elements = 0; }}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Destroy(TYPE* elm){ elm->~TYPE();}//------------------------------------------------------------------------------/***/template<class TYPE>Array<TYPE>::Array(const Array<TYPE>& rhs) : grow(0), capacity(0), size(0), elements(0){ this->Copy(rhs);}//------------------------------------------------------------------------------/***/template<class TYPE>Array<TYPE>::~Array(){ this->Delete();}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Realloc(SizeT _capacity, SizeT _grow){ this->Delete(); this->grow = _grow; this->capacity = _capacity; this->size = 0; if (this->capacity > 0) { this->elements = n_new_array(TYPE, this->capacity); } else { this->elements = 0; }}//------------------------------------------------------------------------------/***/template<class TYPE> void Array<TYPE>::operator=(const Array<TYPE>& rhs){ if (this != &rhs) { if ((this->capacity > 0) && (rhs.size <= this->capacity)) { // source array fits into our capacity, copy in place n_assert(0 != this->elements); IndexT i; for (i = 0; i < rhs.size; i++) { this->elements[i] = rhs.elements[i]; } // properly destroy remaining original elements for (; i < this->size; i++) { this->Destroy(&(this->elements[i])); } this->grow = rhs.grow; this->size = rhs.size; } else { // source array doesn't fit into our capacity, need to reallocate this->Delete(); this->Copy(rhs); } }}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::GrowTo(SizeT newCapacity){ TYPE* newArray = n_new_array(TYPE, newCapacity); if (this->elements) { // copy over contents IndexT i; for (i = 0; i < this->size; i++) { newArray[i] = this->elements[i]; } // discard old array and update contents n_delete_array(this->elements); } this->elements = newArray; this->capacity = newCapacity;}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Grow(){ #if NEBULA3_BOUNDSCHECKS n_assert(this->grow > 0); #endif SizeT growToSize; if (0 == this->capacity) { growToSize = this->grow; } else { // grow by half of the current capacity, but never more then MaxGrowSize SizeT growBy = this->capacity >> 1; if (growBy == 0) { growBy = MinGrowSize; } else if (growBy > MaxGrowSize) { growBy = MaxGrowSize; } growToSize = this->capacity + growBy; } this->GrowTo(growToSize);}//------------------------------------------------------------------------------/** 30-Jan-03 floh serious bugfixes!07-Dec-04jobugfix: neededSize >= this->capacity => neededSize > capacity*/template<class TYPE> voidArray<TYPE>::Move(IndexT fromIndex, IndexT toIndex){ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements); n_assert(fromIndex < this->size); #endif // nothing to move? if (fromIndex == toIndex) { return; } // compute number of elements to move SizeT num = this->size - fromIndex; // check if array needs to grow SizeT neededSize = toIndex + num; while (neededSize > this->capacity) { this->Grow(); } if (fromIndex > toIndex) { // this is a backward move IndexT i; for (i = 0; i < num; i++) { this->elements[toIndex + i] = this->elements[fromIndex + i]; } // destroy remaining elements for (i = (fromIndex + i) - 1; i < this->size; i++) { this->Destroy(&(this->elements[i])); } } else { // this is a forward move int i; // NOTE: this must remain signed for the following loop to work!!! for (i = num - 1; i >= 0; --i) { this->elements[toIndex + i] = this->elements[fromIndex + i]; } // destroy freed elements for (i = int(fromIndex); i < int(toIndex); i++) { this->Destroy(&(this->elements[i])); } } // adjust array size this->size = toIndex + num;}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Append(const TYPE& elm){ // grow allocated space if exhausted if (this->size == this->capacity) { this->Grow(); } #if NEBULA3_BOUNDSCHECKS n_assert(this->elements); #endif this->elements[this->size++] = elm;}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::AppendArray(const Array<TYPE>& rhs){ IndexT i; SizeT num = rhs.Size(); for (i = 0; i < num; i++) { this->Append(rhs[i]); }}//------------------------------------------------------------------------------/** This increases the capacity to make room for N elements. If the number of elements is known before appending the elements, this method can be used to prevent reallocation. If there is already enough room for N more elements, nothing will happen. NOTE: the functionality of this method has been changed as of 26-Apr-08, it will now only change the capacity of the array, not its size.*/template<class TYPE> voidArray<TYPE>::Reserve(SizeT num){ #if NEBULA3_BOUNDSCHECKS n_assert(num > 0); #endif SizeT neededCapacity = this->size + num; if (neededCapacity > this->capacity) { this->GrowTo(neededCapacity); }}//------------------------------------------------------------------------------/***/template<class TYPE> SizeTArray<TYPE>::Size() const{ return this->size;}//------------------------------------------------------------------------------/***/template<class TYPE> SizeTArray<TYPE>::Capacity() const{ return this->capacity;}//------------------------------------------------------------------------------/** Access an element. This method will NOT grow the array, and instead do a range check, which may throw an assertion.*/template<class TYPE> TYPE&Array<TYPE>::operator[](IndexT index) const{ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (index < this->size)); #endif return this->elements[index];}//------------------------------------------------------------------------------/** The equality operator returns true if all elements are identical. The TYPE class must support the equality operator.*/template<class TYPE> boolArray<TYPE>::operator==(const Array<TYPE>& rhs) const{ if (rhs.Size() == this->Size()) { IndexT i; SizeT num = this->Size(); for (i = 0; i < num; i++) { if (!(this->elements[i] == rhs.elements[i])) { return false; } } return true; } else { return false; }}//------------------------------------------------------------------------------/** The inequality operator returns true if at least one element in the array is different, or the array sizes are different.*/template<class TYPE> boolArray<TYPE>::operator!=(const Array<TYPE>& rhs) const{ return !(*this == rhs);}//------------------------------------------------------------------------------/***/template<class TYPE> TYPE&Array<TYPE>::Front() const{ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (this->size > 0)); #endif return this->elements[0];}//------------------------------------------------------------------------------/***/template<class TYPE> TYPE&Array<TYPE>::Back() const{ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (this->size > 0)); #endif return this->elements[this->size - 1];}//------------------------------------------------------------------------------/***/template<class TYPE> bool Array<TYPE>::IsEmpty() const{ return (this->size == 0);}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::EraseIndex(IndexT index){ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (index < this->size)); #endif if (index == (this->size - 1)) { // special case: last element this->Destroy(&(this->elements[index])); this->size--; } else { this->Move(index + 1, index); }}//------------------------------------------------------------------------------/** NOTE: this method is fast but destroys the sorting order!*/template<class TYPE> voidArray<TYPE>::EraseIndexSwap(IndexT index){ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (index < this->size)); #endif // swap with last element, and destroy last element IndexT lastElementIndex = this->size - 1; if (index < lastElementIndex) { this->elements[index] = this->elements[lastElementIndex]; } this->Destroy(&(this->elements[lastElementIndex])); this->size--;}//------------------------------------------------------------------------------/***/template<class TYPE> typename Array<TYPE>::IteratorArray<TYPE>::Erase(typename Array<TYPE>::Iterator iter){ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->size))); #endif this->EraseIndex(IndexT(iter - this->elements)); return iter;}//------------------------------------------------------------------------------/** NOTE: this method is fast but destroys the sorting order!*/template<class TYPE> typename Array<TYPE>::IteratorArray<TYPE>::EraseSwap(typename Array<TYPE>::Iterator iter){ #if NEBULA3_BOUNDSCHECKS n_assert(this->elements && (iter >= this->elements) && (iter < (this->elements + this->size))); #endif this->EraseSwapIndex(IndexT(iter - this->elements)); return iter;}//------------------------------------------------------------------------------/***/template<class TYPE> voidArray<TYPE>::Insert(IndexT index, const TYPE& elm){ #if NEBULA3_BOUNDSCHECKS n_assert(index <= this->size); #endif if (index == this->size) { // special case: append element to back this->Append(elm); } else { this->Move(index, index + 1); this->elements[index] = elm; }}//------------------------------------------------------------------------------/** The current implementation of this method does not shrink the preallocated space. It simply sets the array size to 0.*/template<class TYPE> voidArray<TYPE>::Clear(){ IndexT i; for (i = 0; i < this->size; i++) { this->Destroy(&(this->elements[i])); } this->size = 0;}//------------------------------------------------------------------------------/** This is identical with Clear(), but does NOT call destructors (it just resets the size member. USE WITH CARE!*/template<class TYPE> voidArray<TYPE>::Reset(){ this->size = 0;}//------------------------------------------------------------------------------/***/template<class TYPE> typename Array<TYPE>::IteratorArray<TYPE>::Begin() const{ return this->elements;}//------------------------------------------------------------------------------/***/template<class TYPE> typename Array<TYPE>::IteratorArray<TYPE>::End() const{ return this->elements + this->size;}//------------------------------------------------------------------------------/** Find element in array, return iterator, or 0 if element not found. @param elm element to find @return element iterator, or 0 if not found*/template<class TYPE> typename Array<TYPE>::IteratorArray<TYPE>::Find(const TYPE& elm) const{ IndexT index; for (index = 0; index < this->size; index++) { if (this->elements[index] == elm) { return &(this->elements[index]); } } return 0;}//------------------------------------------------------------------------------/** Find element in array, return element index, or InvalidIndex if element not found. @param elm element to find @return index to element, or InvalidIndex if not found*/template<class TYPE> IndexTArray<TYPE>::FindIndex(const TYPE& elm) const{ IndexT index; for (index = 0; index < this->size; index++) { if (this->elements[index] == elm) { return index; } } return InvalidIndex;}//------------------------------------------------------------------------------/** Fills an array range with the given element value. Will grow the array if necessary @param first index of first element to start fill @param num num elements to fill @param elm fill value*/template<class TYPE> voidArray<TYPE>::Fill(IndexT first, SizeT num, const TYPE& elm){ if ((first + num) > this->size) { this->GrowTo(first + num); } IndexT i; for (i = first; i < (first + num); i++) { this->elements[i] = elm; }}//------------------------------------------------------------------------------/** Returns a new array with all element which are in rhs, but not in this. Carefull, this method may be very slow with large arrays! @todo this method is broken, check test case to see why!*/template<class TYPE> Array<TYPE>Array<TYPE>::Difference(const Array<TYPE>& rhs){ Array<TYPE> diff; IndexT i; SizeT num = rhs.Size(); for (i = 0; i < num; i++) { if (0 == this->Find(rhs[i])) { diff.Append(rhs[i]); } } return diff;}//------------------------------------------------------------------------------/** Sorts the array. This just calls the STL sort algorithm.*/template<class TYPE> voidArray<TYPE>::Sort(){ std::sort(this->Begin(), this->End());}//------------------------------------------------------------------------------/** Does a binary search on the array, returns the index of the identical element, or InvalidIndex if not found*/template<class TYPE> IndexTArray<TYPE>::BinarySearchIndex(const TYPE& elm) const{ SizeT num = this->Size(); if (num > 0) { IndexT half; IndexT lo = 0; IndexT hi = num - 1; IndexT mid; while (lo <= hi) { if (0 != (half = num/2)) { mid = lo + ((num & 1) ? half : (half - 1)); if (elm < this->elements[mid]) { hi = mid - 1; num = num & 1 ? half : half - 1; } else if (elm > this->elements[mid]) { lo = mid + 1; num = half; } else { return mid; } } else if (0 != num) { if (elm != this->elements[lo]) { return InvalidIndex; } else { return lo; } } else { break; } } } return InvalidIndex;}//------------------------------------------------------------------------------/** This tests, whether the array is sorted. This is a slow operation O(n).*/template<class TYPE> boolArray<TYPE>::IsSorted() const{ if (this->size > 1) { IndexT i; for (i = 0; i < this->size - 1; i++) { if (this->elements[i] > this->elements[i + 1]) { return false; } } } return true;}//------------------------------------------------------------------------------/** This inserts an element at the end of a range of identical elements starting at a given index. Performance is O(n). Returns the index at which the element was added.*/template<class TYPE> IndexTArray<TYPE>::InsertAtEndOfIdenticalRange(IndexT startIndex, const TYPE& elm){ IndexT i = startIndex + 1; for (; i < this->size; i++) { if (this->elements[i] != elm) { this->Insert(i, elm); return i; } } // fallthrough: new element needs to be appended to end this->Append(elm); return (this->Size() - 1);}//------------------------------------------------------------------------------/** This inserts the element into a sorted array. Returns the index at which the element was inserted.*/template<class TYPE> IndexTArray<TYPE>::InsertSorted(const TYPE& elm){ SizeT num = this->Size(); if (num == 0) { // array is currently empty this->Append(elm); return this->Size() - 1; } else { IndexT half; IndexT lo = 0; IndexT hi = num - 1; IndexT mid; while (lo <= hi) { if (0 != (half = num/2)) { mid = lo + ((num & 1) ? half : (half - 1)); if (elm < this->elements[mid]) { hi = mid - 1; num = num & 1 ? half : half - 1; } else if (elm > this->elements[mid]) { lo = mid + 1; num = half; } else { // element already exists at [mid], append the // new element to the end of the range return this->InsertAtEndOfIdenticalRange(mid, elm); } } else if (0 != num) { if (elm < this->elements[lo]) { this->Insert(lo, elm); return lo; } else if (elm > this->elements[lo]) { this->Insert(lo + 1, elm); return lo + 1; } else { // element already exists at [low], append // the new element to the end of the range return this->InsertAtEndOfIdenticalRange(lo, elm); } } else { #if NEBULA3_BOUNDSCHECKS n_assert(0 == lo); #endif this->Insert(lo, elm); return lo; } } if (elm < this->elements[lo]) { this->Insert(lo, elm); return lo; } else if (elm > this->elements[lo]) { this->Insert(lo + 1, elm); return lo + 1; } else { // can't happen(?) } } // can't happen n_error("Array::InsertSorted: Can't happen!"); return InvalidIndex;}
因为这个是商业引擎使用的代码，考虑的比较完整，通过这个封装也是告诉读者，引擎内部的实现原理。平时我们自己写代码并没有考虑的这么周到，希望通过这些知识的学习帮你把数据结构重新复习一下，把基础知识掌握好，你才能腾飞。