AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【C++】STL | 模拟实现简易string

2023-10-31 59
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【C++】STL | 模拟实现简易string

1. 框架搭建

首先啊，我们需要搭建好一个框架，

然后在往里面填充内容。

那搭建框架主要包括这几个点：

1. 基本的默认成员函数

2. 必须的成员变量

3. 常用的简单接口（先让代码跑起来）

来看代码：

#pragma once
#include <iostream>
#include <string>
#include <assert.h>
#include <string.h>
using namespace std;
namespace xl {
  class string {
  private:
    char* _str;
    size_t _size;
    size_t _capacity;
  public:
    string(const char* str = "")
      : _size(strlen(str))
      , _capacity(_size)
    {
      _str = new char[_capacity + 1];
      strcpy(_str, str);
    }
    ~string()
    {
      delete[] _str; 
      _str = nullptr;
      _size = _capacity = 0;
    }
  public:
    char& operator[](size_t pos) {
      assert(pos < _size);
      return _str[pos];
    }
    char& operator[](size_t pos) const {
      assert(pos < _size);
      return _str[pos];
    }
    const char* c_str() const {
      return _str;
    }
    size_t size() const {
      return _size;
    }
  };
}

实现功能包括：

1. 构造和析构函数

2. 基本的 [ ] 访问

3. 可供转换类型的 c_str

4. 以及容量相关的 size

我们就能先跑起来一段遍历：

#include "string.h"
int main()
{
  xl::string s1("hello");
  cout << s1.c_str() << endl;
  for (int i = 0; i < s1.size(); i++) {
    cout << s1[i] << " ";
  }
  cout << endl;
  return 0;
}

输出：

2. 迭代器的实现

迭代器可能是指针，也可能不是，

不过在string里面，迭代器就是指针。

我们把迭代器实现到类里面，因为标准库中的迭代器，就存在类内，

我们直接通过类域就能访问到。

来看代码：

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

这样我们就能直接跑起来：

#include "string.h"
int main()
{
  xl::string s1("hello");
  cout << s1.c_str() << endl;
  for (int i = 0; i < s1.size(); i++) {
    cout << s1[i] << " ";
  }
  cout << endl;
  xl::string::iterator it = s1.begin();
  while (it != s1.end()) {
    cout << *it << " ";
    it++;
  }
  cout << endl;
  return 0;
}

输出：

但是啊，这样只支持了普通对象的迭代器，

还有const对象，所以我们要再实现一份：

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;
  }

我们可以观察一下，

使用 const 迭代器确实是禁止访问了：

而使用普通迭代器是可以修改指向的值的：

void test2() {
  xl::string s1("hello");
  xl::string::const_iterator cit = s1.begin();
  while (cit != s1.end()) {
    //*cit += 1;
    cout << *cit << " ";
    cit++;
  }
  cout << endl;
  xl::string::iterator it = s1.begin();
  while (it != s1.end()) {
    *it += 1;
    cout << *it << " ";
    it++;
  }
  cout << endl;
}

输出：

3. string的拷贝构造和赋值（深拷贝）

拷贝构造

需要新开一块空间：

string(const string& s) {
  _str = new char[s._capacity + 1];
  memcpy(_str, s._str, s.size() + 1);
  _size = s._size;
  _capacity = s._capacity;
}

赋值构造

我们就直接采取删除旧空间，开辟新空间，拷贝数据的策略：

string& operator=(const string& s) {
  if (this != &s) {
    char* tmp = new char[s._capacity + 1];
    memcpy(tmp, s._str, s._size + 1);
    delete[] _str;
    _str = tmp;
  }
  return *this;
}

上面的这种中规中矩的方法，我们称之为传统写法，

那么有传统写法，当然还有现代写法，来看这种写法：

void swap(string& tmp) {
  ::swap(_str, tmp._str);
  ::swap(_size, tmp._size);
  ::swap(_capacity, tmp._capacity);
}
// 现代写法
string& operator=(string tmp) {
  swap(tmp);
  return *this;
}

我们实现了一个string类内的一个swap，通过拷贝构造形成的 tmp 帮我们打工，

