【c++】string的底层实现
·
前言
C++ 中的 std::string 是日常开发最常用的字符串容器，相比 C 语言裸 char* 字符串，封装了内存管理、扩容、拷贝、拼接、查找等能力，自动处理内存分配释放，规避野指针、越界、内存泄漏问题。
很多人只会调用 +=、size()、substr()，却不清楚底层内存怎么存、扩容规则、深浅拷贝、短字符串优化，本文结合标准库原理 + 手写简易 string，彻底吃透底层。
在这里的底层实现仅仅是简单实现。
为了更方便观察与测试，和之前一样建立三个文件分别是声明、定义、测试。
声明与定义
先将整体架构给写出来
#pragma once
#include<iostream>
#include<string>
#include<assert.h>
using namespace std;
namespace XU
{
class string
{
public:
private:
char* _str;
size_t _size;
size_t _capacity;
static const szie_t npos;
}
}
string就是针对字符串的顺序表因此private很显然，与顺序表中的变量是一样的。这里在这用一个域进行封装是为了后续进行操作时方便。这里的npos是为了代表失败或不存在，值为-1。
接着就是对功能的声明与定义。有一些常用的就直接在声明直接就进行定义了（内联函数），一些不常用的进行声明与定义分离。
内联函数
构造函数（给变量进行初始化）
string(const char* str = " ")
{
_size = strlen(str);
_capacity = _size;
_str = new char[_capacity + 1];
strcpy(_str, str);
}new的时候加的1是给\0的空间。成员列表进行初始化需要按照private中变量的定义顺序进行由于_strz在最前面无法进行列表初始化。
静态变量不能再类中初始化需要在类外单独初始化。
const size_t string::npos=-1;拷贝构造（深拷贝）
string(const string& s)
{
_str = new char[s._capacity + 1];
strcpy(_str, s._str);
_size = s._size;
_capacity = s._capacity;
}这是传统的一种方式。接下来写一个现代的方式
string(const String& s)
: _str(nullptr)
{
string strTmp(s._str);
swap(_str, strTmp._str);
//swap(strTmp)
}意思就是将创建一个新的串对象strtmp并将其初始化为s._str，然后再将_str的值与strtmp值进行交换。注销掉的代码也可以执行是因为在这里面有隐含的this指针。
因为串中的赋值底层与拷贝很像因此接下来实现重载赋值
重载赋值（s1=s2)
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& operator=(const String& s)
{
if (this != &s)
{
string strTmp(s);
swap(_str, strTmp._str);
}
return *this;
}
这里的逻辑与上面拷贝的一样
然后就是析构函数
析构函数
~string()
{
delete[]_str;
_str=nillptr;
_size=_capacity=0;
} 然后是对迭代器的实现
迭代器
当然这里的逻辑很简单
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;
}接下来还比较重要的就是重载[ ]其可以是strig像数组一样是使用。
重载[ ]
//重载[]
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];
}然后就是对一些私有的变量进行声明，使得这些变量在类外面也可以使用
对private成员变量的使用
/使用私有的_str
const char* c_str()const
{
return _str;
}
//使用私有的_size
size_t size()const
{
return _size;
}
//使用私有的_capacity
size_t capacity()const
{
return _capacity;
}
非内联函数
首先是reserve这个还是比较重要的插入时必须的判断空间是否足够
reserve
void string::reserve(size_t n)
{
if (n > _capacity)
{
char* tmp = new char[n + 1];
strcpy(tmp, _str);
delete[]_str;
_str = tmp;
_capacity = n;
}
}
push_back
这里是尾插一个字符
void string::push_back(char ch)
{
if (_size >= _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
_str[_size++] = ch;
_str[_size + 1] = '\0';
}append
这里就相当与尾插了一个字符串（多个字符）
void string::append(const char* str)
{
int len=strlen(str);
if (_size + len >= _capacity)
{
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
}
strcpy(_str + _size, str);
_size += len;
}
重载+=
重载了上面的两种情况
string& string:: operator+=(char ch)
{
push_back(ch);
return *this;
}
string& string::operator+=(const char* str)
{
append(str);
return *this;
}insert
这里的插入也分为两种插入一个字符与插入多个字符
//这里的插入逻辑都与顺序表一样
void string::insert(size_t pos, char ch)
{
if (_size >= _capacity)
{
reserve(_capacity == 0 ? 4 : 2 * _capacity);
}
for (int i = _size + 1; i > pos; i--)
{
_str[i] = _str[i - 1];
}
_str[pos] = ch;
_size++;
}
void string::insert(size_t pos, const char* str)
{
int len = strlen(str);
if (_size + len >= _capacity)
{
reserve(_size + len > 2 * _capacity ? _size + len : 2 * _capacity);
}
for (int i = _size + len; i > pos; i--)
{
_str[i] = _str[i - len];
}
//将新的string片段插入原来的string中
for (int i = 0; i < len; i++)
{
_str[pos + i] = str[i];
}
_size += len;
}
左边是插入一个字符，右边是插入多个字符
delete
删除又有两种情况一种是后面全部删除，另一种删除固定字符
void string::erase(size_t pos, size_t len )
{
assert(pos < _size);
if (pos + len > _size)
{
_str[pos] = '\0';
_size = pos;
}
else
{
for (int i = pos + len; i < _size; i++)
{
_str[i - len] = _str[i];
}
}
_size -= len;
}这里是第一种逻辑图
这里是第二种逻辑图
find
size_t string::find(char ch, size_t pos)
{
assert(pos < _size);
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)
{
assert(pos < _size);
const char* ptr = strstr(_str + pos, str);
if (ptr == NULL)
{
return npos;
}
else
{
return ptr - _str;
}
}substr
string string::substr(size_t pos , size_t len)
{
assert(pos < _size);
if (len > _size - pos)
{
len = _size - pos;
}
string sub;
sub.reserve(len);
for (size_t i = 0; i < len; i++)
{
sub += _str[pos + i];
}
return sub;
}重载比大小的符号
记住重载类似的符号时先自己实现两个，其余的直接重载定义过的。
bool operator <(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) < 0;
}
bool operator <=(const string& s1, const string& s2)
{
return s1 < s2 || s1 == s2;
}
bool operator >=(const string& s1, const string& s2)
{
return !(s1 < s2);
}
bool operator >(const string& s1, const string& s2)
{
return !(s1 <= s2);
}
bool operator ==(const string& s1, const string& s2)
{
return strcmp(s1.c_str(), s2.c_str()) == 0;
}
bool operator !=(const string& s1, const string& s2)
{
return !(s1 == s2);
}重载流插入和流提取
这一部分写在了类的外面，是因为这两个用不到成员函数和园，因此也没有声明成友元函数。
ostream& operator <<(ostream& out, const string& s)
{
for (auto ch : s)
{
out << ch;
}
return out;
}
istream& operator >>(istream& in, string& s)
{
s.clear();
const int N = 256;
char buff[N];
int i = 0;
char ch;
ch = in.get();
while (ch != ' ' && ch != '\n')
{
buff[i++] = ch;
if (i == N - 1)
{
buff[i] = '\0';
s += buff;
i = 0;
}
ch = in.get();
}
if (i > 0)
{
buff[i] = '\0';
s += buff;
}
return in;
}在这里我所介绍的功能就结束了。
上面我将声明与定义本该分开写的我放在了一起，方便介绍。也就是前两个部分已经介绍完成接下来是测试环节。
测试
namespace bit
{
void test_string1()
{
string s1;
string s2("hello world");
cout << s1.c_str() << endl;
cout << s2.c_str() << endl;
for (size_t i = 0; i < s2.size(); i++)
{
s2[i] += 2;
}
cout << s2.c_str() << endl;
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
string::iterator it = s2.begin();
while (it != s2.end())
{
//*it += 2;
cout << *it << " ";
++it;
}
cout << endl;
}
void test_string2()
{
string s1("hello world");
s1 += 'x';
s1 += '#';
cout << s1.c_str() << endl;
s1 += "hello bit";
cout << s1.c_str() << endl;
s1.insert(5, '$');
cout << s1.c_str() << endl;
s1.insert(0, '$');
cout << s1.c_str() << endl;
string s2("hello world");
cout << s2.c_str() << endl;
s2.insert(5, "$$$");
cout << s2.c_str() << endl;
s2.insert(0, "$$$&&&&&&&&&&&&&&&&&&&&&&&&&&&&&");
cout << s2.c_str() << endl;
}
void test_string3()
{
string s1("hello world");
s1.erase(6, 100);
cout << s1.c_str() << endl;
string s2("hello world");
s2.erase(6);
cout << s2.c_str() << endl;
string s3("hello world");
s3.erase(6, 3);
cout << s3.c_str() << endl;
}
void test_string4()
{
string s("test.cpp.zip");
size_t pos = s.find('.');
string suffix = s.substr(pos);
cout << suffix.c_str() << endl;
string copy(s);
cout << copy.c_str() << endl;
s = suffix;
cout << suffix.c_str() << endl;
cout << s.c_str() << endl;
s = s;
cout << s.c_str() << endl;
}
void test_string5()
{
string s1("hello world");
string s2("hello world");
cout << (s1 < s2) << endl;
cout << (s1 == s2) << endl;
cout << ("hello world" < s2) << endl;
cout << (s1 == "hello world") << endl;
//cout << ("hello world" == "hello world") << endl;
cout << s1 << s2 << endl;
string s0;
cin >> s0;
cout << s0 << endl;
}
}
int main()
{
//bit::test_string5();
// 编码 值和符号映射编码关系
// 文字 -- 符号
// 内存和磁盘只有0101
//char buff[] = "apple sort";
char buff[4];
buff[0] = 97;
buff[1] = 98;
buff[2] = 99;
buff[3] = 0;
cout << buff << endl;
char str[] = "牛马";
cout << strlen(str) << endl;
str[1]++;
cout << str << endl;
str[3]--;
cout << str << endl;
str[1]++;
cout << str << endl;
str[3]--;
cout << str << endl;
return 0;
}到这里介绍完毕感谢支持!!!
更多推荐
4
0- 0
已为社区贡献2条内容
所有评论(0)