背景

如果google一下“C++ StringBuilder”，你會(huì)得到不少答案。有些會(huì)建議（你）使用std::accumulate，這可以完成幾乎所有你要實(shí)現(xiàn)的：

#include <iostream>// for std::cout, std::endl  
#include <string>  // for std::string  
#include <vector>  // for std::vector  
#include <numeric> // for std::accumulate  
int main()  
{  
    using namespace std;  
    vector<string> vec = { "hello", " ", "world" };  
    string s = accumulate(vec.begin(), vec.end(), s);  
    cout << s << endl; // prints 'hello world' to standard output.   
    return 0;  
} 

目前為止一切都好：當(dāng)你有超過(guò)幾個(gè)字符串連接時(shí)，問(wèn)題就出現(xiàn)了，并且內(nèi)存再分配也開(kāi)始積累。

std::string在函數(shù)reserver()中為解決方案提供基礎(chǔ)。這也正是我們的意圖所在：一次分配，隨意連接。

字符串連接可能會(huì)因?yàn)榉敝?、遲鈍的工具而嚴(yán)重影響性能。由于上次存在的隱患，這個(gè)特殊的怪胎給我制造麻煩，我便放棄了Indigo（我想嘗試一些C++11里的令人耳目一新的特性），并寫(xiě)了一個(gè)StringBuilder類(lèi)的部分實(shí)現(xiàn)：

// Subset of http://msdn.microsoft.com/en-us/library/system.text.stringbuilder.aspx  
template <typename chr>  
class StringBuilder {  
    typedef std::basic_string<chr> string_t;  
    typedef std::list<string_t> container_t; // Reasons not to use vector below.   
    typedef typename string_t::size_type size_type; // Reuse the size type in the string.  
    container_t m_Data;  
    size_type m_totalSize;  
    void append(const string_t &src) {  
        m_Data.push_back(src);  
        m_totalSize += src.size();  
    }  
    // No copy constructor, no assignement.  
    StringBuilder(const StringBuilder &);  
    StringBuilder & operator = (const StringBuilder &);  
public:  
    StringBuilder(const string_t &src) {  
        if (!src.empty()) {  
            m_Data.push_back(src);  
        }  
        m_totalSize = src.size();  
    }  
    StringBuilder() {  
        m_totalSize = 0;  
    }  
    // TODO: Constructor that takes an array of strings.  
 
 
    StringBuilder & Append(const string_t &src) {  
        append(src);  
        return *this; // allow chaining.  
    }  
        // This one lets you add any STL container to the string builder.   
    template<class inputIterator>  
    StringBuilder & Add(const inputIterator &first, const inputIterator &afterLast) {  
        // std::for_each and a lambda look like overkill here.  
                // <b>Not</b> using std::copy, since we want to update m_totalSize too.  
        for (inputIterator f = first; f != afterLast; ++f) {  
            append(*f);  
        }  
        return *this; // allow chaining.  
    }  
    StringBuilder & AppendLine(const string_t &src) {  
        static chr lineFeed[] { 10, 0 }; // C++ 11. Feel the love!  
        m_Data.push_back(src + lineFeed);  
        m_totalSize += 1 + src.size();  
        return *this; // allow chaining.  
    }  
    StringBuilder & AppendLine() {  
        static chr lineFeed[] { 10, 0 };   
        m_Data.push_back(lineFeed);  
        ++m_totalSize;  
        return *this; // allow chaining.  
    }  
 
    // TODO: AppendFormat implementation. Not relevant for the article.   
 
    // Like C# StringBuilder.ToString()  
    // Note the use of reserve() to avoid reallocations.   
    string_t ToString() const {  
        string_t result;  
        // The whole point of the exercise!  
        // If the container has a lot of strings, reallocation (each time the result grows) will take a serious toll,  
        // both in performance and chances of failure.  
        // I measured (in code I cannot publish) fractions of a second using 'reserve', and almost two minutes using +=.  
        result.reserve(m_totalSize + 1);  
    //  result = std::accumulate(m_Data.begin(), m_Data.end(), result); // This would lose the advantage of 'reserve'  
        for (auto iter = m_Data.begin(); iter != m_Data.end(); ++iter) {   
            result += *iter;  
        }  
        return result;  
    }  
 
    // like javascript Array.join()  
    string_t Join(const string_t &delim) const {  
        if (delim.empty()) {  
            return ToString();  
        }  
        string_t result;  
        if (m_Data.empty()) {  
            return result;  
        }  
        // Hope we don't overflow the size type.  
        size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1;  
        result.reserve(st);  
                // If you need reasons to love C++11, here is one.  
        struct adder {  
            string_t m_Joiner;  
            adder(const string_t &s): m_Joiner(s) {  
                // This constructor is NOT empty.  
            }  
                        // This functor runs under accumulate() without reallocations, if 'l' has reserved enough memory.   
            string_t operator()(string_t &l, const string_t &r) {  
                l += m_Joiner;  
                l += r;  
                return l;  
            }  
        } adr(delim);  
        auto iter = m_Data.begin();   
                // Skip the delimiter before the first element in the container.  
        result += *iter;   
        return std::accumulate(++iter, m_Data.end(), result, adr);  
    }  
 
}; // class StringBuilder 

