STL快速入门

vector

查看详细分析

#include<iostream>
using namespace std;
#include<memory.h>  // alloc是SGI STL的空间配置器
template <class T, class Alloc = alloc>
class vector
{
public:// vector的嵌套类型定义,typedefs用于提供iterator_traits<I>支持typedef T value_type;typedef value_type* pointer;typedef value_type* iterator;typedef value_type& reference;typedef size_t size_type;typedef ptrdiff_t difference_type;
protected:// 这个提供STL标准的allocator接口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(){// 由于使用的是data_allocator进行内存空间的分配,// 所以需要同样使用data_allocator::deallocate()进行释放// 如果直接释放, 对于data_allocator内部使用内存池的版本// 就会发生错误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; }iterator end() { return finish; }// 返回当前对象个数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); }// 本实作中默认构造出的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); }// 需要对象提供默认构造函数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;}~vector(){// 析构对象destroy(start, finish);// 释放内存deallocate();}vector<T, Alloc>& operator=(const vector<T, Alloc>& x);// 提供访问函数reference front() { return *begin(); }reference back() { return *(end() - 1); }void push_back(const T& x){// 内存满足条件则直接追加元素, 否则需要重新分配内存空间if (finish != end_of_storage){construct(finish, x);++finish;}elseinsert_aux(end(), x);}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()); }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;}// 调整size, 但是并不会重新分配内存空间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);uninitialized_fill_n(result, n, x);return result;}template <class T, class Alloc>void insert_aux(iterator position, const T& x){if (finish != end_of_storage)    // 还有备用空间{// 在备用空间起始处构造一个元素，并以vector最后一个元素值为其初值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;// 以上配置元素：如果大小为0，则配置1（个元素大小）// 如果大小不为0，则配置原来大小的两倍// 前半段用来放置原数据，后半段准备用来放置新数据iterator new_start = data_allocator::allocate(len);  // 实际配置iterator new_finish = new_start;// 将内存重新配置try{// 将原vector的安插点以前的内容拷贝到新vectornew_finish = uninitialized_copy(start, position, new_start);// 为新元素设定初值 xconstruct(new_finish, x);// 调整水位++new_finish;// 将安插点以后的原内容也拷贝过来new_finish = uninitialized_copy(position, finish, new_finish);}catch(...){// 回滚操作destroy(new_start, new_finish);data_allocator::deallocate(new_start, len);throw;}// 析构并释放原vectordestroy(begin(), end());deallocate();// 调整迭代器，指向新vectorstart = new_start;finish = new_finish;end_of_storage = new_start + len;}}template <class T, class Alloc>void insert(iterator position, size_type n, const T& x){// 如果n为0则不进行任何操作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;    // 将vector 尾端标记后移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);// 以下配置新的vector空间iterator new_start = data_allocator::allocate(len);iterator new_finish = new_start;__STL_TRY{// 以下首先将旧的vector的插入点之前的元素复制到新空间new_finish = uninitialized_copy(start, position, new_start);// 以下再将新增元素（初值皆为n）填入新空间new_finish = uninitialized_fill_n(new_finish, n, x);// 以下再将旧vector的插入点之后的元素复制到新空间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;}}}
};

set

查看详细分析

