VS2010 std::string 源码分析

源码分析"/>

VS2010 std::string 源码分析

分配内存原理分配内存原理

union _Bxty
{	// storage for small buffer or pointer to larger one_Elem _Buf[_BUF_SIZE];_Elem *_Ptr;char _Alias[_BUF_SIZE];	// to permit aliasing
} _Bx;

这个_Bxty是一个union。当分配字符串所需内存小于_BUF_SIZE，_Buf存放我们的字符串，当然也不一定是字符串，也可以放int数组这种东西。当分配内存大于_BUF_SIZE，_Ptr由内存分配器_ALLOCATOR分配，然后存放我们的字符串。

类构成关系

typedef basic_string<char, char_traits<char>, allocator<char> > string;
template<class _Elem>struct char_traits: public _Char_traits<_Elem, long>{	// properties of a string or stream unknown element};

xmemory文件：

#define _ALLOCATOR	allocator
template<class _Ty>class _ALLOCATOR: public _Allocator_base<_Ty>{	// generic allocator for objects of class _Ty
...
}

		// TEMPLATE CLASS basic_string
template<class _Elem,class _Traits,class _Ax>class basic_string: public _String_val<_Elem, _Ax>{	// null-terminated transparent array of elements
...
}

		// TEMPLATE CLASS _String_val
template<class _Elem,class _Alloc>class _String_val: public _Container_base{	// base class for basic_string to hold data
...union _Bxty{	// storage for small buffer or pointer to larger one_Elem _Buf[_BUF_SIZE];_Elem *_Ptr;char _Alias[_BUF_SIZE];	// to permit aliasing} _Bx;size_type _Mysize;	// current length of stringsize_type _Myres;	// current storage reserved for string_Alty _Alval;	// allocator object for strings
}

typedef _Container_base12 _Container_base;
struct _CRTIMP2_PURE _Container_base12{	// store pointer to _Container_proxy
...
}

从实例构造说起

	string str5("abcdefghijklmn12345");string str("abc");str = "abcdefghijklmn12345";

	basic_string(const _Elem *_Ptr): _Mybase(){	// construct from [_Ptr, <null>)_Tidy();assign(_Ptr);}_String_val(_Alty _Al = _Alty()): _Alval(_Al){	// construct allocator from _Altypename _Alloc::template rebind<_Container_proxy>::other_Alproxy(_Alval);this->_Myproxy = _Alproxy.allocate(1);_Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());this->_Myproxy->_Mycont = this;}

上面这一大堆就是stl里面公用的那一套机制。暂且不表。

	void _Tidy(bool _Built = false,size_type _Newsize = 0){	// initialize buffer, deallocating any storageif (!_Built);else if (this->_BUF_SIZE <= this->_Myres){	// copy any leftovers to small buffer and deallocate_Elem *_Ptr = this->_Bx._Ptr;if (0 < _Newsize)_Traits::copy(this->_Bx._Buf, _Ptr, _Newsize);this->_Alval.deallocate(_Ptr, this->_Myres + 1);}this->_Myres = this->_BUF_SIZE - 1;_Eos(_Newsize);}

其实我一直在想stl里面的_Tidy函数到底干啥的。tidy这个单词有整洁的，整齐的，使整洁，使整齐，整理之意。那这里呢。看这句注释// initialize buffer, deallocating any storage 意思大概是初始化内存，这里用的buffer，即缓存，反正也是内存吧，然后释放所有的存储。来具体看看代码。_Built这参数的含义应该就是是否使用了堆内存机制，即是否使用了this->_Bx._Ptr。若是使用了，就把堆内存考到栈内存this->_Bx._Buf，再把堆内存释放掉，当然了，刚构造一个basic_string的时候，肯定还未使用堆内存机制，无论用于初始化的字符串有多长。this->_Myres是说当前保留了几个字节可以用来分配内存，当然还有一个字节用来保存0。然后把_Newsize处置0。

	_Myt& assign(const _Elem *_Ptr, size_type _Count){	// assign [_Ptr, _Ptr + _Count)if (_Inside(_Ptr))return (assign(*this, _Ptr - _Myptr(), _Count));	// substringif (_Grow(_Count)){	// make room and assign new stuff_Traits::copy(_Myptr(), _Ptr, _Count);_Eos(_Count);}return (*this);}

这里_Inside得false，后面可以讨论得true的情况。

bool _Grow(size_type _Newsize,	bool _Trim = false)
{	// ensure buffer is big enough, trim to size if _Trim is true
if (max_size() < _Newsize)//情况①：这种情况崩溃，分配字符数太大了。_Xlen();	// result too long
if (this->_Myres < _Newsize)//情况②：要分配的大于能够为字符串提供内存大小，重新分配内存_Copy(_Newsize, this->_Mysize);	// reallocate to grow
else if (_Trim && _Newsize < this->_BUF_SIZE)//情况③：砍掉不要的字符串，只有栈内存机制可行_Tidy(true,	// copy and deallocate if trimming to small string_Newsize < this->_Mysize ? _Newsize : this->_Mysize);
else if (_Newsize == 0)//情况④_Eos(0);	// new size is zero, just null terminate
return (0 < _Newsize);	// return true only if more work to do情况⑤：当然是不需要分配就够了,
//比如本来”abc”,现在”abcde”，没超过16字节，依旧栈内存机制，无需再分配内存。
}

着重讲一下情况②：

void _Copy(size_type _Newsize, size_type _Oldlen){	// copy _Oldlen elements to newly allocated buffersize_type _Newres = _Newsize | this->_ALLOC_MASK;if (max_size() < _Newres)//情况①_Newres = _Newsize;	// undo roundup if too bigelse if (this->_Myres / 2 <= _Newres / 3)//情况②;else if (this->_Myres <= max_size() - this->_Myres / 2)//情况③_Newres = this->_Myres+ this->_Myres / 2;	// grow exponentially if possibleelse//情况④_Newres = max_size();	// settle for max_size()_Elem *_Ptr;_TRY_BEGIN_Ptr = this->_Alval.allocate(_Newres + 1);_CATCH_ALL_Newres = _Newsize;	// allocation failed, undo roundup and retry_TRY_BEGIN_Ptr = this->_Alval.allocate(_Newres + 1);_CATCH_ALL_Tidy(true);	// failed again, discard storage and reraise_RERAISE;_CATCH_END_CATCH_ENDif (0 < _Oldlen)_Traits::copy(_Ptr, _Myptr(), _Oldlen);	// copy existing elements_Tidy(true);this->_Bx._Ptr = _Ptr;this->_Myres = _Newres;_Eos(_Oldlen);}

string str5("abcdefghijklmn12345");这句话会调用到上面这个函数，那么_Newsize为19，毕竟"abcdefghijklmn12345"是有19个字符。_Oldlen为0。大概有这么几种情况，会调用这个函数：

1. 刚初始化的时候，字符占字节数超过_BUF_SIZE；
2. 刚初始化，字符占字节数不超过_BUF_SIZE，后来重新赋值的字符串占字节数超过_BUF_SIZE；
3. 刚初始化，字符占字节数超过_BUF_SIZE为sizeA，后来重新赋值的字符串占字节数sizeB超过sizeA；

这个函数叫做_Copy，意思就是把之前内存字符串拷贝到现在内存处，如果之前有分配内存，比如上面情况1,2，现内存是从新分配的，现内存大小取值由上面标注四种情况，情况②④不太理解，暂时不表。反正重新分配了内存，拷贝内存，_Tidy(true)把栈内存置null。然后修改_Bx._Ptr与_Myres，然后_Eos(_Oldlen)置null，这里是_Oldlen，毕竟还没有把现字符串赋值进来。

回到assign函数。现在_Grow调用成功后，有下面两句。

_Traits::copy(_Myptr(), _Ptr, _Count);

_Eos(_Count);

这两句也简单。不过我在想，_Grow里面调用了_Copy，把之前内存拷到现内存，现在又把当前字符串赋值到现内存，那么把原先字符串拷到现内存是不是就多此一举了。

其他一些组件

迭代器

			// TEMPLATE CLASS _String_const_iterator
template<class _Elem,class _Traits,class _Alloc>class _String_const_iterator: public _Iterator012<random_access_iterator_tag,typename _Alloc::value_type,typename _Alloc::difference_type,typename _Alloc::const_pointer,typename _Alloc::const_reference,_Iterator_base>{	// iterator for nonmutable string
public:typedef _String_const_iterator<_Elem, _Traits, _Alloc> _Myiter;typedef basic_string<_Elem, _Traits, _Alloc> _Mystr;typedef random_access_iterator_tag iterator_category;typedef typename _Alloc::value_type value_type;typedef typename _Alloc::difference_type difference_type;typedef typename _Alloc::const_pointer pointer;typedef typename _Alloc::const_reference reference;_String_const_iterator(pointer _Parg, const _Container_base *_Pstring){	// construct with pointer _Pargthis->_Adopt(_Pstring);this->_Ptr = _Parg;}
...//这里无非一些 operator*,->,++,--之类的东西。
pointer _Ptr;	// pointer to element in string
};
template<class _Elem,class _Traits,class _Alloc>class _String_iterator: public _String_const_iterator<_Elem, _Traits, _Alloc>{	// iterator for mutable string
...
}

字符特性Traits

iosfwd文件：

template<class _Elem,class _Int_type>struct _Char_traits{	// properties of a string or stream element
...//这里面一些compare，length，copy，find，move函数
}// TEMPLATE STRUCT char_traits
template<class _Elem>struct char_traits: public _Char_traits<_Elem, long>{	// properties of a string or stream unknown element
...};
template<>struct char_traits<wchar_t>{	// properties of a string or stream wchar_t element
...
}
template<> struct char_traits<unsigned short>{	// properties of a string or stream unsigned short element
...
}
template<> struct char_traits<char>{	// properties of a string or stream char element
...
}

其他一些重要函数

_Elem *_Myptr()
{	// determine current pointer to buffer for mutable string
return (this->_BUF_SIZE <= this->_Myres ? this->_Bx._Ptr: this->_Bx._Buf);
}

这个函数就是返回到底是栈内存还是堆内存。

_Myt& append(const _Myt& _Right,size_type _Roff,size_type _Count)//_Roff从第几个字符开始复制
{	// append _Right [_Roff, _Roff + _Count)if (_Right.size() < _Roff)			//一共三个字符，你却从第四个开始复制，over_Xran();	// _Roff off endsize_type _Num = _Right.size() - _Roff;if (_Num < _Count)_Count = _Num;	// trim _Count to sizeif (npos - this->_Mysize <= _Count)//npos为(size_type)(-1),判断是否复制后超过最大字符数_Xlen();	// result too longif (0 < _Count && _Grow(_Num = this->_Mysize + _Count))//增长内存(_Grow里面判断是否真的需要增){	// make room and append new stuff	//把_Right字符串复制到本字符串尾端_Traits::copy(_Myptr() + this->_Mysize,_Right._Myptr() + _Roff, _Count);_Eos(_Num);}return (*this);
}

  #define _STRING_ITERATOR(ptr)			iterator(ptr, this)iterator begin(){	// return iterator for beginning of mutable sequencereturn (_STRING_ITERATOR(_Myptr()));}

返回一个_String_iterator变量。

	const _Elem *c_str() const{	// return pointer to null-terminated nonmutable arrayreturn (_Myptr());}

返回保存字符串的内存的地址，栈内存或堆内存。

	void clear(){	// erase all_Eos(0);}

这里并没有释放内存，只是把第一个字符置null。

	_Myt& erase(size_type _Off = 0,size_type _Count = npos){	// erase elements [_Off, _Off + _Count)if (this->_Mysize < _Off)_Xran();	// _Off off endif (this->_Mysize - _Off < _Count)_Count = this->_Mysize - _Off;	// trim _Countif (0 < _Count){	// move elements down_Traits::move(_Myptr() + _Off, _Myptr() + _Off + _Count,this->_Mysize - _Off - _Count);size_type _Newsize = this->_Mysize - _Count;_Eos(_Newsize);}return (*this);}