#p#

有趣的部分

函數(shù)ToString()使用std::string::reserve()來(lái)實(shí)現(xiàn)最小化再分配。下面你可以看到一個(gè)性能測(cè)試的結(jié)果。

函數(shù)join()使用std::accumulate()，和一個(gè)已經(jīng)為首個(gè)操作數(shù)預(yù)留內(nèi)存的自定義函數(shù)。

你可能會(huì)問(wèn)，為什么StringBuilder::m_Data用std::list而不是std::vector？除非你有一個(gè)用其他容器的好理由，通常都是使用std::vector。

好吧，我（這樣做）有兩個(gè)原因：

1. 字符串總是會(huì)附加到一個(gè)容器的末尾。std::list允許在不需要內(nèi)存再分配的情況下這樣做；因?yàn)関ector是使用一個(gè)連續(xù)的內(nèi)存塊實(shí)現(xiàn)的，每用一個(gè)就可能導(dǎo)致內(nèi)存再分配。

2. std::list對(duì)順序存取相當(dāng)有利，而且在m_Data上所做的唯一存取操作也是順序的。

你可以建議同時(shí)測(cè)試這兩種實(shí)現(xiàn)的性能和內(nèi)存占用情況，然后選擇其中一個(gè)。

性能評(píng)估

為了測(cè)試性能，我從Wikipedia獲取一個(gè)網(wǎng)頁(yè)，并將其中一部分內(nèi)容寫(xiě)死到一個(gè)string的vector中。

隨后，我編寫(xiě)兩個(gè)測(cè)試函數(shù)，第一個(gè)在兩個(gè)循環(huán)中使用標(biāo)準(zhǔn)函數(shù)clock()并調(diào)用std::accumulate()和StringBuilder::ToString()，然后打印結(jié)果。

void TestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {  
    const int loops = 500;  
    clock_t start = clock(); // Give up some accuracy in exchange for platform independence.  
    for (int i = 0; i < loops; ++i) {  
        std::wstring accumulator;  
        std::accumulate(tested2.begin(), tested2.end(), accumulator);  
    }  
    double secsAccumulate = (double) (clock() - start) / CLOCKS_PER_SEC;  
 
    start = clock();  
    for (int i = 0; i < loops; ++i) {  
        std::wstring result2 = tested.ToString();  
    }  
    double secsBuilder = (double) (clock() - start) / CLOCKS_PER_SEC;  
    using std::cout;  
    using std::endl;  
    cout << "Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds." 
            << " The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%" 
            << endl;  
} 

第二個(gè)則使用更精確的Posix函數(shù)clock_gettime()，并測(cè)試StringBuilder::Join()。

#ifdef __USE_POSIX199309  
 
// Thanks to <a href="http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/">Guy Rutenberg</a>.  
timespec diff(timespec start, timespec end)  
{  
    timespec temp;  
    if ((end.tv_nsec-start.tv_nsec)<0) {  
        temp.tv_sec = end.tv_sec-start.tv_sec-1;  
        temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;  
    } else {  
        temp.tv_sec = end.tv_sec-start.tv_sec;  
        temp.tv_nsec = end.tv_nsec-start.tv_nsec;  
    }  
    return temp;  
}  
 
void AccurateTestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {  
    const int loops = 500;  
    timespec time1, time2;  
    // Don't forget to add -lrt to the g++ linker command line.  
    ////////////////  
    // Test std::accumulate()  
    ////////////////  
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);  
    for (int i = 0; i < loops; ++i) {  
        std::wstring accumulator;  
        std::accumulate(tested2.begin(), tested2.end(), accumulator);  
    }  
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);  
    using std::cout;  
    using std::endl;  
    timespec tsAccumulate =diff(time1,time2);  
    cout << tsAccumulate.tv_sec << ":" <<  tsAccumulate.tv_nsec << endl;  
    ////////////////  
    // Test ToString()  
    ////////////////  
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);  
    for (int i = 0; i < loops; ++i) {  
        std::wstring result2 = tested.ToString();  
    }  
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);  
    timespec tsToString =diff(time1,time2);  
    cout << tsToString.tv_sec << ":" << tsToString.tv_nsec << endl;  
    ////////////////  
    // Test join()  
    ////////////////  
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);  
    for (int i = 0; i < loops; ++i) {  
        std::wstring result3 = tested.Join(L",");  
    }  
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time2);  
    timespec tsJoin =diff(time1,time2);  
    cout << tsJoin.tv_sec << ":" << tsJoin.tv_nsec << endl;  
 
    ////////////////  
    // Show results  
    ////////////////  
    double secsAccumulate = tsAccumulate.tv_sec + tsAccumulate.tv_nsec / 1000000000.0;  
    double secsBuilder = tsToString.tv_sec + tsToString.tv_nsec / 1000000000.0;  
        double secsJoin = tsJoin.tv_sec + tsJoin.tv_nsec / 1000000000.0;  
    cout << "Accurate performance test:" << endl << "    Accumulate took " << secsAccumulate << " seconds, and ToString() took " << secsBuilder << " seconds." << endl  
            << "    The relative speed improvement was " << ((secsAccumulate / secsBuilder) - 1) * 100 << "%" << endl <<  
             "     Join took " << secsJoin << " seconds." 
            << endl;  
}  
#endif // def __USE_POSIX199309 