//代码摘录于stl_set.h
template <class _Key, class _Compare, class _Alloc>
class set {// requirements:__STL_CLASS_REQUIRES(_Key, _Assignable);__STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);public:// typedefs:typedef _Key     key_type;typedef _Key     value_type;typedef _Compare key_compare;typedef _Compare value_compare;
private:typedef _Rb_tree<key_type, value_type, _Identity<value_type>, key_compare, _Alloc> _Rep_type;_Rep_type _M_t;  // 采用红黑树来表现set
public:typedef typename _Rep_type::const_pointer pointer;typedef typename _Rep_type::const_pointer const_pointer;typedef typename _Rep_type::const_reference reference;typedef typename _Rep_type::const_reference const_reference;typedef typename _Rep_type::const_iterator iterator;//注意上一行，iterator定义为RB-tree的const_iterator，表示//set的迭代器无法执行写入操作typedef typename _Rep_type::const_iterator const_iterator;typedef typename _Rep_type::const_reverse_iterator reverse_iterator;typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;typedef typename _Rep_type::size_type size_type;typedef typename _Rep_type::difference_type difference_type;typedef typename _Rep_type::allocator_type allocator_type;// allocation/deallocation//注意，set一定使用RB-=tree的insert_unique()而非insert_equal()//multiset才使用RB-tree的insert_equal()set() : _M_t(_Compare(), allocator_type()) {}explicit set(const _Compare& __comp,const allocator_type& __a = allocator_type()): _M_t(__comp, __a) {}#ifdef __STL_MEMBER_TEMPLATEStemplate <class _InputIterator>set(_InputIterator __first, _InputIterator __last): _M_t(_Compare(), allocator_type()){ _M_t.insert_unique(__first, __last); }template <class _InputIterator>set(_InputIterator __first, _InputIterator __last, const _Compare& __comp,const allocator_type& __a = allocator_type()): _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
#elseset(const value_type* __first, const value_type* __last) : _M_t(_Compare(), allocator_type()) { _M_t.insert_unique(__first, __last); }set(const value_type* __first, const value_type* __last, const _Compare& __comp,const allocator_type& __a = allocator_type()): _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }set(const_iterator __first, const_iterator __last): _M_t(_Compare(), allocator_type()) { _M_t.insert_unique(__first, __last); }set(const_iterator __first, const_iterator __last, const _Compare& __comp,const allocator_type& __a = allocator_type()): _M_t(__comp, __a) { _M_t.insert_unique(__first, __last); }
#endif /* __STL_MEMBER_TEMPLATES */set(const set<_Key,_Compare,_Alloc>& __x) : _M_t(__x._M_t) {}set<_Key,_Compare,_Alloc>& operator=(const set<_Key, _Compare, _Alloc>& __x){ _M_t = __x._M_t; return *this;}//以下所有的set操作，RB-tree都已提供，所以set只要传递调用即可// accessors:key_compare key_comp() const { return _M_t.key_comp(); }value_compare value_comp() const { return _M_t.key_comp(); }allocator_type get_allocator() const { return _M_t.get_allocator(); }iterator begin() const { return _M_t.begin(); }iterator end() const { return _M_t.end(); }reverse_iterator rbegin() const { return _M_t.rbegin(); } reverse_iterator rend() const { return _M_t.rend(); }bool empty() const { return _M_t.empty(); }size_type size() const { return _M_t.size(); }size_type max_size() const { return _M_t.max_size(); }void swap(set<_Key,_Compare,_Alloc>& __x) { _M_t.swap(__x._M_t); }// insert/erasepair<iterator,bool> insert(const value_type& __x) { pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x); return pair<iterator, bool>(__p.first, __p.second);}iterator insert(iterator __position, const value_type& __x) {typedef typename _Rep_type::iterator _Rep_iterator;return _M_t.insert_unique((_Rep_iterator&)__position, __x);}
#ifdef __STL_MEMBER_TEMPLATEStemplate <class _InputIterator>void insert(_InputIterator __first, _InputIterator __last) {_M_t.insert_unique(__first, __last);}
#elsevoid insert(const_iterator __first, const_iterator __last) {_M_t.insert_unique(__first, __last);}void insert(const value_type* __first, const value_type* __last) {_M_t.insert_unique(__first, __last);}
#endif /* __STL_MEMBER_TEMPLATES */void erase(iterator __position) { typedef typename _Rep_type::iterator _Rep_iterator;_M_t.erase((_Rep_iterator&)__position); }size_type erase(const key_type& __x) { return _M_t.erase(__x); }void erase(iterator __first, iterator __last) { typedef typename _Rep_type::iterator _Rep_iterator;_M_t.erase((_Rep_iterator&)__first, (_Rep_iterator&)__last); }void clear() { _M_t.clear(); }// set operations:iterator find(const key_type& __x) const { return _M_t.find(__x); }size_type count(const key_type& __x) const {return _M_t.find(__x) == _M_t.end() ? 0 : 1;}iterator lower_bound(const key_type& __x) const {return _M_t.lower_bound(__x);}iterator upper_bound(const key_type& __x) const {return _M_t.upper_bound(__x); }pair<iterator,iterator> equal_range(const key_type& __x) const {return _M_t.equal_range(__x);}#ifdef __STL_TEMPLATE_FRIENDStemplate <class _K1, class _C1, class _A1>friend bool operator== (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);template <class _K1, class _C1, class _A1>friend bool operator< (const set<_K1,_C1,_A1>&, const set<_K1,_C1,_A1>&);
#else /* __STL_TEMPLATE_FRIENDS */friend bool __STD_QUALIFIERoperator== __STL_NULL_TMPL_ARGS (const set&, const set&);friend bool __STD_QUALIFIERoperator<  __STL_NULL_TMPL_ARGS (const set&, const set&);
#endif /* __STL_TEMPLATE_FRIENDS */
};

pair & map

来源

