【c++丨STL】string模拟实现(附源码)

举报
ephemerals__ 发表于 2025/03/21 11:03:54 2025/03/21
【摘要】 前言之前我们学习了STL的第一个容器–string及其常用接口的使用方法,不过仅仅掌握使用方法还不够,面试当中常常会让我们模拟实现STL的某个容器的关键框架。所以今天我们深入string底层,用我们的功底来模拟实现一个简单的string类。本篇博客我们不会将string的所有接口原模原样地实现出来,而是根据string的逻辑,模拟实现一些重点接口函数。 一、头文件(成员变量与函数声明)头文...

前言

之前我们学习了STL的第一个容器–string及其常用接口的使用方法,不过仅仅掌握使用方法还不够,面试当中常常会让我们模拟实现STL的某个容器的关键框架。所以今天我们深入string底层,用我们的功底来模拟实现一个简单的string类。

本篇博客我们不会将string的所有接口原模原样地实现出来,而是根据string的逻辑,模拟实现一些重点接口函数

一、头文件(成员变量与函数声明)

头文件中的内容是类成员以及我们将要实现的接口声明,代码如下:

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;

#pragma once
class String
{
public:
    typedef char* iterator;
    typedef const char* const_iterator;

    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;

    static size_t npos;

    String(const char* str = "");

    String(const String& str);

    String& operator=(String s);

    ~String();

    const char* c_str() const;

    void swap(String& s);

    void clear();

    size_t size() const;
    size_t capacity() const;

    void reserve(size_t n);

    char& operator[](size_t i);
	const char& operator[](size_t i) const;

    void insert(size_t pos, char c);
    void insert(size_t pos, const char* str);
    void push_back(char c);
    void append(const char* str);
    String& operator+=(char c);
    String& operator+=(const char* str);

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

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

    String substr(size_t pos = 0, size_t len = npos) const;
private:
    char* _str;
    size_t _size;
    size_t _capacity;
};
bool operator<(const String& l, const String& r);
bool operator>(const String& l, const String& r);
bool operator<=(const String& l, const String& r);
bool operator>=(const String& l, const String& r);
bool operator==(const String& l, const String& r);
bool operator!=(const String& l, const String& r);
ostream& operator<<(ostream& out, const String& str);
istream& operator>>(istream& in, String& str);

istream& getline(istream& in, String& str, char delim = '\n');

void swap(String& s1, String& s2);

二、源文件(功能实现)

对于上述声明的函数,我们会一一进行实现并分析代码。首先从交换函数开始:

交换两字符串

之前我们就了解到string类中有两个交换函数,一个重载为成员函数,另一个是非成员函数。我们就将二者都实现一下:

void String::swap(String& s)
{
    std::swap(_str, s._str);
    std::swap(_size, s._size);
    std::swap(_capacity, s._capacity);
}

void swap(String& s1, String& s2)
{
    s1.swap(s2);
}

交换函数非常简单,虽然两对象都有各自所维护的内存,但是我们只需要调用标准库中的交换函数交换两指针的指向即可。然后将_size和_capacity也交换一下。

image.png

对于非成员函数般的交换函数,直接调用成员函数即可。

构造函数

String::String(const char* str)
    :_size(strlen(str))
{
    _str = new char[_size + 1] {'\0'};
    _capacity = _size;
    strcpy(_str, str);
}

在构造函数当中,我们首先将元素个数调整为等同于str长度的值,便于将字符串中的内容拷贝给新对象,然后在起始指针处动态开辟内存(注意大小是_size + 1,因为最后一个位置存放 ‘\0’ )。注意我们_capacity的大小是不包含 ‘\0’ 的,但实际开辟的内存大小要大于它。最后,将str中的数据拷贝给_str就好。不传参时,str的内容默认设置为空字符串。

image.png

拷贝构造

String::String(const String& s)
{
    _str = new char[s._capacity + 1] {'\0'};
    strcpy(_str, s._str);
    _size = s._size;
    _capacity = s._capacity;
}

与构造函数的逻辑相同,先开辟空间,然后拷贝数据即可。不过这是传统写法,还有一个现代写法

String::String(const String& s)
{
    String tmp(s._str);
    swap(tmp);
}

仔细观察就会发现,这种写法非常巧妙:首先我们用s中的字符串构造临时对象tmp,然后用swap交换tmp与新对象的内容,这样就很轻松地完成了拷贝构造

image.png

赋值重载

与拷贝构造类似,赋值重载也有传统写法和现代写法:

String& String::operator=(const String& s)
{
    if (this != &s)
    {
        delete[] _str;
        _str = new char[s._capacity + 1] {'\0'};
        strcpy(_str, s._str);
        _size = s._size;
        _capacity = s._capacity;
    }
    return *this;
}
String& String::operator=(String s)
{
    swap(s);
    return *this;
}