最后，通過(guò)一個(gè)main函數(shù)調(diào)用以上實(shí)現(xiàn)的兩個(gè)函數(shù)，將結(jié)果顯示在控制臺(tái)，然后執(zhí)行性能測(cè)試：一個(gè)用于調(diào)試配置。
 

另一個(gè)用于發(fā)行版本：

看到這百分比沒(méi)？垃圾郵件的發(fā)送量都不能達(dá)到這個(gè)級(jí)別!
 

#p#

代碼使用

在使用這段代碼前， 考慮使用ostring流。正如你在下面看到Jeff先生評(píng)論的一樣，它比這篇文章中的代碼更快些。

你可能想使用這段代碼，如果：

• 你正在編寫(xiě)由具有C#經(jīng)驗(yàn)的程序員維護(hù)的代碼，并且你想提供一個(gè)他們所熟悉接口的代碼。
• 你正在編寫(xiě)將來(lái)會(huì)轉(zhuǎn)換成.net的、你想指出一個(gè)可能路徑的代碼。
• 由于某些原因，你不想包含<sstream>。幾年之后，一些流的IO實(shí)現(xiàn)變得很繁瑣，而且現(xiàn)在的代碼仍然不能完全擺脫他們的干擾。

要使用這段代碼，只有按照main函數(shù)實(shí)現(xiàn)的那樣就可以了：創(chuàng)建一個(gè)StringBuilder的實(shí)例，用Append()、AppendLine()和Add()給它賦值，然后調(diào)用ToString函數(shù)檢索結(jié)果。

就像下面這樣：

int main() {  
    ////////////////////////////////////  
    // 8-bit characters (ANSI)  
    ////////////////////////////////////  
    StringBuilder<char> ansi;  
    ansi.Append("Hello").Append(" ").AppendLine("World");  
    std::cout << ansi.ToString();  
 
    ////////////////////////////////////  
    // Wide characters (Unicode)  
    ////////////////////////////////////  
    // http://en.wikipedia.org/wiki/Cargo_cult  
    std::vector<std::wstring> cargoCult  
    {  
        L"A", L" cargo", L" cult", L" is", L" a", L" kind", L" of", L" Melanesian", L" millenarian", L" movement",  
// many more lines here...  
L" applied", L" retroactively", L" to", L" movements", L" in", L" a", L" much", L" earlier", L" era.\n" 
    };  
    StringBuilder<wchar_t> wide;  
    wide.Add(cargoCult.begin(), cargoCult.end()).AppendLine();  
        // use ToString(), just like .net  
    std::wcout << wide.ToString() << std::endl;  
    // javascript-like join.  
    std::wcout << wide.Join(L" _\n") << std::endl;  
 
    ////////////////////////////////////  
    // Performance tests  
    ////////////////////////////////////  
    TestPerformance(wide, cargoCult);  
#ifdef __USE_POSIX199309  
    AccurateTestPerformance(wide, cargoCult);  
#endif // def __USE_POSIX199309  
    return 0;  
} 

任何情況下，當(dāng)連接超過(guò)幾個(gè)字符串時(shí)，當(dāng)心std::accumulate函數(shù)。

現(xiàn)在稍等一下！

你可能會(huì)問(wèn)：你是在試著說(shuō)服我們提前優(yōu)化嗎？

不是的。我贊同提前優(yōu)化是糟糕的。這種優(yōu)化并不是提前的：是及時(shí)的。這是基于經(jīng)驗(yàn)的優(yōu)化：我發(fā)現(xiàn)自己過(guò)去一直在和這種特殊的怪胎搏斗。基于經(jīng)驗(yàn)的優(yōu)化（不在同一個(gè)地方摔倒兩次）并不是提前優(yōu)化。

當(dāng)我們優(yōu)化性能時(shí)，“慣犯”會(huì)包括磁盤(pán)I-O操作、網(wǎng)絡(luò)訪問(wèn)（數(shù)據(jù)庫(kù)、web服務(wù)）和內(nèi)層循環(huán)；對(duì)于這些，我們應(yīng)該添加內(nèi)存分配和性能糟糕的 Keyser Söze。

鳴謝

首先，我要為這段代碼在Linux系統(tǒng)上做的精準(zhǔn)分析感謝Rutenberg。

多虧了Wikipedia，讓“在指尖的信息”的夢(mèng)想得以實(shí)現(xiàn)。

最后，感謝你花時(shí)間閱讀這篇文章。希望你喜歡它：不論如何，請(qǐng)分享您的意見(jiàn)。

英文原文：4350% Performance Improvement with the StringBuilder for C++!

譯文鏈接：http://www.oschina.net/translate/performance-improvement-with-the-stringbuilde