GeekBand STL與泛型編程 First Week
泛型編程
模版介紹
模版是C++的一種特性，允許函數(shù)或類通過泛型的形式表現(xiàn)和運行。模版的類型有 類模版延欠，函數(shù)模版， 成員模版等阐斜。
模版的實例化是從模版構(gòu)建出一個真正函數(shù)或類的過程衫冻。模版被編譯了兩次诀紊。沒有被實例化之前谒出，檢查模版代碼本身是否有語法錯誤，在實例化期間邻奠，檢查對模版代碼的調(diào)用是否合法笤喳。
函數(shù)模版是參數(shù)化的一族函數(shù)。通過模版函數(shù)碌宴，可以定義一系列函數(shù)杀狡。這些函數(shù)都是基于同一套代碼，但是可以作用在不同型別的參數(shù)上
C++類模版贰镣，與函數(shù)模版類似呜象，類也可以通過參數(shù)泛化，從而可以構(gòu)建出一族不同型別的類實例碑隆。類模版實參可以是某一型別或常量恭陡。
const std::size_t DefaultStackSize = 1024;
template <typename T, std::size_t n = DefaultStackSize > class stack
{
public:
void push(const T const& elememt);
int Pop(T& element);
int Top(T& elememt) const;
private:
std::vector<T> m_Members;
std::size_t m_nMaxSize = n;
}
類模版的特化，允許對一個類模版的某些模版參數(shù)類型做特化上煤。特化的作用在于：對于某種特殊的型別休玩，可能可以做些特別的優(yōu)化或提供不同的實現(xiàn)；避免在實例化類的時候引起一些可能產(chǎn)生的詭異行為劫狠。類模版同樣可以特化或者偏特化拴疤。 如果有不止一個偏特化銅等程度地能匹配某個應(yīng)用，那么該調(diào)用具有二義性独泞，會產(chǎn)生編譯錯誤呐矾。
C++類模版參數(shù)可以有默認(rèn)值。
Traits(特性)
Traits在面向?qū)ο蟪绦蛟O(shè)計中懦砂，是一個不可實例化（uninstantiable）的方法與類型的集合蜒犯，為一個對象或算法提供了策略（policy）或?qū)崿F(xiàn)自身界面的細(xì)節(jié)功能。
Traits作為模板類孕惜，既聲明了統(tǒng)一的界面（包括類型愧薛、枚舉、函數(shù)方法等）衫画，又可以通過模板特化毫炉，針對不同數(shù)據(jù)類型或其他模板參數(shù)，為類削罩、函數(shù)或者通用算法在因為使用的數(shù)據(jù)類型不同而導(dǎo)致處理邏輯不同時瞄勾，提供了區(qū)分不同類型的具體細(xì)節(jié)费奸，從而把這部分用Traits實現(xiàn)的功能與其它共同的功能區(qū)分開來。例如进陡，容器的元素的不同數(shù)據(jù)類型愿阐，或者iostream是使用char還是wchar_t。
C++標(biāo)準(zhǔn)模板庫中大量使用了traits趾疚。將因為模板形參（包括類型形參缨历、非類型形參）不同而導(dǎo)致的不同抽取到新的模板（即traits）中去；然后通過traits的模板特化來實現(xiàn)針對具體情況的優(yōu)化實現(xiàn)糙麦。一個traits包括了enum辛孵、typedef、模板偏特化（template partial specialization）赡磅。其中魄缚，enum定義了各種類的標(biāo)識的統(tǒng)一表示；typedef定義了各個類的各自不同的類型定義焚廊，這對于使用模板元編程（template meta-programming）的靈活性非常重要冶匹；模板偏特化用于實現(xiàn)各個類的不同功能。
Example:
// tag struct
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public forward_iterator_tag {};
traits 必須能夠施行于內(nèi)置類型咆瘟，意味著 類型內(nèi)嵌套信息(nesting inforamtion) 這種東西出局了嚼隘，因為我們無法將信息嵌套于原始指針內(nèi)。因此類型的traits信息搞疗。因此類型的traits信息必須位于類型自身之外嗓蘑。標(biāo)準(zhǔn)技術(shù)放入一個template及其一個或多個特化版本中。
Example:
// trabit classes
template<typename IterT>
struct iterator_traits;
template <...>
class deque {
public:
class iterator {
public:
typedef random_access_iterator_tag iterator_category;
}
};
template <...>
class list {
public:
class iterator {
public:
typedef bidirectional_iterator_tag iterator_category;
}
};
template<typename IterT>
struct iterator_traits {
typedef typename IterT::iterator_category iterator_category;
};
template<typename IterT>
struct iterator_traits<Iter T*> {
typedef random_access_itrator_tag iterator_category;
}
Trabit Class 如何設(shè)計
- 確認(rèn)若干希望將來可以取得的類型信息匿乃，比如對于Iterator而言桩皿，我們希望可以取得其category
- 為信息選擇一個名稱，例如 iterator_category
- 提供一個template和一組特化版本幢炸，內(nèi)含你希望支持的類型相關(guān)信息
此處編譯期間的if...else語句 判斷類型泄隔，可以使用重載
template<typename IterT, typename DistT>
void advance(IterT &iter, DistT d)
{
doAdvance(iter, d, typename std::iterator_trabits<IterT>::iterator_category())
}
tempalte<typename IterT, typename Dist T>
void doAdvance(IterT &iter, DistT d, std::random_access_iterator_tag)
{
iter += d;
}
tempalte<typename IterT, typename Dist T>
void doAdvance(IterT &iter, DistT d, std::bidirectional_iterator_tag)
{
if (d >= 0) { while(d--) ++iter; }
else { while (d++) --iter; }
}
tempalte<typename IterT, typename Dist T>
void doAdvance(IterT &iter, DistT d, std::bidirectional_iterator_tag)
{
if (d < 0) { throw std::out_of_range("Negative distance"); }
while (d--) ++iter;
}
總結(jié):
- 建立一組重載函數(shù)或者函數(shù)模板(例如doAdvance)，彼此之間的差異只在于各自的trabit參數(shù)宛徊。令各個函數(shù)實現(xiàn)碼與其接受之trabits信息相應(yīng)和
- 建立一個控制函數(shù)或者函數(shù)模板(例如advance)佛嬉，它調(diào)用上述的"勞工函數(shù)"，并傳遞traits class提供的信息
迭代器 Iterator
迭代器是一種 Pointer-like class闸天。是指針的泛化暖呕。迭代器本身是一個對象。在STL中迭代器是容器與算法之間的接口苞氮。在STL中湾揽，算法和容器是分離的，而迭代器就是它們之間的粘合劑。如 find 算法库物，接收一對迭代器作為參數(shù)霸旗，分別指向容器的開始和結(jié)束。
template<class _InIt, class _Ty>
inline _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val)
{
for(; _First != _Last; ++_First)
if(*_First == _Val)
break;
return (_First);
}
Iterator也是一種很長的設(shè)計模式的手法戚揭，用來遍歷一個Resource诱告，這樣可以屏蔽很多內(nèi)部操作，直接利用了C++的operator++/operator--/operator+/operator-重載民晒。
當(dāng)然C++的iterator也是有好幾個分類的精居。具體而言
1.輸入迭代器(input iterator)
2.輸出迭代器(output iterator)
3.前向迭代器(forward iterator)
4.雙向迭代器(bidirectional iterator)
5.隨機(jī)存取迭代器(random access iterator)
輸入迭代器(input iterator)
input iterator就像其名字所說的,工作的就像輸入流一樣.我們必須能
- 取出其所指向的值
- 訪問下一個元素
- 判斷是否到達(dá)了最后一個元素
- 可以復(fù)制
因此其支持的操作符有 *p,++p,p++,p!=q,p == q這五個.凡是支持這五個操作的類都可以稱作是輸入迭代器.當(dāng)然指針是符合的.
輸出迭代器(output iterator)
output iterator工作方式類似輸出流,我們能對其指向的序列進(jìn)行寫操作,其與input iterator不相同的就是*p所返回的值允許修改,而不一定要讀取,而input只允許讀取,不允許修改.
支持的操作和上頭一樣,支持的操作符也是 *p,++p,p++,p!=q,p == q.
Example:
template<class In,class Out>
void copy(In start,In beyond, Out result)
{
while(start != beyond) {
*result = *start; // result是輸出迭代器,其*result返回的值允許修改
++result;
++start;
}
}
// 簡寫
template<class In,class Out>
void copy(In start,In beyond, Out result)
{
while(start != beyond)
*result++ = *start++;
}
前向迭代器(forward iterator)
前向迭代器就像是輸入和輸出迭代器的結(jié)合體,其*p既可以訪問元素,也可以修改元素.因此支持的操作也是相同的.
雙向迭代器(bidirectional iterator)
雙向迭代器在前向迭代器上更近一步,其要求該種迭代器支持operator--,因此其支持的操作有*p,++p,p++,p!=q,p == q,--p,p--
隨機(jī)存取迭代器(random access iterator)
即如其名字所顯示的一樣,其在雙向迭代器的功能上,允許隨機(jī)訪問序列的任意值.顯然,指針就是這樣的一個迭代器.
對于隨機(jī)存取迭代器來說, 其要求高了很多:
- 可以判斷是否到結(jié)尾(
a==b or a != b) - 可以雙向遞增或遞減(
--a or ++a) - 可以比較大小(
a < b or a > b or a>=b ...etc) - 支持算術(shù)運算(
a + n) - 支持隨機(jī)訪問(
a[n]) - 支持復(fù)合運算(
a+= n)
容器 Containter
我們所用的常用的數(shù)據(jù)結(jié)構(gòu)不外乎 array, list, tree, stack, queue, hash table, set, map 等。這些數(shù)據(jù)結(jié)構(gòu)分為序列式（sequence）和關(guān)聯(lián)式（associative）兩種镀虐。
Sequence Container : array, vector, list, deque
Associative Containter : set, map, multimap, unordered map
對于Sequence Container箱蟆，我們一般認(rèn)為這個是一個動態(tài)的數(shù)組，只是實現(xiàn)上各有差異刮便，可以為鏈表，這個差異就是索引時候的速度绽慈，數(shù)組是O(1), 鏈表是O(n)恨旱。且從空間上來說動態(tài)數(shù)組在capacity相同的時候空間占用會比鏈表要少一些。但是鏈表在指定位置插入的成本會比數(shù)組少很多坝疼，是O(1)搜贤。
