定义和结构
对字符串的使用和操作往往非常频繁，在C++中，为了便于对字符串进行管理，引入了string类。string类是basic_string类模板的一个实例：有typedef basic_string<char, char_traits, allocator>
string。string类的存储结构其实是一个顺序表，与C语言传统字符串的使用相比，用string类对字符串进行管理，往往更加简单、方便、快捷和安全。因为字符串使用频繁，string的出现比STL更早，并在后续发展中对其进行了重写，本文通过模拟实现string类及其部分常用的接口以深入体会和理解string类的使用。
class string
{
private:
size_t _size;
size_t _capacity;
char* _str;
/*…………*/同时要在类域中声明一个静态成员变量npos作为某些操作的操作范围标识：
static const size_t npos;
/*…………*/
const size_t string::npos = -1;迭代器
在STL中，容器和算法是分别设计的，而迭代器是二者之间的胶合剂，便于两者之间更好地配合。迭代器提供了一种统一的方式拿到容器的数据，而无需暴露容器的底层实现。从使用上看，任何容器都支持迭代器，并且用法相似。
string维护的是一个连续线性空间，普通指针可以作为string的迭代器而满足所有的必要条件，例如对迭代器的加减操作(operator++，operator--)和解引用操作(operator*)等，这些操作普通指针可以天然满足，string支持随机存取，普通指针同样可以做到。
public:
typedef char* iterator;
typedef const char* const_iterator;
////迭代器
iterator begin() {
return _str;
}
iterator end() {
return _str + _size;
}
const_iterator cbegin() const {
return _str;
}
const_iterator cend() const {
return _str + _size;
}构造&析构和内存管理
C++标准库中提供了多种string的构造方式，本文实现以字符串构造的方式和拷贝构造。
需要注意的是，string中成员变量_capacity和_size只将有效字符考虑在内，而不包括 '\0'，但是为了兼容C语言，依然要为 '\0' 分配空间。
////构造&析构
//注意初始化列表的成员变量初始化顺序要与定义顺序一致
string(const char* str = "")
:_size(strlen(str)),
_capacity(_size),
_str(new char[_size + 1]) //+ 1是为了给'\0'预留空间
{
//因为str一定是一个以'\0'结尾的字符串，所以使用strcpy即可
strcpy(_str, str);
}
//深拷贝
string(const string& s)
{
_str = new char[s._capacity + 1];
//使用memcpy,将'\0'考虑在内
memcpy(_str, s._str, s._size + 1); //_size + 1，为'\0'预留空间
_size = s._size;
_capacity = s._capacity;
}
~string()
{
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}在C语言中，'\0'是字符串结束的标志，C语言库中对字符串的各种操作函数，例如strlen、strcpy等也是以 '\0' 作为字符串操作终止标志的，但是在string中，序列中的'\0'不一定标识对象的结束。即在string中，有效字符的范围是以_size进行标识的，而与序列中的'\0'无关，'\0'可能成为string中的有效字符。因为这一点，在实现一些接口时，不能简单地复用C库中的str系列函数，而需使用mem系列函数对内存进行操作，否则就会造成一些问题。
reserve()是一个对string容量进行操作的成员函数，在元素操作时，为了保证内存空间充足，会频繁调用这个接口。reserve的实现有三步：配置新空间、数据移动和释放旧空间。
void reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1]; //为'\0'多开一个字节空间
//考虑'\0'在内
memcpy(tmp, _str, n + 1);
delete[] _str;
_str = tmp;
_capacity = n;
}
}元素访问和操作
Access
string可以支持下标操作，这主要得益于对下标访问操作符的重载。下标访问操作符根据对象是否为const对象被设计成两个函数的重载。
为了与C语言更好的兼容，设计一个c_str()接口返回序列的字符串数据部分。
//针对普通对象，可读可写
char& operator[](size_t pos)
{
assert(pos < _size);
return _str[pos];
}
//针对const对象，只读
const char& operator[](size_t pos) const
{
assert(pos < _size);
return _str[pos];
}
const char* c_str() const
{
return _str;
}Add
void push_back(char ch)
{
if (_size == _capacity) {
//push之前有可能是空串，_capacity为0
reserve(_capacity == 0 ? 4 : _size * 2);
}
_str[_size++] = ch;
_str[_size] = '\0'; //末尾补'\0'
}
void append(const char* str)
{
int len = strlen(str);
//判断_size + len与_capacity的关系
if (_size + len > _capacity) {
reserve(_size + len);
}
strcpy(_str + _size, str);
_size += len;
}
string& insert(size_t pos, size_t n, char ch)
{
assert(pos < _size); //检查pos的合法性
//检查容量
if (_size + n > _capacity) {
reserve(_size + n);
}
//挪动数据
size_t end = _size;
while (end >= pos && end != npos)
{
_str[end + n] = _str[end];
--end;
}
//插入数据
for (int i = 0; i < n; ++i) {
_str[pos + i] = ch;
}
_size += n; //注意不要忘记调整_size
return *this;
}
string& insert(size_t pos, const char* str)
{
assert(pos < _size);
//检查容量
int len = strlen(str);
if (_size + len > _capacity) {
reserve(_size + len);
}
//挪动数据
size_t end = _size;
//由于end在与pos比较时会被提升至size_t类型，所以要额外判断end与npos的关系
while (end >= pos && end != npos)
{
_str[end + len] = _str[end];
--end;
}
//插入数据
for (int i = 0; i < len; ++i) {
_str[pos + i] = str[i];
}
//调整_size
_size += len;
return *this;
}在进行push操作时，往往更加习惯使用+=操作符，故而对+=运算符进行重载以简化push的使用：
string& operator+=(char ch)
{
push_back(ch);
return *this;
}
string& operator+=(const char* str)
{
append(str);
return *this;
}Delete
iterator erase(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
//从pos位置清理至最后
if (len == npos || pos + len >= _size) {
_str[pos] = '\0';
}
else
{
//挪动数据，包括'\0'
size_t end = pos + len;
while (end <= _size) {
_str[pos++] = _str[end++];
}
}
//注意不能直接_size -= len,len 可能是npos
_size = pos;
return _str + pos;
}
void clear()
{
if (_size != 0) {
erase();
}
}Search
size_t find(char ch, size_t pos = 0)
{
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)
{
assert(pos < _size);
char* ret = strstr(_str, str);
if (ret) {
return ret - _str;
}
else {
return npos;
}
}在上述第二个接口寻找子串时，由于使用的是strstr，所以当在_str中遇到'\0'时就停止搜索了，由上文可知，这对于string中含多个'\0'的情况可能会造成一些问题。为了避免问题，可以手动实现一个定制的strstr。关于字符串匹配，请参考BP算法和KMP算法。
截取和判断
string substr(size_t pos = 0, size_t len = npos)
{
assert(pos < _size);
string tmp;
//从pos位置截取到最后
if (len == npos || len + pos > _size)
{
for (int i = pos; i < _size; ++i) {
tmp += _str[i];
}
}
else
{
for (int i = pos; i < pos + len; ++i) {
tmp += _str[i];
}
}
return tmp;
}
void resize(size_t n, char ch = '\0')
{
if(n <= _size) {
_str[_size] = '\0';
}
//n > _size，判断并调整容量后添加字符
else
{
reserve(n);
for (int i = _size; i < n; ++i) {
_str[i] = ch;
}
_str[n] = '\0';
}
_size = n;
}
void swap(string& s)
{
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
bool empty()
{
return _size == 0;
}运算符重载
赋值运算符重载
string的赋值运算符重载有两种写法，一种是传统的深拷贝写法，分为开新空间、移动数据两个步骤；另一种写法将这两个步骤委托给拷贝构造进行，可以简化重载函数的书写。
//传统写法
string& operator=(const string& s)
{
reserve(s._capacity);
memcpy(_str, s._str, s._size + 1);
_size = s._size;
return *this;
}
//现代写法的参数是一个临时的类对象，该类对象是右值对象调用拷贝构造所得
//将tmp临时对象与this对象交换，可以达到赋值的目的
//tmp的生命周期在本函数域内，会自动调用析构释放空间
string& operator=(string tmp)
{
swap(tmp);
return *this;
}类似的，拷贝构造也有一种现代写法，利用构造函数来简化拷贝构造的书写：
//现代写法
//写初始化列表，防止因this对象的随机内容在swap时产生问题
string(const string& s)
:_size(s._size),
_capacity(s._capacity),
_str(nullptr)
{
string tmp(s._str);
swap(tmp);
}现代写法的拷贝构造利用构造函数拷贝了已有对象的内容，并将其交还给this对象以达到拷贝构造的目的。这种写法的拷贝构造有一个缺陷，即当已有对象的有效数据部分含'\0'时，tmp只会构造出 '\0' 之前的部分数据。综合来说，不建议用这种方式写拷贝构造函数。
比较和判断
bool operator>(const string& s)
{
//hello helloxxx true
//helloxxx hello false
//hello hello false
int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
return ret == 0 ? _size > s._size : ret > 0;
}
bool operator==(const string& s)
{
return _size == s._size && memcmp(_str, s._str, _size) == 0;
}
bool operator!=(const string& s)
{
return !(*this == s);
}
bool operator>=(const string& s)
{
return (*this > s || *this == s);
}
bool operator<(const string& s)
{
return !(*this >= s);
}
bool operator<=(const string& s)
{
return !(*this > s);
}
};流运算符重载
////输入输出
std::ostream& operator<<(std::ostream& cout, const shr::string& s)
{
for (int i = 0; i < s.size(); ++i) {
cout << s[i];
}
return cout;
}
std::istream& operator>>(std::istream& cin, shr::string& s)
{
s.clear(); //clear实现数据覆盖
//get可以读取单个字符
char ch = cin.get();
//清空缓冲区中的前置空格和换行
while (ch == ' ' || ch == '\n') {
ch = cin.get();
}
//先将输入的字符放入buff中，buff满后再放入对象中
//减少扩容次数
char buff[128];
int i = 0;
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
buff[i] = '\0';
if (i == 127)
{
s += buff;
i = 0;
}
ch = cin.get();
}
if (i != 0) {
s += buff;
i = 0;
}
return cin;
}string类的引用计数和写时拷贝
当进行拷贝构造时，总是进行深拷贝，适用于需要对对象进行读写操作的情况。因为存在只对某些对象进行读操作的情况，多余的深拷贝便会占据多余的内存空间，解决办法便是进行浅拷贝。
浅拷贝有两个问题：对同一块内存的重复释放和对同一块内存数据的操作冲突。对于第一个问题，可以使用引用计数解决，对于每一块内存空间，用一个整型记录本块内存空间目前被引用的次数，当进行拷贝构造时，进行浅拷贝，被引用次数加一；对象销毁时，不释放空间，被引用次数减一；当被引用次数减至0时，释放内存空间。对于第二个问题，可以进行写时拷贝，拷贝构造时进行浅拷贝，此时对于只读情况完全适用，当对对象进行写操作时，进行深拷贝，以避免对原内存空间数据的修改。
通过引用计数和写时拷贝，可以尽量节省不必要的内存消耗。对于对对象进行只读操作的情况，无需开辟额外空间，而是在进行写操作时才进行深拷贝申请必要的内存空间。
