【C++】STL源码仿写（一）：string

一、介绍STL源码很难懂但是我们可以从中学到许多有趣的知识。有没有可能既规避源码复杂度又可以一窥STL的各种实现呢——本系列是一个仿写STL的系列我在这个系列中力求简化的源码复杂度带你手撕一遍核心的实现。当然了无论如何简化读者必须拥有一定的C基础如果你有其他程序的经验go、java等但是对C不够了解可以先看我的五分钟带你了解C系列这个C介绍系列同样力求删繁就简让你可以快速了解必要的C特性上手编码。二、string 概览string是一种C STL当中常见的容器对象用于操作字符串支持字符串类型C风格与二进制安全字符串string包括了C风格string和二进制安全string两种我们在实现的过程中要注意这一点C风格的string包含了‘\0’并且以此为分隔符而二进制安全的string则是基于长度的。private 字段数据结构我们在实现的中string实际上是char*字符数组data_内存中为数组所分配的内存长度是capacity_字符数组的实际长度是size_。要注意我们capacity和size字段都不应该将\0记录在内。rule of fiveRAII为了实现RAII资源管理我们手撕string必须遵守Rule of five——拷贝构造函数、析构函数、拷贝赋值运算符重载、移动构造函数、移动赋值运算符重载。public 方法提供对外操作还有就是仿造STL string实现string的一些公有方法比如append()、empty()、c_str()、data()、size()这类。还有一些辅助函数和辅助字段这些到我们后面实现的时候遇到了再说。三、string 实现3.1. 构造函数以及string包含的字段上面我们分析过private字段需要包含的内容private:char*data_;//实际的字符size_t size_;//大小即实际的字符长度size_t capacity_;//容量即内存已分配的空间STL源码当中针对不同大小的字符串有堆栈内存优化默认以15字节为阈值小于15字节的存在栈上大于则存在堆上为了简化设计我们的实现中不做堆栈优化但是需要保留这个15字节的阈值。classstring{//...//static修饰的作用全体string对象共享staticconstsize_t s_min_cap_;//...};constsize_t s_min_cap_15;//外部初始化接下来我们先实现构造函数值得注意的是构造函数需要提供C风格和二进制安全两种字符串还有无参数默认为空的构造。我们的实现中因为需要兼容C风格的字符串所以内部的data_需要在末尾添加\0但capacity_和size_均不算入这个特殊的字符。我们用strlen取长度一样是没有包括这个特殊字符的。//无参数默认string():size_(0),capacity_(s_min_cap_){data_newchar[capacity_1];data[size_]\0;}//C风格构造string(constchar*str){if(!str)throwstd::invalid_argument(null pointer);size_std::strlen(str);capacity_std::max(s_min_cap_,size_);data_newchar[capacity_1];std::memcpy(data_,str,size_);data_[size_]/0;}//二进制安全字符串string(constchar*str,size_t len){if(!str)throwstd::invalid_argument(null pointer);size_len;capacity_std::max(s_min_cap_,size_);data_newchar[capacity_1];std::memcpy(data_,str,size_);data_[size_]/0;}3.2. Rule of Five 的实现rule of five的析构函数非常简单~string(){delete[]data_;}rule of five当中除了析构函数还有拷贝构造函数和移动构造函数这两种构造函数都是从另一个string获取资源但是拷贝构造是复制了一份另一个string移动构造是将另一个string转移到了自己这里偷取。这里要注意的细节是拷贝构造的参数需要用const修饰这样才可以对其他全部的string对象进行拷贝比如同样用const修饰的string、无默认构造函数的string以及右值对象而移动构造则需要用noexcept修饰这样才能确保移动语义不退化为拷贝。//拷贝构造string(conststringother):size_(other.size_),capacity_(other.capacity_){data_newchar[capacity_1];std::memcpy(data_,other.data_,size_);data_[size_]\0;}//移动构造string(stringother)noexcept:size_(other.size_),capacity_(other.capacity_),data_(other.data_){//偷取之后置空other.size_0;other.capacity_0;other.data_nullptr;}我们已经实现了rule of five的析构、拷贝构造和移动构造还剩下拷贝复制运算符和移动复制运算符的重载运算符的重载的语义是这样的this所指向的对象本身已经有一块装着data的地址了但是赋值后这块地址装的东西需要变更为其他的内容原先的data需要丢弃。//拷贝赋值运算符重载stringoperator(conststringother){if(this!other){char*new_datanewchar[other.capacity_1];delete[]data_;//丢弃std::memcpy(new_data,other.data_,other.size_);data_new_data;//现在data指向newdata了data_[other.size_]\0;size_other.size_;capacity_other.capacity_;}return*this;}//移动赋值运算符重载stringoperator(stringother)noexcept{if(this!other){delete[]data_;//丢弃size_other.size_;capacity_other.capacity_;data_other.data_;other.size_0;other.capacity_0;other.data_nullptr;}return*this;}至此rule of five所要求的已经全部实现。3.3. append() 以及其他公有方法的实现append()的实现需要考虑内存管理即扩容的问题——要求我们判断append之后新string的长度是否超出当前的容量一般我们采取的扩容策略都是直接翻倍扩容。需要实现一个reserve()方法来预先分配内存再填入数据。voidreserve(size_t new_cap){realloc_memory(new_cap);}stringappend(constchar*str){returnappend(str,std::strlen(str));}stringappend(constchar*str,size_t len){if(!str)throwstd::invalid_argument(null pointer);if(size_lencapacity_){// 扩容改capacityreserve((size_len)*2);}std::memcpy(data_size_,str,len);//将str的内容追加到data后面size_len;data_[size_]\0;return*this;}我们需要设计一个私有的辅助函数 realloc_memory() 用于修改capacity并且分配新的内存、将老的data拷贝过去并且释放老datavoidrealloc_memory(size_t new_cap){capacity_std::max(s_min_cap_,new_cap);//最小是15字节char*new_datanewchar[capacity_1];if(size_0)std::memcpy(new_data,data_,size_);//把老数据拷贝过来delete[]data_;//释放老数据data_new_data;data_[size_]\0;capacity_new_cap;//不要忘记修改capacity}还有一些公有接口实现很简单值得一提的第一个const修饰是为了避免外部通过this指针修改内部数据第二个const修饰是为了防止this指向被修改。constchar*c_str()constnoexcept{returndata_;}constchar*data()constnoexcept{returndata_;}size_tsize()constnoexcept{returnsize_;}size_tcapacity()constnoexcept{returncapacity_;}boolempty()constnoexcept{returnsize_0;}