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

简介: 【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;
  }
}

写在最后:

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

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

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

相关文章
|
24天前
|
编译器 C语言 C++
【c++丨STL】list模拟实现(附源码)
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构,相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口,然后详细讲解了节点、迭代器及容器的实现过程。 最终,通过这些步骤,我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现,并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣,建议先掌握相关基础知识后再阅读本文,以便更好地理解内容。
30 1
|
1月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构,适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码,读者可以更好地理解如何使用这些接口。最后,作者总结了`list`的特点和适用场景,并预告了后续关于`list`模拟实现的文章。
54 7
|
2月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器,包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组,能够根据需要自动调整大小,提供了丰富的操作接口,如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后,还展示了如何使用`vector`创建字符串数组,体现了`vector`在实际编程中的灵活性和实用性。
103 4
|
2月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现(附源码)
本文详细介绍了如何模拟实现C++ STL中的`string`类,包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能,以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符,使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现,读者不仅能加深对`string`类的理解,还能提升对C++编程技巧的掌握。
104 5
|
2月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色,它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作,帮助读者更好地理解和掌握`string`类的应用。
78 2
|
2月前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库(STL)的基本概念、组成部分及学习方法,强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件:容器、算法、迭代器、仿函数、配接器和空间配置器,并提出了学习STL的三个层次,旨在帮助读者深入理解和掌握STL。
83 0
|
1月前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理,并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表,使用三个迭代器(指针)来维护数组,分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码,帮助读者更好地理解和掌握 `vector` 的实现细节。
50 0
|
4月前
|
Java 索引
java基础(13)String类
本文介绍了Java中String类的多种操作方法,包括字符串拼接、获取长度、去除空格、替换、截取、分割、比较和查找字符等。
54 0
java基础(13)String类
|
3月前
|
Java
【编程基础知识】(讲解+示例实战)方法参数的传递机制(值传递及地址传递)以及String类的对象的不可变性
本文深入探讨了Java中方法参数的传递机制,包括值传递和引用传递的区别,以及String类对象的不可变性。通过详细讲解和示例代码,帮助读者理解参数传递的内部原理,并掌握在实际编程中正确处理参数传递的方法。关键词:Java, 方法参数传递, 值传递, 引用传递, String不可变性。
81 1
【编程基础知识】(讲解+示例实战)方法参数的传递机制(值传递及地址传递)以及String类的对象的不可变性
|
3月前
|
安全 Java 测试技术
Java零基础-StringBuffer 类详解
【10月更文挑战第9天】Java零基础教学篇,手把手实践教学!
81 2