課堂大綱
這周的課程大致上應(yīng)該是這三個(gè)部分
- C++模板介紹
- 泛型編程
- 容器
概述STL與泛型編程
泛型編程作為一種編程思維和想法，它是一種編程方法瞳氓，不依賴于具體的語(yǔ)言签则。
STL中主要由容器，迭代器翘单，算法三個(gè)部件構(gòu)成彩届。
容器用來(lái)管理對(duì)象的集合伪冰，每一種容器都有自己的優(yōu)缺點(diǎn)，儲(chǔ)存的方式等都有所不同樟蠕，使用時(shí)需根據(jù)程序的需求考慮不同容器的效率來(lái)選擇
迭代器為所有容器提供了一組公共接口贮聂，并且，每一種容器都提供自己的迭代器
STL中把數(shù)據(jù)和算法分開寨辩，賦予了STL極大的彈性
下圖演示了三個(gè)部件之間的交互關(guān)系
可以看出寂汇，迭代器是容器和算法之間的接口，總體說(shuō)來(lái)捣染，STL使容器與算法分離，使其二者不需要相互依賴停巷，而迭代器又將算法和不同的容器stick在一起耍攘，從而使需要的算法能夠運(yùn)用到不同的容器上
Templates and Generic Programming
- 泛型技術(shù)（Generic Programming）。比如：模板技術(shù)畔勤，RTTI技術(shù)蕾各，虛函數(shù)技術(shù)，要么是試圖做到在編譯時(shí)決議庆揪，要么試圖做到運(yùn)行時(shí)決議式曲。
- 模板（Templates）是泛型編程的基礎(chǔ)
C++模板介紹
C++主要有兩種類型的模板
- 類模板(Class template):使用泛型參數(shù)的類
- 函數(shù)模板(Function template):使用泛型參數(shù)的函數(shù)
模板實(shí)例化：顯示和隱式兩種方式
類模板實(shí)參可以是某一型別或常量(僅限int或enum)
C++類模板的聲明注意事項(xiàng)：
- 聲明類模板和聲明函數(shù)模板類似
- 關(guān)鍵字class和typename都可以用，但還是傾向于使用typename
templateclass Stack{......};
template class Stack{......};
3.在類模板內(nèi)部缸榛，T可以像其他型別一樣(比如int,char等)定義成員變量和成員函數(shù)
void Push(const T const& element);
int Pop(T& element);
int Top(T& element) const;
std::vector m_Members;
泛型編程(Generic programming)
泛型編程作為一種編程思維和想法吝羞，它是一種編程方法，不依賴于具體的語(yǔ)言内颗。
- 關(guān)聯(lián)特性(Traits)
Traits可以實(shí)現(xiàn)為模板類, 而關(guān)聯(lián)則是針對(duì)每個(gè)具體型別T的特化.
template< typename T > class Simg{ };
template< > class Simg< char>{
public: typedef int ReturnType ;
};
template< > class Simg< short>{
public: typedef int ReturnType ;
};
template< > class Simg< int>{
public: typedef long ReturnType ;
};
Traits實(shí)現(xiàn): (函數(shù)定義)
template< typename T>
typename Simg< T >::ReturnType Sigma ( const T const* Start, const T const* end)
{
Simg< T >::ReturnType type;
type r = ReturnType();
return r ; //這里返回的就是特性的新類型}
- 迭代器(Iterators)：迭代器是指針的泛化（generalization of pointers）
2.1 迭代器本身是一個(gè)對(duì)象钧排，指向另外一個(gè)（可以被迭代的）對(duì)象。
2.2 用來(lái)迭代一組對(duì)象均澳，即如果迭代器指向一組對(duì)象中的某個(gè)元素恨溜，則通過(guò)increment以后它就可以指向下一組對(duì)象中的一個(gè)元素。
迭代器是指針的泛化(generalization of pointers)
- 迭代器本身是一個(gè)對(duì)象找前，指向另外一個(gè)(可以被迭代的)對(duì)象
- 用來(lái)迭代一組對(duì)象糟袁，即如果迭代器指向一組對(duì)象中的某個(gè)元素，則通過(guò)increment以后它就可以指向這組對(duì)象的下一個(gè)元素
- 在STL中迭代器是容器與算法之間的接口
- 算法通常以迭代器作為輸入?yún)?shù)
- 容器只要提供一種方式躺盛，可以讓迭代器訪問(wèn)容器中的元素即可项戴。
迭代器的基本思想
- 在STL中，迭代器最重要的思想就是分離算法和容器颗品，使之不需要相互依賴
- 迭代器將算法和容器粘合(stick)在一起從而使得一種算法的實(shí)現(xiàn)可以運(yùn)用到多種不同的容器上肯尺，如下面的例子所示沃缘，find算法接收一對(duì)迭代器，分別指向容器的開始和終止位置：
templalte
inline _InIt find(_InIt _First,_InIt _Last,const _Ty& _Val){
//find frist matching _Val
for(;_First != _Last;++_First)
if(*_First == _Val)
break;
return (_First);
}
容器container
總的來(lái)說(shuō)则吟，容器可以分為兩類：
- 順序式容器sequence containers
排列順序與置入次序一致槐臀，例如vector，deque氓仲，list - 關(guān)聯(lián)式容器associative containers
sort群集水慨，元素的順序取決于特定的排序規(guī)則，例如set敬扛，multiset晰洒，map，multimap.
順序容器
Vector
- Vector是一個(gè)能夠存放任意型別的動(dòng)態(tài)數(shù)組
- Vector的數(shù)據(jù)結(jié)構(gòu)和操作于數(shù)組類似啥箭，在內(nèi)存中的表示是一段地址連續(xù)的空間谍珊。
- Vector與數(shù)組的區(qū)別在于，數(shù)組大小往往是定義的時(shí)候已經(jīng)指定急侥，而Vector支持動(dòng)態(tài)空間大小調(diào)整砌滞，隨著元素的增加，Vector內(nèi)部會(huì)自動(dòng)擴(kuò)充內(nèi)存空間坏怪。
- 為了使用Vector,必須用include指令包含如下文件贝润，并通過(guò)std命名空間去訪問(wèn):
#include
int main(){
std::vector v;
}
創(chuàng)建一個(gè)vector,提醒兩個(gè)比較特殊的：
vector<T> v(v,i); //創(chuàng)建一個(gè)容量為n的T型別的vector，并都初始化為i
int a[] = {1,2,3,4,5,6,7,8,9,10};
vecotr<int> v(a,a+10); //用數(shù)組創(chuàng)建vector
相關(guān)函數(shù):
vector我們平時(shí)使用的比較多铝宵，push_back()打掘，empty()都是常用的就不說(shuō)了，注意vector沒有push_front()鹏秋，因?yàn)閷?duì)于vector來(lái)說(shuō)如果要push_front()效率很低所以不提供這個(gè)函數(shù)尊蚁。
對(duì)于vector的at()和operator[]，at會(huì)做邊界檢查侣夷，但效率比operator低枝誊。
刪除元素的操作：
clear()直接清空
pop_back()彈出尾部
erase()借助迭代器清除（傳入迭代器，也就是位置惜纸，也可以是一個(gè)范圍）
iterator erase (iterator position);
iterator erase (iterator first, iterator last);
另外叶撒，我們可以用eraze結(jié)合remove_if(定義在<algorithm>中)來(lái)刪除我們指定的元素：
首先，我們需要定義一個(gè)刪選器：用一個(gè)一元對(duì)象（unary_function)耐版，其關(guān)鍵在于重載operator()：
struct ContainsString:public unary_function<string,bool>
{
ContainsString(const string& szMatch) :m_szMatch(szMatch) {}
bool operator()(const string& szStringToMatch)const {
return (szStringToMatch.find(m_szMatch) != -1);
}
string m_szMatch;
};
還記的我們上面所說(shuō)的erase的用法么祠够，第二個(gè)用法第一個(gè)參數(shù)為eraze的起點(diǎn)，我們的erase函數(shù)這樣寫：
v.erase(remove_if(
v.begin(),
v.end(),
ContainsString("bushuang")
),
v.end());
我們看remove_if的用法：
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator remove_if (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred);
第三個(gè)參數(shù)可以看到就是一個(gè)一元條件粪牲，而前兩個(gè)參數(shù)為起止迭代器古瓤，返回值是迭代器，所以現(xiàn)在就很清楚了，通過(guò)remove_if得到一個(gè)迭代器位置落君，然后從該位置把后面的東西都刪了穿香。
remove_if屬于移除性算法，根據(jù)元素值或某一準(zhǔn)則绎速，在一個(gè)區(qū)間內(nèi)移除某些元素皮获。這些算法并不能改變?cè)氐臄?shù)量，它們只是以邏輯上的思考纹冤，將原本置于后面的“不移除元素”向前移動(dòng)洒宝，覆蓋那些被移除元素而已，它們都返回新區(qū)間的邏輯終點(diǎn)（也就是最后一個(gè)“不移除元素”的下一位置）萌京。
Deque
Deque是一個(gè)能夠存放任意型別的雙向隊(duì)列雁歌，故比vector多了push_front和pop_front兩個(gè)函數(shù)，而我們之前提到過(guò)vector因?yàn)樾试虿惶峁┻@兩個(gè)函數(shù)知残，所以deque必然與vector有不同的內(nèi)存管理方法：大塊的內(nèi)存分配靠瞎。
如果不是要在前面插入，一般我們不會(huì)去用Deque求妹，所以也就不多說(shuō)了较坛，其用法和vector差不多，只是效率上的差別
List
list相較于vector和deque扒最，其優(yōu)勢(shì)在于可以很快的隨意插入和刪除元素，對(duì)于插入华嘹，刪除吧趣，替換等操作，效率極高耙厚，合并list强挫，也僅僅只需要節(jié)點(diǎn)的鏈接
相關(guān)函數(shù):
void remove (const value_type& val);直接刪除指定內(nèi)容的元素
erase與上面差不多，不多說(shuō)了
具體說(shuō)一下splice
void splice (iterator position, list& x); //entire list
void splice (iterator position, list& x, iterator i); //single element
void splice (iterator position, list& x, iterator first, iterator last); //element range
簡(jiǎn)單說(shuō)明一下參數(shù)薛躬，第二個(gè)函數(shù)剪貼單個(gè)元素俯渤，第三個(gè)參數(shù)為傳入list x的迭代器；
第三個(gè)函數(shù)后兩個(gè)參數(shù)為傳入list x的迭代器范圍
用以下代碼說(shuō)明用法：
// splicing lists
#include <iostream>
#include <list>
int main ()
{
std::list<int> mylist1, mylist2;
std::list<int>::iterator it;
// set some initial values:
for (int i=1; i<=4; ++i)
mylist1.push_back(i); // mylist1: 1 2 3 4
for (int i=1; i<=3; ++i)
mylist2.push_back(i*10); // mylist2: 10 20 30
it = mylist1.begin();
++it; // points to 2
mylist1.splice (it, mylist2); // mylist1: 1 10 20 30 2 3 4
// mylist2 (empty)
// "it" still points to 2 (the 5th element)
mylist2.splice (mylist2.begin(),mylist1, it);
// mylist1: 1 10 20 30 3 4
// mylist2: 2
// "it" is now invalid.
it = mylist1.begin();
std::advance(it,3); // "it" points now to 30
mylist1.splice ( mylist1.begin(), mylist1, it, mylist1.end());
// mylist1: 30 3 4 1 10 20
std::cout << "mylist1 contains:";
for (it=mylist1.begin(); it!=mylist1.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
std::cout << "mylist2 contains:";
for (it=mylist2.begin(); it!=mylist2.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
里面用到的advance函數(shù)作用是移動(dòng)迭代器（第二參數(shù)可為負(fù)數(shù)）
我們?cè)谑褂胹plice的時(shí)候型宝，注意iterator 的位置八匠，advance函數(shù)第二參數(shù)不要讓迭代器超過(guò)范圍，否則將導(dǎo)致不可預(yù)知的問(wèn)題趴酣。另外梨树，list還有sort()與merge()函數(shù)。