在传统写法当中,我们老老实实地销毁原字符串,然后重新开辟空间,再将新字符串拷贝过来…非常麻烦。现代写法当中,我们使用传值传参,构造一份相同的对象s,然后直接交换s与this对象,this对象就被成功赋值,并且等号右边的对象也没有被改动

析构函数

由于我们的字符串是动态开辟的,所以就要显示写析构函数,在对象销毁时释放这些内存:

String::~String()
{
    delete[] _str;
    _str = nullptr;
    _size = _capacity = 0;
}

这里不必多说,写法和c语言实现的顺序表没什么区别。接下来我们开始正式实现常量成员nops和一些比较常用的接口

常量成员npos

常量成员定义如下:

size_t String::npos = -1;

常量成员用无符号整数的-1来表示,是size_t的最大值,它作为一些接口的缺省参数,用于表示“直到字符串结束”。

获取只读字符串

const char* String::c_str() const
{
    return _str;
}

获取只读字符串时,直接返回字符串起始指针即可。注意返回值被const修饰,该字符串不能被外部修改

清除字符串

void String::clear()
{
    _str[0] = '\0';
    _size = 0;
}

清除字符串时,只需将第一个字符设为 ‘\0’ ,然后调整长度为0即可,无需调整空间容量。

容量接口

容量接口便于用户访问字符串的长度或空间容量。

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

增容

void String::reserve(size_t n)
{
    if (n > _capacity)
    {
        char* tmp = new char[n + 1] {'\0'};
        strcpy(tmp, _str);
        delete[] _str;
        _str = tmp;
        _capacity = n;
    }
}

reserve的作用是为字符串预留空间,单位是字节注意:当参数n的值小于已有空间的总大小时,不会改变其大小。当我们实现增容时,首先需要开辟一块n + 1字节的内存空间(最后位置放 ‘\0’ ),然后将数据拷贝到新空间,再释放原来的空间

image.png

接下来,我们开始实现字符串元素访问与遍历相关操作。首先从下标引用开始:

下标引用重载

char& String::operator[](size_t i)
{
    assert(i < _size);
    return _str[i];
}
const char& String::operator[](size_t i) const
{
    assert(i < _size);
    return _str[i];
}

注意:为了确保用户能够修改字符串的内容,函数返回值是字符的引用。对于const对象,内容不能修改,则返回const引用。

迭代器

之前已经提到过,现阶段我们可以将迭代器理解成一种指针,通过解引用来访问数据元素。我们定义String类时,使用指针来模拟迭代器。迭代器定义如下:

typedef char* iterator;
typedef const char* const_iterator;
String::iterator String::begin()
{
    return _str;
}
String::iterator String::end()
{
    return _str + _size;
}
String::const_iterator String::begin() const
{
    return _str;
}
String::const_iterator String::end() const
{
    return _str + _size;
}

注意:我们实现的迭代器接口函数名只有和STL保持一致,才可以支持范围for

让我们使用一下自己的迭代器:

int main()
{
    String str = "hello world";
    for (auto it = str.begin(); it != str.end(); it++)
    {
        cout << *it << ' ';
    }
    cout << endl;
    for (auto e : str)
    {
        cout << e << ' ';
    }
    cout << endl;
    return 0;
}

image.png

字符串插入和删除操作

接下来,我们开始实现string字符串的插入和删除操作。

insert

insert支持指定位置的插入操作,我们首先实现它,后续实现其他插入删除操作时就可以直接调用该接口。代码如下:

void String::insert(size_t pos, char c)
{
    assert(pos <= _size);
    if (_size == _capacity)
    {
        reserve(_capacity == 0 ? 4 : 2 * _capacity);
    }
    for (size_t i = _size; i >= pos; i--)
    {
        _str[i + 1] = _str[i];
        if (i == 0) break;
    }
    _str[pos] = c;
    _size++;
}
void String::insert(size_t pos, const char* str)
{
    assert(pos <= _size);
    size_t len = strlen(str);
    if (len == 0) return;
    if (_size + len > _capacity)
    {
        size_t newcapacity = _capacity * 2;
        if (newcapacity < _size + len)
        {
            newcapacity = _size + len;
        }
        reserve(newcapacity);
    }
    for (size_t i = _size; i >= pos; i--)
    {
        _str[i + len] = _str[i];
        if (i == 0) break;
    }
    for (size_t i = 0; i < len; i++)
    {
        _str[pos + i] = str[i];
    }
    _size += len;
}

第一个函数实现的是字符的插入,第二个是字符串的插入。实现思路类似于顺序表指定位置的插入,这里不再赘述。接下来实现剩余的插入接口:

push_back、append、operator+=

void String::push_back(char c)
{
    insert(_size, c);
}
void String::append(const char* str)
{
    insert(_size, str);
}
String& String::operator+=(char c)
{
    insert(_size, c);
    return *this;
}
String& String::operator+=(const char* str)
{
    insert(_size, str);
    return *this;
}

