C++string底层框架模拟实现代码

目录
  • 一、 前言
  • 二、 浅拷贝与深拷贝优缺点
    • 1. 浅拷贝
    • 2. 深拷贝
    • 3. 深拷贝现代版
    • 4. 写时拷贝
  • 三、 string框架搭建
    • 1. 框架定义
    • 2. 构造函数
    • 3. 析构函数
    • 4. 赋值重载
    • 5. 实现扩容
    • 6. 增添数据
    • 7. 删除数据
    • 8. 数据查找
    • 9. iterator迭代器
    • 10. 插入/提取流与getline函数
  • 四. 完整代码

一、 前言

本节文章主要说明浅拷贝和深拷贝的优缺点,以及仿写string类的逻辑并分析实现过程
如果人对一个事物感兴趣,总是那么好奇,就会刨根问底

二、 浅拷贝与深拷贝优缺点

1. 浅拷贝

话不多说,先来上一组代码

class string{
   public:
       string(char* str="")
           :_size(strlen(str))
           ,_capacity(_size)
       {
           _str = new char[_capacity+1];
           strcpy(_str, str);
       }

       char& operator[](const char& pos) const {
           return _str[pos];
       }

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

   private:
       char* _str;
       size_t _size;
       size_t _capacity;
};
void Test1(){
    string s1("never gonna give you up");
    string s2 = s1;
    s2[0] = 'Y';
}

当我们把s1拷贝给s2,这里是深拷贝还是浅拷贝呢?先不说答案我们debug看一下

一目了然,这里的s1和s2为同一个地址

那么当我们改变s2[0]的值时,s1[0]也随之改变,那么还是给人一种藕断丝连的感觉没有完全独立拷贝,这就是浅拷贝,相信我们也看到了浅拷贝带来的弊端

其次,当我们调用析构函数也会出现问题,由于他们指向的是同一块空间,s2会先析构将里面的数组delete并置空

接着s1调用析构函数时就会报错,所以不能指向同一块空间

总结一下浅拷贝问题:

这块空间会在两个对象析构函数被delete两次一个对象修改会影响另外一个对象

2. 深拷贝

深拷贝怎么实现?

string(const string& s) //函数重载
    :_str(new char[strlen(s._str)+1])
{
    strcpy(this->_str, s._str);
}

我们重新new一个空间给s2,下面下图可以看到s1和s2在堆上不再是同一个空间
这里第一个参数是this被匿名了,为了方面看,我把this加了进去
和浅拷贝区别就在于指明了当前字符串需重新分配空间和重新赋值到新开的这组新空间,这里的深拷贝就不会出现上面的问题,当我们改变s2[0]的值,s1[0]不会跟着改变

赋值重载的方式解决浅拷贝问题

string& operator=(string& s){
    if(this != &s){
        char* tmp = new char[strlen(s._str)+1];
        delete[] _str; //删除this原来的内容
        _str = tmp; //将新空间赋给_str
        strcpy(_str, s._str);
        _size = _capacity = strlen(s._str);
        _str[_size] = '\0';
    }
    return *this;
}

3. 深拷贝现代版

上面都为传统写法,通过new开辟一组新的堆空间,和现代写法的思路是有区别的
这里是重新构造一个临时string tmp变量新开了一组空间,然后再swap把两者进行交换,等于this->_str获得了这个新空间,最后把不需要的空间自动析构

string (const string& str)
    :_str(nullptr)
{
    string tmp(str);
    swap(_str, tmp._str);
}

//这组没有用到引用,因为形参自动调用拷贝构造
string& operator=(string t)
{
    swap(_s,t._s);
    return *this;
}

4. 写时拷贝

那么是不是深拷贝一定就是最好的呢?
答案是不一定,写时拷贝在浅拷贝基础上增加了引用计数方式,换句话说有多少个对象指向这块空间,计数就会++,那么只有当某个对象去写数据时,那个对象才会进行深拷贝,然后计数–

这本质上是写的时候一种延迟深拷贝,但如果拷贝对象后没有人进行修改,没有进行深拷贝重开一块空间,也就顺理成章的提高效率。但是实际应用场景中不是很理想

三、 string框架搭建

1. 框架定义

这里私有成员结构就类似顺序表,当我们增加或删除数据时需要记录当前的信息,以及是否需要扩容等,npos用于查找是否有此字符,默认返回-1

class string{
   public:
   private:
       char* _str;
       size_t _size;
       size_t _capacity;
       static const size_t npos;
};
const size_t string::npos = -1;

2. 构造函数

void Test2(){
    string s1("helloworld");
    string s2(5, 'g');
    string();
}

上面的函数名都构成函数重载,目前实现了三种常见的

string(const char* str="")
    :_size(strlen(str))
    ,_capacity(_size)
{
    _str = new char[_capacity+1];
    strcpy(_str, str);
}