然后我们再通过 swap 白嫖 tmp 的内容即可。

我个人认为这种方法其实本质上就是对拷贝构造的复用。

实际上，拷贝构造也可以用现代写法：

string(const string& s)
  : _str(nullptr)
  , _size(0)
  , _capacity(0)
{
  string tmp(s._str);
  swap(tmp);
}

发现没有，拷贝构造的现代写法本质也是一个复用，

他复用的就是我们实现的构造函数。

4. string的增删查改

在实现那些花里胡哨的接口之前啊，

先把扩容的问题搞定再说：

reserve 接口

根据给的 n 的大小直接扩容即可：

void reserve(size_t n) {
  if (n > _capacity) {
    char* tmp = new char[n + 1];
    memcpy(tmp, _str, _size + 1);
    delete[] _str;
    _str = tmp;
    _capacity = n;
  }
}

resize 接口

还有一种扩容方法就是resize，不过string一般很少用resize，

来看实现：

void resize(size_t n, char ch = '\0') {
  if (n < _size) {
    _size = n;
    _str[_size] = '\0';
  }
  else {
    reserve(n);
    for (size_t i = _size; i < n; i++) {
      _str[i] = ch;
    }
    _size = n;
    _str[_size] = '\0';
  }
}

push_back 接口

string的 push_back 就是尾插一个元素，

采取的是二倍扩容的机制（这个看个人喜好，也有1.5倍扩容的）

void push_back(char ch) {
  if (_size == _capacity) {
    // 2倍扩容
    reserve(_capacity == 0 ? 4 : _capacity * 2);
  }
  _str[_size] = ch;
  _size++;
  _str[_size] = '\0';
}

append 接口

append 是尾插一段字符串，

扩容机制我使用的是按需扩容。

void append(const char* str) {
  size_t len = strlen(str);
  if (_size + len > _capacity) {
    // 至少扩容到 _size + len
    reserve(_size + len);
  }
  memcpy(_str + _size, str, len + 1);
  _size += len;
}

当然，我们其实更喜欢使用 +=：

operator+=() 实现

当然，这个函数我们就直接复用前面实现的push_back和append就行：

string& operator+=(char ch) {
  push_back(ch);
  return *this;
}
string& operator+=(const char* str) {
  append(str);
  return *this;
}

这用起来当然是爽多了：

void test4() {
  xl::string s1("hello");
  cout << s1.c_str() << endl;
  s1 += " ";
  s1 += "a";
  s1 += "a";
  s1 += "a";
  s1 += "a";
  s1 += "a";
  s1 += "a";
  s1 += " ";
  s1 += "string";
  cout << s1.c_str() << endl;
}

输出：

insert 接口

实际上STL的string 实现了很多比较冗余的重载，

作为学习，我们就只实现最核心的调用方法。

insert我们实现两种重载：

void insert(size_t pos, size_t n, char ch) {
}
void insert(size_t pos, const char* str) {
}

先来实现第一种，插入一种字符：

void insert(size_t pos, size_t n, char ch) {
  assert(pos <= _size);
  if (_size + n > _capacity) {
    // 至少扩容到_size + n
    reserve(_size + n);
  }
  // 挪动数据
  size_t end = _size;
  while (end >= pos && end != npos) {
    _str[end + n] = _str[end];
    end--;
  }
  // 填值
  for (size_t i = 0; i < n; i++) _str[pos + i] = ch;
  _size += n;
}

第二种，插入一个字符串：

实现方法都是相似的：

void insert(size_t pos, const char* str) {
  assert(pos <= _size);
  size_t len = strlen(str);
  if (_size + len > _capacity) {
    // 至少扩容到_size + len
    reserve(_size + len);
  }
  // 挪动数据
  size_t end = _size;
  while (end >= pos && end != npos) {
    _str[end + len] = _str[end];
    end--;
  }
  // 填值
  for (size_t i = 0; i < len; i++) _str[pos + i] = str[i];
  _size += len;
}

我们来测试一下：

void test5() {
  xl::string s1("hello");
  cout << s1.c_str() << endl;
  s1.insert(5, 3, 'x');
  s1.insert(0, "string ");
  cout << s1.c_str() << endl;
}

