详解C++中StringBuilder类的实现及其性能优化
介绍 背景 如果google一下“C++ StringBuilder”,你会得到不少答案。有些会建议(你)使用std::accumulate,这可以完成几乎所有你要实现的: #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; } 目前为止一切都好:当你有超过几个字符串连接时,问题就出现了,并且内存再分配也开始积累。 // 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,result,adr); } }; // class StringBuilder
性能评估 为了测试性能,我从Wikipedia获取一个网页,并将其中一部分内容写死到一个string的vector中。 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; } 第二个则使用更精确的Posix函数clock_gettime(),并测试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(),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 最后,通过一个main函数调用以上实现的两个函数,将结果显示在控制台,然后执行性能测试:一个用于调试配置。 另一个用于发行版本: 看到这百分比没?垃圾邮件的发送量都不能达到这个级别! 代码使用 在使用这段代码前, 考虑使用ostring流。正如你在下面看到Jeff先生评论的一样,它比这篇文章中的代码更快些。 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" 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; } 任何情况下,当连接超过几个字符串时,当心std::accumulate函数。 现在稍等一下! 你可能会问:你是在试着说服我们提前优化吗? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |