Skip to main content

Posts

Showing posts from November, 2012

How to outperform std::vector in 1 easy step

Everyone who's familiar with C++ knows that you should avoid resizing a std::vector inside a loop wherever possible. The reasoning's pretty obvious: the memory allocated for the vector doubles in size each time it fills up and that doubling is a costly operation. Have you ever wondered why it's so costly though? It's tempting to assume that because implementations of the STL have been around for so long that they must be pretty efficient. It turns out that's a bad assumption because the problem, in this case, is the standard itself: specifically, the allocator interface. The allocator interface provides two methods that obtain and release memory: allocate allocates uninitialized storage (public member function) deallocate deallocates storage (public member function) (taken from this page ). What's missing is a   way of growing an existing memory allocation in place. In C this is provided by the realloc function, but there's no equiva