[plorkyeran]

It always calls (the equivalent of) malloc + memcpy + free for each grow, so it can be anywhere from the exact same speed (when realloc does the same thing internally) to absurdly slower (in the given case of a large array that has to be paged in). The first case is by far the most common case, but it is something that sometimes matters.

[yongjik]

It seems that even vector::shrink_to_fit is implemented that way.

That is, when you call shrink_to_fit, it first copies all elements it has, swaps itself with the new copy, and deletes the original vector. (Probably because there's no portable way of returning only part of a contiguous memory region. Yikes.)

http://stackoverflow.com/questions/2695552/how-to-shrink-to-...

[dbaupp]

I think the reason is the existence of move/copy constructors, i.e. it's invalid to just move a C++ object in memory (as a realloc would do), in general.

(shrink_to_fit does need to (attempt to) get a smaller allocation, otherwise or wouldn't be shrinking the vector.)

[BugBrother]

Huh, is it really implemented like that?!

Why use realloc when growing an array you have an interface to? Just add another allocated buffer to the previous allocated areas. When there are too many small areas, consolidate with realloc/free.

Much faster (yes yes, almost always).

(Disclaimer: Last time I used C++ I had hair. :-) )

Edit: OK, thanks plorkyeran.

[stormbrew]

> Huh, is it really implemented like that?!

Well, there is no grow() method on std::vector, so ... no?

But generally speaking, std::vector implementations are basically required to[1] grow the backing store exponentially so that adding elements to them absolutely does not call malloc on every growth of the vector.

You can make a vector do this kind of pessimistic allocation by calling reserve() for every element you add, which will cause the allocation of exactly the amount you reserved. This would be dumb, though. Reserve is there so you can allocate a precise large number and avoid even the logarithmic cost of allocation in adding elements to the vector.

It's really worth noting that this is a better worst case than the worst case for realloc(), which is entirely entitled to reallocate and copy every single time you call it. You're pretty likely to implement the exact same algorithm as vector if you DIY because of this exact issue when performance is important.

I do agree, though, that it would be nice if there was a failable realloc in C++ (and C for that matter) as described above, where it simply returns NULL if there's no more room in the allocated space. What to do in that event should really be up to the caller, not a black box algorithm sensitive to all sorts of variables.

[1] Because push_back() has a requirement of having amortized constant complexity, which means that it would be non-conforming to have the entire array moved for every push. http://www.cplusplus.com/reference/vector/vector/push_back/

[N] However, std::basic_string allows linear complexity on its push_back, so that may be what the poster meant. I'm not aware of any widely used implementation that actually does it in worse than amortized constant, though.

[BugBrother]

I was talking of the standard way of sllocating extra buffers, to keep new data. With a layer on top of this, using a series of pointers (8-16) to the underlaying memory areas.

(When you fill up the sub-buffers, you do a realloc to all of them. Future sub-buffers get the new size.)

This needs less copying and (potentially) free calls. On the other hand: An access would need some extra operation to find the right buffer and get an offset into it.

Edit: Ok, thanks. I explained if I was unclear, since you went off on a tangent. It was informative, so it is all good. (I'm not going back to C++ et al anyway. :-) )

[stormbrew]

I know. I wasn't really replying to that, though.

The standard library actually does have a built in container that's (almost) exactly as you describe, though. It's called std::deque (http://www.cplusplus.com/reference/deque/deque/).

[plorkyeran]

std::vector guarantees that it stores its elements contiguously, as this is required for a lot of use-cases (such as passing the buffer to one of the millions of functions that take just a pointer and a size).

[KayEss]

What you're talking about is some sort of rope data structure which is pretty simple to implement on top of std::vector and std::list. The std::vector guarantees contiguous memory locations so you can't do it for that particular container.