第一种最普遍,直接将字符串赋给s1即可

string(size_t n, char c)
    :_size(n)
    ,_capacity(_size)
{
    _str = new char[ _size + 1];
    for(size_t i=0; i<n; ++i) _str[i] = c;
}

第二种可以创建一组n个相同的字符

string()
    :_str(new char[1])
    ,_size(0)
    ,_capacity(0)
{
    *_str = '\0';
}

最后一种创建一个空函数,里面并不为空,默认放一个斜杠零

3. 析构函数

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

用于释放空间,当我们new完一组空间后需要手动创建析构函数

4. 赋值重载

下列赋值重载中,第一个支持读和写

char& operator[](size_t pos){
   return _str[pos];
}

第二个不支持写

const char& operator[](size_t pos) const{
    return _str[pos];
}

这里我把赋值重载都给列出来,push_back函数在下面会提到

//可读可写
String& operator+=(char ch){
    push_back(ch);
    return *this;
}

下列的赋值重载,实现依次比较数组中值的大小

//按照ASCII码进行比较
//s1 > s2 ?
//"abc" "abc" false
//"abc" "ab" true
//"ab"  "abc" false
bool operator>(const string& s1, const string& s2){
    size_t i1 = 0, i2 =0;
    while(i1 < s1.size() && i2 < s2.size()){
        if(s1[i1] > s2[i2]){
            return true;
        }else if(s1[i1] < s2[i2]){
            return false;
        }else{
            ++i1;
            ++i2;
        }
    }
    if(i1 == s1.size()){
        return false;
    }else{
        return true;
    }

    return true;
}

bool operator==(const string& s1, const string& s2){
    size_t i1 = 0, i2 =0;
    while(i1 < s1.size() && i2 < s2.size()){
        if(s1[i1] > s2[i2]){
            return true;
        }else if(s1[i1] < s2[i2]){
            return false;
        }else{
            ++i1;
            ++i2;
        }
    }
    if(i1 == s1.size() && i2 == s2.size()){
        return true;
    }else{
        return false;
    }
}

bool operator!=(const string& s1, const string& s2){
    return !(s1==s2);
}

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

String operator+(const string& s1, const string& str){
    String ret = s1;
    ret += str;
    return ret;
}

5. 实现扩容

resize分为三种情况

  • 当n小于等于size,则size等于n
  • 当n大于size但小于capacity,无法添加数据
  • 当n大于capacity时,先增容,然后从size开始填数据,填到n
 void reserve(size_t n){
     if(n > _capacity){
         char* tmp = new char[n+1]; //开一个更大的空间
         strcpy(tmp, _str); //进行拷贝,然后释放此空间
         delete[] _str;
         _str = tmp; //然后指向新开的空间
     }

     _capacity = n;
 }

 void resize(size_t n, char ch='\0'){
     //大于,小于,等于的情况
     if(n <= _size){
         _size = n;
         _str[_size] = '\0';
     }else{
         if(n > _capacity){ //空间不够,先增容
             reserve(n);
             for(size_t i = _size; i<n; i++){ //从size开始填数据,填到n
                 _str[i] = ch;
             }
             _size = n;
             _str[_size] = '\0';
         }
     }
 }

6. 增添数据

在字符串的最后增加一个字符

void push_back(char c){
    if(_size >= _capacity){
    	//这种如果size和capacity都为0,那么计算出的2倍w也为0,最后调用析构的时候报错
        //reserve(_capacity * 2);
        size_t newCapacity = _capacity == 0 ? 4 : _capacity*2;
        reserve(newCapacity);
    }
    _str[_size] = c;
    ++_size;
    _str[_size] = '\0';
}

在字符串的最后增加一串字符,这里需要注意判断原本容量的大小是否比新增的字符串容量要小,如果是就需要新reserve一组更大的空间

void append(const char* s){
    size_t len = strlen(s);
    if(_size + len >= _capacity){
        reserve(_size + len);
    }
    strcpy(_str + _size, s); //把这个字符串给拷贝过去
    _size += len;
}

在pos位置,插入字符或者字符串,这里我们实际应用中,不推荐使用,因为数组数据过于庞大时,在中间插入后,pos后面的数据都需要依次向后挪动

string& insert(size_t pos, char ch){
    assert(pos<=_size); //pos不能超出此范围
    if(_size == _capacity){
        size_t newcapacity = _capacity == 0 ? 4 : _capacity*2;
        reserve(newcapacity);
    }

    size_t end = _size+1;
    while( end > _size){
        _str[end-1] = _str[end];
        --end;
    }
    _str[_size] = ch;
    ++_size;

    return *this;
}

