[C++] Vector memory management

Quote:

Original post by Degra This is out of pure curiosity - how does a vector store elements? Does it use a linked list? contiguous memory? a combination of both? Degra

The definition of a vector in the C++ standard implies that the elements are always stored in contiguous memory (more exactly, the requirements that the standard puts on the vector implies this).

A contiguous block of memory; this is guaranteed by the Standard. std::list is a doubly-linked list, and std::deque is usually (very roughly) kind of a list of contiguous blocks.

Ok cool thanks. I presume, that when the vector can't extend itself because it runs out of free memory, it'll move the whole thing to where there's a block of free memory big enough?

Quote:

Original post by Degra Ok cool thanks. I presume, that when the vector can't extend itself because it runs out of free memory, it'll move the whole thing to where there's a block of free memory big enough?

When the vector runs out of mem and needs to extend, it allocates a new memory bloc using its allocator and copies the existing data at the beginning of this chunk of memory.

Yes; it allocates a new block that is larger than the current one by some constant factor (usually 2). This exponential growth strategy guarantees that insertions to the end are "fast" on average (as required by the Standard; linear-time in the number of new elements instead of quadratic).

Of course, this means that some space is wasted, but that's rarely a problem. If it is, you can always micromanage with reserve().

Any of you standards gurus know whether a vector is able to increase its capacity in-place, like re-alloc, and save on some copying? And/or is that all down to the allocator? Just out of interest.

I don't believe so. The allocator interface is standardized, and doesn't include any functions for reallocation, so vector wouldn't have a way to ask.

Quote:

Original post by Sneftel I don't believe so. The allocator interface is standardized, and doesn't include any functions for reallocation, so vector wouldn't have a way to ask.

Not true, the standard does provide a mechanism to allow for standard containers to provide a hint during allocation, this is what the other pointer in the allocate member function decleration is for, it is a hint to the implementation. However, most implementations do ignore any benefits that using the hint may provide.

Quote:

Original post by Sharlin A contiguous block of memory; this is guaranteed by the Standard. std::list is a doubly-linked list, and std::deque is usually (very roughly) kind of a list of contiguous blocks.

Actually, the standard does not guarantee this. TR1 did provide additional requirements that includes this for the standard vector, however TR1 is entirely optional to support. As such, an implementation of a vector is not guaranteed to be contiguous, at least until C++0x. In practice though, all known implementations of the standard library provide a contiguous vector.

That would be tricky. You would have to first ask "extend this block of memory if possible, but if not possible just fail". If that failed, do the usual vector stuffs.

Quote:

Original post by Washu Actually, the standard does not guarantee this. TR1 did provide additional requirements that includes this for the standard vector, however TR1 is entirely optional to support. As such, an implementation of a vector is not guaranteed to be contiguous, at least until C++0x.

TC1 (Technical Corrigendum #1, or "C++03"), not TR1, added the guarantee that the storage is contiguous; TR1 made no modifications to the standard library apart from adding the tr1 namespace and its contents. Thus, a C++03-conformant implementation is required to provide contiguous storage, though a C++98-conformant one would not.

Quote:

Original post by NotAYakk That would be tricky. You would have to first ask "extend this block of memory if possible, but if not possible just fail". If that failed, do the usual vector stuffs.

It's actually not tricky at all. realloc() in the standard C library does exactly that with plain memory, and it's not unknown for standard C++ libraries to be implemented with malloc/free.

realloc isn't sufficient. You want to call operator= if and only if you actually reallocate.

realloc does a memcopy if it can't resize the memory block.

Is there a C standard library function for "try to extend this memory block, and if it fails just tell me and do nothing"?

It's easy to tell if realloc moved the block or not. I guess the real issue is what to do about objects that find themselves in a different position in memory, which may be referring to other objects that don't know they've moved. I doubt there's anything in the standard library that can handle that, so it would have to be a platform specific thing I suppose.

In the C++ world, when you move a block of memory, you should call operator=, not just copy the bits over.

By the time the memory has been moved, you have already broken the std::vector guarantees (and any reasonable modifications of the guarantees). So being able to tell that it moved the memory, after it moves it, is useless. :)

Quote:

I guess the real issue is what to do about objects that find themselves in a different position in memory, which may be referring to other objects that don't know they've moved.

That is one of the many reasons why you have to call operator=, and not just copy bits, yes.

Still, it would make a decent extension to the standard: a "attempt to realloc in place" method on an allocator (which does nothing on failure). Sadly, adding methods to an allocator would break all existing custom allocators. :(

Quote:

Original post by Kylotan Quote: Original post by NotAYakk That would be tricky. You would have to first ask "extend this block of memory if possible, but if not possible just fail". If that failed, do the usual vector stuffs. It's actually not tricky at all. realloc() in the standard C library does exactly that with plain memory, and it's not unknown for standard C++ libraries to be implemented with malloc/free.

Hang on a second... The standard states that:
if realloc needs to grow/shrink the space and malloc fails it returns NULL
otherwise it returns a pointer to the beginning of the memory block.

But what if the memory manager implementation is storing 1 or more bits as flags in the pointer (feasible with word-size alignment for instance)? I don't see the standard specifying that in the case that realloc does not copy the buffer, that the pointer returned will be the pointer input. Therefore is it actually possible to confirm (in a fully portable way) that realloc did not move the buffer?

Quote:

Original post by Anonymous Poster For the love of my life, I can't seem to be able to figure out how to add a link.

The first step is to register for the forums. It's free :)

After that, you just use HTML, i.e. e.g..