STL讲解——模拟实现string

STL讲解——模拟实现string

经典的string类问题

大厂在面试中，面试官总喜欢让学生自己来模拟实现string类，最主要是实现string类的增、删、查、改、构造、拷贝构造、赋值运算符重载以及析构函数。大家看下自己可不可以写一个string类？

class string
{
public:string(const char* str = ""){// 构造string类对象时，如果传递nullptr指针，认为程序非法，此处断言下if(nullptr == str){assert(false);return;}_str = new char[strlen(str) + 1];strcpy(_str, str);}~string(){if(_str){delete[] _str;_str = nullptr;}}private:char* _str;
};

大家肯定会想想我刚刚这样设计一个string类吧？可是你不觉得少了好多东西吗？

缺少什么呢：
1.缺少拷贝构造、赋值构造函数（虽然可以默认生成，但是都是浅拷贝，
这种开辟空间的类肯定是不行的，析构函数会多次析构同一片区域）。
2.增删查改一个都没有。
3.析构函数需要自己编写。
4.iterator和re_iterator也没有编写（还有const形式的）。

仔细讲解一下为什么浅拷贝会引起报错：

就是说浅拷贝是：有个同学的抄你作业，把你的名字都给抄上了，这肯定有问题呀，一个班有两个你，老师一定要批评叫你家长呢！回到编译器方面，一个地址被释放一次变为空，可是还要再释放一次（该地址就变成了野指针了）释放野指针肯定会报错呀。（free（nullptr）是没问题的哦，但是释放野指针就会报错了）

浅拷贝

浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共
享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为
还有效，所以 当继续对资源进项操作时，就会发生发生了访问违规。要解决浅拷贝问题，C++中引入了深拷
贝。

深拷贝

如果一个类中涉及到资源的管理，其拷贝构造函数、赋值运算符重载以及析构函数必须要显式给出。一般情
况都是按照深拷贝方式提供。

也就是说我单独开一个空间，把我要复制的内容都复制过来，复制到了一个新空间（容器）中，等于这两个除了里面的内容一样，但是空间地址不一样了。

开始写正确的string类

先写一个命名空间，把自己设计的类放到你自己写的命名空间中，防止你有时候和std中的string冲突了。
以后自己写代码时最好不要把std库里面的东西都释放出来，自己写东西也设计一个命名空间。

传统版本：

namespace tom
{class string{public://构造函数string(const char* str=""):_size(strlen(str)),_capacity(_size){_str=new char[_capacity+ 1];strcpy(_str, str);}/*拷贝构造*/string(const string& s):_str(new char[strlen(s._str) + 1]){strcpy(_str, s._str);}//赋值构造string& operator=(const string& s){if (this != &s){char* Str = new char[strlen(s._str) + 1];if (Str){strcpy(Str, s._str);delete[] _str;_str = Str;_size = s._size;_capacity = s._capacity;}else{cout << "赋值失败" << endl;}}}~string(){if (_str){delete[] _str;_str = NULL;}}private:char* _str;size_t _capacity;size_t _size;};

这里的构造函数最好是把size和capacity在初始化列表中就初始化了，但是呢，
开空间还在构造函数中完成，不是说不能在初始化列表中完成，而是当你没有初始化string 是传一个‘\0’,
所以给一个缺省值“”，没错不写任何东西，默认里面只有一个‘\0’。

析构函数
设计一个判断如果是空指针就不用处理了。

现代版本：

namespace tom
{class string{public:void swap(string& s){std::swap(_str, s._str);std::swap(_size, s._size);std::swap(_capacity, s._capacity);}//构造函数string(const char* str=""):_size(strlen(str)),_capacity(_size){_str=new char[_capacity+ 1];strcpy(_str, str);}/*拷贝构造*//*string(const string& s):_str(new char[strlen(s._str) + 1]){strcpy(_str, s._str);}*/string(const string& s)//现代写法:_str(nullptr),_size(0),_capacity(0){string tmp(s._str);/*this->swap(tmp);*/swap(tmp);}//赋值构造string& operator=(string s){/*delete[] _str;_str = new char[strlen(s._str) + 1];strcpy(_str, s._str);*///现代写法swap(s);return *this;}private:char* _str;size_t _capacity;size_t _size;static const size_t Npos=-1;};

swap（）
需要自己写一个string：：swap（）函数，为什么非要写一个类的swap呢，用函数库（algorithm.h)内的swap会有三次深拷贝，会降低效率。可是类内部的swap只用交换内置类型就可以了代价小很多。

然后利用传值拷贝形成临时拷贝变量，和this指针内的所有内容交换一下，由于是临时拷贝，出了作用域就会调用析构函数自动析构临时变量。太方便了！（要善于利用特性与机制）

增加关键细节

size（）

设计一个string的size（）函数 这个函数虽然很容易，但是相当重要。

//sizesize_t size()const{return _size;}

size（）和lenth（）是一样的所以就不写lenth（）了。

[ ]方括号函数重载

就和字符串，数组的随机访问一样——arr[n] 或者str[n]
其实就是传元素的引用（因为是可以修改的，这时候是不是觉得引用的设计太棒了）

//[]char& operator[](size_t pos){assert(pos < _size);return _str[pos];}char& operator[](size_t pos) const  //const版本{assert(pos < _size);return _str[pos];}

也一定要设计一个const类型。

扩容

//扩容void reserve(size_t n){if (n > _capacity){char* tmp = new char[n + 1];strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;}}void resize(size_t n, char ch = '\0'){if (n <= _size){_str[n] = '\0';_size = n;}else {if (n > _capacity){reserve(n);}memset(_str + _size, ch, n - _size);_size = n;_str[n] = '\0';}}

reserve：就是普通的扩容，但是不能初始化。
resize：可以扩容，并且初始化你想要的字符。（还可以缩容）

迭代器

namespace tom
{class string{public:typedef char* iterator;typedef const char* const_iterator;typedef char* reverse_iterator;const_iterator begin() const{return _str;}const_iterator end() const{return _str + _size;}iterator begin(){return _str;}iterator end(){return _str + _size;}reverse_iterator rbegin(){return _str + _size;}reverse_iterator rend(){return _str;}~string(){if (_str){delete[] _str;_str = NULL;}}private:char* _str;size_t _capacity;size_t _size;static const size_t Npos=-1;};
}

增、删、查、改

增加的设计

尾插
可以设计成一个尾插一个字母，在设计一个尾插一个字符串。
于是乎设计一个push_back()尾插一个字母.
设计一个append（）尾插一个字符串。
有了append（）既可以设计一个运算符重载“+=”。

void push_pack(char ch){if (_size == _capacity){reserve(_capacity==0?4:_capacity * 2);//扩容一定要写这个判断，//因为刚开始是一个空字符串的话capacity=0，//乘二还是0.}_str[_size] = ch;++_size;_str[_size] = '\0';}void append(const char* str){int len = strlen(str);if (_size + len > _capacity){reserve(_size+len);}strcpy(_str + _size, str);_size += len;}string& operator+=(const char ch){push_pack(ch);return *this;}string& operator+=(const char* str){append(str);return *this;}

这里的“+=”函数一定要重载一下（pushback（）和append（））。

删除

//删除string& erase(size_t pos=0 , size_t len=Npos){assert(pos < _size);if (len==Npos||pos+len>=_size){_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len;}return *this;}

有了erase函数就可以函数服用设计一个pop_back()函数

void pop_back(){if (_size > 0){this->erase(_size - 1, 1);}}

查找

查找一个字符还是很简单的，循环判断就可以了。

		size_t find(char ch){for (size_t i = 0; i < _size; i++){if (ch == _str[i]){return i;}}return Npos; }

还可以设计一个查找字符串。再加一个小功能，指定位置开始查找，如果不给位置，再给个缺省值也行。（缺省值pos为0）

//查询整个字符串是否存在size_t find(const char* s,size_t pos=0){const char* ptr = strstr(_str + pos, s);if(ptr==nullptr){return Npos;}return ptr - _str;}

这个返回的位置就是ptr（肯定是大于等于_str）减去_str的值。.

更改

可以插入一个字符或者一个字符串。

//插入string& insert(size_t pos, char ch){assert(pos <= _size);if (_size == _capacity){reserve(_capacity == 0 ? 4 : _capacity * 2);}size_t end = _size+1;while (end > pos){_str[end] = _str[end - 1];--end;}_str[pos] = ch;++_size;return *this;}string& insert(size_t pos, const char* s){assert(pos <= _size);size_t len = strlen(s);if (_size+len >= _capacity){reserve(_size+len);}size_t end = _size +len;while (end > pos){_str[end] = _str[end - len];--end;}//strcpy(_str + pos, s); 绝不能用，因为会把\0 也复制过去的。strncpy(_str + pos, s,len);_size+=len;return *this;}

有了这个插入函数就可以再设计一下push_back():

		void push_pack(char ch){insert(_size,ch);}void append(const char* str){insert(_size,str);}

这就简洁许多了，要学会复用。
其实学会服用，面试的时候真的可以在十分钟之内写完string类。