这三个函数的功能是尾插字符或字符串,直接调用我们刚才实现的insert就可以实现。

erase

erase支持指定位置的删除操作,代码如下:

void String::erase(size_t pos, size_t len)
{
    assert(pos < _size);
    if (pos + len >= _size)
    {
        _str[pos] = '\0';
        _size = pos;
    }
    else
    {
        for (size_t i = pos + len; i <= _size; i++)
        {
            _str[i - len] = _str[i];
        }
        _size -= len;
    }
}

这里的逻辑与顺序表指定位置删除类似,不再多说。

查找

接下来,我们实现查找功能find:

size_t String::find(char c, size_t pos)
{
    assert(pos < _size);
    for (size_t i = pos; i < _size; i++)
    {
        if (_str[i] == c)
        {
            return i;
        }
    }
    return 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;
    }
    return p - _str;
}

查找可分为字符查找和字符串查找,其中字符串查找调用strstr函数即可,注意返回值细节处理。

构造子串

substr可以构造一个string类,内容是原字符串中pos位置开始的len个字符组成的子串。代码如下:

String String::substr(size_t pos, size_t len) const
{
    assert(pos < _size);
    if (len > (_size - pos))
    {
        len = _size - pos;
    }
    String sub;
    for (size_t i = 0; i < len; i++)
    {
        sub += _str[pos + i];
    }
    return sub;
}

compare

compare指的是一些字符串之间的比较函数,属于非成员函数,实现方法也很简单:

bool operator<(const String& l, const String& r)
{
    return strcmp(l.c_str(), r.c_str()) < 0;
}
bool operator>(const String& l, const String& r)
{
    return !(l <= r);
}
bool operator<=(const String& l, const String& r)
{
    return (l == r || l < r);
}
bool operator>=(const String& l, const String& r)
{
    return (l == r || l > r);
}
bool operator==(const String& l, const String& r)
{
    return strcmp(l.c_str(), r.c_str()) == 0;
}
bool operator!=(const String& l, const String& r)
{
    return !(l == r);
}

输入和输出

最后要实现的就是输入和输出。它们可以让我们直接配合cin和cout去操作我们自己的string类。 注意这里的细节处理

ostream& operator<<(ostream& out, const String& str)
{
    for (auto ch : str)
    {
        out << ch;
    }
    return out;
}
istream& operator>>(istream& in, String& str)
{
    str.clear();
    char ch = in.get();
    while (ch != ' ' && ch != '\n')
    {
        str += ch;
        ch = in.get();
    }
    return in;
}

接下来我们再实现一个自定义读取结束符的getline函数:

istream& getline(istream& in, String& str, char delim)
{
    str.clear();
    char ch = in.get();
    while (ch != delim)
    {
        str += ch;
        ch = in.get();
    }
    return in;
}

三、程序全部代码

我们模拟实现string类的全部代码如下:

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstring>
using namespace std;

#pragma once
class String
{
public:
    typedef char* iterator;
    typedef const char* const_iterator;

    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;

    static size_t npos;

    String(const char* str = "");

    String(const String& str);

    String& operator=(String s);

    ~String();

    const char* c_str() const;

    void swap(String& s);

    void clear();

    size_t size() const;
    size_t capacity() const;

    void reserve(size_t n);

    char& operator[](size_t i);
	const char& operator[](size_t i) const;

    void insert(size_t pos, char c);
    void insert(size_t pos, const char* str);
    void push_back(char c);
    void append(const char* str);
    String& operator+=(char c);
    String& operator+=(const char* str);

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

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

    String substr(size_t pos = 0, size_t len = npos) const;
private:
    char* _str;
    size_t _size;
    size_t _capacity;
};
bool operator<(const String& l, const String& r);
bool operator>(const String& l, const String& r);
bool operator<=(const String& l, const String& r);
bool operator>=(const String& l, const String& r);
bool operator==(const String& l, const String& r);
bool operator!=(const String& l, const String& r);
ostream& operator<<(ostream& out, const String& str);
istream& operator>>(istream& in, String& str);

istream& getline(istream& in, String& str, char delim = '\n');

void swap(String& s1, String& s2);


void String::swap(String& s)
{
    std::swap(_str, s._str);
    std::swap(_size, s._size);
    std::swap(_capacity, s._capacity);
}

