• C++面试八股文:std::string是如何实现的?


    某日二师兄参加XXX科技公司的C++工程师开发岗位第18面:

    面试官:std::string用过吧?

    二师兄:当然用过(废话,C++程序员就没有没用过std::string的)。

    面试官:std::string("hello")+"world""hello"+std::string("world")std::string("hello")+std::string("world")的结果是什么?为什么?

    二师兄:前者和后者的结果都是std::string的对象,内容是“helloworld\0”,而中间的这个表达式无法通过编译。原因是std::string重载了operator+(const char*)operator+(const std::string&),但是const char* 却没有重载operator+运算符。

    面试官:std::string 有两个APIresizereserve,你知道它们之间的区别吗?

    二师兄:resize对应的是sizeresize可以改变字符串的大小。reserve对应的是capacityreserve只能改变capacity的大小。

    二师兄:当resize传入的参数小于字符串的szie时,多余的字符串会被截取。当reserve传入的参数小于capacity时,reserve什么也不会做。

    二师兄:当resize传入的参数大于字符串的szie时,增加的字符串会被默认初始化。当reserve传入的参数大于capacity时,capacity会被扩容。

    面试官:好的。可以通过下标访问std::string实例的内容吗?

    二师兄:可以的,std::string重载了下标运算符,可以像数组一样通过下标运算取出某个字符。

    面试官:你知道std::stringat成员方法吗?

    二师兄: 嗯,和下标运算功能相似,不过不用担心越界问题。可以安全的访问字符串中的字符。

    面试官:既然有at方法了,为什么还要重载下标运算符呢?

    二师兄:主要是因为性能上的考量。at虽然保证了不会超出字符串范围(超出范围抛出异常),但是性能低于下标操作。这就是有舍有得。为了安全使用at,为了性能使用下标操作。C++给了你多个选择,如何选择看你的需求。

    面试官:那你知道std::string是如何实现的吗?

    二师兄:在string内部维护一个指针,这个指针指向真正的字符串的位置。

    面试官:能简单的写一下实现代码吗?

    二师兄:好的。

    class string
    {
    public: 
        string():size_(0),data_(nullptr){}
        explicit string(const char* c)
        {
            size_ = strlen(c);
            data_ = (char*)malloc(size_+1);
            memset(data_,0,size_+1);
            memcpy(data_,c,size_);
        }
        size_t size() const {return size_;}
    	const char* c_str() const {return data_;}
    private:
        size_t size_;
        char* data_;
    };
    

    二师兄:在实现append或者+=的时候,需要把当前字符的长度加上append的内容的长度,以此长度申请一块新内存,然后把当前字符串的内存和append 的内容考入新申请的内存中。free掉之前data_指向的内存,然后把data_指针指向新申请的内存。

    面试官:好的。这样的实现有一些弊端。如果频繁的对一个std::string对象append内容,会发生什么?

    二师兄:是的,因为频繁的mallocfree,会有性能问题。因所以编译器在实现std::string的时候一般会预先申请一块大的内存,这块内存的长度是capacity,当添加的字符串的长度加上当前的字符串长度小于capacity时,直接添加到当前的块上即可。

    面试官:好的。针对字符串比较少的情况,一般编译器会做一些优化,你知道如何优化的吗?

    二师兄:这个好像在哪看过,不记得额。。。

    面试官:好的,今天的面试结束了,请回去等通知吧。

    今天二师兄的表现不错,除了最后一个问题,基本上都答上来了。让我们来看下这个问题:

    针对字符串比较少的情况,一般编译器会做一些优化,你知道如何优化的吗?

    我们可以看看GCC中std::string的实现:

     typedef basic_string<char>    string;   
    
    _Alloc_hider	_M_dataplus;
    size_type		_M_string_length;
    enum { _S_local_capacity = 15 / sizeof(_CharT) };
    union
    {
        _CharT           _M_local_buf[_S_local_capacity + 1];
        size_type        _M_allocated_capacity;
    };
    

    这里的_CharT就是char,所以_S_local_capacity等于15。当字符串的长度小于等于15时,直接存在_M_local_buf中,而不需要在堆中申请内存。当字符串长度大于15时,在内存中申请一块内存,这块内存的起始地址保存在_M_dataplus中,这块内存的容量保存在_M_allocated_capacity 中,而字符串的真实长度保存在_M_string_length中。当向字符串中添加字符时,如果添加字符的长度大于 _M_allocated_capacity - _M_string_length,则需要resize,否则直接追加到_M_dataplus保存的内存块中即可。

    好了,今天的面试到这里就结束了。感谢小伙伴们的耐心阅读,咱们明天继续二师兄的面试之旅!

    关注我,带你21天“精通”C++!(狗头)

  • 相关阅读:
    接口技术:输入输出接口部分笔记
    jvm概述
    K8S之prometheus-operator监控
    List的使用
    超强高温天气来袭,“幕后推手”是谁
    Hyperledge Fabric-身份与角色认证
    Redis的高可用集群 完
    【教学类-18-01】20221123《蒙德里安红黄蓝格子画》(大班)
    Java(七)——集合框架---Set集合
    第 2 章 线性表(静态链表示例)
  • 原文地址:https://www.cnblogs.com/binarch/p/17489618.html