std :: basic_string構造函數如何事先知道要預留多少空間？

std::basic_string具有以下構造函數初始化與空值終止字符串的內容指向的字符串s：std :: basic_string構造函數如何事先知道要預留多少空間？

std::basic_string(const CharT* s, const Allocator& alloc = Allocator());

但如何構造事先知道有多少空間保留在串中的內部緩衝區？

我能想到的方法有兩種：

1）它可以先通過全空值終止字符串，直到它找到第一個NULL字符，記得有多少個字符走過，並用其作爲容量爲其內部緩衝區並開始複製。

缺點：它必須讀取字符串兩次，一次用於計數字符，第二次用於複製字符串。

2）它可以在其內部緩衝區保留一個保守的數量，並開始複製。如果它在緩衝區用完之前遇到NULL字符，那麼我們就可以，否則我們需要預留更多空間（再次保守一些），然後重複這些步驟。

缺點：如果字符串相當大，不斷重新調整容量的開銷可能會變得很明顯。

那麼，一個理智的std :: basic_string實現是做什麼的（或者甚至是在標準中指定的）？

來源

2013-11-04 JohnCand

你爲什麼問？ –

2並不像您想象的那樣糟糕，通過將每個展開式展開的空間加倍（這是相當標準的做法），您可以獲得指數級的增長，這通常足以限制性能問題。老實說，你錯過了一個混合的方法：做2直到你確定字符串太大，然後切換到1. – IdeaHat

@MadScienceDreams：2比1差太多了。幾何增長方法會造成空間浪費，單個內存分配的成本將超出計算字符串的成本以計算出長度。 –

第一種方法就是答案。每標準§21.4.2：

basic_string(const charT* s, const Allocator& a = Allocator());

效果：構造類basic_string的的目的和從長度的圖表陣列traits::length(s)其第一元件確定其初始字符串值被指定爲...

and

注：用途traits::length()。

GCC的實現是：

template<typename _CharT, typename _Traits, typename _Alloc> 
    basic_string<_CharT, _Traits, _Alloc>:: 
    basic_string(const _CharT* __s, const _Alloc& __a) 
    : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 
        __s + npos, __a), __a) 
    { }

它採用traits_type::length這是像std::char_traits::length發現C風格的零結尾的字符串的長度。

如果你有巨大的進入字符串傳遞功能，你有它的長度，你可以使用另一個重載它得到的大小和不重新計算它：

basic_string(const CharT* s, size_type count, ...)

你提到的第二種方法有另外一個缺點，它必須分配內存以免浪費內存。這個操作也很昂貴。

來源

2013-11-04 22:21:57 deepmax

常見的實現將走原始字符串來計算長度，然後分配那麼多的空間。它需要兩次走字符串，但這是一種快速操作，在某些情況下可以使用硬件支持，即使在沒有硬件支持的情況下，它也可能與單個內存分配相比較。

來源

2013-11-04 22:22:20

此外，複製已知數量的字節也比複製未知大小更快。 – microtherion

我想不出一個使用第二種方法的理智的實現。某些實現（即Visual C++）可以執行默認初始化，它可以分配一些最小長度（如1或16），然後調用assign，這將獲得字符串的長度，如果需要重新分配，然後複製該字符串。很多（如果不是全部的話）現代編譯器將使用手動調整彙編語言來獲得以空字符結尾的字符串的長度，這通常是非常快的極其。做一個分配 - 複製 - 重新分配 - 複製等等......真的是瘋了，至少在我所知道的所有平臺上。

來源

2013-11-04 22:40:35 Gerald

std :: basic_string構造函數如何事先知道要預留多少空間？

回答

相關問題