广州专业的网站建设公司排名,申请免费个人网站和域名,苏州网站建设logo,建筑公司排名前十强✨ Blog’s 主页: 白乐天_ξ( ✿#xff1e;◡❛) #x1f308; 个人Motto#xff1a;他强任他强#xff0c;清风拂山冈#xff01; #x1f525; 所属专栏#xff1a;C深入学习笔记 #x1f4ab; 欢迎来到我的学习笔记#xff01; 参考博客#xff1a;【C】透过STL源… ✨ Blog’s 主页: 白乐天_ξ( ✿◡❛) 个人Motto他强任他强清风拂山冈 所属专栏C深入学习笔记 欢迎来到我的学习笔记 参考博客【C】透过STL源码深度剖析及模拟实现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_iteratorconst_iterator const_reverse_iterator;typedef reverse_iteratoriterator reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_iteratorconst_iterator, value_type, const_reference, difference_type const_reverse_iterator;typedef reverse_iteratoriterator, value_type, reference, difference_typereverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:typedef simple_allocvalue_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 vectorT, 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 InputIteratorvector(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();}vectorT, Alloc operator(const vectorT, 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(vectorT, 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 InputIteratorvoid 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 ForwardIteratoriterator 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 InputIteratorvoid 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 ForwardIteratorvoid 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 InputIteratorvoid range_insert(iterator pos,InputIterator first, InputIterator last,input_iterator_tag);template class ForwardIteratorvoid range_insert(iterator pos,ForwardIterator first, ForwardIterator last,forward_iterator_tag);#endif /* __STL_MEMBER_TEMPLATES */
};template class T, class Alloc
inline bool operator(const vectorT, Alloc x, const vectorT, Alloc y) {return x.size() y.size() equal(x.begin(), x.end(), y.begin());
}template class T, class Alloc
inline bool operator(const vectorT, Alloc x, const vectorT, 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(vectorT, Alloc x, vectorT, Alloc y) {x.swap(y);
}#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */template class T, class Alloc
vectorT, Alloc vectorT, Alloc::operator(const vectorT, 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 vectorT, 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 vectorT, 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 vectorT, 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 vectorT, 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 vectorT, 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:
二、分析源码
源码的分析方法先看框架再分析细节最好要学会画图直观的展现清楚类内部、类之间的关系例如分析一个类先分析它的大致框架功能是什么、核心成员是什么、核心函数是什么、该类的大致方向是做什么。然后再分析类与类之间是什么关系。
2.1 捋顺牵头框架
切记不要看细节不要一行一行地看例如这里就是先找到一个大类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_iteratorconst_iterator const_reverse_iterator;typedef reverse_iteratoriterator reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */typedef reverse_iteratorconst_iterator, value_type, const_reference, difference_type const_reverse_iterator;typedef reverse_iteratoriterator, value_type, reference, difference_typereverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
protected:typedef simple_allocvalue_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;可以发现这里定义两三个迭代器在此之前【链接】string的模拟实现我们就已经知道迭代器名称是typedef来的因此在这里我们可以找一下它的typedef在public位置找到了iterator的重定义位置。这里就找到了iterator最根本的面貌。
typedef T value_type;
typedef value_type* iterator;在找到成员变量后我们要学会“猜”它的作用例如猜测start是空间内存的开始位置或者数据开始的位置猜测finish是数据结束位置猜测end_of_storage是空间结束位置。猜测是基于自己的学习经验有依据的进行推测而并非是乱猜。合理的猜测有助于我们更加顺利的理解源码但也容易误导我们自己。猜测需要使用后面的步骤进行证实
注意细节不要硬扣这里不能涉及太多的细节我们目前的目标主要是学习它的基本框架。源码的细节都是一层套着一层关注细节容易绕晕自己我们应该知道不要让本应该读绘本的幼儿园小朋友去读《水浒》即俗语“少不读水浒老不读三国”。
2.3 分析构造函数
在分析完成员函数后我们开始分析构造函数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); }在这里我们可以发现vector()是初始化为无参的构造函数接下来我们开始分析核心的接口。
2.4 分析核心接口
一个类的实现会调用很多的接口我们要关注核心接口、常用接口。例如这里我们查找一下常用的push_back接口。在这里开始证实我们方才的猜测是否正确。
void push_back(const T x) {if (finish ! end_of_storage) {construct(finish, x);finish;}elseinsert_aux(end(), x);}按照我们的猜测以及push_back接口进行画图 在这里有一个construct函数我们没有经验时你就会不知道它的作用。在有些项目里面会考虑使用内 存池提高效率STL的六大组件之一空间配置器内存池出来的数据只开辟了空间并没有进行初始化。
这里就使用了内存池里面的空间自然是没有进行初始化。它使用了construct进行初始化头文件是stl_construct.h。 construct是一个类模板的定位new定位new相当于显示调用构造函数。
// stl_construct.h
template class T1, class T2
inline void construct(T1* p, const T2 value) {new (p) T1(value);
}分析到这里就基本印证了我们方才的猜测。如果不确定还可以继续往下分析。else里面的一种清况
insert_aux(end(), x);我们可以右击insert_aux()转到定义
template class T, class Alloc
void vectorT, 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);}根据上面的定义代码我们可以大概知道if是判断空间足够后的插入数据的操作else是空间不够、中间插入数据时后面的数据需要往后挪动可能会出现抛出异常的清况就使用了__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源码的分析我们了解了其框架结构、成员变量、构造函数和核心接口的实现原理。vector容器通过巧妙地使用迭代器和内存管理技术提供了高效的动态数组功能。我们也可以根据现在所掌握的东西进行vector的模拟实现。
