[Boolan] C++第七周 STL 泛型編程（一）

2019-11-06 07:08:15

字體：大中小

來源：轉載

供稿：網友

參考鏈接:C++new和delete實現原理

1. OOP(面向對象編程) vs GP(泛型編程)

OOP：將datas跟methods關聯放到一起GP：將datas和methods分開，通過迭代器關聯在一起 sort(c.begin(), c.end()) 優點:可以將容器和算法分別開發，低耦合，算法通過迭代器確定操作范圍，并且通過迭代器獲取數據

2. 分配器

VC++中

//newop2.cpp VC中new操作符的源碼// newop2 Operator new(size_t, const nothrow_t&) for Microsoft C++#include <cstdlib>#include <new>_C_LIB_DECLint _callnewh(size_t size);_END_C_LIB_DECLvoid *operator new(size_t size, const std::nothrow_t&) _THROW0() { // try to allocate size bytes void *p; while ((p = malloc(size)) == 0) { // buy more memory or return null pointer _TRY_BEGIN if (_callnewh(size) == 0) break; _CATCH(std::bad_alloc) return (0); _CATCH_END } return (p); }

由上述源碼可以看到，new是調用了系統函數malloc來分配的內存

//VC中allocator的部分源碼 <xmemory>template<class _Ty> class allocator {public: typedef _SIZT size_type; typedef _PDFT difference_type; typedef _Ty _FARQ *pointer; typedef const _Ty _FARQ *const_pointer; typedef _Ty _FARQ& reference; typedef const _Ty _FARQ& const_reference; typedef _Ty value_type; pointer address(reference _X) const {return (&_X); } const_pointer address(const_reference _X) const {return (&_X); } pointer allocate(size_type _N, const void *) {return (_Allocate((difference_type)_N, (pointer)0)); } }; template<class _Ty> inline _Ty _FARQ *_Allocate(_PDFT _N, _Ty _FARQ *) {if (_N < 0) _N = 0; return ((_Ty _FARQ *)operator new( (_SIZT)_N * sizeof (_Ty))); }

由上述源碼可知，VC的分配器是調用的_Allocate模板函數來分配內存，_Allocate是調用的operator new，new是調用的malloc系統函數分配的可知VC的分配器并沒有什么特殊處理

int *p = allocator<int>().allocate(512, *int*)0);allocator<int>().deallocate(p, 512);

在GUN4.5中有兩種分配器,一個是allocator，跟VC的一樣；另一個叫_pool_alloc，這個分配器會有一個整的內存池，由16個指針組成，每個指針指向不同大小的內存，根據每次申請的大小分配那個指針上的內存，這樣就避免了每次申請內存時，所帶來的額外消耗，例如記錄當前分配的內存大小，開始結束的標志。第二種的用法,認為指定分配器

vector<string, __gun_cxx::__pool_alloc<string>> vec;

3. 容器

[圖]

4. List

雙向鏈表實現，里面包含著迭代器，并且迭代器進行了大量的操作符重載,讓他可以向指針一樣使用template <class T, class Alloc = alloc>class list{PRotected: typedef __list_node<t> list_node;public: typedef list_node* link_type; typedef __list_iterator<T, T&, T*> iterator;protected: link_type node;};

[圖-迭代器重載]

其中需要注意的是下面這兩個，前加加和后加加self & operator++() {node = (link_type)((*node).next); return *this;}self operator++(int) {self tmp = *this; ++*this; return tmp;}首先需要注意的是，雖然iterator也重載operator*(), 但是這里面的*this并沒有使用這個重載；例如self tmp = *this, return *this;這兩次*this已經被解釋為拷貝構造的參數了++*this也沒有使用重載的operator*();也是已經把*this解釋成了operator++()的參數了操作符重載所看齊的對象是int(整型),應該符合整型的使用直覺int i(6);++++i; ---> ++(++i); //成立i++++; ---> (i++)++; //不成立遵循這個原則；所以operator++(int)的返回值是self，而不是self&, ++++的預期效果和int一致

Gnu2.9 —> Gnu4.9 自行體會 [圖]

5. 迭代器的設計原則和Iterator Traits的作用與設計

鏈接：iterator_traits 19: 迭代器特性-iterator traits 我認為traints是容器跟算法中間的橋梁，因為容器是多種多樣的，但是在實現某種功能是，會使用同一種算法，此時，算法就需要根據各個容器的特性來進行不同的計算那算法怎么知道各個容器的特征的呢？通過Traits

所以在每個Itreator中，都規定需要定義一下五種typedeftemplate<typename _Tp>struct _List_iterator{ typedef std::bidirectional_iterator_tag iterator_category; //容器的類別 typedef _Tp value_type; //容器的元素的類型 typedef _Tp* pointer; typedef _Tp& reference; typedef ptrdiff_t difference_type; //位置差類型};如果僅僅是重命名，直接在iterator中定義就好了，為什么還要有一個Traits呢？這是為了一個情況，就是iterator不是一個類；而是一個指針，那算法在調用一個指針作為參數的時候，就沒有辦法獲得他的value_type,pointer,difference_type等特征所以，就抽了一個中間層，利用模板的偏特化的特性來進行一層包裝//以value_type 為例給出示例template <class I>struct iterator_traits { //如果I是class iterator，就進這里 typedef typename I::value_type value_type;};template <class T>struct iterator_traits<T*> { typedef T value;};template <class T>struct iterator_traits<const T*>{ typedef T value_type; };//為什么const T* 的value_type不是const的，因為聲明一種無法被賦值的變量沒什么用，沒辦法被算法調用并進行計算template <typename T, ...>void algorithm(...) { typename iterator_traits<T>::value_type v1;}