C++中string的实现原理
C++中string的实现原理
背景
当我刚开始学习C++，对C还是有⼀部分的了解，所以以C的思维去学C++，导致我很长⼀段时间的学习都处于⼀个懵逼的状态，C++的各种特性，标准库，模板还有版本的迭代，简直是欲仙欲死。
后来在论坛中就有热⼼的朋友们出招了：你得放弃C的思维去学C++！！嗯，说得好有道理，这就去试试！！
但是我⼜发现⼀个问题，不⽤C的思维学C++，难道我以撸铁(博主业余喜欢健⾝)的思维来学C++？⼜在论坛中⼀问，原来是要⽤⾯向对象的思维来学习。
问题依然没有解决，因为博主压根就不知道⾯向对象的思维是个啥思维？难道是学C++还要先个对象？那就没时间学习了！！要知道有对象的程序员处于程序员鄙视链的顶端。
结果问来问去，啥思维都没搞懂，反倒是浪费了时间，回过头来才发现，学习这东西，还是得动⼿动脑去学，思维转换也不是个拨码开关，看得写得多了，⾃然会有⼀些⼼得，在不断的积累中量变成为质变，⽽别⼈给的建议往往只能是过眼云烟，当时觉得很有道理，结果回头就忘.
蛋扯得有点长了，我们来回归正题：
C++中string类的实现原理简述
请注意简述这两个字，因为博主⽬前依旧处于C++初级学习阶段，对C++的理解仍不够透彻，对于底层的原理尤其是内存实现部分还在进⾏艰难的研究，不敢妄称详解。但是博主可以保证的是，所有的内容都是经过上机实验的，可能不全⾯，但是已经是⾮常努⼒地保证正确性。
string
定义
string的内容其实就是C中的字符串，在C中是char*类型，⽽在C++中变成了string类型，定义是这样的：
C:
char *str="downey";
C++:
string str="downey";
string str("downey");
操作
对于C中字符串的操作，其实就是对str指针的操作，增删改查都是在内存的基础上进⾏操作，⾮常⾼的⾃由度，但是对新⼿并不友好，因为⼀旦操作失误，将会引起内存上的问题，⽽内存上的问题往往是很难进⾏debug的。
⽽在C++中，string类提供很多內建⽅法，可以⽆害地进⾏增删改查，基本覆盖⽤户的所有操作，⽤户并不需要了解底层实现，拿来直接⽤，也不会造成内存的问题，对初、中级⽔平程序员⾮常友好，⽽且还有⼀些亮点(仅列出⼀些博主认为主要的亮点，欢迎指正与补充)：
⽀持运算符，'+'运算符可以直接拼接字符串，以及⼀些內建的查替换⽅法，使⽤⾮常⽅便
迭代器的发明使得数据与操作分离，对程序的移植、接⼝扩展和维护都是很有优势的。
⽀持变长。
关于第⼀点以及其他string⽅法，其实就是封装的问题，在C标准库中也能到相应的函数，但是由于关联性不强，强⼤的C标准库经常被程序员们忽略。
⽽第⼆点中，迭代器其实也可以看成是⼀种泛型指针，由类本⾝来实现，但是在C中实现泛型是⽐较⿇烦的，很多程序员对void* 以及其转换简直是恨之⼊⾻，C++在这⼀点上算是⼀个突破。
⽽第三点中的C++变长特性，这个特性相对于C⽽⾔是个巨⼤的优势，在C中如果直接定义⼀个字符串如：
char *str="downey";
这个字符串默认被编译器识别为const类型，也就⽆法进⾏写操作。如果要进⾏写操作，我们就得将其定义成数组：
char str[]="downey";
但是这个数组的长度是固定的，想删除可以，但是如果想增加⼀个字符，就会发⽣数组越界的情况，导致内存问题，好像也很难到⼀个好的办法来⽤C语⾔来实现这个问题。
C++是如何实现字符串变长的
我们可以继续以沿着C语⾔的思路来思考怎么样实现变长数组：
V1.0
实现
既然数组是固定的⽆法扩展，那么我们就⽤动态申请内存的⽅式来存字符串，在字符串定义的时候申请⼀⽚内存空间，在需要增加字符的时候再申请内存，放置增加的那⼀部分。
问题
这样有⼀个弊端，内存动态申请是个⼗分费时的操作，这样频繁地申请刚好合适的⼤⼩在空间上能够达到最优，但是在执⾏效率上是⼀个⾮常⼤的损失，在⽬前普遍接受的时间复杂度重要性>空间复杂度重要性的软件环境下，这个是完全不能接受的。
V1.1
实现
在V1.0上做改版：在第⼀次申请的时候就申请⼀块⼤⼀些的内存，⽐如初始化的字符串长度为10，那
我就申请⼀块⼤⼩为20的内存，如果⽤完了就⼜申请⼀块⽐⽬前需要的空间⼤⼀些的内存空间，这种情况下，会浪费⼀部分空间，只要策略得当，浪费的空间是可以接受的。
问题
但是仔细⼀想，这样⼜有问题了，经过多次字符串变长之后，⼀个字符串中的内容很可能对应好⼏个分段的存储地址，这样会给底层实现带来更⼤的难度以及更多的操作时间，⽐如遍历、删除、内存回收等操作。
V1.2
实现
既然上述的版本都存在内存不连续的问题，那我就在V1.1的版本上做相应改进，让它实现内存连续。具体的实现⽅法为：
还是在第⼀次申请的时候就申请⼀块⼤⼀些的内存，⽐如初始化的字符串长度为10，那我就申请⼀块⼤⼩为20的内存，如果这块内存⽤完了⽽字符串还需要扩展，那我就去⼀块更⼤的内存，能够同时容纳需要的内存空间，⽽且还有⼀些余量，直接将字符串整体迁移到新内存空间中，放弃原来那部分内存空间，这样就实现了字符串的内存连续。
问题
仔细⼀想，这样⼜存在⼀个问题，如果在操作之前未扩展的字符串时，我使⽤的是指针访问，那在字符串扩展之后，字符串存储地址已经改变了，那这个指针就成了⽆效指针，再次操作它甚⾄可能导致严重的内存问题。
V1.3
博主智商余额已经不⾜，想不出更好的实现⽅法，欢迎各路⼤神补充....
STL的string实现
事实上，在STL的实现中，⽤的就是上述的V1.2版本，在中，明确指出base_string类型是连续存储的,⽽string继承⾃base_string类型，实现也是⼀样的，尽管确实存在指针失效的问题，但是在不到理想的解决⽅案时，如果没有⽐它更好的，那么它就是最好的。
string的实现细节以及⽰例
注：所有⽰例代码运⾏环境为：平台：ubuntu 16.04，编译⼯具链版本：gcc 5.4.0
上⾯既然说了string类的内存是连续的，⼝说⽆凭，当然是要上代码才有说服⼒：
char *p=NULL;
string str="(downey)";
p=&str[0];
/*如果直接输出p，cout⽅法会识别p为指向字符串的指针，将p指向的字符串输出，转换成void*类之后就会输出地址值*/
cout<<"addr of p is "<<(void*)p<<endl;
cout<<"str= ";
for(int i=0;i<str.size();i++)
cout<<*p++;
cout<<endl;
str+="+(abcdefghijklmnopqrstuvwxyz)";
p=&str[0];
cout<<"addr of p is "<<(void*)p<<endl;
cout<<"str= ";
for(int i=0;i<str.size();i++)
cout<<*p++;
cout<<endl;
c++string类型执⾏结果：
addr of p is 0x7ffd330eeb40
str= (downey)
addr of p is 0x237b030
str= (downey)+(abcdefghijklmnopqrstuvwxyz)
上述⽰例的内容为，将字符指针p赋值为str的⾸地址，然后⽤指针⾃增的⽅式遍历整个类内字符串，同时打印出p的地址，这⾥⾯还有⼀次字符串的扩展，从这⾥我们可以看出两点：
在字符串扩展前后，将str[0]的地址赋值给p，p都能以地址⾃增的⽅式访问整个字符串，表明string类的存储为连续的。
在字符串的扩展前后，p的地址出现了变化，表明string类在扩展之后改变了地址，⽽存储空间是连续的，可以推出整个str都进⾏了地址迁移。
问题到这⾥并没有结束，因为我们还需要弄清楚string在的内存分配策略，我们可以⽤string內建⽅法 capacity()⽅法来获取⽬前string对象申请的内存⼤⼩，继续看下列代码：
string str;
cout<<str.capacity()<<endl;
str.append(16,'c');
cout<<str.capacity()<<endl;
str.append(15,'c');
cout<<str.capacity()<<endl;
在程序中，添加字符串，让其⼀次⼀次超出原始内存容量，输出结果：
15
30
60
120
看起来像是以 2^n*15的⽅式增长，我们再来试试：
string str;
cout<<str.capacity()<<endl;
str.append(10,'c');
cout<<str.capacity()<<endl;
str.append(20,'c');
cout<<str.capacity()<<endl;
str.append(40,'c');
cout<<str.capacity()<<endl;
在这次扩展中，并没有每次都超出原始内存容量，结果：
15
15
30
70
跟上述结果不⼀致，事实证明，string的内存扩展并⾮遵循某个单⼀规则，博主的猜测应该是遵循某种扩展算法，根据之前的应⽤情况采取弹性的策略(博主⽬前还没搞懂具体分配算法....)。
但是可以确认的是，每个初始化长度不超过15的字符串初始容量是15.
同时我们可以通过reserve()⽅法来修改内存分配容量的⼤⼩，如果我们提前知道需要操作的字符串⼤⼩，例如⼀个⼏K的⽂件，我们可以直接这样写：
std::ifstream file ("",std::ios::in|std::ios::ate);
if (file) {
std::ifstream::streampos filesize = llg();
如果不直接指定，⼀个⼏K的⽂件肯定会触发好⼏次内存重新分配，导致时间和空间上的浪费。
从字符串层⾯看C和C++⽐较(仅从字符串层⾯！)
在这⾥博主⽃胆从C++ string类和C char*字符串层⾯对⽐C和C++，如果你看了上⾯博主的分析，就会觉得不管是从易⽤性，容错性还是开发效率上C++都要优于C，但是这有个前提，这个前提就是对初、中级程序员⽽⾔，因为对初、中级程序员⽽⾔，标准化意味着⾼效，⽽灵活性反⽽像是个累赘。
其实在上⾯的string例⼦中，不管string实例化的对象中有没有字符串，字符串的长度都是15，这对硬件资源来说⽆疑是⼀种浪费，(当然
C++有其他策略来弥补，⽐如写时复制，但是也⽆法避免浪费)，如果能精确地控制每块内存的应⽤，可以将硬件资源发挥到极致，同时封装本⾝也将带来资源的浪费，同时C++很多操作中，伴随着⼀些隐形的临时变量，这些临时变量的构造和析构也是⽐较费时的。
但是很多盆友就要说了，将硬件资源⽤到极致必然带来的是开发难度的⼤幅上升，是的，但是如果⽤C，我们⾄少有选择！
在⼀般的开发过程中，我们⼀般会从开发效率、执⾏效率、硬件资源这⼏个层⾯来考虑软件的实现，在实际的项⽬中，很可能会对其中的⼀项作严格要求，⽐如硬件资源，⽐如执⾏效率，⼜或者开发效率，C语⾔⾄少提供了这么⼀种可能性，以牺牲其他性能为代价来将⼀种性能做到极致。
⽽对于已经标准化的C++⽽⾔，便失去了这种柔韧性，虽然说C++是C的超集，但是就如同我在⽂章开头说的⼀样，两种语⾔的设计⽬的有根本上的区别，或者说思维的不⼀致注定了C++不会像C那样进⾏开发。
其实说到这⾥，C和C++并没有⾼下之分，语⾔本⾝是⼯具，⼯具只有合适不合适，没有绝对的谁⽐谁好，如果有，那么其中⼀个肯定会被马上淘汰，但是就⽬前⽽⾔，C和C++的存在证明了这两种语⾔各有各的应⽤场合。
(这⾥好像跑题了？？)
好了，关于C++标准库string实现的讨论就到此为⽌啦，如果朋友们对于这个有什么疑问或者发现有⽂章中有什么错误，欢迎留⾔
原创博客，转载请注明出处！
祝各位早⽇实现项⽬丛中过，bug不沾⾝.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。