string& insert(size_t pos, const char* str){
    assert(pos <= _size);
    size_t len = strlen(str);
    if(len == 0){
        return *this;
    }

    if(len + _size > _capacity){
        reserve(len + _size);
    }

    size_t end = _size + len;
    while(end >= pos + len){
        _str[end] = _str[end-len];
        --end;
    }

    for(size_t i= 0; i<len; ++i){
        _str[pos + i] = str[i];
    }

    _size += len;

    return *this;
}

7. 删除数据

String& erase(size_t pos, size_t len=npos){
    assert(pos < _size);
    //1. pos后面删完
    //2. pos后面删一部分
    if(len == npos || len+pos >= _size){
        _str[pos] = '\0';
        _size = pos;
    }else{
        //删一部分
        strcpy(_str + pos, _str + pos + len);
        _size -= len;
    }
    return *this;
}

8. 数据查找

查找匹配的第一个字符,返回其下标

//查找,直接返回字符的下标位置
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;
}

查找字符串,这里就直接调用C语言中的strstr函数进行暴力匹配查找

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

9. iterator迭代器

前面不加const的支持数据修改
初次用迭代器玩不明白,其实刨开看也没有特别神奇,只不过是封装起来了

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

10. 插入/提取流与getline函数

//流插入
ostream& operator<<(ostream& out, const String& s){
   for(size_t i = 0; i<s.size(); ++i){
       out << s[i];
   }
   return out;
}

//流提取
istream& operator>>(istream& in, String& s){
   s.clear();
   char ch;
//        in >> ch; 遇到换行会自动停止
   ch = in.get();
   while(ch != ' ' && ch != '\n'){
       s += ch; //提取字符串到这个String s字符串中去
       ch = in.get();
   }
   return in;
}
//上面的是遇到空格就停止了然后传给cout,而下面我们要实现一行哪怕中间有空格
istream& getline(istream& in, String& s){
    s.clear();
    char ch;
    ch = in.get();
//    while(ch != ' ' && ch != '\n'){
    while(ch != '\n'){ //遇到空格不结束
        s += ch;
        ch = in.get();
    }
    return in;
}

我们可以看到流提取和getline的最大区别在于,流提取遇到空格后,就直接结束了
而getline不一样,函数里面忽略判断空格条件,而只保留判断换行符

void test1(){
	// cin >> s1;
	// cout << s1 << endl; //注意如果有空格的hello world,hello打印出来了但是 world check the rythm还在缓冲区
	getline(cin, s1); //打印带有空格的一个字符串
	cout << s1 <<endl;
}

四. 完整代码

Gitee链接🔗 🔗 🔗

string simulation

