//============================================================================
// Name : StringBuilderDemo.cpp
// Author : Pablo Aliskevicius
// Copyright : Licensed under the Code Project Open License
// Description : std::basic_string<>::reserve can save _lots_ of time in reallocations.
// Using std::accumulate on strings can have a _big_ performance cost.
// Version II modifications:
// 1. Added std::basic_stringstream to the tests.
// Thanks to http://www.codeproject.com/script/Membership/View.aspx?mid=797594
// 2. Removed a function that is no longer relevant.
// 3. Performance test with side effects, so the compiler doesn't optimize it away.
// Inspired on the code at http://code.google.com/p/strtk/source/browse/trunk/strtk_tokenizer_cmp.cpp#699
// There are two modifications:
// a. Less tests (4001 instead of 40000 * number of items in vector)
// b. Using ^= instead of if ... += else ... -=.
// Thanks to: http://www.codeproject.com/script/Membership/View.aspx?mid=1256594
// 4. Added this lambda:
// for_each(test.begin(), test.end(), [&](const std::wstring &s){ accumulator += s; });
// Thanks to http://www.codeproject.com/script/Membership/View.aspx?mid=10171025
//
// C++ 11 Support in Eclipse:
// See http://stackoverflow.com/questions/9131763/eclipse-cdt-c11-c0x-support
//============================================================================
#include <iostream> // for std::cout
#include <fstream>
#include <sstream>
#include <algorithm> // for for_each
#include <string> // for std::basic_string;
#include <vector> // used in main()
#include <deque> // used in class StringBuilder, slightly faster than list.
#include <numeric> // for accumulate
#include <ctime> // clock_t, clock, CLOCKS_PER_SEC
// 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;
// After testing several times with deque, vector and list, deque performed _slightly_ better.
typedef std::deque<string_t> container_t;
container_t m_Data;
typedef typename string_t::size_type size_type; // Reuse the size type in the string.
size_type m_totalSize;
void append(const string_t &src) {
m_Data.push_back(src);
m_totalSize += src.size();
}
// No copy constructor, no assignment.
StringBuilder(const StringBuilder &);
StringBuilder & operator = (const StringBuilder &);
public:
StringBuilder(const string_t &src) {
if (src.empty()) {
m_totalSize = 0;
} else {
m_Data.push_back(src);
m_totalSize = src.size();
}
}
StringBuilder() {
m_totalSize = 0;
}
StringBuilder & Append(const string_t &src) {
append(src);
return *this; // allow chaining.
}
template<class iterator>
StringBuilder & Add(const iterator &first, const iterator &afterLast) {
// std::for_each and a lambda look like overkill here.
for (iterator f = first; f != afterLast; ++f) {
append(*f);
}
return *this;
}
StringBuilder & AppendLine(const string_t &src) {
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() {
chr lineFeed[] { 10, 0 };
m_Data.push_back(lineFeed);
++m_totalSize;
return *this; // allow chaining.
}
StringBuilder &Clear() {
m_totalSize = 0;
m_Data.clear();
return *this;
}
// ADVANCED TOPIC: AppendFormat()
// Like C# StringBuilder.ToString()
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) may take a serious toll,
// both in performance and chances of failure.
// I measured (in code I don't own) fractions of a second using 'reserve', and almost two minutes using +=.
result.reserve(1 + m_totalSize); // leave room for the ending zero.
// 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;
}
// Compute the required size, hoping it won't overflow the size type.
size_type st = (delim.size() * (m_Data.size() - 1)) + m_totalSize + 1;
result.reserve(st);
// Another nice feature in C++11: local structs can be used with STL algorithms.
struct adder {
string_t m_Joiner;
adder(const string_t &s): m_Joiner(s) {
// This constructor is NOT empty.
}
string_t operator()(string_t &preAllocated, const string_t ¤t) {
preAllocated += m_Joiner;
preAllocated += current;
return preAllocated;
}
} adr(delim);
auto iter = m_Data.begin();
result += *iter;
return std::accumulate(++iter, m_Data.end(), result, adr);
}
}; // class StringBuilder
#ifdef __USE_POSIX199309
class StopWatch {
enum { clockId = CLOCK_THREAD_CPUTIME_ID };
timespec m_startTime;
timespec m_endTime;
double m_seconds;
public:
static timespec diff(timespec start, timespec end)
{
// Thanks to Guy Rutenberg: http://www.guyrutenberg.com/2007/09/22/profiling-code-using-clock_gettime/
// Don't forget to add -lrt to the g++ linker command line.
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;
}
static double ToSeconds(const timespec &diff) {
return diff.tv_sec + diff.tv_nsec / 1e9;
}
void Start() {
clock_gettime(clockId, &m_startTime);
}
void Stop() {
clock_gettime(clockId, &m_endTime);
m_seconds = ToSeconds(diff(m_startTime, m_endTime));
}
double GetSeconds() const {
return m_seconds;
}
StopWatch() {
Start();
}
}; // struct StopWatch
void TestPerformance(const StringBuilder<wchar_t> &tested, const std::vector<std::wstring> &tested2) {
const int loops = 4001; // Odd number to keep 1 result at the end.
////////////////
// Test std::accumulate()
////////////////
std::wstring accumulate_result;
size_t accumulate_len = 0;
StopWatch swAccumulate;
for (int i = 0; i < loops; ++i) {
std::wstring accumulator;
accumulate_result = std::accumulate(tested2.begin(), tested2.end(), accumulator);
accumulate_len ^= accumulate_result.size();
}
swAccumulate.Stop();
using std::cout;
using std::endl;
cout << "\tstd::accumulate: " << swAccumulate.GetSeconds() << ": size " << accumulate_len << endl;
////////////////
// Test ToString()
////////////////
std::wstring toString_result;
size_t toString_len = 0;
StopWatch swToString;
for (int i = 0; i < loops; ++i) {
toString_result = tested.ToString();
toString_len ^= toString_result.size();
}
swToString.Stop();
cout << "\tToString: " << swToString.GetSeconds() << ": size " << toString_len << endl;
////////////////
// Test join()
////////////////
std::wstring join_result;
size_t join_len = 0;
StopWatch swJoin;
for (int i = 0; i < loops; ++i) {
join_result = tested.Join(L",");
join_len ^= join_result.size();
}
swJoin.Stop();
cout << "\tJoin: " << swJoin.GetSeconds() << ": size " << join_len << endl;
////////////////
// basic_ostringstream<wchar_t>
// First test: only getting the string, not filling the stream.
////////////////
typedef std::basic_ostringstream<wchar_t> wostringstream;
wostringstream woss;
for(size_t j = 0; j < tested2.size(); ++j)
woss << tested2[j];
std::wstring stringStream_result;
size_t stringStream_len = 0;
StopWatch swStringStream;
for (int i = 0; i < loops; ++i) {
stringStream_result = woss.str();
stringStream_len ^= stringStream_result.size();
}
swStringStream.Stop();
cout << "\tostringstream: " << swStringStream.GetSeconds() << ": size " << stringStream_len << endl;
////////////////
// Test lambda
////////////////
std::wstring strAccumulator;
size_t lambdaResult_len = 0;
StopWatch swLambda;
for (int i = 0; i < loops; ++i) {
std::wstring strtmp;
std::for_each(tested2.begin(), tested2.end(), [&](const std::wstring &s){ strtmp += s; });
if (0 == i) {
strAccumulator = strtmp;
}
lambdaResult_len ^= strtmp.size();
}
swLambda.Stop();
cout << "\tLambda: " << swLambda.GetSeconds() << ": size " << lambdaResult_len << endl;
////////////////
// Show results so far.
////////////////
cout << "* Performance test:" << endl
<< " Accumulate took " << swAccumulate.GetSeconds() << " seconds, and ToString() took " << swToString.GetSeconds() << " seconds." << endl
<< " The relative speed improvement was " << ((swAccumulate.GetSeconds() / swToString.GetSeconds()) - 1) * 100 << "%" << endl
<< " std::ostringstream took " << swStringStream.GetSeconds() << " with a relative speed improvement of " << ((swAccumulate.GetSeconds() / swStringStream.GetSeconds()) - 1) * 100 << "% (winning, you say?)" << endl
<< " lambda took " << swLambda.GetSeconds() << " with a relative speed improvement of " << ((swAccumulate.GetSeconds() / swLambda.GetSeconds()) - 1) * 100 << "% (winning, you say?)" << endl
<< " Join took " << swJoin.GetSeconds() << " seconds."
<< endl;
////////////////
// basic_ostringstream<wchar_t> and tostring: fill and execute.
////////////////
if (true) {
size_t tmp = 0;
typedef std::basic_ostringstream<wchar_t> wostringstream;
StopWatch swStringStream2;
for (int i = 0; i < loops; ++i) {
wostringstream woss;
for(size_t j = 0; j < tested2.size(); ++j)
woss << tested2[j];
/*
for (auto iter = tested2.begin(); iter != tested2.end(); ++iter) {
woss << *iter;
}
*/
tmp ^= woss.str().size();
}
swStringStream2.Stop();
cout << "\tostringstream (fill and convert to string): " << swStringStream2.GetSeconds() << ", length " << tmp << endl;
}
if (true) {
size_t tmp = 0;
StopWatch swToString2;
for (int i = 0; i < loops; ++i) {
StringBuilder<wchar_t> test;
test.Add(tested2.begin(), tested2.end());
tmp ^= test.ToString().size();
}
swToString2.Stop();
cout << "\tToString (fill and convert to string): " << swToString2.GetSeconds() << ", length " << tmp << endl;
}
}
#endif // def __USE_POSIX199309
std::vector<std::wstring> GetVector (const char * fileName) {
// http://www.cplusplus.com/doc/tutorial/files/
// reading a text file
using namespace std;
wstring line;
vector<wstring> results;
wifstream inputFile (fileName);
if (inputFile.is_open())
{
while ( getline (inputFile,line) )
{
results.push_back(line);
}
inputFile.close();
}
return results;
}
std::vector<std::wstring> GetWordByWordVector() {
// From http://en.wikipedia.org/wiki/Cargo_cult
static 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",
L" encompassing", L" a", L" diverse", L" range", L" of", L" practices", L" and", L" occurring", L" in",
L" the", L" wake", L" of", L" contact", L" with", L" the", L" commercial", L" networks", L" of", L" colonizing",
L" societies.", L" The", L" name", L" derives", L" from", L" the", L" apparent", L" belief", L" that", L" various",
L" ritualistic", L" acts", L" will", L" lead", L" to", L" a", L" bestowing", L" of", L" material", L" wealth",
L" (\"cargo\").", L" Cargo", L" cults", L" often", L" develop", L" during", L" a", L" combination", L" of",
L" crises.", L" Under", L" conditions", L" of", L" social", L" stress,", L" such", L" a", L" movement", L" may",
L" form", L" under", L" the", L" leadership", L" of", L" a", L" charismatic", L" figure.", L" This", L" leader",
L" may", L" have", L" a", L" 'vision'", L" (or", L" 'myth-dream')", L" of", L" the", L" future,", L" often", L" linked",
L" to", L" an", L" ancestral", L" efficacy", L" thought", L" to", L" be", L" recoverable", L" by", L" a", L" return",
L" to", L" traditional", L" morality.\n", L" This", L" leader", L" may", L" characterize", L" the", L" present",
L" state", L" (often", L" imposed", L" by", L" colonial", L" capitalist", L" regimes)", L" as", L" a", L" dismantling",
L" of", L" the", L" old", L" social", L" order,", L" meaning", L" that", L" social", L" hierarchy", L" and", L" ego",
L" boundaries", L" have", L" been", L" broken", L" down.", L" Contact", L" with", L" colonizing", L" groups", L" brought",
L" about", L" a", L" considerable", L" transformation", L" in", L" the", L" way", L" indigenous", L" peoples", L" of",
L" Melanesia", L" have", L" thought", L" about", L" other", L" societies.", L" Early", L" theories", L" of", L" cargo",
L" cults", L" began", L" from", L" the", L" assumption", L" that", L" practitioners", L" simply", L" failed", L" to",
L" understand", L" technology,", L" colonization,", L" or", L" capitalist", L" reform;", L" in", L" this", L" model,",
L" cargo", L" cults", L" are", L" a", L" misunderstanding", L" of", L" the", L" trade", L" networks", L" involved", L" in",
L" resource", L" distribution", L" and", L" an", L" attempt", L" to", L" acquire", L" such", L" goods", L" in", L" the",
L" wake", L" of", L" interrupted", L" trade.", L" However,", L" many", L" of", L" these", L" practitioners", L" actually",
L" focus", L" on", L" the", L" importance", L" of", L" sustaining", L" and", L" creating", L" new", L" social",
L" relationships,", L" with", L" material", L" relations", L" being", L" secondary.\n",
L"Since", L" the", L" late", L" twentieth", L" century,", L" alternative", L" theories", L" have", L" arisen.", L" For", L" example,", L" some", L" scholars,", L" such", L" as", L" Kaplan", L" and", L" Lindstrom,", L" focus", L" on", L" Europeans'", L" characterization", L" of", L" these", L" movements", L" as", L" a", L" fascination", L" with", L" manufactured", L" goods", L" and", L" what", L" such", L" a", L" focus", L" says", L" about", L" Western", L" commodity", L" fetishism.\n", L" Others", L" point", L" to", L" the", L" need", L" to", L" see", L" each", L" movement", L" as", L" reflecting", L" a", L" particularized", L" historical", L" context,", L" even", L" eschewing", L" the", L" term", L" \"cargo", L" cult\"", L" for", L" them", L" unless", L" there", L" is", L" an", L" attempt", L" to", L" elicit", L" an", L" exchange", L" relationship", L" from", L" Europeans.\n",
L"Causes, beliefs, and practices\n",
L"Cargo", L" cults", L" are", L" marked", L" by", L" a", L" number", L" of", L" common", L" characteristics,", L" including", L" a", L" 'myth-dream'", L" that", L" is", L" a", L" synthesis", L" of", L" indigenous", L" and", L" foreign", L" elements;", L" the", L" expectation", L" of", L" help", L" from", L" the", L" ancestors;", L" charismatic", L" leaders;", L" and", L" lastly,", L" belief", L" in", L" the", L" appearance", L" of", L" an", L" abundance", L" of", L" goods.\n",
L"The", L" indigenous", L" societies", L" of", L" Melanesia", L" were", L" typically", L" characterized", L" by", L" a", L" 'Big", L" Man'", L" political", L" system", L" in", L" which", L" individuals", L" gained", L" prestige", L" through", L" gift", L" exchanges.", L" The", L" more", L" wealth", L" a", L" man", L" could", L" distribute,", L" the", L" more", L" people", L" in", L" his", L" debt,", L" and", L" the", L" greater", L" his", L" renown.", L" Those", L" who", L" were", L" unable", L" to", L" reciprocate", L" were", L" identified", L" as", L" 'Rubbish", L" men'.", L" Faced,", L" through", L" colonialism,", L" with", L" foreigners", L" with", L" a", L" seemingly", L" unending", L" supply", L" of", L" goods", L" for", L" exchange,", L" indigenous", L" Melanesians", L" experienced", L" 'value", L" dominance.'", L" That", L" is,", L" they", L" were", L" dominated", L" by", L" others", L" in", L" terms", L" of", L" their", L" own", L" (not", L" the", L" foreign)", L" value", L" system;", L" exchange", L" with", L" foreigners", L" left", L" them", L" feeling", L" like", L" Rubbish", L" men.\n",
L"Since", L" the", L" modern", L" manufacturing", L" process", L" is", L" unknown", L" to", L" them,", L" members,", L" leaders,", L" and", L" prophets", L" of", L" the", L" cults", L" maintain", L" that", L" the", L" manufactured", L" goods", L" of", L" the", L" non-native", L" culture", L" have", L" been", L" created", L" by", L" spiritual", L" means,", L" such", L" as", L" through", L" their", L" deities", L" and", L" ancestors.", L" These", L" goods", L" are", L" intended", L" for", L" the", L" local", L" indigenous", L" people,", L" but", L" the", L" foreigners", L" have", L" unfairly", L" gained", L" control", L" of", L" these", L" objects", L" through", L" malice", L" or", L" mistake.\n", L" Thus,", L" a", L" characteristic", L" feature", L" of", L" cargo", L" cults", L" is", L" the", L" belief", L" that", L" spiritual", L" agents", L" will,", L" at", L" some", L" future", L" time,", L" give", L" much", L" valuable", L" cargo", L" and", L" desirable", L" manufactured", L" products", L" to", L" the", L" cult", L" members.\n",
L"Symbols", L" associated", L" with", L" Christianity", L" and", L" modern", L" Western", L" society", L" tend", L" to", L" be", L" incorporated", L" into", L" their", L" rituals", L" as", L" magical", L" artifacts,", L" for", L" example", L" the", L" use", L" of", L" cross-shaped", L" grave", L" markers.", L" Notable", L" examples", L" of", L" cargo", L" cult", L" activity", L" include", L" the", L" setting", L" up", L" of", L" mock", L" airstrips,", L" airports,", L" offices,", L" and", L" dining", L" rooms,", L" as", L" well", L" as", L" the", L" fetishization", L" and", L" attempted", L" construction", L" of", L" Western", L" goods,", L" such", L" as", L" radios", L" made", L" of", L" coconuts", L" and", L" straw.", L" Believers", L" may", L" stage", L" \"drills\"", L" and", L" \"marches\"", L" with", L" sticks", L" for", L" rifles", L" and", L" use", L" military-style", L" insignia", L" and", L" national", L" insignia", L" painted", L" on", L" their", L" bodies", L" to", L" make", L" them", L" look", L" like", L" soldiers,", L" thereby", L" treating", L" the", L" activities", L" of", L" Western", L" military", L" personnel", L" as", L" rituals", L" to", L" be", L" performed", L" for", L" the", L" purpose", L" of", L" attracting", L" the", L" cargo.\n",
L"Examples:\n",
L"The", L" term", L" 'Cargo", L" cult'", L" was", L" first", L" used", L" in", L" print", L" in", L" 1945", L" by", L" Norris", L" Mervyn", L" Bird,", L" repeating", L" a", L" derogatory", L" description", L" used", L" by", L" planters", L" and", L" businessmen", L" in", L" the", L" Australian", L" protectorate", L" of", L" Papua.", L" The", L" term", L" was", L" later", L" adopted", L" by", L" anthropologists,", L" and", L" applied", L" retroactively", L" to", L" movements", L" in", L" a", L" much", L" earlier", L" era.\n"
};
return cargoCult;
}
int main(int argc, char **argv) {
////////////////////////////////////
// ANSI, chaining.
////////////////////////////////////
std::cout << argv[0] << std::endl;
StringBuilder<char> ansi;
ansi.Append("Hello").Append(" ").AppendLine("World!");
std::cout << ansi.ToString();
////////////////////////////////////
// Unicode
////////////////////////////////////
StringBuilder<wchar_t> wide;
// Load from text file, to make it 'not deterministic'.
std::vector<std::wstring> cargoCult = GetVector("./cargoCult.txt");
// Files are not always there.
if (!cargoCult.empty())
{
// The .AppendLine() call at the end of the chain explains the extra character in the length.
wide.Add(cargoCult.begin(), cargoCult.end()).AppendLine();
std::wstring cargoCultString = wide.ToString();
std::wcout << cargoCultString << std::endl << "Length " << cargoCultString.size() << std::endl;
// javascript-like join.
std::wcout << wide.Join(L" _\n") << std::endl;
#ifdef __USE_POSIX199309
std::wcout << std::endl << L"Testing long lines" << std::endl;
TestPerformance(wide, cargoCult);
#endif // def __USE_POSIX199309
}
// The text file has a few long strings.
// This version, many short strings
cargoCult = GetWordByWordVector();
// The .AppendLine() call at the end of the chain explains the extra character in the length.
wide.Clear().Add(cargoCult.begin(), cargoCult.end()).AppendLine();
#ifdef __USE_POSIX199309
std::wcout << std::endl << L"Testing word by word" << std::endl;
TestPerformance(wide, cargoCult);
#endif // def __USE_POSIX199309
return 0;
}
Submit an article or tip