输出：

erase 接口

如果删除的字符超过了有的字符，或者是没有说明删除的字符数，就全部删完：

void erase(size_t pos, size_t len = npos) {
  assert(pos <= _size);
  if (len == npos || pos + len >= _size) {
    _size = pos;
    _str[pos] = '\0';
  }
  else {
    size_t end = pos + len;
    while (end <= _size) {
      _str[pos++] = _str[end++];
    }
    _size -= len;
  }
}

我们可以测试一下：

void test5() {
  xl::string s1("hello");
  cout << s1.c_str() << endl;
  s1.insert(5, 3, 'x');
  s1.insert(0, "string ");
  cout << s1.c_str() << endl;
  s1.erase(10, 3);
  cout << s1.c_str() << endl;
  s1.erase(2, 100);
  cout << s1.c_str() << endl;
}

输出：

find 接口

如果是单个字符，直接找就行了：

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

字符串的话我们用strstr暴力匹配就行：

size_t find(const char* str, size_t pos = 0) {
  const char* ptr = strstr(_str + pos, str);
  if (ptr) return ptr - _str;
  else return npos;
}

substr 接口

截取字符串的操作：

string substr(size_t pos = 0, size_t len = npos) {
  assert(pos <= _size);
  size_t n = len + pos;
  if (len == npos || pos + len > _size) {
    n = _size;
  }
  string tmp;
  tmp.reserve(n);
  for (size_t i = pos; i < n; i++) {
    tmp += _str[i];
  }
  return tmp;
}

来测试一下：

void test6() {
  xl::string s1("hello string");
  cout << s1.c_str() << endl;
  size_t pos = s1.find('s');
  cout << s1.substr(pos, 3).c_str() << endl;
  pos = s1.find('s');
  cout << s1.substr(pos, 100).c_str() << endl;
}

输出：

clear 接口

顺便实现一下：

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

流插入和流提取

这个我们需要实现在类外，因为操作符的顺序要求，

先来看流插入：

ostream& operator<<(ostream& out, const string& s) {
  for (auto e : s) cout << e;
  return out;
}

再来看流提取：

istream& operator>>(istream& in, string& s) {
  s.clear();
  char ch = in.get();
  while (ch != ' ' && ch != '\n') {
    s += ch;
    ch = in.get();
  }
  return in;
}

测试时间~

void test7() {
  string s1;
  cin >> s1;
  cout << s1 << endl;
}

输出：

5. 用于比较的操作符重载函数

我们还是一样的操作，先实现两个，在复用到全部：

operator<

我们用库函数memcmp实现：

bool operator<(const string& s) {
  int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
  return ret == 0 ? _size < s._size : ret < 0;
}

operator==

bool operator==(const string& s) {
  return memcmp(_str, s._str, _size < s._size ? _size : s._size) == 0;
}

其它复用

bool operator<=(const string& s) {
  return *this < s || *this == s;
}
bool operator>(const string& s) {
  return !(*this <= s);
}
bool operator>=(const string& s) {
  return !(*this < s);
}
bool operator!=(const string& s) {
  return !(*this == s);
}

6. 源码分享

