网游之转生,发明家的故事,布温巴之魂任务怎么做
gcc 8.2提供了两个版本的std::string:一个是基于copy on write的,另一个直接字符串拷贝的。前者针对c++11以前的,那时候没有移动构造,一切以效率为先,需要使用cow这种奇技淫巧。后者针对c++11,也就是_glibcxx_use_cxx11_abi
宏被设置为非零时会被用到,并没有cow的功能,更简单,用户可以在必要时使用移动构造。如果不使用移动构造,字符串的频繁拷贝将会是异常灾难,这一点,在我的项目中已经踩过坑。
本文主要研究modern c++中的string实现,因为使用c++11以后的标准都使用它。
数据的组织很简单,如果字符串长度不超过15字节(加上后缀0一共16字节),则在栈上保存,否则会在堆上分配内存。
// use empty-base optimization: http://www.cantrip.org/emptyopt.html struct _alloc_hider : allocator_type // todo check __is_final { #if __cplusplus < 201103l _alloc_hider(pointer __dat, const _alloc& __a = _alloc()) : allocator_type(__a), _m_p(__dat) { } #else _alloc_hider(pointer __dat, const _alloc& __a) : allocator_type(__a), _m_p(__dat) { } _alloc_hider(pointer __dat, _alloc&& __a = _alloc()) : allocator_type(std::move(__a)), _m_p(__dat) { } #endif pointer _m_p; // the actual data. }; _alloc_hider _m_dataplus; ////数据指针,指向本地或者堆内存 size_type _m_string_length; ////实际长度,如果大于_s_local_capacity则是堆内存,否则,是栈内存 enum { _s_local_capacity = 15 / sizeof(_chart) }; ////注意这是union,16字节的栈内存和整个堆的容量(capacity)共用一块存储 union { _chart _m_local_buf[_s_local_capacity + 1]; size_type _m_allocated_capacity; };
里面那个union挺有意思,如果_m_string_length>=_s_local_capacity,那么_m_allocated_capacity保存了整块缓冲区的大小(注意不是字符串的大小);如果_m_string_length<_s_local_capacity则_m_dataplus._m_p指针指向_m_local_buf这块栈上内存区。union的特性是全部元素共用一块空间,根据程序的语义只使用其中一个变量,在这里_m_local_buf有效的时候_m_allocated_capacity无效,反之亦然,巧妙地运用空间,减少内存浪费。
_m_local_buf
,包括以下函数:
basic_string()
basic_string(const _alloc& __a)
_m_construct()
构造对象,也就是把字符串拷贝一个(而不是增加引用计数);关于_m_construct()
的细节,在下面会分析。包括以下函数:basic_string(const basic_string& __str)
:拷贝__str的完整字符串;basic_string(const basic_string& __str, const _alloc& __a)
:同上,指定构造器;basic_string(const basic_string& __str, size_type __pos, const _alloc& __a = _alloc())
:拷贝__str从__pos位置到末尾的所有字符;basic_string(const basic_string& __str, size_type __pos, size_type __n)
:拷贝__str从__pos位置开始的n个字符(或者到末尾);basic_string(const basic_string& __str, size_type __pos, size_type __n, const _alloc& __a)
:同上,指定构造器;basic_string(const _chart* __s, const _alloc& __a = _alloc())
:拷贝__s的全部字符串,构造时会计算__s的长度,使用char_traits<char>::length()
内联函数;basic_string(const _chart* __s, size_type __n, const _alloc& __a = _alloc())
:拷贝__s字符串的前__n个字符,不检测越界问题,留给调用方保证;basic_string(const _tp& __t, size_type __pos, size_type __n, const _alloc& __a = _alloc())
:这个比上面两个构造函数更加宽泛,可以是任意数据指针,编译器会对数据能否正确转换进行检测(warnning或者error);basic_string(initializer_list<_chart> __l, const _alloc& __a = _alloc())
:使用初始化列表构造;basic_string(size_type __n, _chart __c, const _alloc& __a = _alloc())
:以n个相同的字符填充缓冲区:调用_m_construct()
初始化缓冲区并填充字符。basic_string(basic_string&& __str)
basic_string(basic_string&& __str, const _alloc& __a)
_m_construct()
,根据迭代器的类型进行分类处理:
basic_string(_inputiterator __beg, _inputiterator __end, const _alloc& __a = _alloc())
:把迭代器区间内的数据(允许不是char/wchar_t,只要编译器不抱怨);basic_string(const _tp& __t, const _alloc& __a = _alloc())
:需要__t是std::string_view类型,取整个std::string_view字符串构建std::string;basic_string(const _tp& __t, size_type __pos, size_type __n, const _alloc& __a = _alloc())
:需要__t是std::string_view类型,并且取它的字符串一部分构建新的字符串,调用上面的构造函数完成构造。basic_string(__sv_wrapper __svw, const _alloc& __a)
:允许某个类型,如果可以转换成std::string_view,则使用此构造函数,类似于basic_string(sv.data(), sv.size(), alloc)
。assign()
函数,进而调用_m_assign()
系列函数,这部分下面会详细分析
operator=(const basic_string& __str)
:代码相对比较复杂,其实就是字符串拷贝,没有cow。operator=(const _chart* __s)
:同上operator=(_chart __c)
:只插入一个字符上面大部分版本的构造函数都是给定一个起始区间,调用_m_construct(_initerator __beg, _initerator __end)
函数。下面分析这个函数的来龙去脉。
_m_construct(_initerator __beg, _initerator __end)
:根据std::__is_integer<_initerator>::__type
分析这个“迭代器”是否数值类型;
basic_string(size_type __n, _chart __c)
这一组的函数,那么就调用_m_construct_aux(_integer __beg, _integer __end, std::__true_type)
去生成,最终调用_m_construct(size_type __req, _chart __c)
函数;_m_construct_aux(_integer __beg, _integer __end, std::__true_type)
,继而调用_m_construct(_initerator __beg, _initerator __end)
函数;_m_construct()函数执行字符串的实际构造操作。它按照迭代器/参数的类型,有两种实现:
_m_construct(size_type __req, _chart __c)
:实现的算法很简单,申请一段__req的内存空间(如果小于15字节则直接写在栈上),并拷贝__req个__c字符;_m_construct(_initerator __beg, _initerator __end, std::forward_iterator_tag)
:只有当迭代器类型是forward_iterator
或者比它更宽的迭代器时使用,它会根据迭代器之间的长度来确定字符串的长度,并逐字符拷贝。关于迭代器的“更宽”,可以参考。_m_construct(_initerator __beg, _initerator __end, std::input_iterator_tag)
:用于input_iterator
迭代器,如输入迭代器等。这个构造比较低效,每次输入一个字符,会检测是否达到缓冲区的末尾,如果是,则把缓冲区的大小加1,重新分配空间并拷贝字符串。realloc()
函数。如果使用realloc()
函数,有可能在扩大内存的同时,不需要拷贝字符串(也就是原来分配的内存区域末尾还有足够的字符串)。c++很单纯地分配一块新内存,再把就内存拷贝过去。这一点在效率上会比较低下。个人认为解决办法是,使用std::dequebasic_string(_inputiterator __beg, _inputiterator __end)
构造函数生成std::stringstd::input_iterator
的构造,它每次重新分配内存只会分配“刚刚适合需要的大小”,而不会如std::vector那样分配2倍,所以将会有频繁分配内存和拷贝的操作。解决的办法还是用std::deque
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论