【Vlpp源碼閱讀】集合篇（一）

01-29

前言

重新拜讀輪大寫的C++庫，提升自身水平，如有錯誤請提出。另：代碼在vczh-libraries/Vlpp。

自己寫的庫畢竟疏漏很多，在前面的文章中，除開第一次提交，就目前為止我起碼發現了5個錯誤，所以跟理想還是差得遠。想實現perfect的庫就必須再花很多時間，對代碼不斷打磨，但是做到能用就不錯了，達到perfect是異想天開。因此，暫時開啟源碼閱讀系列，沒錯，本專欄第一篇的標準庫目錄我是參照了Gaclib的(有野心沒能力哈哈)，現在想想還是要讀大佬的代碼！

簡要介紹Vlpp

打開vczh-libraries/Vlpp，分析目錄列表，我們發現了幾個模塊：

Collections，泛型集合及枚舉器
Parsing，LR文法分析
Reflection，反射
Regex，正則表達式
Stream，流

那後面的文章大致就從上面這幾部分來介紹。介紹完後，再接著閱讀vczh-libraries/GacUI的源碼。

集合的實現

我自己寫的vector庫只是一個簡單的內存管理類而已，太精簡，木有其他功能，所以為了節省時間，就以Vlpp這個庫為例，大家要用就用大佬寫的代碼。

先查看https://github.com/vczh-libraries/Vlpp/blob/master/Source/Collections/List.h：

ListStore<T,PODType>tttt：列表存儲複製演算法，PODType這個參數是亮點
tListBase<T,K>tttttt：列表基類
tArray<T,K>ttttttt：數組
tList<T,K>ttttttt：列表
tSortedList<T,K>tttttt：有序列表

平常寫的list或是vector，都只有一個模版參數，可是這裡有兩個，這是為什麼？

K究竟是何方神聖？

template<typename T, bool PODType>nclass ListStore abstract : public Objectn{n};n

問題接踵而至：PODType是什麼？

我們進去https://github.com/vczh-libraries/Vlpp/blob/master/Source/Basic.h看：

/// <summary>Test is a type a Plain-Old-Data type for containers.</summary>n/// <typeparam name="T">The type to test.</typeparam>ntemplate<typename T>nstruct PODn{nt/// <summary>Returns true if the type is a Plain-Old-Data type.</summary>ntstatic const bool Result=false;n};nntemplate<>struct POD<bool>{static const bool Result=true;};ntemplate<>struct POD<vint8_t>{static const bool Result=true;};ntemplate<>struct POD<vuint8_t>{static const bool Result=true;};ntemplate<>struct POD<vint16_t>{static const bool Result=true;};ntemplate<>struct POD<vuint16_t>{static const bool Result=true;};ntemplate<>struct POD<vint32_t>{static const bool Result=true;};ntemplate<>struct POD<vuint32_t>{static const bool Result=true;};ntemplate<>struct POD<vint64_t>{static const bool Result=true;};ntemplate<>struct POD<vuint64_t>{static const bool Result=true;};ntemplate<>struct POD<char>{static const bool Result=true;};ntemplate<>struct POD<wchar_t>{static const bool Result=true;};ntemplate<typename T>struct POD<T*>{static const bool Result=true;};ntemplate<typename T>struct POD<T&>{static const bool Result=true;};ntemplate<typename T, typename C>struct POD<T C::*>{static const bool Result=true;};ntemplate<typename T, vint _Size>struct POD<T[_Size]>{static const bool Result=POD<T>::Result;};ntemplate<typename T>struct POD<const T>{static const bool Result=POD<T>::Result;};ntemplate<typename T>struct POD<volatile T>{static const bool Result=POD<T>::Result;};ntemplate<typename T>struct POD<const volatile T>{static const bool Result=POD<T>::Result;};n

一臉蒙，POD裡面有個Result，然而POD有許多特化，上面這些全是true，我的理解是對於像基本類型這樣的POD，POD中的Result為true，其他為false。

這裡明白了，ListStore多了個模版參數是為了鑒別POD的。

列表存儲複製演算法（區分POD）

06/09更新

ListStore將分別管理struct(POD)和class(非POD，有this指針)。

也就是ListStore<T,false>，ListStore第二個參數K特化，為了專門管理對象而非結構體，這個方法很好：

