C++中string的底层实现,关于string的一切在你面前轻松拿捏

酷酷的崽798 2024-10-20 11:05:01 阅读 56

文章目录

字符串类模拟介绍string实现的头文件string头文件的解析构造函数基本功能迭代器容量与大小管理字符串操作比较运算符string实现的源文件

string源文件的解析内存管理与构造函数字符的插入与删除字符串搜索高级字符串操作源文件中的比较运算符输入和输出操作符的重载<<>>

自定义 getline 函数的实现

建议:

字符串类模拟介绍

C++ 中的 std::string 是最常用的数据结构之一。然而,深入了解它的底层实现机制,可以显著提升你对内存管理和数据操作的理解。

本教程中,我们将通过使用动态内存分配(new 和 delete)模拟一个基本的字符串类 bit::string。通过这个过程,你将深入学习以下概念:

动态内存分配。

手动字符串处理。

迭代器的使用。

字符串操作如插入、删除、连接等。

bit::string 类的实现分为两个部分:

头文件:声明类的接口。

源文件:提供这些方法的具体实现。

string实现的头文件

下面是关于string的常用的一些底层实现

<code>#pragma once

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<assert.h>

using namespace std;

namespace bit

{ -- -->

class string

{

public:

//string();

using iterator = char*;

using const_iterator = const char*;

string(const char* str = " ");

string(const string& s);

string& operator=(const string& s);

~string();

void reserve(size_t n);

void push_back(char ch);

void append(const char* str);

string& operator +=(char ch);

string& operator +=(const char* str);

void insert(size_t pos,char ch);

void insert(size_t pos,const char* str);

void erase(size_t pos, size_t len = npos);

size_t find(char ch, size_t pos = 0);

size_t find(const char* str, size_t pos = 0);

char& operator[](size_t i)

{

assert(i < _size);

return _str[i];

}

const char& operator[](size_t i) const

{

assert(i < _size);

return _str[i];

}

iterator begin()

{

return _str;

}

iterator end()

{

return _str + _size;

}

const_iterator begin() const

{

return _str;

}

const_iterator end() const

{

return _str + _size;

}

size_t size() const

{

return _size;

}

const char* c_str() const

{

return _str;

}

void clear()

{

_str[0] = '\0';

_size = 0;

}

string substr(size_t pos, size_t len = npos);

private:

char* _str = nullptr;

size_t _size = 0;

size_t _capacity = 0;

public:

//const 静态可以给值 特殊处理只有整型可以

//static const size_t npos = -1;

static const size_t npos;

};

bool operator== (const string& lhs, const string& rhs);

bool operator!= (const string& lhs, const string& rhs);

bool operator> (const string& lhs, const string& rhs);

bool operator< (const string& lhs, const string& rhs);

bool operator>= (const string& lhs, const string& rhs);

bool operator<= (const string& lhs, const string& rhs);

ostream& operator<<(ostream& os, const string& str);

istream& operator>>(istream& is, string& str);

istream& getline(istream& is, string& str, char delim);

}

string头文件的解析

首先,我们来看看头文件的内容。头文件声明了 bit::string 类及其成员函数,还包括了一些重要的运算符和函数,用于模拟字符串的各种操作。

类声明

