目录
kmp详解可移步至:KMP算法详解(一眼看穿next[ ]数组)
准备
为了自己创建的string类不和库当中的发生冲突,可以自己创建一个命名空间
namespace test { }
string需要三个参数,一个存放字符串(char* _str),一个存放大小(size_t _size),一个存放容量(size_t _capacity)
//自定义一个命名空间,防止与stl中的string同 namespace test { class string { public: //构造函数 string() { } //析构函数 private: char* _str; size_t _size; size_t _capacity; }; }
构造函数
构造函数需要做的就是对成员进行初始化,由于字符串是常量,类型为const char*,所以接收的时候也需要用const char*来接收,但这里不能简单的直接将str给_str,因为str是存放在常量区的,如果直接将_str=str,会将str在常量区的地址也拷贝过去,会导致之后无法修改string的内容,所以需要给_str分配一个空间,然后再将str的值全部拷贝过去,在分配空间的时候要多分配一个空间给'\0'
string(const char* str) :_size(strlen(str)) ,_capacity(_size) { _str = new char[_capacity + 1]; strcpy(_str, str); }
为了方便测试函数是否正确,提供一个c_str函数来获取对象中的字符串
c_str
官方解释:
函数类型是const char*因为这只是一个提取对象内容的函数,为了防止权限放大,因为某些原因导致指针被修改就麻烦大了
返回一个指针包括'\0'的字符串
const char* c_str() const { //添加const防止修改指针的内容 return _str; }
测试一下构造函数,传一个hello world
通过监视窗口可以看到是拷贝成功了的
运行结果:
再提供两个接口来获取size和capacity
size
官方解释:
首先返回类型为size_t,大小肯定不会为负数,用const修饰
返回的是字符串的实际长度,不包括'\0',也不是容量的大小
size_t size() const { return _size; }
capacity
官方解释:
和size差不多,返回的容量不包括'\0'
size_t capacity() const { return _capacity; }
运行结果:
运行结果是正确的,但这里存在两个构造函数,第一种是默认的
string() { }
第二种就是我们自主实现的,其实这里可以简化一下,将两种合并为一种,在传的字符串为空的时候就会调用第一种构造函数,空的话字符串内容就是'\0',_capacity=0,_size=0,可以直接将第二种构造函数的参数给个缺省值,如果不填就默认是""或者"\0",这两种是等效的,第一种也是直接填一个'\0'上去,所以构造函数也可以写成:
string(const char* str="") :_size(strlen(str)) ,_capacity(_size) { _str = new char[_capacity + 1]; strcpy(_str, str); }
或者:
string(const char* str="\0") :_size(strlen(str)) ,_capacity(_size) { _str = new char[_capacity + 1]; strcpy(_str, str); }
析构函数
成员变量中_str是动态开辟出来的,所以需要对内存进行delete释放,释放后再将其指向nullptr空
~string() { delete[] _str; _str = nullptr; _size = 0; _capacity = 0; }
拷贝构造
思路1:
对_str重新分配空间,然后利用strcpy函数来讲str中的字符串全部拷贝到_str中
string(const string& str) :_size(str._size) ,_capacity(str._capacity) { _str = new char[_capacity + 1]; strcpy(_str, str._str); }
测试:
运行结果:
思路2:
创建一个临时变量tmp来拷贝str,再通过swap函数来交换,因为tmp是临时变量,出了函数作用域就会调用析构函数来销毁tmp,所以在tmp和str交换之后,因为str的原地址需要被销毁,这里就不需要手动销毁了,我们将str的地址给到了tmp,出了函数作用域之后调用析构函数就将其销毁了。
string(const string& str) :_str(nullptr) ,_size(0) ,_capacity(0) { string tmp(str._str); swap(tmp); }
swap
全局的那个swap对于内置类型交换很快,但对于自定义类型会比较慢了,它会掉用三次构造函数,所以可以自己实现一个swap函数
void swap(string& str) { string tmp(str._str); std::swap(_str, tmp._str); std::swap(_size, tmp._size); std::swap(_capacity, tmp._capacity); }
operator[ ]
对操作符[ ]进行重载,可以通过[ ]来获取字符
官方解释:
char& operator[](size_t pos) { assert(pos < _size); return _str[pos]; }
const char& operator[](size_t pos) const { assert(pos < _size); return _str[pos]; }
迭代器iterator的实现
iterator实质上就是一个类似指针的东西但又不是指针,但是在string类中可以将其当作指针,所以对iterator进行重命名即可
typedef char* iterator;
begin
官方解释:
返回第一个字符的指针
iterator begin() { return _str; }
const_iterator begin() const { return _str; }
end
官方解释:
返回的是字符串最后一个字符的后一个位置的指针,比如一个字符串为"hello world\0",end()指向的就是'\0'的位置
iterator end() { return _str + _size; }
const_iterator end() const { return _str + _size; }
测试:
void test_string() { string s1("hello world"); for (test::string::iterator it = s1.begin(); it < s1.end(); ++it) { cout << *it << " "; } }
输出结果:
reserve
官方解释:
该函数对字符串内容不能进行修改,大小也不能修改,只能增加其容量,并且只能增容不能缩容
所以可以通过创建一个临时变量tmp,大小为n+1,将_str的内容通过strcpy函数复制给tmp,然后将_str给delete[ ]掉,最后将tmp地址给_str,就实现了扩容。
void reserve(size_t n = 0) { assert(n > _capacity); char* tmp = new char[n + 1]; strcpy(tmp, _str); delete[] _str; _str = tmp; _capacity = n; }
insert在任意位置插入字符/字符串
官方解释:
string& insert(size_t pos, char ch) { assert(pos <= _size); if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } size_t end = _size; while (end >= pos) { _str[end] = _str[end - 1]; --end; } _str[pos] = ch; ++_size; _str[_size] = '\0'; return *this; }
这样的代码看起来是没有什么问题,下面进行测试:
void test_string() { string s1("hello world"); s1.insert(2, 'a'); cout << s1.c_str() << endl; }
运行结果:
看起来好像一切都正常,但进行头插的时候
void test_string() { string s1("hello world"); s1.insert(0, 'a'); cout << s1.c_str() << endl; }
程序就崩溃了
这里导致程序崩溃的原因是因为end和pos都是size_t类型,size_t的0是一个很大的数,所以导致这里死循环了,但如果将end的类型从size_t改成int,程序还是会报错
而这里报错的原因是存在一个隐式类型转换,end>=pos这个式子当中,end是int类型,pos是size_t类型,int会自动转换成size_t,所以这里改成int类型也是没有用的,除非全都改成int类型,但库当中使用的类型是size_t,我们不能因为实现这个功能将库中变量的类型都改变了,这里有两种解决方式,一种是利用指针,还有一种就是另end=_size+1,只要不判断0就不会出错了
指针的方式:
string& insert(size_t pos, char ch) { assert(pos <= _size); if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } char* end = _str + _size; char* target = _str + pos; size_t end1 = _size; while (end >= target) { _str[end1] = _str[end1 - 1]; --end; --end1; } _str[pos] = ch; ++_size; _str[_size] = '\0'; return *this; }
不判断0的方式:
string& insert(size_t pos, char ch) { assert(pos <= _size); if (_size == _capacity) { reserve(_capacity == 0 ? 4 : 2 * _capacity); } size_t end = _size + 1; while (end > pos) { _str[end] = _str[end - 1]; --end; } _str[pos] = ch; ++_size; _str[_size] = '\0'; return *this; }
如果是插入一个字符串呢?其实思路也是一样的
指针的方式:
string& insert(size_t pos, const char* str) { assert(pos <= _size); int len = strlen(str); size_t end1 = _size + len; if (_capacity == _size) { reserve(_capacity + len); } char* end = _str + _size + len; char* target = _str + pos; while (end >= target) { _str[end1] = _str[end1 - len]; --end1; --end; } strncpy(_str + pos, str, len); return *this; }
不判断0的方式:
string& insert(size_t pos, const char* str) { assert(pos <= _size); int len = strlen(str); size_t end = _size + len; if (_capacity == _size) { reserve(_capacity+len); } while (end-len > pos) { _str[end] = _str[end - len]; --end; } strncpy(_str + pos, str, len); return *this; }
继续测试:
void test_string() { string s1("hello world"); s1.insert(0, "test"); cout << s1.c_str() << endl; }
push_back
官方解释:
插入一个字符到字符串的结尾,并且_size+1。
首先判断是否需要扩容,然后再在_str[_size]进行插入字符,最后++_size。
void push_back(char ch) { if (_size == _capacity) { reserve(_capacity + 1); } _str[_size] = ch; ++_size; _str[_size] = '\0'; }
开始测试:
void test_string() { string s1("hello world"); string s2(""); string s3(" "); s1.push_back('a'); s2.push_back('a'); s3.push_back('a'); cout << "s1的size:" << s1.size() << " " << "s1的capacity:" << s1.capacity() << " " << "字符串为:" << s1.c_str() << endl; cout << "s2的size:" << s2.size() << " " << "s2的capacity:" << s2.capacity() << " " << "字符串为:" << s2.c_str() << endl; cout << "s3的size:" << s3.size() << " " << "s3的capacity:" << s3.capacity() << " " << "字符串为:" << s3.c_str() << endl; }
其实为了简化代码也可以直接调用insert函数
void push_back(char ch) { insert(_size, ch); }
append
官方解释:
也是在字符串的结尾进行插入,与push_back不同的就是push_back只能插入字符但append还能插入字符串,函数返回类型也不同,所以插入字符的就不说了。
插入字符串,首先判断是否需要扩容,然后进行字符串尾插
string& append(const char* str) { int len = strlen(str); if (_capacity < _size + len) { reserve(_size + len); } strcpy(_str + _size, str); _size += len; return *this; }
测试:
void test_string() { string s1("hello world"); string s2(""); string s3(" "); s1.append("test"); s2.append("test"); s3.append("test"); cout << "s1的size:" << s1.size() << " " << "s1的capacity:" << s1.capacity() << " " << "字符串为:" << s1.c_str() << endl; cout << "s2的size:" << s2.size() << " " << "s2的capacity:" << s2.capacity() << " " << "字符串为:" << s2.c_str() << endl; cout << "s3的size:" << s3.size() << " " << "s3的capacity:" << s3.capacity() << " " << "字符串为:" << s3.c_str() << endl; }
为了代码简洁也是可以直接调用insert函数来实现append函数的功能
string& append(const char* str) { insert(_size, str); return *this; }
operator+
string operator+(const string& s2) { char* tmp = new char[strlen(s2._str) + strlen(_str) + 1]; strcpy(tmp, _str); strcat(tmp, s2._str); string res(tmp); delete[] tmp; tmp = nullptr; return res; }
测试:
void test_string() { string s1("hello world"); string s2(""); string s3(" "); string s4 = s1 + s2; string s5 = s2 + s1; string s6 = s2 + s3; string s7 = s3 + s2; string s8 = s1 + s3; string s9 = s3 + s1; cout << "s4的size:" << s4.size() << " " << "s4的capacity:" << s4.capacity() << " " << "字符串为:" << s4.c_str() << endl; cout << "s5的size:" << s5.size() << " " << "s5的capacity:" << s5.capacity() << " " << "字符串为:" << s5.c_str() << endl; cout << "s6的size:" << s6.size() << " " << "s6的capacity:" << s6.capacity() << " " << "字符串为:" << s6.c_str() << endl; cout << "s7的size:" << s7.size() << " " << "s7的capacity:" << s7.capacity() << " " << "字符串为:" << s7.c_str() << endl; cout << "s8的size:" << s8.size() << " " << "s8的capacity:" << s8.capacity() << " " << "字符串为:" << s8.c_str() << endl; cout << "s9的size:" << s9.size() << " " << "s9的capacity:" << s9.capacity() << " " << "字符串为:" << s9.c_str() << endl; }
这里的代码实现我刚开始犯了一个错误,将返回类型string写成了&string,这会导致程序直接崩溃
对不可操作的内存进行strlen了。
由于s1+s2返回的是一个不可操作的内存,因为res是string自定义类型的临时对象,出了函数作用域就会调用析构函数,析构函数会直接将res对象中的_str给delete[ ]销毁掉,但这个res又传过来了,所以s4又会去调用构造函数,所以就出问题了
operator+=
官方解释:
通过在字符串的当前值末尾附加其他字符来扩展字符串
首先要判断是否需要扩容,然后利用strcpy函数将str._str的字符串内容全部复制过去
string& operator+=(const string& str) { if (_size + str._size > _capacity) { reserve(_size + str._size); } strcpy(_str + _size, str._str); _size += str._size; return *this; }
测试:
void test_string() { string s1("hello world"); string s2("test"); string s3(""); string s4(" "); s1 += s3; cout << s1.c_str() << endl; s1 += s4; cout << s1.c_str() << endl; s1 += s2; cout << s1.c_str() << endl; s3 += s1; cout << s3.c_str() << endl; s4 += s1; cout << s4.c_str() << endl; }
运行结果:
也可以为了写的更加简洁,直接调用之前写的append函数即可
string& operator+=(const char* str) { append(str); return *this; }
erase
官方解释:
npos就是size_t -1
删除部分字符串,减少字符串长度。
private: char* _str; size_t _size; size_t _capacity; static const size_t npos;
然后再类外面对npos进行初始化,为什么npos不在初始化列表中初始化呢?
因为npos是一个静态变量,它不属于某一个特定的对象,所以要在类外面对其进行初始化,并且要指定类域
const size_t string::npos = -1;
如果pos比字符串的长度还要大,直接报错。
如果pos+len>=_size,那么直接将_str[pos]位置改为'\0'。
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 { strncpy(_str + pos, _str + pos + len,len); _size -= len; } return *this; }
测试:
void test_string() { string s1("hello world"); s1.erase(0, 10); cout << s1.c_str() << endl; string s2("hello world"); s2.erase(10, 5); cout << s2.c_str() << endl; }
运行结果:
clear
官方解释:
消去字符串的内容成为一个空字符串,_size和_capacity都变为0
void clear() { delete[] _str; _capacity = 0; _size = 0; }
pop_back
void pop_back() { assert(_size > 0); _str[_size-1] = '\0'; --_size; }
比较函数
bool operator >(const string& s) const { return strcmp(_str, s._str) > 0; } bool operator ==(const string& s) const { return strcmp(_str, s._str) == 0; } bool operator >= (const string& s) const { return *this > s || *this == s; } bool operator <(const string& s) const { return !(*this >= s); } bool operator <=(const string& s) const { return !(*this > s); } bool operator !=(const string& s) { return !(*this == s); }
substr
官方解释:
返回一个新构造的对象,其值初始化为此对象的子字符串的拷贝。
子字符串是从字符位置开始并跨越字符(或直到字符串末尾,以先到者为准)的对象部分。
string substr(size_t pos = 0, size_t len = npos) { assert(pos < _size); size_t reallen = len; if (len == npos || pos + len > _size) { reallen = _size - len; } string sub; for (int i = pos; i < reallen; ++i) { sub += _str[i]; } return sub; }
find(利用kmp算法实现)
官方解释:
从pos位置开始,在字符串中找到第一个匹配的下标并且返回
首先是查找单个字符,很简单,直接遍历挨个比对就好了
size_t find(char ch, size_t pos = 0)//查找字符 { for (int i = pos; i < _size; i++) { if (_str[i] == ch) { return i; } } return npos; }
其次就是匹配字符串了,这里使用的是kmp算法来匹配子串并且返回其下标
kmp详解可移步至:KMP算法详解(一眼看穿next[ ]数组)
size_t find(const char* str, size_t pos = 0) { int len = strlen(str); if (strlen(str) > _size) { return npos; } ne = new int[len + 1]{ 0 }; //获取匹配码 for (int i = 1, j = 0; i < len; i++) { while (j && str[i] != str[j]) j = ne[j]; if (str[i] == str[j]) j++; ne[i] = j; } for (int i = 0, j = 0; i < _size; i++) { while (j && _str[i] != str[j]) j = ne[j]; if (_str[i] == str[j]) j++; if (j == len) { return i - j + 1; } } return npos; }
注意到这里使用到了一个ne数组,ne数组主要是用来存储字符串的匹配码的,这个ne数组直接定义在私有成员变量当中,int* ne;
private: char* _str; size_t _size; size_t _capacity; int* ne; static const size_t npos;
成员变量添加了一个ne指针之后,也需要在构造函数中对ne指针进行初始化,否则ne指向的是一片随机的空间,由于无法直接在初始化列表当中给ne分配空间,所以可以先给ne一个空指针。
string(const char* str = "") :_size(strlen(str)) , _capacity(_size) , ne(nullptr) { ne = new int[1]{ 0 }; _str = new char[_capacity + 1]; strcpy(_str, str); }
>>
官方解释:
在C++当中,处理输入时使用命名为cin的istream类型对象,这个对象也叫标准输入,每次输入操作符实例都要接受两个操作数:左操作数必须是istream对象,然后接受一个对象作为右操作数,它从istream操作数当中读取数据并且保存在右操作数中。
因为>>是操作符,只能接收一个参数,如果不使用友元的话调用这个函数的书写方式会变为:
str.cin("test");
这显然不符合正常使用的习惯,所以这里需要添加一个友元函数
friend istream& operator>>(istream& in, string& str);
然后再实现cin
istream& operator>>(istream& in, string& str) { str.clear();//清空原字符串 char ch = in.get(); while (ch != ' ' && ch != '\n') { ch = in.get(); } return in; }
<<
<<为流提取,与>>类似,不过它的左值是一个ostream类型的对象
友元函数:
friend ostream& operator<<(ostream& out, const string& str);
实现cout:
ostream& operator<<(ostream& out, const string& str) { out << str.c_str(); return out; }