template<typename T>nclass ListStore<T, false> abstract : public Objectn{nprotected:ntstatic void InitializeItemsByDefault(void* dst, vint count)nt{nttT* ds = (T*)dst;nnttfor (vint i = 0; i < count; i++)ntt{ntttnew(&ds[i])T();ntt}nt}nntstatic void InitializeItemsByMove(void* dst, void* src, vint count)nt{nttT* ds = (T*)dst;nttT* ss = (T*)src;nnttfor (vint i = 0; i < count; i++)ntt{ntttnew(&ds[i])T(MoveValue(ss[i]));ntt}nt}nntstatic void InitializeItemsByCopy(void* dst, void* src, vint count)nt{nttT* ds = (T*)dst;nttT* ss = (T*)src;nnttfor (vint i = 0; i < count; i++)ntt{ntttnew(&ds[i])T(ss[i]);ntt}nt}nntstatic void MoveItemsInTheSameBuffer(void* dst, void* src, vint count)nt{nttT* ds = (T*)dst;nttT* ss = (T*)src;nnttif (ds < ss)ntt{ntttfor (vint i = 0; i < count; i++)nttt{nttttds[i] = MoveValue(ss[i]);nttt}ntt}nttelse if (ds > ss)ntt{ntttfor (vint i = count - 1; i >= 0; i--)nttt{nttttds[i] = MoveValue(ss[i]);nttt}ntt}nt}nntstatic void ReleaseItems(void* dst, vint count)nt{nttT* ds = (T*)dst;nnttfor (vint i = 0; i < count; i++)ntt{ntttds[i].~T();ntt}nt}ntntstatic void* AllocateBuffer(vint size)nt{nttif (size <= 0) return nullptr;nttreturn (void*)malloc(sizeof(T) * size);nt}nntstatic void DeallocateBuffer(void* buffer)nt{nttif (buffer == nullptr)return;nttfree(buffer);nt}npublic:n};n

上面的代碼涉及了一些內容：new(&ds[i])T(ss[i])、MoveValue(ss[i])、ds[i].~T()這些都好陌生啊！

一個個來，第一個，placement new，涉及C++中placement new操作符（經典），我先前的vector是只管內存的，不管對象的析構，那麼現在對象的創建我已經完成了，這是內存地址ptr，我要在ptr上創建對象，而不是重新new塊內存，那就可以用這個特性，new(ptr) T。

第二個，涉及右值引用，老實說這裡我也很暈，還有引用摺疊等概念，反正好處是不用一次次拷貝同一個的對象了。

第三個，就是主動調用析構。

================================

管理POD，即簡單的內存管理：

template<typename T>nclass ListStore<T, true> abstract : public Objectn{nprotected:ntstatic void InitializeItemsByDefault(void* dst, vint count)nt{nt}nntstatic void InitializeItemsByMove(void* dst, void* src, vint count)nt{nttif (count > 0)ntt{ntttmemcpy(dst, src, sizeof(T) * count);ntt}nt}nntstatic void InitializeItemsByCopy(void* dst, void* src, vint count)nt{nttif (count > 0)ntt{ntttmemcpy(dst, src, sizeof(T) * count);ntt}nt}nntstatic void MoveItemsInTheSameBuffer(void* dst, void* src, vint count)nt{nttif (count > 0)ntt{ntttmemmove(dst, src, sizeof(T) * count);ntt}nt}nntstatic void ReleaseItems(void* dst, vint count)nt{nt}nntstatic void* AllocateBuffer(vint size)nt{nttif (size <= 0) return nullptr;nttreturn (void*)malloc(sizeof(T) * size);nt}nntstatic void DeallocateBuffer(void* buffer)nt{nttif (buffer == nullptr) return;nttfree(buffer);nt}npublic:n};n

其他幾個類

ArrayBase比較常規，對於越界錯誤直接報錯，不過裡面多了個枚舉器Enumerator 。

Array：繼承了最上面的內存管理類。

ListBase：這裡面主要是動態擴容，即內存不夠了要增加空間，這裡的演算法是result = result * 5 / 4 + 1。還設置了lessMemoryMode模式，啟用時當list的size減少，會自動釋放先前申請的多餘空間。

List：最終的list，實現CURD。

SortedList：與list不同，用於二分查找，插入時會保證數組有序。

我的vector實現差不多是按照上面做的，最多是內存擴容方法不一樣，然而還是有人不看代碼就說效率低、說實現渣，我也不想辯解。