#pragma once
#include <iostream>
#include <string>
#include <assert.h>
#include <string.h>
using namespace std;
namespace xl {
  class string {
  private:
    char* _str;
    size_t _size;
    size_t _capacity;
    const static size_t npos = -1; // 可以这样用，但不建议，违背了C++的语法准则（建议声明和定义分离）
  public:
    string(const char* str = "")
      : _size(strlen(str))
      , _capacity(_size)
    {
      _str = new char[_capacity + 1];
      memcpy(_str, str, _size + 1);
    }
     传统写法
    //string(const string& s) {
    //  _str = new char[s._capacity + 1];
    //  memcpy(_str, s._str, s._size + 1);
    //  _size = s._size;
    //  _capacity = s._capacity; 
    //}
    // 现代写法
    string(const string& s) 
      : _str(nullptr)
      , _size(0)
      , _capacity(0)
    {
      string tmp(s._str);
      swap(tmp);
    }
     传统写法
    //string& operator=(const string& s) {
    //  if (this != &s) {
    //    char* tmp = new char[s._capacity + 1];
    //    memcpy(tmp, s._str, s._size + 1);
    //    delete[] _str;
    //    _str = tmp;
    //  }
    //  return *this;
    //}
    void swap(string& tmp) {
      ::swap(_str, tmp._str);
      ::swap(_size, tmp._size);
      ::swap(_capacity, tmp._capacity);
    }
    // 现代写法
    string& operator=(string tmp) {
      swap(tmp);
      return *this;
    }
    ~string()
    {
      delete[] _str; 
      _str = nullptr;
      _size = _capacity = 0;
    }
  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;
    }
  public:
    void reserve(size_t n) {
      if (n > _capacity) {
        char* tmp = new char[n + 1];
        memcpy(tmp, _str, _size + 1);
        delete[] _str;
        _str = tmp;
        _capacity = n;
      }
    }
    void resize(size_t n, char ch = '\0') {
      if (n < _size) {
        _size = n;
        _str[_size] = '\0';
      }
      else {
        reserve(n);
        for (size_t i = _size; i < n; i++) {
          _str[i] = ch;
        }
        _size = n;
        _str[_size] = '\0';
      }
    }
    void push_back(char ch) {
      if (_size == _capacity) {
        // 2倍扩容
        reserve(_capacity == 0 ? 4 : _capacity * 2);
      }
      _str[_size] = ch;
      _size++;
      _str[_size] = '\0';
    }
    void append(const char* str) {
      size_t len = strlen(str);
      if (_size + len > _capacity) {
        // 至少扩容到 _size + len
        reserve(_size + len);
      }
      memcpy(_str + _size, str, len + 1);
      _size += len; 
    }
    string& operator+=(char ch) {
      push_back(ch);
      return *this;
    }
    string& operator+=(const char* str) {
      append(str);
      return *this;
    }
    void insert(size_t pos, size_t n, char ch) {
      assert(pos <= _size);
      if (_size + n > _capacity) {
        // 至少扩容到_size + n
        reserve(_size + n);
      }
      // 挪动数据
      size_t end = _size;
      while (end >= pos && end != npos) {
        _str[end + n] = _str[end];
        end--; 
      }
      // 填值
      for (size_t i = 0; i < n; i++) _str[pos + i] = ch;
      _size += n;
    }
    void insert(size_t pos, const char* str) {
      assert(pos <= _size);
      size_t len = strlen(str);
      if (_size + len > _capacity) {
        // 至少扩容到_size + len
        reserve(_size + len);
      }
      // 挪动数据
      size_t end = _size;
      while (end >= pos && end != npos) {
        _str[end + len] = _str[end];
        end--;
      }
      // 填值
      for (size_t i = 0; i < len; i++) _str[pos + i] = str[i];
      _size += len;
    }
    void erase(size_t pos, size_t len = npos) {
      assert(pos <= _size);
      if (len == npos || pos + len >= _size) {
        _size = pos;
        _str[pos] = '\0';
      } 
      else {
        size_t end = pos + len;
        while (end <= _size) {
          _str[pos++] = _str[end++];
        }
        _size -= len;
      }
    }
    size_t find(char ch, size_t pos = 0) {
      for (size_t i = pos; i < _size; i++) {
        if (_str[i] == ch) return i;
      }
      return npos;
    }
    size_t find(const char* str, size_t pos = 0) {
      const char* ptr = strstr(_str + pos, str);
      if (ptr) return ptr - _str;
      else return npos;
    }
    string substr(size_t pos = 0, size_t len = npos) {
      assert(pos <= _size);
      size_t n = len + pos;
      if (len == npos || pos + len > _size) {
        n = _size;
      }
      string tmp;
      tmp.reserve(n);
      for (size_t i = pos; i < n; i++) {
        tmp += _str[i];
      }
      return tmp;
    }
  public:
    char& operator[](size_t pos) {
      assert(pos < _size);
      return _str[pos];
    }
    char& operator[](size_t pos) const {
      assert(pos < _size);
      return _str[pos];
    }
    bool operator<(const string& s) {
      int ret = memcmp(_str, s._str, _size < s._size ? _size : s._size);
      return ret == 0 ? _size < s._size : ret < 0;
    }
    bool operator==(const string& s) {
      return _size == s._size && memcmp(_str, s._str, _size) == 0;
    }
    bool operator<=(const string& s) {
      return *this < s || *this == s;
    }
    bool operator>(const string& s) {
      return !(*this <= s);
    }
    bool operator>=(const string& s) {
      return !(*this < s);
    }
    bool operator!=(const string& s) {
      return !(*this == s);
    }
    const char* c_str() const {
      return _str;
    }
    size_t size() const {
      return _size;
    }
    void clear() {
      _str[0] = '\0';
      _size = 0;
    }
  };
  ostream& operator<<(ostream& out, const string& s) {
    for (auto e : s) cout << e;
    return out;
  }
  istream& operator>>(istream& in, string& s) {
    s.clear();
    char ch = in.get();
    while (ch != ' ' && ch != '\n') {
      s += ch;
      ch = in.get();
    }
    return in;
  }
}

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

