c++初阶 string的底层实现

声明：非纯手搓，运用到了部分c语言的函数

首先可以明确的是string的底层结构是字符串数组，但是由于字符串数组中是使用\0来终止的，因此他实际的存储空间是要比显示的多一个的。

更多详细内容可以去c++官网查看 https://legacy.cplusplus.com/reference/string/string/?kw=string

代码如下：

基础函数成员

成员变量

private:char* _str;int _size;int _capacity;static const unsigned int npos = -1;

构造函数

第一种写法：分开写
string() :_str(new char[1]),//多开辟一个放\0_size(0),_capacity(0)
{_str[0] = '\0';
}string(const char* str) :_str(new char[strlen(str) + 1]),_size(strlen(str)),_capacity(strlen(str))
{strcpy(_str, str);
}第二种写法：全缺省，一个函数全包括了
string(const char* str = "") ://写成"\0"也可以_size(strlen(str))	{_capacity = _size;_str = new char[_size + 1];strcpy(_str, str);}	

析构函数：

~string()
{delete[] _str;//注意别忘了这个方括号,要和申请空间时new格式相同_str = nullptr;_size = _capacity = 0;
}

拷贝构造

//传统写法
string(const string& s)//深拷贝
{_str = new char[s._capacity + 1];strcpy(_str, s._str);_size = s._size;_capacity = s._capacity;}//现代写法
string(const string& s)
{string tmp(s._str);swap(tmp);//swap函数的实现在后面了}

赋值构造

//传统写法
string& operator=(const string& s) // 赋值构造
{char* tmp = new char[s._capacity + 1];strcpy(tmp, s._str);delete[] _str;		//原空间不要了_str = tmp;_size = s._size;_capacity = s._capacity;return *this;
}//现代写法,本质区别是是用现成的还是自己再做一遍
string& operator=(const string& s)
{string tmp(s);swap(tmp);return *this;
}
//更简洁的版本
string& operator=(string s)
{swap(tmp);return *this;
}

遍历

下标访问

inline char& operator[](int pos)//下标引用是可读可写的，所以返回类型是char引用// 因为在使用时会多次调用并且函数的体量小，所以可以使用内联函数进行优化
{assert(pos < _size); //检查是否越界return _str[pos];
}inline const char& operator[](int pos) const
// 再写一个是为了应对const string的情况,这种情况可读不可写
{assert(pos < _size); return _str[pos];
}

迭代器

这里的迭代器用的指针进行模拟，事实上g++也用的这种模式，但他真实的情况却要复杂的多。

typedef char* iterator;
iterator begin()
{return _str;
}
iterator end()
{return _str + _size;
}//这种方式可以使用范围for来进行访问既:for (auto i : s)的形式，具体将不再演示
//范围for的本质是替代，只要你定义的有begin,end,和itrator 他就可以运行  注：它最早起源于python

增删插

开辟空间

void reserve(int n)
{if (n > _capacity){char* tmp = new char[n + 1]; // 注意要多开辟一个放\0strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;//开辟新空间，替换空间内容，释放原空间，改变原空间指向}
}

push_back

void push_back(char ch)
{if (_size == _capacity)reserve(_capacity == 0 ? 4 : 2 * _capacity); //注意要判断空间为0的情况_str[_size] = ch;++_size;_str[_size] = '\0'; // 小细节}

append

void append(const char* str)//它有很多重载，这里只写这一种
{int len = strlen(str);if (_size + len > _capacity)reserve(_size + len);   // 较为保险的扩容方式，思考一下为什么不单纯的扩二倍？strcpy(_str + _size, str);  // strcat效率较低，因此用strcpy_size += len;
}

+=

string& operator+= (char ch)
{push_back(ch);return *this;
}
string& operator+= (const char* s)
{append(s);return *this;
}
//没什么好说的就是调用之前的函数

insert

void insert(size_t pos, char ch)
{assert(pos <= _size);if (_size == _capacity)reserve(_capacity == 0 ? 4 : 2 * _capacity); int end = _size;while (end >= (int)pos){_str[end + 1] = _str[end];end--;}//整体往后挪一位，没什么技术含量_str[pos] = ch;_size++;
}void insert(size_t pos, const char* str)//插入字符串
{int len = strlen(str);if (_size + len > _capacity)reserve(_size + len);for (int i = pos; i < len + pos; i++){if (i < _size)  // 避免多搬运数据导致超出内存_str[i + len] = _str[i];_str[i] = str[i - pos];}_size += len;_str[_size] = '\0';
}

erase

void erase(size_t pos, int len = npos)
{assert(pos < _size);if (len == npos || len > _size - pos) // 写成len + pos 的形式有溢出风险{_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len;}
}

功能函数

swap

void swap(string& s)
{std::swap(_str, s._str);//这里std::必须要加上的，避免调用到的函数是写的这个;std::swap(_size, s._size);std::swap(_capacity, s._capacity);
}
//直接使用swap(s1, s2)的话效率要低一些

find

//查字符
size_t find(char ch, size_t pos = 0) const
{assert(pos < _size);for (int i = pos; i < _size; i++){if (_str[i] == ch)return i;}return npos;
}
//查子串
size_t find(const char* str, size_t pos = 0) const
{assert(pos < _size);//可以用kmp/bm算法优化一下char* p = strstr(_str + pos, str);if (p)return p - _str;elsereturn npos;
}

c_str

//(函数作用是以c语言可以接受的形式返回字符串,方便向c的部分函数兼容)
char* c_str() const
{return _str;
}

substr

string substr(size_t pos = 0, size_t len = npos)
{string sub;for (int i = 0; i < _size && i < pos + len; i++)sub += _str[i];return sub;
}

clear

void clear()
{_size = 0;_str[0] = '\0';
}

其他函数

比较函数

bool operator==(const string& a, const string& b)//得写成全局变量,在类里面定义的==只能写一个参数
{int ret = strcmp(a.c_str(), b.c_str());return ret == 0;
}
bool operator<=(const string& a, const string& b)
{int ret = strcmp(a.c_str(), b.c_str());return ret >= 0;
}
bool operator>=(const string& a, const string& b)
{int ret = strcmp(a.c_str(), b.c_str());return ret <= 0;
}
bool operator>(const string& a, const string& b)
{int ret = strcmp(a.c_str(), b.c_str());return ret < 0;
}
bool operator<(const string& a, const string& b)
{int ret = strcmp(a.c_str(), b.c_str());return ret > 0;
}
bool operator!=(const string& a, const string& b)
{int ret = strcmp(a.c_str(), b.c_str());return ret != 0;
}

流提取<<

ostream& operator<<(ostream& out, const string& s)
{for (auto i : s)out << i;return out;
}

流插入>>

istream& operator>>(istream& in, string& s)
{s.clear();char ch;ch = in.get();// 不可以直接使用cin因为他会自动跳过空格和换行//cin.get()相当于c语言中的getchar()while (ch != ' ' && ch != '\n'){s += ch;ch = in.get();}return in;
}
//优化版本，上面的版本存在多次扩容消耗更大的问题
istream& operator>>(istream& in, string& s)
{s.clear();char ch;ch = in.get();int i = 0;char buff[128];while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 127){buff[i] = '\0';s += buff;i = 0;}ch = in.get();}if (ch > 0){buff[i] = '\0';s += buff;}return in;
}

getline

//比流插入就少了一个比较
istream& getline(istream& in, string& s)
{s.clear();char ch;ch = in.get();while (ch != '\n'){s += ch;ch = in.get();}return in;
}

完整版

#pragma once
#include<iostream>
#include<assert.h>using namespace std;namespace bit
{class string {public://string() ://	_str(new char[1]),//多开辟一个放\0//	_size(0),//	_capacity(0)//{//	_str[0] = '\0';//}//string(const char* str) ://	_str(new char[strlen(str) + 1]),//	_size(strlen(str)),//	_capacity(strlen(str))//{//	strcpy(_str, str);//}typedef char* iterator;typedef const char* const_iterator;iterator begin(){return _str;}iterator end(){return _str + _size;}//const版本const_iterator begin() const{return _str;}const_iterator end() const{return _str + _size;}string(const char* str = "") ://写成"\0"也可以_size(strlen(str)){_capacity = _size;_str = new char[_size + 1];strcpy(_str, str);}//string(const string& s)//深拷贝//{//	_str = new char[s._capacity + 1];//	strcpy(_str, s._str);//	_size = s._size;//	_capacity = s._capacity;//}//现代写法string(const string& s){string tmp(s._str);swap(tmp);}string& operator=(const string& s){char* tmp = new char[s._capacity + 1];strcpy(tmp, s._str);delete[] _str;_str = tmp;_size = s._size;_capacity = s._capacity;return *this;}//string& operator=(const string& s)//{//	string tmp(s);//	swap(tmp);// 	return *this;//}~string(){delete[] _str;//注意别忘了这个方括号,要和申请空间时new格式相同_str = nullptr;_size = _capacity = 0;}size_t size() const//加个const使其调用时无法再修改{return _size;}size_t capacity() const{return _capacity;}inline char& operator[](int pos) //下标引用是可读可写的，所以返回类型是char引用{assert(pos < _size); //检查是否越界return _str[pos];}inline const char& operator[](int pos) const// 再写一个是为了应对const string的情况,这种情况可读不可写{assert(pos < _size);return _str[pos];}void reserve(int n){if (n > _capacity){char* tmp = new char[n + 1]; // 注意要多开辟一个放\0strcpy(tmp, _str);delete[] _str;_str = tmp;_capacity = n;//开辟新空间，替换空间内容，释放原空间，改变原空间指向}}void push_back(char ch){if (_size == _capacity)reserve(_capacity == 0 ? 4 : 2 * _capacity); //注意要判断空间为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);  // strcat效率较低，因此用strcpy_size += len;}string& operator+= (char ch){push_back(ch);return *this;}string& operator+= (const char* s){append(s);return *this;}void insert(size_t pos, char ch){assert(pos <= _size);if (_size == _capacity)reserve(_capacity == 0 ? 4 : 2 * _capacity); int end = _size;while (end >= (int)pos){_str[end + 1] = _str[end];end--;}_str[pos] = ch;_size++;}void insert(size_t pos, const char* str){int len = strlen(str);if (_size + len > _capacity)reserve(_size + len);for (int i = pos; i < len + pos; i++){if (i < _size)  // 避免多搬运数据导致超出内存_str[i + len] = _str[i];_str[i] = str[i - pos];}_size += len;_str[_size] = '\0';}void erase(size_t pos, int len = npos){assert(pos < _size);if (len == npos || len > _size - pos) // 写成len + pos 的形式有溢出风险{_str[pos] = '\0';_size = pos;}else{strcpy(_str + pos, _str + pos + len);_size -= len;}}void resize(int n, char ch = '\0'){//resize两个功能，比size大时增加内容，反之则删除到n的大小;if (n >= _size){reserve(n);for (int i = _size; i < n; i++){_str[i] = ch;}_size = n;_str[_size] = '\0';}else{_str[n] = '\0';_size = n;}}void swap(string& s){std::swap(_str, s._str);//这里std::必须要加上的，避免调用到的函数是写的这个;std::swap(_size, s._size);std::swap(_capacity, s._capacity);}void swap(string& a, string& b){a.swap(b);}size_t find(char ch, size_t pos = 0) const{assert(pos < _size);for (int i = pos; i < _size; i++){if (_str[i] == ch)return i;}return npos;}size_t find(const char* str, size_t pos = 0) const{assert(pos < _size);//可以用kmp/bm算法优化一下char* p = strstr(_str + pos, str);if (p)return p - _str;elsereturn npos;}string substr(size_t pos = 0, size_t len = npos){string sub;for (int i = 0; i < _size && i < pos + len; i++)sub += _str[i];return sub;}char* c_str() const{return _str;}void clear(){_size = 0;_str[0] = '\0';}private:char* _str;int _size;int _capacity;static const unsigned int npos = -1;};bool operator==(const string& a, const string& b)//得写成全局变量,在类里面只能写一个参数{int ret = strcmp(a.c_str(), b.c_str());return ret == 0;}bool operator<=(const string& a, const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret >= 0;}bool operator>=(const string& a, const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret <= 0;}bool operator>(const string& a, const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret < 0;}bool operator<(const string& a, const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret > 0;}bool operator!=(const string& a, const string& b){int ret = strcmp(a.c_str(), b.c_str());return ret != 0;}ostream& operator<<(ostream& out, const string& s){for (auto i : s)out << i;return out;}//istream& operator>>(istream& in, string& s)//{//	s.clear();//	char ch;//	ch = in.get();//	// 不可以直接使用cin因为他会自动跳过空格和换行//	//cin.get()相当于c语言中的getchar()//	while (ch != ' ' && ch != '\n')//	{//		s += ch;//		ch = in.get();//	}//	return in;//}istream& operator>>(istream& in, string& s){s.clear();char ch;ch = in.get();int i = 0;char buff[128];while (ch != ' ' && ch != '\n'){buff[i++] = ch;if (i == 127){buff[i] = '\0';s += buff;i = 0;}ch = in.get();}if (ch > 0){buff[i] = '\0';s += buff;}return in;}istream& getline(istream& in, string& s){s.clear();char ch;ch = in.get();while (ch != '\n'){s += ch;ch = in.get();}return in;}};