namespace bit {

class string {

public:

using iterator = char*;

using const_iterator = const char*;

string(const char* str = " ");

string(const string& s);

string& operator=(const string& s);

~string();

在这里,string 类位于 bit 命名空间下。我们定义了一些关键组件,包括构造函数、赋值运算符和析构函数。接下来,我们将逐步解析每个部分。

构造函数

string 类提供了以下构造函数:

默认构造函数:带有默认参数,初始化字符串为一个空格(" ")。

拷贝构造函数:实现深拷贝,允许用一个字符串对象初始化另一个字符串对象。

赋值运算符:用于将一个字符串对象赋值给另一个对象。

基本功能

void reserve(size_t n);

void push_back(char ch);

void append(const char* str);

string& operator+=(char ch);

string& operator+=(const char* str);

这些基本功能函数实现了:

reserve():预留空间,避免频繁的重新分配内存。

push_back():向字符串末尾添加单个字符。

append():向字符串末尾添加整个字符串。

operator+=():将字符或字符串追加到当前字符串对象。

迭代器

迭代器为遍历字符串提供了机制:

iterator begin();

iterator end();

const_iterator begin() const;

const_iterator end() const;

begin() 和 end() 方法分别返回字符串起始和结束的指针,允许我们使用标准迭代器风格来遍历字符串中的字符。

容量与大小管理

字符串的大小和容量是两个关键的概念:

size():返回字符串中当前字符的数量。

reserve():提前分配一定的内存容量,以减少频繁的内存重分配。

size_t size() const;

void reserve(size_t n);

通过提前分配内存,可以提升性能,避免每次添加新字符时都进行内存扩展操作。

字符串操作

字符串类提供了一些常见的操作,如插入、删除、查找等。

void insert(size_t pos, char ch);

void insert(size_t pos, const char* str);

void erase(size_t pos, size_t len = npos);

size_t find(char ch, size_t pos = 0);

size_t find(const char* str, size_t pos = 0);

insert():在指定位置插入字符或字符串。

erase():从指定位置删除一段字符串。

find():查找字符或子串在字符串中的位置。

比较运算符

自定义的字符串类中需要重载比较运算符,使得字符串可以用来进行比较。

bool operator==(const string& lhs, const string& rhs);

bool operator!=(const string& lhs, const string& rhs);

bool operator<(const string& lhs, const string& rhs);

bool operator>(const string& lhs, const string& rhs);

bool operator<=(const string& lhs, const string& rhs);

bool operator>=(const string& lhs, const string& rhs);

通过重载这些比较运算符,字符串对象可以通过==、!=、<、>等符号进行直接比较,从而简化字符串的比较逻辑。

string实现的源文件

#define _CRT_SECURE_NO_WARNINGS 1

#include"string.h"

using namespace std;

namespace bit

{

const size_t string::npos = -1;

/*string::string()

:_str(new char[1] {'\0'})

, _size(0)

, _capacity(0)

{}*/

string::string(const char* str)

: _size(strlen(str))

{

_capacity = _size;

_str = new char[_size + 1];

strcpy(_str, str);

}

//s2(s1)

string::string(const string& s)

{

_str = new char[s._capacity + 1];

strcpy(_str, s._str);

_size = s._size;

_capacity = s._capacity;

}

//s1 = s3

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()

{

delete[] _str;

_str = nullptr;

_size = 0;

_capacity = 0;

}

void string::reserve(size_t n)

{

if (n > _capacity)

{

char* tmp = new char[n + 1];

strcpy(tmp, _str);

delete[] _str;

_str = tmp;

_capacity = n;

}

}

void string::push_back(char ch)

{

/*if (_size == _capacity)

{

reserve(_capacity == 0 ? 4 : 2 * _capacity);

}

_str[_size++] = ch;*/

insert(_size, ch);

}

void string::append(const char* str)

{

size_t len = strlen(str);

if (_size + len > _capacity)

{

size_t newCapacity = 2 * _capacity;

if (newCapacity < _size + len)

{

newCapacity = _size + len;

}

reserve(newCapacity);

}

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;

}

void string::insert(size_t pos, char ch)

{

assert(pos <= _size);

if (_size == _capacity)

{

reserve(_capacity == 0 ? 4 : 2 * _capacity);

}

/*size_t end = _size;

while (end >= (int)pos)

{

_str[end + 1] = _str[end];

--end;

}*/

size_t end = _size + 1;

while (end > pos)

{

_str[end] = _str[end - 1];

--end;

}

_str[pos] = ch;

_size++;

}

void string::insert(size_t pos, const char* str)

{

assert(pos <= _size);

size_t len = strlen(str);

if (_size + len > _capacity)

{

size_t newCapacity = 2 * _capacity;

if (newCapacity < _size + len)

{

newCapacity = _size + len;

}

reserve(newCapacity);

}

int end = _size;

while (end >= (int)pos)

{

_str[end + len] = _str[end];

--end;

}

for (size_t i = 0; i < len; i++)

{

_str[i + pos] = str[i];

}

_size += len;

}

void string::erase(size_t pos, size_t len)

{

assert(pos < _size);

if (len >= _size + pos)

{

_str[pos] = '\0';

_size = pos;

}

else

{

// 从后往前挪

size_t end = pos + len;

while (end <= _size)

{

_str[end - len] = _str[end];

++end;

}

_size -= len;

}

}

size_t string::find(char ch, size_t pos)

{

assert(pos < _size);

for (size_t i = pos; i < _size; i++)

{

if (ch == _str[i])

return i;

}

return npos;

}

size_t string::find(const char* str, size_t pos)

{

assert(pos < _size);

const char* p1 = strstr(_str + pos, str);

if (p1 == nullptr)

{

return npos;

}

else

{

return p1 - _str;

}

}

string string::substr(size_t pos, size_t len)

{

assert(pos < _size);

// 大于后面剩余串的长度,则直接取到结尾

if (len > (_size - pos))

{

len = _size - pos;

}

bit::string sub;

sub.reserve(len);

for (size_t i = 0; i < len; i++)

{

sub += _str[pos + i];

}

//cout << sub.c_str() << endl;

return sub;

}

bool operator== (const string& lhs, const string& rhs)

{

return strcmp(lhs.c_str(), rhs.c_str()) == 0;

}

bool operator!= (const string& lhs, const string& rhs)

{

return !(lhs == rhs);

}

bool operator> (const string& lhs, const string& rhs)

{

return !(lhs <= rhs);

}

bool operator< (const string& lhs, const string& rhs)

{

return strcmp(lhs.c_str(), rhs.c_str()) < 0;

}

bool operator>= (const string& lhs, const string& rhs)

{

return !(lhs < rhs);

}

bool operator<= (const string& lhs, const string& rhs)

{

return lhs < rhs || lhs == rhs;

}

ostream& operator<<(ostream& os, const string& str)

{

//os<<'"';

//os << "xx\"xx";

for (size_t i = 0; i < str.size(); i++)

{

//os << str[i];

os << str[i];

}

//os << '"';

return os;

}

istream& operator>>(istream& is, string& str)

{

str.clear();

char ch;

//is >> ch;

ch = is.get();

while (ch != ' ' && ch != '\n')

{

str += ch;

ch = is.get();

}

return is;

}

istream& getline(istream& is, string& str, char delim)

{

str.clear();

int i = 0;

char buff[256];

char ch;

ch = is.get();

while (ch != delim)

{

// 放到buff

buff[i++] = ch;

if (i == 255)

{

buff[i] = '\0';

str += buff;

i = 0;

}

ch = is.get();

}

if (i > 0)

{

buff[i] = '\0';

str += buff;

}

return is;

}

}

string源文件的解析

接下来,我们详细剖析源文件中的实现逻辑。

内存管理与构造函数

内存管理是字符串类的核心,尤其是在动态分配和释放内存时。我们来看构造函数、析构函数以及赋值运算符的实现。

string::string(const char* str)

: _size(strlen(str)) {

_capacity = _size;

_str = new char[_size + 1];

strcpy(_str, str);

}

这里首先获取输入字符串的长度,并分配足够的空间(包括终止符 \0)。

将输入字符串复制到内部的字符数组 _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::insert(size_t pos, char ch) {

assert(pos <= _size);

if (_size == _capacity) {

reserve(_capacity == 0 ? 4 : 2 * _capacity);

}

size_t end = _size + 1;

while (end > pos) {

_str[end] = _str[end - 1];

--end;

}

_str[pos] = ch;

_size++;

}

在指定位置插入字符时,首先确保容量足够,然后通过移动字符的位置,为新字符腾出空间。

void string::erase(size_t pos, size_t len) {

assert(pos < _size);

if (len >= _size + pos)

{

_str[pos] = '\0';

_size = pos;

} else

{

size_t end = pos + len;

while (end <= _size)

{

_str[end - len] = _str[end];

++end;

}

_size -= len;

}

}

在删除操作中,首先检查位置 pos 是否合法,然后通过移动后续字符,覆盖要删除的部分,最后调整字符串的大小 _size。

字符串搜索

字符串的查找功能也是常见需求之一。bit::string 提供了对字符和子串的查找功能。

size_t string::find(char ch, size_t pos) {

assert(pos < _size);

for (size_t i = pos; i < _size; ++i) {

if (ch == _str[i]) {

return i;

}

}

return npos;

}

这个方法从 pos 位置开始,遍历字符串寻找指定的字符。如果找到,则返回字符的下标;否则,返回 npos(表示未找到)。

size_t string::find(const char* str, size_t pos) {

assert(pos < _size);

const char* p = strstr(_str + pos, str);

if (p == nullptr) {

return npos;

} else {

return p - _str;

}

}

对于子串的查找,利用了 strstr 函数从 pos 位置开始查找子串。如果找到,返回子串在原字符串中的起始位置;否则,返回 npos。

高级字符串操作

字符串截取和拼接是高级操作的体现,bit::string 同样提供了这些功能。

string string::substr(size_t pos, size_t len) {

assert(pos < _size);

// 如果指定的长度大于从起始位置到结尾的长度,调整为剩余的长度

if (len > (_size - pos)) {

len = _size - pos;

}

bit::string sub;

sub.reserve(len); // 为子串分配足够的空间

for (size_t i = 0; i < len; ++i) {

sub += _str[pos + i];

}

return sub;

}

这个 substr() 方法允许从当前字符串中截取子串。首先,它检查位置和长度的合法性,然后通过复制指定范围内的字符,生成并返回一个新字符串。

源文件中的比较运算符

在实现自定义的 bit::string 类时,我们需要为其定义比较运算符,以便进行字符串的比较。以下是重载的运算符。

bool operator==(const string& lhs, const string& rhs) {

return strcmp(lhs.c_str(), rhs.c_str()) == 0;

}

bool operator!=(const string& lhs, const string& rhs) {

return !(lhs == rhs);

}

bool operator<(const string& lhs, const string& rhs) {

return strcmp(lhs.c_str(), rhs.c_str()) < 0;

}

bool operator>(const string& lhs, const string& rhs) {

return !(lhs <= rhs);

}

bool operator<=(const string& lhs, const string& rhs) {

return lhs < rhs || lhs == rhs;

}

bool operator>=(const string& lhs, const string& rhs) {

return !(lhs < rhs);

}

这些比较运算符的实现基于 C 标准库中的 strcmp 函数。strcmp 会返回负值、零或正值,分别对应比较时小于、等于或大于的关系。通过这些重载运算符,用户可以轻松地比较两个 bit::string 对象。

输入和输出操作符的重载

为了方便使用,我们还需要重载 << 和 >> 运算符,以支持 bit::string 对象的输入和输出操作。

<<

ostream& operator<<(ostream& os, const string& str) {

for (size_t i = 0; i < str.size(); ++i) {

os << str[i];

}

return os;

}

通过重载 <<,我们可以将 bit::string 对象输出到标准输出流或文件输出流中。循环遍历字符串中的每个字符并输出到 os 中。

>>

istream& operator>>(istream& is, string& str) {

str.clear(); // 清空当前字符串内容

char ch;

ch = is.get(); // 逐个读取字符

while (ch != ' ' && ch != '\n') {

str += ch;

ch = is.get();

}

return is;

}

在 >> 的重载中,我们首先清空字符串,然后逐字符从输入流中读取,直到遇到空格或换行符为止。

自定义 getline 函数的实现

在字符串处理的过程中,读取输入流中的数据是一个非常常见的操作。在 C++ 标准库中,std::getline 函数允许我们从输入流中读取字符串,直到遇到换行符或指定的分隔符。为了在我们的 bit::string 类中也能够实现类似的功能,我们需要重载 getline 函数。

istream& getline(istream& is, string& str, char delim)

{

str.clear(); // 清空字符串,准备接收新的输入。

int i = 0; // 用于记录buff中字符的索引

char buff[256]; // 定义一个临时缓冲区,用于暂时存储从流中读取的字符

char ch;

ch = is.get(); // 从输入流中获取一个字符

while (ch != delim) // 当字符不是分隔符时,继续读取

{

buff[i++] = ch; // 将字符存储到缓冲区中

if (i == 255) // 当缓冲区接近满时,将其内容添加到字符串中

{

buff[i] = '\0'; // 为缓冲区添加结束符

str += buff; // 将缓冲区中的字符添加到字符串中

i = 0; // 重置缓冲区索引

}

ch = is.get(); // 继续从输入流中读取下一个字符

}

// 如果缓冲区中还有未处理的字符,将其添加到字符串中

if (i > 0)

{

buff[i] = '\0'; // 添加结束符

str += buff; // 将剩余的字符追加到字符串中

}

return is; // 返回输入流对象

}

使用场景与优势

这种自定义的 getline 函数非常有用,尤其是在需要处理复杂输入时,比如从文件或网络读取数据。与标准库的 std::getline 类似,这个函数的主要优点是可以自定义分隔符,这使得它非常灵活。

此外,使用缓冲区来暂时存储输入数据可以减少频繁的内存分配操作,从而提高程序的性能,特别是在处理大规模数据时。

建议:

进一步阅读与学习建议:

C++ Primer - 这是一本经典的 C++ 教程书,适合深入学习 C++ 基础与进阶内容。

研究标准库中的 std::string 实现,深入理解它的内存管理、性能优化和接口设计。

希望这篇博客能够帮助你更好地理解 C++ 字符串类的内部实现。如果有任何问题或建议,欢迎在评论区留言!



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。