? Blog’s 主頁: 白樂天_ξ( ?＞??)
🌈 個人Motto：他強任他強，清風拂山岡！
🔥 所屬專欄：C++深入學習筆記
💫 歡迎來到我的學習筆記！

參考博客：【C++】透過STL源碼深度剖析及模擬實現(xiàn)vector-CSDN博客

一、源碼引入

這里我們學習的是基于SGI版本的STL源碼。源碼如下：

// stl_vector.h/*** Copyright (c) 1994* Hewlett-Packard Company** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Hewlett-Packard Company makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*** Copyright (c) 1996* Silicon Graphics Computer Systems, Inc.** Permission to use, copy, modify, distribute and sell this software* and its documentation for any purpose is hereby granted without fee,* provided that the above copyright notice appear in all copies and* that both that copyright notice and this permission notice appear* in supporting documentation.  Silicon Graphics makes no* representations about the suitability of this software for any* purpose.  It is provided "as is" without express or implied warranty.*//* NOTE: This is an internal header file, included by other STL headers.*   You should not attempt to use it directly.*/#ifndef __SGI_STL_INTERNAL_VECTOR_H
#define __SGI_STL_INTERNAL_VECTOR_H__STL_BEGIN_NAMESPACE #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endiftemplate <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type>  const_reverse_iterator;typedef reverse_iterator<iterator, value_type, reference, difference_type>reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:typedef simple_alloc<value_type, Alloc> data_allocator;iterator start;iterator finish;iterator end_of_storage;void insert_aux(iterator position, const T& x);void deallocate() {if (start) data_allocator::deallocate(start, end_of_storage - start);}void fill_initialize(size_type n, const T& value) {start = allocate_and_fill(n, value);finish = start + n;end_of_storage = finish;}
public:iterator begin() { return start; }const_iterator begin() const { return start; }iterator end() { return finish; }const_iterator end() const { return finish; }reverse_iterator rbegin() { return reverse_iterator(end()); }const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }size_type size() const { return size_type(end() - begin()); }size_type max_size() const { return size_type(-1) / sizeof(T); }size_type capacity() const { return size_type(end_of_storage - begin()); }bool empty() const { return begin() == end(); }reference operator[](size_type n) { return *(begin() + n); }const_reference operator[](size_type n) const { return *(begin() + n); }vector() : start(0), finish(0), end_of_storage(0) {}vector(size_type n, const T& value) { fill_initialize(n, value); }vector(int n, const T& value) { fill_initialize(n, value); }vector(long n, const T& value) { fill_initialize(n, value); }explicit vector(size_type n) { fill_initialize(n, T()); }vector(const vector<T, Alloc>& x) {start = allocate_and_copy(x.end() - x.begin(), x.begin(), x.end());finish = start + (x.end() - x.begin());end_of_storage = finish;}
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>vector(InputIterator first, InputIterator last) :start(0), finish(0), end_of_storage(0){range_initialize(first, last, iterator_category(first));}
#else /* __STL_MEMBER_TEMPLATES */vector(const_iterator first, const_iterator last) {size_type n = 0;distance(first, last, n);start = allocate_and_copy(n, first, last);finish = start + n;end_of_storage = finish;}
#endif /* __STL_MEMBER_TEMPLATES */~vector() { destroy(start, finish);deallocate();}vector<T, Alloc>& operator=(const vector<T, Alloc>& x);void reserve(size_type n) {if (capacity() < n) {const size_type old_size = size();iterator tmp = allocate_and_copy(n, start, finish);destroy(start, finish);deallocate();start = tmp;finish = tmp + old_size;end_of_storage = start + n;}}reference front() { return *begin(); }const_reference front() const { return *begin(); }reference back() { return *(end() - 1); }const_reference back() const { return *(end() - 1); }void push_back(const T& x) {if (finish != end_of_storage) {construct(finish, x);++finish;}elseinsert_aux(end(), x);}void swap(vector<T, Alloc>& x) {__STD::swap(start, x.start);__STD::swap(finish, x.finish);__STD::swap(end_of_storage, x.end_of_storage);}iterator insert(iterator position, const T& x) {size_type n = position - begin();if (finish != end_of_storage && position == end()) {construct(finish, x);++finish;}elseinsert_aux(position, x);return begin() + n;}iterator insert(iterator position) { return insert(position, T()); }
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void insert(iterator position, InputIterator first, InputIterator last) {range_insert(position, first, last, iterator_category(first));}
#else /* __STL_MEMBER_TEMPLATES */void insert(iterator position,const_iterator first, const_iterator last);
#endif /* __STL_MEMBER_TEMPLATES */void insert (iterator pos, size_type n, const T& x);void insert (iterator pos, int n, const T& x) {insert(pos, (size_type) n, x);}void insert (iterator pos, long n, const T& x) {insert(pos, (size_type) n, x);}void pop_back() {--finish;destroy(finish);}iterator erase(iterator position) {if (position + 1 != end())copy(position + 1, finish, position);--finish;destroy(finish);return position;}iterator erase(iterator first, iterator last) {iterator i = copy(last, finish, first);destroy(i, finish);finish = finish - (last - first);return first;}void resize(size_type new_size, const T& x) {if (new_size < size()) erase(begin() + new_size, end());elseinsert(end(), new_size - size(), x);}void resize(size_type new_size) { resize(new_size, T()); }void clear() { erase(begin(), end()); }protected:iterator allocate_and_fill(size_type n, const T& x) {iterator result = data_allocator::allocate(n);__STL_TRY {uninitialized_fill_n(result, n, x);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}#ifdef __STL_MEMBER_TEMPLATEStemplate <class ForwardIterator>iterator allocate_and_copy(size_type n,ForwardIterator first, ForwardIterator last) {iterator result = data_allocator::allocate(n);__STL_TRY {uninitialized_copy(first, last, result);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}
#else /* __STL_MEMBER_TEMPLATES */iterator allocate_and_copy(size_type n,const_iterator first, const_iterator last) {iterator result = data_allocator::allocate(n);__STL_TRY {uninitialized_copy(first, last, result);return result;}__STL_UNWIND(data_allocator::deallocate(result, n));}
#endif /* __STL_MEMBER_TEMPLATES */#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void range_initialize(InputIterator first, InputIterator last,input_iterator_tag) {for ( ; first != last; ++first)push_back(*first);}// This function is only called by the constructor.  We have to worry//  about resource leaks, but not about maintaining invariants.template <class ForwardIterator>void range_initialize(ForwardIterator first, ForwardIterator last,forward_iterator_tag) {size_type n = 0;distance(first, last, n);start = allocate_and_copy(n, first, last);finish = start + n;end_of_storage = finish;}template <class InputIterator>void range_insert(iterator pos,InputIterator first, InputIterator last,input_iterator_tag);template <class ForwardIterator>void range_insert(iterator pos,ForwardIterator first, ForwardIterator last,forward_iterator_tag);#endif /* __STL_MEMBER_TEMPLATES */
};template <class T, class Alloc>
inline bool operator==(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}template <class T, class Alloc>
inline bool operator<(const vector<T, Alloc>& x, const vector<T, Alloc>& y) {return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDERtemplate <class T, class Alloc>
inline void swap(vector<T, Alloc>& x, vector<T, Alloc>& y) {x.swap(y);
}#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */template <class T, class Alloc>
vector<T, Alloc>& vector<T, Alloc>::operator=(const vector<T, Alloc>& x) {if (&x != this) {if (x.size() > capacity()) {iterator tmp = allocate_and_copy(x.end() - x.begin(),x.begin(), x.end());destroy(start, finish);deallocate();start = tmp;end_of_storage = start + (x.end() - x.begin());}else if (size() >= x.size()) {iterator i = copy(x.begin(), x.end(), begin());destroy(i, finish);}else {copy(x.begin(), x.begin() + size(), start);uninitialized_copy(x.begin() + size(), x.end(), finish);}finish = start + x.size();}return *this;
}template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {if (finish != end_of_storage) {construct(finish, *(finish - 1));++finish;T x_copy = x;copy_backward(position, finish - 2, finish - 1);*position = x_copy;}else {const size_type old_size = size();const size_type len = old_size != 0 ? 2 * old_size : 1;iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;__STL_TRY {new_finish = uninitialized_copy(start, position, new_start);construct(new_finish, x);++new_finish;new_finish = uninitialized_copy(position, finish, new_finish);}#       ifdef  __STL_USE_EXCEPTIONS catch(...) {destroy(new_start, new_finish); data_allocator::deallocate(new_start, len);throw;}
#       endif /* __STL_USE_EXCEPTIONS */destroy(begin(), end());deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}
}template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {if (n != 0) {if (size_type(end_of_storage - finish) >= n) {T x_copy = x;const size_type elems_after = finish - position;iterator old_finish = finish;if (elems_after > n) {uninitialized_copy(finish - n, finish, finish);finish += n;copy_backward(position, old_finish - n, old_finish);fill(position, position + n, x_copy);}else {uninitialized_fill_n(finish, n - elems_after, x_copy);finish += n - elems_after;uninitialized_copy(position, old_finish, finish);finish += elems_after;fill(position, old_finish, x_copy);}}else {const size_type old_size = size();        const size_type len = old_size + max(old_size, n);iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;__STL_TRY {new_finish = uninitialized_copy(start, position, new_start);new_finish = uninitialized_fill_n(new_finish, n, x);new_finish = uninitialized_copy(position, finish, new_finish);}
#         ifdef  __STL_USE_EXCEPTIONS catch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}}
}#ifdef __STL_MEMBER_TEMPLATEStemplate <class T, class Alloc> template <class InputIterator>
void vector<T, Alloc>::range_insert(iterator pos,InputIterator first, InputIterator last,input_iterator_tag) {for ( ; first != last; ++first) {pos = insert(pos, *first);++pos;}
}template <class T, class Alloc> template <class ForwardIterator>
void vector<T, Alloc>::range_insert(iterator position,ForwardIterator first,ForwardIterator last,forward_iterator_tag) {if (first != last) {size_type n = 0;distance(first, last, n);if (size_type(end_of_storage - finish) >= n) {const size_type elems_after = finish - position;iterator old_finish = finish;if (elems_after > n) {uninitialized_copy(finish - n, finish, finish);finish += n;copy_backward(position, old_finish - n, old_finish);copy(first, last, position);}else {ForwardIterator mid = first;advance(mid, elems_after);uninitialized_copy(mid, last, finish);finish += n - elems_after;uninitialized_copy(position, old_finish, finish);finish += elems_after;copy(first, mid, position);}}else {const size_type old_size = size();const size_type len = old_size + max(old_size, n);iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;__STL_TRY {new_finish = uninitialized_copy(start, position, new_start);new_finish = uninitialized_copy(first, last, new_finish);new_finish = uninitialized_copy(position, finish, new_finish);}
#         ifdef __STL_USE_EXCEPTIONScatch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}}
}#else /* __STL_MEMBER_TEMPLATES */template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, const_iterator first, const_iterator last) {if (first != last) {size_type n = 0;distance(first, last, n);if (size_type(end_of_storage - finish) >= n) {const size_type elems_after = finish - position;iterator old_finish = finish;if (elems_after > n) {uninitialized_copy(finish - n, finish, finish);finish += n;copy_backward(position, old_finish - n, old_finish);copy(first, last, position);}else {uninitialized_copy(first + elems_after, last, finish);finish += n - elems_after;uninitialized_copy(position, old_finish, finish);finish += elems_after;copy(first, first + elems_after, position);}}else {const size_type old_size = size();const size_type len = old_size + max(old_size, n);iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;__STL_TRY {new_finish = uninitialized_copy(start, position, new_start);new_finish = uninitialized_copy(first, last, new_finish);new_finish = uninitialized_copy(position, finish, new_finish);}
#         ifdef __STL_USE_EXCEPTIONScatch(...) {destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}
#         endif /* __STL_USE_EXCEPTIONS */destroy(start, finish);deallocate();start = new_start;finish = new_finish;end_of_storage = new_start + len;}}
}#endif /* __STL_MEMBER_TEMPLATES */#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif__STL_END_NAMESPACE #endif /* __SGI_STL_INTERNAL_VECTOR_H */// Local Variables:
// mode:C++
// End:

二、分析源碼

源碼的分析方法：先看框架，再分析細節(jié)，最好要學會畫圖直觀的展現(xiàn)清楚類內部、類之間的關系！例如分析一個類：先分析它的大致框架，功能是什么、核心成員是什么、核心函數(shù)是什么、該類的大致方向是做什么。然后再分析類與類之間是什么關系。

2.1 捋順牽頭框架

切記不要看細節(jié)，不要一行一行地看；例如這里就是先找到一個大類vector。

template <class T, class Alloc = alloc>
class vector {
public:typedef T value_type;typedef value_type* pointer;typedef const value_type* const_pointer;typedef value_type* iterator;typedef const value_type* const_iterator;typedef value_type& reference;typedef const value_type& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;#ifdef __STL_CLASS_PARTIAL_SPECIALIZATIONtypedef reverse_iterator<const_iterator> const_reverse_iterator;typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_iterator<const_iterator, value_type, const_reference, difference_type>  const_reverse_iterator;typedef reverse_iterator<iterator, value_type, reference, difference_type>reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:typedef simple_alloc<value_type, Alloc> data_allocator;iterator start;iterator finish;iterator end_of_storage;void insert_aux(iterator position, const T& x);void deallocate() {if (start) data_allocator::deallocate(start, end_of_storage - start);}

2.2 分析成員變量

在上一步找到的一個大類里面，開始查找成員變量，成員變量一般在private或者protected里面。

protected:iterator start;iterator finish;iterator end_of_storage;

可以發(fā)現(xiàn)這里定義兩三個迭代器，在此之前（【鏈接】string的模擬實現(xiàn)）我們就已經(jīng)知道迭代器名稱是typedef來的，因此在這里我們可以找一下它的typedef，在public位置找到了iterator的重定義位置。這里就找到了iterator最根本的面貌。

typedef T value_type;
typedef value_type* iterator;

在找到成員變量后我們要學會“猜”它的作用：例如猜測start是空間內存的開始位置或者數(shù)據(jù)開始的位置；猜測finish是數(shù)據(jù)結束位置；猜測end_of_storage是空間結束位置。猜測是基于自己的學習經(jīng)驗，有依據(jù)的進行推測，而并非是亂猜。合理的猜測有助于我們更加順利的理解源碼，但也容易誤導我們自己。猜測需要使用后面的步驟進行證實！

注意：細節(jié)不要硬扣，這里不能涉及太多的細節(jié)，我們目前的目標主要是學習它的基本框架。源碼的細節(jié)都是一層套著一層，關注細節(jié)容易繞暈自己，我們應該知道：不要讓本應該讀繪本的幼兒園小朋友去讀《水滸》，即俗語“少不讀水滸，老不讀三國”。

2.3 分析構造函數(shù)

在分析完成員函數(shù)后，我們開始分析構造函數(shù)vector(……)，看看該類的對象初始化以后是什么樣的結果。

vector() : start(0), finish(0), end_of_storage(0) {}
vector(size_type n, const T& value) { fill_initialize(n, value); }
vector(int n, const T& value) { fill_initialize(n, value); }
vector(long n, const T& value) { fill_initialize(n, value); }

在這里我們可以發(fā)現(xiàn)vector()是初始化為無參的構造函數(shù)，接下來我們開始分析核心的接口。

2.4 分析核心接口

一個類的實現(xiàn)會調用很多的接口，我們要關注核心接口、常用接口。例如這里我們查找一下常用的push_back接口。在這里開始證實我們方才的猜測是否正確。

void push_back(const T& x) {if (finish != end_of_storage) {construct(finish, x);++finish;}elseinsert_aux(end(), x);}

按照我們的猜測以及push_back接口進行畫圖：

在這里有一個construct函數(shù)，我們沒有經(jīng)驗時你就會不知道它的作用。在有些項目里面會考慮使用內 存池提高效率，STL的六大組件之一空間配置器（內存池）出來的數(shù)據(jù)只開辟了空間，并沒有進行初始化。

這里就使用了內存池里面的空間，自然是沒有進行初始化。它使用了construct進行初始化，頭文件是stl_construct.h。 construct是一個類模板的定位new，定位new相當于顯示調用構造函數(shù)。

// stl_construct.h
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {new (p) T1(value);
}

分析到這里就基本印證了我們方才的猜測。如果不確定，還可以繼續(xù)往下分析。else里面的一種清況：

insert_aux(end(), x);

我們可以右擊insert_aux()轉到定義：

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {if (finish != end_of_storage) {construct(finish, *(finish - 1)); // 空間不滿，走此處++finish;T x_copy = x;copy_backward(position, finish - 2, finish - 1);*position = x_copy;}else {const size_type old_size = size();// 在這里轉到定義const size_type len = old_size != 0 ? 2 * old_size : 1;iterator new_start = data_allocator::allocate(len);// 這里使用的是內存池開辟的空間iterator new_finish = new_start;__STL_TRY {new_finish = uninitialized_copy(start, position, new_start);construct(new_finish, x);++new_finish;new_finish = uninitialized_copy(position, finish, new_finish);}

根據(jù)上面的定義代碼，我們可以大概知道if是判斷空間足夠后的插入數(shù)據(jù)的操作，else是空間不夠、中間插入數(shù)據(jù)時，后面的數(shù)據(jù)需要往后挪動，可能會出現(xiàn)拋出異常的清況，就使用了__STL_TRY這一段宏定義過的內容，在拋異常的時候進行捕獲。

下面這幾句代碼就是最終確定我們的猜測的關鍵代碼。

// stl_vector.h
public:iterator begin() { return start; }//const_iterator begin() const { return start; }iterator end() { return finish; }//const_iterator end() const { return finish; }size_type size() const { return size_type(end() - begin()); }size_type capacity() const { return size_type(end_of_storage - begin()); }

通過對 SGI 版本 STL 中vector源碼的分析，我們了解了其框架結構、成員變量、構造函數(shù)和核心接口的實現(xiàn)原理。vector容器通過巧妙地使用迭代器和內存管理技術，提供了高效的動態(tài)數(shù)組功能。我們也可以根據(jù)現(xiàn)在所掌握的東西，進行vector的模擬實現(xiàn)。