4 ms·
I'm old enough to remember that Microsoft got this wrong back in the early 90s. In early versions of Microsoft Foundation Classes, which Windows C++ programmer
by not2b 5y ago
I'm old enough to remember that Microsoft got this wrong back in the early 90s. In early versions of Microsoft Foundation Classes, which Windows C++ programmers were using before the STL took over and std::string became the thing, repeatedly appending a character to a string (I think it was CString) was quadratic, because they didn't increase array size by a multiplicative factor, but by a linear amount, so you'd get a ton of reallocation and copying. I used to use versions of this as an interview question.
However, language for concepts evolves with time, and younger programmers shouldn't assume that older programmers don't know a concept because they learned it by a different name. (Though they might not know the concept).
- Chris_Newton 5y agoIn early versions of Microsoft Foundation Classes … repeatedly appending a character to a string (I think it was CString) was quadratic, because they didn't increase array size by a multiplicative factor, but by a linear amount, so you'd get a ton of reallocation and copying. I remember seeing production code slow to a crawl once because of that one. It wasn’t long after I’d left university, where I’d studied CS but the lectures on complexity theory had seemed quite theoretical at the time. Suddenly, here was a vivid example of how it could cause a problem in practice, in a situation as everyday as putting some text in a UI. The solution — using a string builder — then led me to several other principles about choosing an efficient internal representation for data and it being OK not to convert that data into its “true” form until you’re ready to use it. I suppose I should thank whoever made the original mistake, because despite causing a frustrating afternoon with a profiler, it also created several lightbulb moments early in my career.