到此这篇关于C++string底层框架模拟实现代码的文章就介绍到这了,更多相关C++string底层框架内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++ 字符串string和整数int的互相转化操作

    一.string转int的方式 1.采用最原始的string, 然后按照十进制的特点进行算术运算得到int,但是这种方式太麻烦,这里不介绍了. 2.采用标准库中atoi函数. string s = "12"; int a = atoi(s.c_str()); 对于其他类型也都有相应的标准库函数,比如浮点型atof(),long型atol()等等. 3.采用sstream头文件中定义的字符串流对象来实现转换. istringstream is("12"); //构造输

  • C++string中的insert()插入函数详解

    下面通过代码给大家介绍c++  string insert() 函数,具体内容如下: basic_string& insert (size_type pos, const basic_string& str); 在原串下标为pos的字符前插入字符串str basic_string& insert (size_type pos, const basic_string& str, size_type pos1, size_type n); str从下标为pos1开始数的n个字符

  • C++中string转换为char*类型返回后乱码问题解决

    问题来源: 在写二叉树序列化与反序列化时发现序列化函数为char* Serialize1(TreeNode *root)  其函数返回类型为char*,但是我在实现的过程中为了更方便的操作添加字符串使用的是C++中string类型的变量,这就导致我最后得到的结果res是string类型,若是要返回需要转化为char *类型.而等我将string类型转为char*后返回在主函数中就成了乱码. 先直接说最后的解决办法: 第一种:定义一个char数组,数组长度为stringlength+1,将stri

  • C++中string替换所有指定字符串的方法

    C++的string提供了replace方法来实现字符串的替换,但是对于将字符串中某个字符串全部替换这个功能,string并没有实现,我们今天来做的就是这件事. 首先明白一个概念,即string替换所有字符串,将"12212″这个字符串的所有"12″都替换成"21″,结果是什么? 可以是22211,也可以是21221,有时候应用的场景不同,就会希望得到不同的结果,所以这两种答案都做了实现,代码如下: # include # include using namespace st

  • C++string底层框架模拟实现代码

    目录 一. 前言 二. 浅拷贝与深拷贝优缺点 1. 浅拷贝 2. 深拷贝 3. 深拷贝现代版 4. 写时拷贝 三. string框架搭建 1. 框架定义 2. 构造函数 3. 析构函数 4. 赋值重载 5. 实现扩容 6. 增添数据 7. 删除数据 8. 数据查找 9. iterator迭代器 10. 插入/提取流与getline函数 四. 完整代码 一. 前言 本节文章主要说明浅拷贝和深拷贝的优缺点,以及仿写string类的逻辑并分析实现过程 如果人对一个事物感兴趣,总是那么好奇,就会刨根问底

  • java集合框架线程同步代码详解

    List接口的大小可变数组的实现.实现了所有可选列表操作,并允许包括null在内的所有元素.除了实现List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小.(此类大致上等同于Vector类,除了此类是不同步的.)size.isEmpty.get.set.iterator和listIterator操作都以固定时间运行.add操作以分摊的固定时间运行,也就是说,添加n个元素需要O(n)时间.其他所有操作都以线性时间运行(大体上讲).与用于LinkedList实现的常数因子相比,此实现的

  • Kryo框架使用方法代码示例

    Kryo框架的source已移至https://github.com/EsotericSoftware/kryo ,进入此页面,然后点击右边的Download Zip按钮,就能下载到最新版本的Kryo框架. 导入Eclipse时,记得JDK/JRE选用 JDK1.7版本,因为Kryo会引用到unsafe()对象的一些方法JDK1.7才兼容.. 先来一个String类的序列化跟还原,是不是很简单? </pre><pre name="code" class="j

  • Yii框架模拟组件调用注入示例

    本文实例讲述了Yii框架模拟组件调用注入.分享给大家供大家参考,具体如下: yii 中组件只有在被调用的时候才会被实例化,且在当前请求中之后调用该组件只会使用上一次实例化的实例,不会重新生成该实例. 'components' => array( '组件调用名' => '组件调用命名空间', '组件调用名' => array( 'class' => '组件调用命名空间' ); '组件调用名' => function(){ return new '组件调用命名空间'; } ) 一

  • c++ vector模拟实现代码

    vector的介绍 1.vector是表示可变大小数组的序列容器. 2.就像数组一样,vector也采用的连续存储空间来存储元素.也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效.但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理. 3.本质讲,vector使用动态分配数组来存储它的元素.当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间.其做法是,分配一个新的数组,然后将全部元素移到这个数组.就时间而言,这是一个相对代价高的任务,因为每当一个新

  • C语言之通讯录的模拟实现代码

    在C语言学习结束之际,谨以此篇文章来对C语言的学习告一段落. 纲要: 通讯录的静态版本 通讯录的动态版本 通讯录的带文件版本 因为三种实现方法除了储存形式不同,其他都基本相同,所以我们重点论述静态版本的实现,以及它们不同的储存方式. 一.通讯录的静态版本 为什么叫它为静态版本呢,因为在此部分的储存是以数组来储存的,那对于各种各样的信息,我们要拿什么数组来存放它呢?当然是结构体数组了,所以我们来定义一个结构体来表示个人信息: //采用宏的目的是方便日后修改 #define NAME_MAX 20

  • C++ String部分成员模拟实现流程详解

    目录 string类的成员设计 普通构造函数的模拟 拷贝构造函数的模拟 赋值重载函数的模拟 String的析构函数模拟 补全上述的成员函数 迭代器的简单模拟 其他成员函数的模拟 string类的成员设计 class string { private: char* _str; int _size; int _capacity; }; 说明:以下的五个成员函数的模拟实现,均去除了_size 和_capacity成员变量,目的是为了更方便解释重点.在五个成员函数模拟后,会对string类的设计进行补全

  • Zend Framework框架路由机制代码分析

    本文分析了Zend Framework框架路由机制代码.分享给大家供大家参考,具体如下: 在框架中,有关路由的调用关系为: 1.apache的mod_rewrite模块把请求路由到框架的启动脚本,一般是index.php: 2.前端控制器Zend_Controller_Front通过dispatch函数进行请求分发: 3.路由器Zend_Controller_Router_Rewrite通过route函数处理路由,对路由器中已有的路由规则,按照加入顺序的逆序(类似于栈,后进先出)对每个route

  • C++ string 字符串查找匹配实例代码

    在写C++程序中,总会遇到要从一个字符串中查找一小段子字符串的情况,对于在C中,我们经常用到strstr()或者strchr()这两种方法.而对于C++的string,我们往往会用到find(). C++:#inlcude<string> C: #include<string.h> find():在一个字符串中查找一个指定的单个字符或字符数组.如果找到,就返回首次匹配的开始位置:如果没有查找到匹配的内容,就返回string::npos. find_first_of():在一个目标串

  • js当前页面登录注册框,固定div,底层阴影的实例代码

    这是一个实例,保存代码为html文件运行试试吧.兼容火狐.ie6.ie7.ie8.Chrome等. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1- transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"&

随机推荐