//stl_pair.h里 pair 的定义
template <class T1, class T2>
struct pair {typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair() : first(T1()), second(T2()) {}pair(const T1& a, const T2& b) : first(a), second(b) {}#ifdef __STL_MEMBER_TEMPLATEStemplate <class U1, class U2>pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};

//stl_map.h 源代码
#ifndef __SGI_STL_INTERNAL_MAP_H
#define __SGI_STL_INTERNAL_MAP_H__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endif#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
#else
template <class Key, class T, class Compare, class Alloc = alloc>
#endif
class map {
public:// typedefs:typedef Key key_type;  //键值类型typedef T data_type;   //数值类型typedef T mapped_type;typedef pair<const Key, T> value_type; //元素类型(键值/实值)typedef Compare key_compare; //键值比較函数// functor。 其作用是调用 "元素比較函数"class value_compare: public binary_function<value_type, value_type, bool> {friend class map<Key, T, Compare, Alloc>;protected :Compare comp;value_compare(Compare c) : comp(c) {}public:bool operator()(const value_type& x, const value_type& y) const {return comp(x.first, y.first); //以 x, y 的键值调用了键值比較函数}};private:typedef rb_tree<key_type, value_type,select1st<value_type>, key_compare, Alloc> rep_type;rep_type t;  // 以红黑树表现 map
public:typedef typename rep_type::pointer pointer;typedef typename rep_type::const_pointer const_pointer;typedef typename rep_type::reference reference;typedef typename rep_type::const_reference const_reference;//set 的 iterator 定义为 const 。由于它不同意改变 set 里的值//map 的 iterator 不定义为 const，由于它虽不同意改变键值。但同意改变实值typedef typename rep_type::iterator iterator;typedef typename rep_type::const_iterator const_iterator;typedef typename rep_type::reverse_iterator reverse_iterator;typedef typename rep_type::const_reverse_iterator const_reverse_iterator;typedef typename rep_type::size_type size_type;typedef typename rep_type::difference_type difference_type;// allocation/deallocationmap() : t(Compare()) {}explicit map(const Compare& comp) : t(comp) {}// 传递 Compare() 产生的函数对象给底层的红黑树作为初始化时设定的比較函数//不同意键值反复，所以仅仅能使用 RB-tree 的 insert_unique()
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>map(InputIterator first, InputIterator last): t(Compare()) { t.insert_unique(first, last); }template <class InputIterator>map(InputIterator first, InputIterator last, const Compare& comp): t(comp) { t.insert_unique(first, last); }
#elsemap(const value_type* first, const value_type* last): t(Compare()) { t.insert_unique(first, last); }map(const value_type* first, const value_type* last, const Compare& comp): t(comp) { t.insert_unique(first, last); }map(const_iterator first, const_iterator last): t(Compare()) { t.insert_unique(first, last); }map(const_iterator first, const_iterator last, const Compare& comp): t(comp) { t.insert_unique(first, last); }
#endif /* __STL_MEMBER_TEMPLATES */map(const map<Key, T, Compare, Alloc>& x) : t(x.t) {}map<Key, T, Compare, Alloc>& operator=(const map<Key, T, Compare, Alloc>& x){t = x.t;  // 调用了底层红黑树的 operator= 函数return *this;}//下面全部的 map 操作行为，RB-tree 都已提供，所以 map 仅仅要调用就可以// accessors:key_compare key_comp() const { return t.key_comp(); }value_compare value_comp() const { return value_compare(t.key_comp()); }iterator begin() { return t.begin(); }const_iterator begin() const { return t.begin(); }iterator end() { return t.end(); }const_iterator end() const { return t.end(); }reverse_iterator rbegin() { return t.rbegin(); }const_reverse_iterator rbegin() const { return t.rbegin(); }reverse_iterator rend() { return t.rend(); }const_reverse_iterator rend() const { return t.rend(); }bool empty() const { return t.empty(); }size_type size() const { return t.size(); }size_type max_size() const { return t.max_size(); }T& operator[](const key_type& k) {return (*((insert(value_type(k, T()))).first)).second;}void swap(map<Key, T, Compare, Alloc>& x) { t.swap(x.t); }// insert/erasepair<iterator,bool> insert(const value_type& x) { return t.insert_unique(x); }iterator insert(iterator position, const value_type& x) {return t.insert_unique(position, x);}
#ifdef __STL_MEMBER_TEMPLATEStemplate <class InputIterator>void insert(InputIterator first, InputIterator last) {t.insert_unique(first, last);}
#elsevoid insert(const value_type* first, const value_type* last) {t.insert_unique(first, last);}void insert(const_iterator first, const_iterator last) {t.insert_unique(first, last);}
#endif /* __STL_MEMBER_TEMPLATES */void erase(iterator position) { t.erase(position); }size_type erase(const key_type& x) { return t.erase(x); }void erase(iterator first, iterator last) { t.erase(first, last); }void clear() { t.clear(); }// map operations:iterator find(const key_type& x) { return t.find(x); }const_iterator find(const key_type& x) const { return t.find(x); }size_type count(const key_type& x) const { return t.count(x); }iterator lower_bound(const key_type& x) {return t.lower_bound(x); }const_iterator lower_bound(const key_type& x) const {return t.lower_bound(x);}iterator upper_bound(const key_type& x) {return t.upper_bound(x); }const_iterator upper_bound(const key_type& x) const {return t.upper_bound(x);}pair<iterator,iterator> equal_range(const key_type& x) {return t.equal_range(x);}pair<const_iterator,const_iterator> equal_range(const key_type& x) const {return t.equal_range(x);}friend bool operator== __STL_NULL_TMPL_ARGS (const map&, const map&);friend bool operator< __STL_NULL_TMPL_ARGS (const map&, const map&);
};template <class Key, class T, class Compare, class Alloc>
inline bool operator==(const map<Key, T, Compare, Alloc>& x,const map<Key, T, Compare, Alloc>& y) {return x.t == y.t;
}template <class Key, class T, class Compare, class Alloc>
inline bool operator<(const map<Key, T, Compare, Alloc>& x,const map<Key, T, Compare, Alloc>& y) {return x.t < y.t;
}#ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDERtemplate <class Key, class T, class Compare, class Alloc>
inline void swap(map<Key, T, Compare, Alloc>& x,map<Key, T, Compare, Alloc>& y) {x.swap(y);
}#endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif__STL_END_NAMESPACE#endif /* __SGI_STL_INTERNAL_MAP_H */// Local Variables:
// mode:C++
// End:

queue

原文

