当前位置 博文首页 > RandyLambert的博客：C++STL库String类实现
前言：按照源码中String类的设计方式实现简单的写了一个myString，参考C++官网中的标准stringAPI完成几乎所有的String类的方法，尽量与源码实现风格类似，有部分没实现有的功能之间相似度较高，重复工作意义不大就没写，有的是没办法写。
亲自在我写的数据结构课设哈弗曼树中使用，没有出现特殊问题，自己测试也没有出问题，如果哪里有错希望大家可以给我指出来。
在开始写的时候我先查阅相关资料和源码，对与String的扩容，我发现在源码中String的实现里，它预先会有一个16字节的在栈区的缓冲区，如果你的String对象不到16字节，则不会申请堆区内存使用这部分栈区内存，在所占内存较小的情况下，直接使用栈区内存的会增强运行效率，提高CPU cache命中率，而当你使用的string类占据内存过大时，据我查我的系统（Deepin 15.10.1），默认栈内存只开辟8192KB。
如果String类对象所占内存过大，很有可能程序直接爆栈，所以，在字符串内存高于16字节时，会开辟堆区内存，在源码中，为了节省空间，在这里使用了一个联合体，下面是该联合体结构。
我自己模拟的结构
enum
{
BUF_LEN = 16
};
union _Bxty {
char _Buf[BUF_LEN];
char *_ptr;
} _Bx;
在扩容的时候，我采用一种二倍扩容的方法，我判断字符串占满以申请的空间，我会使用c语言库函数的realloc函数申请一块之前容量两倍的空间，由于在realloc在实现的时候是如果在你当时字符串后面有足够的内存，则直接扩容，如果没有，则在内存足够大的地方申请够内存，然后将数据复制到新内存，然后在free掉老内存，这样处理的效率比较高，既不会经常分配新内存，也不会因为分配内存的占据过多消耗，当时学长说可以自己写一个内存池来处理，我赶着写课设也就没去实现。
这是函数实现
inline void myString::rrsize(size_t x)
{
if (ssize < x)
_Bx._ptr = (char *)realloc(_Bx._ptr, x * 2);
}
这里我没有想到很好的解决方案，就很蠢的将字符一个一个读入到临时字符ch中，每次读一个判断是不是’\n’结束符，如果是就结束，返回，如果不是继续读，我的getline也是这样实现的，感觉效率并不高。
下面是代码实现
std::istream &operator>>(std::istream &in, myString &str)
{
char ch;
/* size_t oldSize = str.size(); */
bool hasPrevBlank = false;
while(in.get(ch))
if(isblank(ch) || ch == '\n'){
hasPrevBlank = true;
}
else
break;
in.putback(ch);
str.clear();
while (in.get(ch)){
if (ch != EOF && !isblank(ch) && ch != '\n'){
str+=ch;
}
else
break;
}
return in;
}
std::istream& getline(std::istream& in, myString& str, char delim){
char ch;
str.clear();
while (in.get(ch)){
if (ch == delim)
break;
else
str+=ch;
}
return in;
}
这里我写了两个find函数的实现，其中一个find()函数是直接调用c库函数strstr()，一个是手写KMP算法的fastfind()，听说c++源代码的find函数是使用的BF算法…我个人认为可能是感觉kmp算法还需要申请一段额外空间给next()数组，所以就没有使用，但是我也没具体查真是原因。
代码实现如下
fastfind
const char *myString::getnext(const char *w)
{
int wlen = strlen(w);
char *next1 = new char[wlen + 1];
int j = 0, k = -1;
next1[0] = -1;
while (j < wlen)
{
if (k == -1 || w[k] == w[j])
{
++k;
++j;
next1[j] = k;
}
else
{
k = next1[k];
}
}
return next1;
}
const char *myString::fastfind(const myString &w)
{
int tlen = w.ssize;
const char *next1 = getnext(w.c_str());
int i = 0, j = 0;
while (j < tlen)
{
if (i == -1 || w[i] == at(j))
{
i++;
j++;
}
else
{
i = next1[i];
}
}
if (next1 != NULL)
{
delete[] next1;
}
if (j == tlen)
{
return (char *)&at(i - j);
}
else
{
return NULL;
}
}
find
const char *myString::find(const myString &w) const
{
return strstr(c_str(), w.c_str());
}
因为完整迭代器的实现实在是过于复杂，因此实现了一个比较小的模板类，里面有一套接口是重载了一些比较基础的符号，由于std::string的迭代器属于随机迭代器（Random Access Iterator），我是在写自己的myString，但是由于在写迭代器的过程中，由于很多地方需要判断操作是否合适，我简单写了一个异常处理捕捉到异常时返回一个字符串。
bool operator>=(const iTerator<value_type> &rhs)
{
try
{
if (it != rhs.it)
{
throw string("迭代器不同，>=无法比较");
}
else
{
return (index >= rhs.index);
}
}
catch (string tp)
{
std::cerr << tp << std::endl;
}
}
iTerator.hpp
#ifndef ITERATOR_HPP
#define ITERATOR_HPP
#include <iostream>
template <typename T>
class iTerator
{
public:
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T *pointer;
typedef T &reference;
iTerator():it(nullptr),index(0) {}
iTerator(const value_type *sp):it(sp),index(0) {}
iTerator(const iTerator<value_type> &rhs):it(rhs.it),index(rhs.index){}
iTerator(const value_type *sp, int n):it(sp),index(n) {}
~iTerator() { it = NULL; }
char operator*(){return *(it->data() + index);}
iTerator<value_type> operator++(int)
{
iTerator<value_type> copy(*this);
operator++();
return copy;
}
iTerator<value_type> &operator++()
{
try
{
if (it == NULL)
{
throw "迭代器未初始化";
}
else
{
index++;
if (index > it->size())
it = NULL;
}
}
catch (const char * tp)
{
std::cerr << tp << std::endl;
}
return *
