Standard Template Library
2017年8月17日
9:30
推薦閱讀
Algorithms + Data Structures
= Programs
1976 wirtten by
Niklasu Wirth
Pascal語言之父
·C++基本語法
·模版(template)基礎(chǔ)
-事半功倍
·數(shù)據(jù)結(jié)構(gòu)(data structures)和算法(algorithms)概念
-如魚得水
三
想
GNU-C V2.9.1 && V4.9
標(biāo)準(zhǔn)庫版本，Visual C++
源代碼分布：
file layout
VS2013
…\include子目錄
Dec+C++ 5.1.1 with GNU V4.9.2
…\include\c++內(nèi)并非實(shí)做內(nèi)容
…\include\c++\ext
blabla allocator
OOP (Object-oriented programming)vs. GP(Generic Programming)
2017年8月21日
11:27
查看大型OOP庫的難點(diǎn)
繼承關(guān)系復(fù)雜、
虛函數(shù)
OOP 企圖將datas和methods關(guān)聯(lián)在一起
?
template<class T,
??? calss Alloc = alloc>
class list{
…
void sort();
};
標(biāo)準(zhǔn)庫沒有這種困擾
list不能使用::sort()的原因
?
*first + *(last - first)/2
只有RandomAccessIterator
才能如此操作
而list的iterator并不是這種類型
所以，不能使用
GP將datas和methods分開來
?
采用GP：
·Containers和Algorithms團(tuán)隊可以各自
閉門造車，其間以Iterator溝通即可
·Algorithms通過Iterators確定操作范圍
，并通過Iterators取用Container元素
所有algorithms，其內(nèi)最終
涉及元素本身的操作，無非
就是比大小
閱讀C++標(biāo)準(zhǔn)庫源碼的必要基礎(chǔ)
2017年8月21日
11:50
·Operator Overloading
迭代器重載
?
·Templates
-Class Templates，類模板
-Function Templates，函數(shù)模板
實(shí)參推導(dǎo)
-Member Templates，成員模板
Specialization，特化
template<>
struct __type_traits<int>
{
…
};
__type_traits<Foo>::has_trivial_destructor
template<> || __STL_TEMPLATE_NULL
Partial Specialization，偏特化
偏：1.數(shù)量上的偏 2.范圍上的偏
推薦閱讀
C++ Templates
再談分配器
不建議直接使用分配器
2017年8月21日
12:51
malloc
VC6附加標(biāo)準(zhǔn)庫的allocator
分配器 調(diào)用 operator new
operator new 調(diào)用malloc
VC6 & BC++ & GCC2.9
的allocator只是以
::operator new和
::operator delete完成
allocate()和dellocate()
沒有任何特殊設(shè)計
malloc附帶額外開銷
allocator
區(qū)塊小 開銷比例大 -->難以接受
區(qū)塊大 開銷比例小
GNU-C 2.9比較好 GNU-C 4.9又回到了VC BC的模式
GNU-C 2.9版本的alloc還在 在G4.9中改名為__pool_alloc
G2.9 alloc 容器模式下 不帶cookie 額外開銷
?
容器之間的實(shí)現(xiàn)關(guān)系與分類
2017年8月21日
14:55
容器，結(jié)構(gòu)與分類
?
容器list
2017年8月21日
15:03
一大堆typedef
node->link_type->list_node*
?
sizeof(list)應(yīng)該是4
?
template<class T>
struct __list_node
{
typedef void* void_pointer;
void_pointer pre;
void_pointer next;
T data;
}
所有的容器必然有一個typedef? blablabla iterator
所有iterator都必須typedef五個類型
?一大組的操作符重載
list's iterator
list<Foo>::iterator it;
postfix form ++
前++ 返回reference
后++ 返回非reference 禁止連續(xù)++
?
像偶像(int)致敬
?
->和* 提取值
*返回T&
->返回T*
容器list
2017年8月22日
15:08
G2.9
一堆typedef + 一堆操作符重載
G4.9相較于G2.9：
·模板參數(shù)只有一個(易理解)
·node結(jié)構(gòu)有其parent
·node的成員type較精確
G4.9
迭代器設(shè)計原則
2017年8月22日
15:23
traits : 特征、特性、特質(zhì)
人為設(shè)置的一種萃取機(jī)制
iterator需要遵循的原則
算法和容器之間的橋梁
?
iterator_category
difference_type
value_type
reference
pointer
iterator associated type
iterator traits
type traits
character traits
pointer traits
算法rotate 調(diào)用std::__rotate()
?
std::__rotate(…, std::__iterator_category(__first));
iterator traits誕生的因由：
iterator并不是一個class而是native pointer的時候
無法回答這五個問題
（native pointer 被視為一種退化的iterator）
迭代器設(shè)計原則
2017年8月22日
15:42
銀彈
判斷扔進(jìn)去的是否為class形式的iterator
如果是 則采用問答方式得出
如果不是 偏特化 typedef? 代其回答
容器vector
2017年8月22日
15:57
template<class T, class Alloc = alloc>
class vector
{
public:
typedef T????????????????????? value_type;
typedef value_type*? iterator;
typedef value_type& reference;
typedef size_t???????????? size_type;
protected:
iterator start;
iterator finish;
iterator end_of_storage;
public:
iterator begin() { return start;}
iterator end() {return finish;}
size_type size() const {return size_type(end() - begin());}
…
};
NOTICE：大量調(diào)用拷貝構(gòu)造和析構(gòu)
vector's iterator
public繼承
是一種
is-a關(guān)系
array和forwardlist
2017年8月22日
16:34
容器array
單向鏈表只能++ 往一個方向走
關(guān)于作業(yè)
2017年8月25日
11:08
創(chuàng)建一個list容器，放置6個整型數(shù)值[0, 1, 30, 20, 10, 0]
1.?從后向前打印出容器內(nèi)的元素
2.?向list容器后面添加兩個元素，并對容器內(nèi)的值求和并打印
3.?打印鏈表的中間元素
4.?找到不為0的元素，復(fù)制到一個vector中并打印vector元素
來自 <http://mooc.study.163.com/learn/GeekBand-2001184001?tid=2001361008#/learn/hw?id=2001591031&r=true>
創(chuàng)建一個list容器 放置整形值
list<int> i_list
以一個數(shù)組進(jìn)行容器的初始化
所以需要先聲明并給這個數(shù)組賦值
int src_int[6] = {0, 1, 30, 20, 10, 0};
list的構(gòu)造函數(shù)允許將兩個其他容器的迭代器
作為參數(shù)傳入進(jìn)行l(wèi)ist的構(gòu)造
list<int> i_list(&src_int[0], &src_int[6]);???????? //創(chuàng)建list容器，并將6個數(shù)值放入
?
?
1.從后向前打印出容器內(nèi)的元素
list自身攜帶逆序迭代器，想要從后向前打印list內(nèi)
元素，則采用逆序迭代器遍歷輸出即可
?
for (auto it = i_list.rbegin(); it != i_list.rend(); ++it) //采用逆序迭代器從后向前打印出容器內(nèi)的元素
{
cout << *it << " ";
}
cout << "\r\n打印完畢" << endl;
2.向list容器后面添加兩個元素并對容器內(nèi)的值求和并打印
先使用cin獲得需要添加的兩個元素
調(diào)用push_back()將這兩個元素添加到list的末尾
初始化和sum為0
采用迭代器遍歷整個容器，將所有值疊加至sum即為所有元素的和
int a, b;
cout << "請輸入需要添加的元素的值:" << endl;
cin >> a >> b;
i_list.push_back(a);
i_list.push_back(b);
int sum = 0;
for (auto it = i_list.begin(); it != i_list.end(); ++it)
{
sum += (*it);
}
?
關(guān)于作業(yè)
2017年8月25日
11:15
3.打印鏈表的中間元素
?
考慮到鏈表的長度(size)可能為奇數(shù)也可能為偶數(shù)
?
當(dāng)長度為奇數(shù)時 正中間的元素即為中間元素
當(dāng)長度為偶數(shù)時 中間的兩個元素均為中間元素
實(shí)現(xiàn)如下：
if (i_list.size()%2 != 0)//如果鏈表size為奇數(shù)則打印正中間元素
{
for (size_t i = 1; i < (i_list.size() + 1)/2; ++i)//從鏈表第一個元素開始到鏈表長度一半的偏移量
{
tar_it++;
}
cout << "鏈表的中間元素為:"???????? << *tar_it << endl;
}
else//如果鏈表size為偶數(shù)則打印中間兩個元素
{
for (size_t i = 1; i < i_list.size()/2 ; ++i) //從鏈表第一個元素開始到鏈表長度一半的偏移量
{
tar_it++;
}
cout << "鏈表的中間元素為:"???????? << *tar_it << "和";
tar_it++;
cout << *tar_it << endl;
}
?
4.找到不為0的元素，插入到vector，并打印
聲明vector，置空
遍歷list 判斷元素是否為0，不為0則插入到vector
遍歷vector輸出每個元素
實(shí)現(xiàn)如下：
vector<int> i_vector;
i_vector.clear();
for (auto it = i_list.begin(); it != i_list.end(); ++it)
{
if (*it != 0)//不為0的元素
{
i_vector.push_back(*it);
}
}
cout << "將不為0的元素拷貝到vector中后打印結(jié)果如下:" << endl;
for (auto value: i_vector)
{
cout << value << " ";
}
?
