C++算法
C++ 实现自定义 String 类：告别 C 字符串陷阱
C++ 中 string 类的常用接口及底层模拟实现。对比了 C 语言字符串的缺陷，阐述了 auto、范围 for 等特性。详细讲解了构造、容量操作、迭代器访问、修改操作及非成员函数的实现逻辑。重点分析了浅拷贝与深拷贝的区别，展示了现代写法下的拷贝构造与赋值运算符重载。最后提供了完整的头文件与源文件代码示例，并扩展了引用计数的写时拷贝概念。
C++ 中 string 类的常用接口及底层模拟实现。对比了 C 语言字符串的缺陷，阐述了 auto、范围 for 等特性。详细讲解了构造、容量操作、迭代器访问、修改操作及非成员函数的实现逻辑。重点分析了浅拷贝与深拷贝的区别，展示了现代写法下的拷贝构造与赋值运算符重载。最后提供了完整的头文件与源文件代码示例，并扩展了引用计数的写时拷贝概念。
C 语言中，字符串是以'\0'结尾的一些字符的集合。为了操作方便，C 标准库提供了一些 str 系列的库函数，但这些库函数与字符串是分离开的，不太符合 OOP 思想，且底层空间需要用户自己管理，稍不留神可能还会越界访问。因此在 C++ 中 string 用封装的方式解决了这一问题。
auto 关键字（自动推导类型）：在早期 C/C++ 中 auto 的含义是使用 auto 修饰的变量具有自动存储器的局部变量。C++11 中，auto 不再是一个存储类型指示符，而是作为一个新的类型指示符来指示编译器，auto 声明的变量必须由编译器在编译时期推导而得。用 auto 声明指针类型时，用 auto 和 auto*没有任何区别，但用 auto 声明引用类型时则必须加&。当在同一行声明多个变量时，这些变量必须是相同的类型，否则编译器将会报错。auto 不能作为函数的参数，可以做返回值，但需谨慎使用。auto 不能直接用来声明数组。
范围 for（底层就是迭代器）：对于一个有范围的集合而言，由程序员来说明循环的范围是多余的。因此 C++11 中引入了基于范围的 for 循环。for 循环后的括号由冒号':'分为两部分：第一部分是范围内用于迭代的变量，第二部分则表示被迭代的范围，自动迭代，自动取数据，自动判断结束。范围 for 可以作用到数组和容器对象上进行遍历，其底层替换为迭代器。
| 函数名称 | 功能说明 |
|---|---|
| string() （重点） | 构造空的 string 类对象，即空字符串 |
| string(const char* s) （重点） | 用 C-string 来构造 string 类对象 |
| string(size_t n, char c) | string 类对象中包含 n 个字符 c |
| string(const string&s) （重点） | 拷贝构造函数 |
| 函数名称 | 功能说明 |
|---|---|
| size（重点） | 返回字符串有效字符长度 |
| length | 返回字符串有效字符长度 |
| capacity | 返回空间总大小 |
| empty | 检测字符串是否为空串，是返回 true，否则返回 false |
| clear | 清空有效字符（不改变底层空间大小） |
| reserve | 为字符串预留空间 |
| resize | 将有效字符的个数改成 n 个，多出的空间用字符 c 填充 |
注意：
| 函数名称 | 功能说明 |
|---|---|
| operator[] (重点) | 返回 pos 位置的字符，const string 类对象调用 |
| begin + end | begin 获取一个字符的迭代器 + end 获取最后一个字符下一个位置的迭代器 |
| rbegin + rend | 反向迭代器 |
| 范围 for | 遍历 |
| 函数名称 | 功能说明 |
|---|---|
| push_back | 在字符串后尾插字符 c |
| append | 在字符串后追加一个字符串 |
| operator+= (重点) | 在字符串后追加字符串 str |
| c_str (重点) | 返回 C 格式字符串 |
| find + npos (重点) | 从字符串 pos 位置开始往后找字符 c，返回该字符在字符串中的位置 |
| rfind | 从字符串 pos 位置开始往后找字符 c，返回该字符在字符串中的位置 |
| substr | 在 str 中从 pos 位置开始，截取 n 个字符，然后将其返回 |
| 函数 | 功能说明 |
|---|---|
| operator+ | 尽量少用，因为传值返回，导致深拷贝效率低 |
| operator>> (重点) | 输入运算符重载 |
| operator<< (重点) | 输出运算符重载 |
| getline (重点) | 获取一行字符串 |
| relational operators (重点) | 大小比较 |
class string {
public:
//...
private:
char* _str = nullptr;
int _size = 0;
int _capacity = 0;
const static size_t npos;
};
在上面定义的结构当中，其常量 npos 表示字符串末尾之前的所有字符，在 substr 接口中有使用。
const size_t string::npos = -1; // -1 的无符号整数即表示最大值
我们知道无论如何字符串当中末尾总会存'\0'，作为标记。因此在构造字符串 string 时，一定要多开一个空间存'\0'。那如果 new 空间失败呢？采用抛异常的方式，在外进行捕获异常。
在如下一段程序中，将字符串 str 拷贝到 string 当中，但是这样会导致多次析构一块空间导致程序崩溃的问题。
string::string(const char* str) :_str(new char[strlen(str)+1]) { strcpy(_str, str); }
浅拷贝：也称位拷贝，编译器只是将对象中的值拷贝过来。如果对象中管理资源，最后就会导致多个对象共享同一份资源，当一个对象销毁时就会将该资源释放掉，而此时另一些对象不知道该资源已经被释放，以为还有效，所以当继续对资源进行操作时，就会发生发生了访问违规。这种拷贝方式，称为浅拷贝。
深拷贝：不单单是把数据拷贝过去，还需要开一块内存空间，防止指向同一块空间。
string::string(const char* str) :_size(strlen(str)) {
_str = new char[_size + 1]; // 如果失败需要捕获异常
_capacity = _size;
strcpy(_str, str);
}
string::string(size_t n, char ch) :_str(new char[n + 1]) , _size(n) , _capacity(n) {
for (size_t i = 0;i < n;i++) {
_str[i] = ch;
}
_str[_size] = '\0';
}
//析构
string::~string() {
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
拷贝构造： 目标是将 s 中的数据拷贝到_str 中，那我们直接调用 strcpy 函数将 s 数据拷过来即可？
string::string(const string& s) { strcpy(_str, s._str); }
但是这样会导致析构时多次析构一块空间，从而报错（依然是浅拷贝的问题）。
string::string(const string& s) {
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
赋值运算符重载： 特殊情况下可能自己给自己赋值，为了不再拷贝一次做判断。
string& string::operator=(const string& s) {
if (this != &s) {
delete _str;
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}
return *this;
}
实际上，上面的两段代码显得过于笨拙且冗杂，都是老老实实自己手写申请空间。而在如下一段程序当中，借用构造函数来完成拷贝及其赋值。而这种方法，也是实践当中最常用到的现代写法。
void string::swap(string& s) {
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
//拷贝构造简洁化 --> 现代写法
string::string(const string& s) {
string tmp(s._str);
swap(tmp);
}
在如上一段程序当中，通过构造函数构造 tmp。s 这里是引用传参，即出了作用域不会销毁；而 tmp 是属于这个栈内的空间，出了作用域就会销毁。此时我们借助 swap 的特性，将_str 指向的指针进行交换，此时就是*this 指向了新申请的空间，再将个数和空间交换即可。
这样看，和平日写的拷贝构造是差不多的。别着急，我们再来看看赋值运算符重载的简化实现。
string& string::operator=(string s) {
//s 即是拷贝构造过来的
swap(s);
//出了作用域就会析构
return *this;
}
//增容
void string::reserve(size_t n) {
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
迭代器的作用是用来访问容器（用来保存元素的数据结构）中的元素，所以使用迭代器，我们就可以访问容器中里面的元素。那迭代器不就相当于指针一个一个访问容器中的元素吗？并不是，迭代器是像指针一样的行为，但是并不等同于指针，且功能更加丰富，这点需在之后慢慢体会。（本章节体现并不是很明显）
typedef char* iterator;
typedef const char* const_iterator;
iterator begin() { return _str; }
iterator end() { return _str + _size; }
const_iterator begin() const { return _str; }
const_iterator end() const { return _str + _size; }
push_back 插入逻辑：当插入元素大于容器容量时，需进行扩容操作；_size 的位置是'\0'，但直接将插入元素覆盖即可，_size++，重新加上'\0'。
void string::push_back(char x) {
if (_size + 1 > _capacity) {
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size++] = x;
_str[_size] = '\0';
}
append 插入逻辑：计算需要插入字符串的长度 len，若 string 的个数+len 大于容量则需扩容；若个数+len 长度大于 2 倍扩容时，则应扩容到个数+len 容量；往 string 末尾插入字符串。
void string::append(const char* str) {
size_t len = strlen(str);
if (len + _size > _capacity) {
int NewCapacity = 2 * _capacity;
if (len + _size > 2 * _capacity) {
NewCapacity = len + _size;
}
reserve(NewCapacity);
}
strcpy(_str + _size, str);
_size += len;
}
+= 运算符重载逻辑：如果插入的是字符串，则采用 append 函数的逻辑；如果插入的是字符，则采用 push_back 函数的逻辑；无论哪种情况，实现方式都和以上两种代码实现方式是相同的，因此我们可以以复用的方式，更容易维护我们的代码。
string& string::operator+=(const char* str) {
append(str);
return *this;
}
string& string::operator+=(char x) {
push_back(x);
return *this;
}
insert 函数实现逻辑：扩容逻辑与其上是类似的，区别在于插入元素后的数据是从后往前还是从前往后挪动；如果是从前往后挪动，那么会发生覆盖数据的现象，而从后往前就不会，这点在之前也有强调过。
void string::insert(size_t pos, size_t n, char ch) {
assert(pos <= _size);
//扩容
if (_size + n > _capacity) {
// size_t newCapacity = 2 * _capacity;
if (_size + n > 2 * _capacity) {
newCapacity = _size + n;
}
reserve(newCapacity);
}
//int end = _size; //while (end >= (int)pos)//这里不强转会有 err
//{ // _str[end + n] = _str[end]; // --end; //}
size_t end = _size + n;
while (end > pos + n - 1) {
_str[end] = _str[end - n];
--end;
}
for (size_t i = 0;i < n;i++) {
_str[pos + i] = ch;
}
_size += n;
}
扩容逻辑与其上对应重载函数是一样的；一样是需要将 pos 后的位置进行挪动后，思路是类似的，那能否复用上面的实现函数呢？
如果复用上面的函数，那么该往这位置插入的字符串都是相同的一个字符，这样想似乎不能复用。
但是没关系，这些位置刚好是为要插入字符串预留的，那么我们只要将这些位置覆盖一遍即可。
void string::insert(size_t pos, const char* str) {
size_t n = strlen(str);
insert(pos, n, 'x');
for (size_t i = 0;i < n;i++) {
_str[i + pos] = str[i];
}
}
复用：通过牺牲空间方法。
string tmp(n, ch);
insert(pos, tmp.c_str());
vs 下 string 的结构 string 总共占 28 个字节，内部结构稍微复杂一点，先是有有一个联合体，联合体用来定义 string 中字符串的存储空间：
union _Bxty{ // storage for small buffer or pointer to larger one value_type _Buf[_BUF_SIZE]; pointer _Ptr; char _Alias[_BUF_SIZE]; // to permit aliasing } _Bx;
这种设计也是有一定道理的，大多数情况下字符串的长度都小于 16，那 string 对象创建好之后，内部已经有了 16 个字符数组的固定空间，不需要通过堆创建，效率高。其次：还有一个 size_t 字段保存字符串长度，一个 size_t 字段保存从堆上开辟空间总的容量。最后：还有一个指针做一些其他事情。故总共占 16+4+4+4=28 个字节。
vs 下额外定义了个 buff 数组以减少扩容，提高效率。我们同样采用这种思想造类似的轮子。
//cin>>s
istream& operator>>(istream& in, string& s) {
s.clear();
//char ch = in.get(); //while (ch != ' ' && ch != '\n')
//{ // s += ch; // ch = in.get(); //}
//为了减少频繁的扩容，定义一个数组
char buff[1024];
char ch = in.get();
size_t i = 0;
while (ch != ' ' && ch != '\n') {
buff[i++] = ch;
if (i == 1023) {
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i > 0) {
buff[i] = '\0';
s += buff;
}
return in;
}
//cout<<s
ostream& operator<<(ostream& out, const string& s) {
for (auto ch : s) {
out << ch;
}
return out;
}
实现逻辑：每次输入都往 buff 数组中填入数据；当数据超过 buff 数组容量时，将数组里的数据加到 string 当中，buff 数组从 0 开始继续填入数据；如果 ch==delim 时，不再填入数据，将 buff 数组里剩下的数据加到 string 当中。
istream& getline(istream& is, string& s, char delim) {
char buff[1024];
char ch = is.get();
size_t i = 0;
while (ch != delim) {
buff[i++] = ch;
if (i == 1023) {
buff[i] = '\0';
s += buff;
i = 0;
}
ch = is.get();
}
if (i > 0) {
buff[i] = '\0';
s += buff;
}
return is;
}
string.h
#pragma once
#include<iostream>
#include<string.h>
#include<assert.h>
using namespace std;
namespace egoist {
class string {
public:
//迭代器
typedef char* iterator;
typedef const char* const_iterator;
iterator begin() { return _str; }
iterator end() { return _str + _size; }
const_iterator begin() const { return _str; }
const_iterator end() const { return _str + _size; }
//计算串的 size 和 capacity
size_t size() const { return _size; }
size_t capacity() const { return _capacity; }
//构造函数
string(const char*);
string(size_t n, char ch);
//交换
void swap(string& s);
//拷贝构造
string(const string& s);
const char* c_str() const { return _str; }
void reserve(size_t n);
void push_back(char x);
void append(const char* str);
////=重载运算符
//string& operator=(const string& s);
//现代简洁化
string& operator=(string s);
string& operator+=(const char* str);
string& operator+=(char x);
//比较大小
bool operator==(const string& s) const;
bool operator!=(const string& s) const;
bool operator<(const string& s) const;
bool operator<=(const string& s) const;
bool operator>(const string& s) const;
bool operator>=(const string& s) const;
//[]运算符重载
char& operator[](size_t pos) { assert(pos < _size); assert(pos >= 0); return _str[pos]; }
const char& operator[](size_t pos) const { assert(pos < _size); assert(pos >= 0); return _str[pos]; }
void insert(size_t pos, size_t n, char ch);
void insert(size_t pos, const char* str);
void erase(size_t pos = 0, size_t len = npos);
size_t find(char ch, size_t pos = 0);
size_t find(const char* str, size_t pos = 0);
void clear() { _str[0] = '\0'; _size = 0; }
string substr(size_t pos, size_t len = npos);
//析构
~string();
private:
char* _str = nullptr;
int _size = 0;
int _capacity = 0;
const static size_t npos;
};
//cout<<s
ostream& operator<<(ostream& out, const string& s);
//cin>>s
istream& operator>>(istream& in, string& s);
istream& getline(istream& is, string& s, char delim = '\n');
}
string.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"string.h"
namespace egoist {
const size_t string::npos = -1;
string::string(const char* str) :_size(strlen(str)) {
_str = new char[_size + 1]; // 如果失败需要捕获异常
_capacity = _size;
strcpy(_str, str);
}
string::string(size_t n, char ch) :_str(new char[n + 1]) , _size(n) , _capacity(n) {
for (size_t i = 0;i < n;i++) {
_str[i] = ch;
}
_str[_size] = '\0';
}
////拷贝构造
//string::string(const string& s)
//{
// _str = new char[s._capacity + 1];
// strcpy(_str, s._str);
// _size = s._size;
// _capacity = s._capacity;
//}
void string::swap(string& s) {
std::swap(_str, s._str);
std::swap(_size, s._size);
std::swap(_capacity, s._capacity);
}
//拷贝构造简洁化 --> 现代写法
string::string(const string& s) {
string tmp(s._str);
swap(tmp);
}
void string::reserve(size_t n) {
//需要增容 --> 为了和 new 配套使用，不用 realloc
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[] _str;
_str = tmp;
_capacity = n;
}
void string::push_back(char x) {
if (_size + 1 > _capacity) {
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size++] = x;
_str[_size] = '\0';
}
void string::append(const char* str) {
size_t len = strlen(str);
if (len + _size > _capacity) {
int NewCapacity = 2 * _capacity;
if (len + _size > 2 * _capacity) {
NewCapacity = len + _size;
}
reserve(NewCapacity);
}
strcpy(_str + _size, str);
_size += len;
}
//=运算符重载
//string& string::operator=(const string& s)
//{
// if (this != &s)
// {
// delete _str;
// _str = new char[s._capacity + 1];
// strcpy(_str, s._str);
// _size = s._size;
// _capacity = s._capacity;
// }
// return *this;
//}
//现代简洁化 --> 通过调用拷贝构造
string& string::operator=(string s) {
//s 即是拷贝构造过来的
swap(s);
//出了作用域就会析构
return *this;
}
string& string::operator+=(const char* str) {
append(str);
return *this;
}
string& string::operator+=(char x) {
push_back(x);
return *this;
}
//比较大小
bool string::operator==(const string& s) const {
return strcmp(_str, s._str) == 0;
}
bool string::operator!=(const string& s) const {
return !(*this == s);
}
bool string::operator<(const string& s) const {
return strcmp(_str, s._str) < 0;
}
bool string::operator<=(const string& s) const {
return (*this < s) || (*this == s);
}
bool string::operator>(const string& s) const {
return !(*this <= s);
}
bool string::operator>=(const string& s) const {
return !(*this < s);
}
void string::insert(size_t pos, size_t n, char ch) {
assert(pos <= _size);
//扩容
if (_size + n > _capacity) {
// size_t newCapacity = 2 * _capacity;
if (_size + n > 2 * _capacity) {
newCapacity = _size + n;
}
reserve(newCapacity);
}
//int end = _size; //while (end >= (int)pos)//这里不强转会有 err
//{ // _str[end + n] = _str[end]; // --end; //}
size_t end = _size + n;
while (end > pos + n - 1) {
_str[end] = _str[end - n];
--end;
}
for (size_t i = 0;i < n;i++) {
_str[pos + i] = ch;
}
_size += n;
}
void string::insert(size_t pos, const char* str) {
////由于高度相似，可采用复用
//assert(pos <= _size);
//size_t n = strlen(str);
////扩容
//if (_size + n > _capacity)
//{
// // // size_t newCapacity = 2 * _capacity;
// if (_size + n > 2 * _capacity)
// {
// newCapacity = _size + n;
// }
// reserve(newCapacity);
//}
//size_t end = _size + n;
//while (end > pos + n - 1)
//{
// _str[end] = _str[end - n];
// --end;
//}
size_t n = strlen(str);
insert(pos, n, 'x');
for (size_t i = 0;i < n;i++) {
_str[i + pos] = str[i];
}
//通过牺牲空间方法复用
/*string tmp(n, ch);
insert(pos, tmp.c_str());*/
}
void string::erase(size_t pos, size_t len) {
assert(pos >= 0);
if (len > _size - pos) {
_str[pos] = '\0';
_size = pos;
} else {
for (size_t i = pos;i <= _size;i++) {
_str[i] = _str[i + len];
}
_size -= len;
}
}
size_t string::find(char ch, size_t pos) {
for (size_t i = pos;i < _size;i++) {
if (_str[i] == ch) return i;
}
return npos;
}
size_t string::find(const char* str, size_t pos) {
const char* p = strstr(_str + pos, str);
if (p == nullptr) {
return npos;
} else {
return p - _str;
}
}
string string::substr(size_t pos, size_t len) {
size_t leftlen = _size - pos;
if (len > leftlen) len = leftlen;
string tmp;
tmp.reserve(len);
for (size_t i = 0; i < len; i++) {
tmp += _str[pos + i];
}
return tmp;
}
string::~string() {
delete[] _str;
_str = nullptr;
_size = _capacity = 0;
}
//cout<<s
ostream& operator<<(ostream& out, const string& s) {
for (auto ch : s) {
out << ch;
}
return out;
}
//cin>>s
istream& operator>>(istream& in, string& s) {
s.clear();
//char ch = in.get(); //while (ch != ' ' && ch != '\n')
//{ // s += ch; // ch = in.get(); //}
//为了减少频繁的扩容，定义一个数组
char buff[1024];
char ch = in.get();
size_t i = 0;
while (ch != ' ' && ch != '\n') {
buff[i++] = ch;
if (i == 1023) {
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i > 0) {
buff[i] = '\0';
s += buff;
}
return in;
}
istream& getline(istream& is, string& s, char delim) {
char buff[1024];
char ch = is.get();
size_t i = 0;
while (ch != delim) {
buff[i++] = ch;
if (i == 1023) {
buff[i] = '\0';
s += buff;
i = 0;
}
ch = is.get();
}
if (i > 0) {
buff[i] = '\0';
s += buff;
}
return is;
}
}
写时拷贝就是一种拖延症，是在浅拷贝的基础之上增加了引用计数的方式来实现的。引用计数：用来记录资源使用者的个数。在构造时，将资源的计数给成 1，每增加一个对象使用该资源，就给计数增加 1，当某个对象被销毁时，先给该计数减 1，然后再检查是否需要释放资源，如果计数为 1，说明该对象是资源的最后一个使用者，将该资源释放；否则就不能释放，因为还有其他对象在使用该资源。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online