C++ string：准 STL Container

历史

STL 最初是一套独立的泛型库（Alexander Stepanov 等人贡献），后来被吸纳进 C++ 标准库；std::basic_string 则是早期 C++ 标准（Cfront / ARM 时代）就存在的“字符串类”，并非 STL 原生物。

std::string 实际上是 std::basic_string<char> 的 typedef，提供了类似 STL 容器的接口（迭代器、begin()/end()、push_back()、size() 等），因此常被称作“近似 STL 容器”或“序列式容器”。

模拟实现 string 类

实现 string 类的构造、拷贝构造、赋值运算符重载、析构函数、以及对 string 对象的增删改查。

成员变量

private:char* _str;size_t _size;size_t _capacity;

构造函数

提供缺省参数的构造函数，使用常量字符串初始化；因为需要兼容 C 字符串的 '\0'，所以为 _str 多开 1 字节的空间用以存放 '\0' 。

myString(const char* str = ""):_size(strlen(str)),_capacity(_size){_str = new char[_capacity + 1];strcpy(_str, str);}

拷贝构造 

注意需要对成员 _str 指向的空间深拷贝；另外还有一种写时拷贝可以进一步节省空间并提高效率。

	myString(const myString& str):_str(nullptr),_size(str.size()),_capacity(str.capacity()){reserve(str.capacity());	// reserve 中已经为 '\0' 多开了 1 字节strcpy(_str, str.c_str());}

增 -- push_back

如果要向 _str 尾部增加元素，先要检查空间是否足够，如果不够，封装扩容逻辑至函数 reserve：

reserve

异地扩容至 n+1 字节，多出来的 1 字节是给 '\0' 的

	void reserve(size_t n){if (n > _capacity){char* tmp = new char[n + 1];	// 开新空间strcpy(tmp, _str);	// 拷贝数据，memcpy 也行swap(tmp, _str);	// 交换指针delete[] tmp;	// 释放旧空间}}

接着在 push_back 中检查空间是否足够，如果不够，使用一个 三目表达式 来决定扩容至多大空间；最后向开辟好的空间内写入字符，并将下一个位置设置为 '\0'，以兼容 C 类型的字符串；

	void push_back(const char& ch){if (_size == _capacity){size_t new_capacity = _capacity == 0 ? 2 : _capacity * 2;reserve(new_capacity);}_str[_size] = ch;_str[_size + 1] = '\0';_size++;}

增 -- insert

标准库中实现了很多重载，我来模拟一部分：

myString& insert(size_t pos, const myString& str)

在 pos 位置，插入同类型 myString str；那么需要向后挪动 pos 位置之后的元素，每个元素挪动 str._size 个空间；这里需要获取形参 str 的私有变量，实现简单的函数来获取：

	size_t size(){return _size;}size_t capacity(){return _capacity;}

接下来向后挪动元素，但是要判断所需空间是否足够，不够就扩容：

	myString& insert(size_t pos, const myString& str){if (_capacity < _size + str.size())	// 判断接下来需要的空间是否足够{reserve(_size + str.size());}}

发现编译这段报错，原因是形参 str 对象被 const 修饰，不能调用非 const 成员函数，将成员函数也用 const 修饰其 this 指针即可：

	size_t size() const{return _size;}size_t capacity() const{return _capacity;}

扩容问题解决，从 pos 位置开始，向后挪动元素：

	myString& insert(size_t pos, const myString& str){if (_capacity < _size + str.size())	// 判断接下来需要的空间是否足够{reserve(_size + str.size());}size_t begin = pos, end = _size;	// _size 处的'\0'一起挪动while (end >= begin)	// 挪动数据{_str[end + str.size()] = _str[end];end--;}}

现在向 pos 处写入 str._str 的数据，但需要获取 str._str 私有指针变量以访问其数据：

	char* c_str() const{return _str;}

插入数据之后，返回原 myString 对象引用：

myString& insert(size_t pos, const myString& str){if (_capacity < _size + str.size())	// 判断接下来需要的空间是否足够{reserve(_size + str.size());}size_t begin = pos, end = _size;	// _size 处的'\0'一起挪动while (end >= begin)	// 挪动数据{_str[end + str.size()] = _str[end];end--;}for (size_t i = 0; i < str.size(); i++)	// 插入数据{_str[pos + i] = str.c_str()[i];}return *this;}

但是在挪动数据时，有个 bug ：如果传入形参 pos 为 0 ，也就是头插；

那么 begin 为 0 ，挪动数据 while 的循环终止条件是 end < begin ，end 要等于 -1 循环才会终止；

但关键问题在于 end 变量类型是无符号整数 size_t，当 end = 0，再 end-- 之后，end 会变成 42亿多，这使 while 变成死循环；

解决办法：可以强制类型转换，不会有什么问题

		int begin = (int)pos, end = (int)_size;	// _size 处的'\0'一起挪动while (end >= begin)	// 挪动数据{_str[end + str.size()] = _str[end];end--;}

myString& insert (size_t pos, size_t n, char c)

在 pos 处插入 n 个 c 字符：判断空间容量是否足够 -- 挪动数据 -- 插入数据，与上面的实现类似，累了。

增 -- append

理解为什么大佬们会吐槽 string 的设计繁琐了(lll￢ω￢)

myString& append (const myString& str)

追加同类型 myString ：检查容量，copy 该 myString 数据到 this->_str 末尾。

	myString& append(const myString& str){if (_capacity < _size + str.size()){reserve(_size + str.size());}strcpy(_str + _size, str.c_str());	// strcpy 会一并拷贝字符串末尾的 '\0'return *this;}

删 -- pop_back

删掉最后一个元素，这个接口是 C++11 增加的，可能是为了向 STL 的容器看齐吧

    void pop_back(){_size--;}

删 -- erase

myString& erase (size_t pos = 0, size_t len = npos)

从 pos 开始，删掉 len 个字符，npos 是无符号最大整数 0x7fffffff

实际上，是将从 pos+len 到 _size 的数据向前挪动 len 个位置进行覆盖，最后 _size-len 即可

注意，如果 pos+len > _size ，即 len > _size-pos ，就会越界访问，所以要处理 len 过大的问题

	myString& erase(size_t pos = 0, size_t len = string::npos){assert(pos < _size);if (len > _size - pos)	// 处理 len 过大造成越界访问{len = _size - pos;}for (size_t i = 0; i < _size-(pos+len)+1; i++)	// 向前覆盖数据{_str[pos + i] = _str[pos + len + i];}_size -= len;return *this;}

查 -- find

size_t find (const myString& str, size_t pos = 0) const

从 pos 位置开始，找子串，直接调用 C库函数 strstr 找，strstr 找到返回 该子串在原字符串中的指针，找不到会返回 NULL

	size_t find(const myString& str, size_t pos = 0) const{char* sub = strstr(_str + pos, str.c_str());if (sub){return sub - _str;}else{return string::npos;}}

size_t find(char c, size_t pos)

找字符首次出现位置

    size_t find(char c, size_t pos){for (size_t i = pos; i < _size; i++){if (_str[i] == c){return i;}}return npos;}

创建子串 -- substr

myString substr (size_t pos = 0, size_t len = npos) const

从字符串 pos 位置开始，取 len 个字符创建新的子串，并传值返回

为新对象开空间，拷贝子串内容

	myString substr(size_t pos = 0, size_t len = string::npos) const{assert(pos < _size);if (len > _size - pos)	// 处理 len 过大造成越界访问{len = _size - pos;}myString sub;sub.reserve(len);	// 存 len 字节memcpy(sub._str, _str + pos, len);	// memcpy可以拷贝固定大小sub._size = len;sub._str[_size] = '\0';	// len 不包括 '\0'return sub;}

赋值运算符重载

myString& operator= (const myString& str)

两个已存在的对象之间的赋值运算符重载，注意深拷贝

	myString& operator= (const myString& str){char* tmp = new char[str.capacity() + 1];strcpy(tmp, str._str);delete[] _str;	// 释放旧空间_str = tmp;	// 指向新空间_size = str._size;_capacity = str._capacity;}

析构函数

~myString()

注意释放对象中的资源即可

	~myString(){delete[] _str;_size = _capacity = 0;}

小结

基本没有复用，主要是练个手熟；要想快，还得当 CV programmer！