C++面試八股文:std::string是如何實現的?

2023-06-18 21:00:29

某日二師兄參加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++!(狗頭)