文章标签：
云数据库 ClickHouse
C++
关键词：
C++ stl
C++ string
C++ stl string
String stl
戊子仲秋
目录
相关文章
平凡程序猿~
|
25天前
|
存储 安全 C语言
C++ String揭秘：写高效代码的关键
在C++编程中，字符串操作是不可避免的一部分。从简单的字符串拼接到复杂的文本处理，C++的string类为开发者提供了一种更高效、灵活且安全的方式来管理和操作字符串。本文将从基础操作入手，逐步揭开C++ string类的奥秘，帮助你深入理解其内部机制，并学会如何在实际开发中充分发挥其性能和优势。
平凡程序猿~
39 0
平凡程序猿~
|
25天前
|
存储 缓存 C++
C++ 容器全面剖析：掌握 STL 的奥秘，从入门到高效编程
C++ 标准模板库（STL）提供了一组功能强大的容器类，用于存储和操作数据集合。不同的容器具有独特的特性和应用场景，因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说，了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器，包括序列容器（`std::vector`、`std::array`、`std::list`、`std::deque`）、关联容器（`std::set`、`std::map`）和无序容器（`std::unordered_set`、`std::unordered_map`），全面解析它们的特点、用法
平凡程序猿~
25 1
C++ 容器全面剖析：掌握 STL 的奥秘，从入门到高效编程
羑悻的小杀马特
|
1月前
|
C++
模拟实现c++中的string
模拟实现c++中的string
羑悻的小杀马特
37 17
ephemerals__
|
17天前
|
存储 算法 C++
【c++丨STL】priority_queue（优先级队列）的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`（优先级队列）。`priority_queue`根据严格的弱排序标准设计，确保其第一个元素始终是最大元素。它底层使用堆结构实现，支持大堆和小堆，默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`，通过仿函数控制堆的类型，并调用封装容器的接口实现功能。最后，感谢大家的支持与关注。
ephemerals__
54 1
ephemerals__
|
2月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器：栈（stack）和队列（queue）。容器适配器是在已有容器基础上添加新特性或功能的结构，如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数（empty、size、top/front/back、push/pop、swap），并提供了使用示例和模拟实现代码。通过这些内容，读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后，作者鼓励读者点赞支持。 总结：本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现，帮助读者掌握这两种容器适配器的特性和应用场景。
ephemerals__
68 21
平凡程序猿~
|
25天前
|
存储 算法 C++
深入浅出 C++ STL：解锁高效编程的秘密武器
C++ 标准模板库（STL）是现代 C++ 的核心部分之一，为开发者提供了丰富的预定义数据结构和算法，极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍，涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
平凡程序猿~
25 0
ephemerals__
|
3月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
63 1
ephemerals__
|
3月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
86 7
ephemerals__
|
4月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
192 4
ephemerals__
|
4月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现（附源码）
本文详细介绍了如何模拟实现C++ STL中的`string`类，包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能，以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符，使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现，读者不仅能加深对`string`类的理解，还能提升对C++编程技巧的掌握。
ephemerals__
199 5