Continuing looking at the performance of data structures and different implementations and languages, let’s look at a simpler but very common container, the dynamic array.
The interesting performance properties of a dynamic array is constant, O(1), lookup time and amortized constant insertion and deletion at the end of the array. Random insertion on the other hand is linear, O(n), and typically something you want to avoid.
Continue reading Benchmarking dynamic array implementations
I think the lack of simple and basic dynamic data structures is a major reason why people sometimes struggle with programming in C.
To take a simple example the naive task of splitting a string into words is near trivial in C++ using the standard library, while in C you are challenged with how to dimension the resulting array. In most cases likely the solution here would be to declare a fixed size array with a MAX_WORDS constant size, and later when the parsing is done and you know the number of words, declare a new array into which you copy the result, and then return. Hardly an elegant solution, and you end up with making difficult assumptions regarding how many words a line realistically can contain.
Continue reading libdynamic – vector