	// 如果编译器不能根据前面模板参数推导出后面使用的默认参数类型,// 那么就需要手工指定, 本实作queue内部容器默认使用deque// 由于queue要求在队尾追加元素, 在队头获取和移除元素// 所以非常适合使用deque
#ifndef __STL_LIMITED_DEFAULT_TEMPLATEStemplate <class T, class Sequence = deque<T> >
#elsetemplate <class T, class Sequence>
#endif
class queue
{// 讲解见<stl_pair.h>中的运算符剖析friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);public:// 由于queue仅支持对队头和队尾的操作, 所以不定义STL要求的// pointer, iterator, difference_typetypedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;protected:Sequence c;   // 这个是我们实际维护的容器,底层容器public:// 这些是STL queue的标准接口, 都调用容器的成员函数进行实现// 其接口和stack实现很接近, 参考<stl_stack.h>//以下完全利用Sequence c的操作完成queue的操作bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference front() { return c.front(); }const_reference front() const { return c.front(); }reference back() { return c.back(); }const_reference back() const { return c.back(); }void push(const value_type& x) { c.push_back(x); }void pop() { c.pop_front(); }
};// 详细讲解见<stl_pair.h>
template <class T, class Sequence>
bool operator==(const queue<T, Sequence>& x, const queue<T, Sequence>& y)
{return x.c == y.c;
}template <class T, class Sequence>
bool operator<(const queue<T, Sequence>& x, const queue<T, Sequence>& y)
{return x.c < y.c;
}

stack

原文

#ifndef __SGI_STL_INTERNAL_STACK_H
#define __SGI_STL_INTERNAL_STACK_H__STL_BEGIN_NAMESPACE#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class T, class Sequence = deque<T> > //默认以 deque 为底层容器
#else
template <class T, class Sequence>
#endif
class stack {friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:typedef typename Sequence::value_type value_type;typedef typename Sequence::size_type size_type;typedef typename Sequence::reference reference;typedef typename Sequence::const_reference const_reference;
protected:Sequence c; //底层容器
public://下面全然利用 Sequence c 的操作完毕 stack 的操作bool empty() const { return c.empty(); }size_type size() const { return c.size(); }reference top() { return c.back(); }const_reference top() const { return c.back(); }//改动接口使符合 stack "前进后出"的特性void push(const value_type& x) { c.push_back(x); }void pop() { c.pop_back(); }
};template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {return x.c == y.c;
}template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {return x.c < y.c;
}
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_STACK_H */
// Local Variables:
// mode:C++
// End:

string

源码解析