void swap(String& s1, String& s2)
{
    s1.swap(s2);
}
String::String(const char* str)
    :_size(strlen(str))
{
    _str = new char[_size + 1] {'\0'};
    _capacity = _size;
    strcpy(_str, str);
}
String::String(const String& s)
{
    String tmp(s._str);
    swap(tmp);
}
String& String::operator=(String s)
{
    swap(s);
    return *this;
}
String::~String()
{
    delete[] _str;
    _str = nullptr;
    _size = _capacity = 0;
}
size_t String::npos = -1;
const char* String::c_str() const
{
    return _str;
}
void String::clear()
{
    _str[0] = '\0';
    _size = 0;
}
size_t String::size() const
{
    return _size;
}
size_t String::capacity() const
{
    return _capacity;
}
void String::reserve(size_t n)
{
    if (n > _capacity)
    {
        char* tmp = new char[n + 1] {'\0'};
        strcpy(tmp, _str);
        delete[] _str;
        _str = tmp;
        _capacity = n;
    }
}
char& String::operator[](size_t i)
{
    assert(i < _size);
    return _str[i];
}
const char& String::operator[](size_t i) const
{
    assert(i < _size);
    return _str[i];
}
String::iterator String::begin()
{
    return _str;
}
String::iterator String::end()
{
    return _str + _size;
}
String::const_iterator String::begin() const
{
    return _str;
}
String::const_iterator String::end() const
{
    return _str + _size;
}
void String::insert(size_t pos, char c)
{
    assert(pos <= _size);
    if (_size == _capacity)
    {
        reserve(_capacity == 0 ? 4 : 2 * _capacity);
    }
    for (size_t i = _size; i >= pos; i--)
    {
        _str[i + 1] = _str[i];
        if (i == 0) break;
    }
    _str[pos] = c;
    _size++;
}
void String::insert(size_t pos, const char* str)
{
    assert(pos <= _size);
    size_t len = strlen(str);
    if (len == 0) return;
    if (_size + len > _capacity)
    {
        size_t newcapacity = _capacity * 2;
        if (newcapacity < _size + len)
        {
            newcapacity = _size + len;
        }
        reserve(newcapacity);
    }
    for (size_t i = _size; i >= pos; i--)
    {
        _str[i + len] = _str[i];
        if (i == 0) break;
    }
    for (size_t i = 0; i < len; i++)
    {
        _str[pos + i] = str[i];
    }
    _size += len;
}
void String::push_back(char c)
{
    insert(_size, c);
}
void String::append(const char* str)
{
    insert(_size, str);
}
String& String::operator+=(char c)
{
    insert(_size, c);
    return *this;
}
String& String::operator+=(const char* str)
{
    insert(_size, str);
    return *this;
}
void String::erase(size_t pos, size_t len)
{
    assert(pos < _size);
    if (pos + len >= _size)
    {
        _str[pos] = '\0';
        _size = pos;
    }
    else
    {
        for (size_t i = pos + len; i <= _size; i++)
        {
            _str[i - len] = _str[i];
        }
        _size -= len;
    }
}
size_t String::find(char c, size_t pos) const
{
    assert(pos < _size);
    for (size_t i = pos; i < _size; i++)
    {
        if (_str[i] == c)
        {
            return i;
        }
    }
    return npos;
}
size_t String::find(const char* str, size_t pos) const
{
    assert(pos < _size);
    const char* p = strstr(_str + pos, str);
    if (p == nullptr)
    {
        return npos;
    }
    return p - _str;
}
String String::substr(size_t pos, size_t len) const
{
    assert(pos < _size);
    if (len > (_size - pos))
    {
        len = _size - pos;
    }
    String sub;
    for (size_t i = 0; i < len; i++)
    {
        sub += _str[pos + i];
    }
    return sub;
}
bool operator<(const String& l, const String& r)
{
    return strcmp(l.c_str(), r.c_str()) < 0;
}
bool operator>(const String& l, const String& r)
{
    return !(l < r);
}
bool operator<=(const String& l, const String& r)
{
    return (l == r || l < r);
}
bool operator>=(const String& l, const String& r)
{
    return (l == r || l > r);
}
bool operator==(const String& l, const String& r)
{
    return strcmp(l.c_str(), r.c_str()) == 0;
}
bool operator!=(const String& l, const String& r)
{
    return !(l == r);
}
ostream& operator<<(ostream& out, const String& str)
{
    for (auto ch : str)
    {
        out << ch;
    }
    return out;
}
istream& operator>>(istream& in, String& str)
{
    str.clear();
    char ch = in.get();
    while (ch != ' ' && ch != '\n')
    {
        str += ch;
        ch = in.get();
    }
    return in;
}
istream& getline(istream& in, String& str, char delim)
{
    str.clear();
    char ch = in.get();
    while (ch != delim)
    {
        str += ch;
        ch = in.get();
    }
    return in;
}

总结

今天,我们在学会使用string类的基础上模拟实现了string类的常用功能,这对于我们学习数据结构和string类有很大帮助。之后博主会和大家一起进入下一个容器——vector的学习。如果你觉得博主讲的还不错,就请留下一个小小的赞在走哦,感谢大家的支持❤❤❤

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。