1

If I were to implement a vector class, I'd use a dynamically allocated array internally to store the items. Whenever that buffer would become to small, I would create a new buffer double the size, copy over the items, and delete the old buffer - thus not needing to regrow the buffer each time an item is pushed.

This approach has some serious problem in C++: It's impossible to allocate an array (new[]) of a type with no default constructor. Obviously std::vector somehow works around that limitation as it allows me to use any item type I want - even if it has no default constructor.

I tried to look at the source code, but it seems to be just turtles all the way down - using endless amounts of code and some serious black magic. I would really appreciate someone explaining how this works under the hood - if possible in a more comprehensible way than the source does.

Askaga
  • 6,061
  • 5
  • 25
  • 49

1 Answers1

8

The underlying mechanism to decouple memory allocation from object lifetime is:

  • call an allocation function to allocate raw memory without creating objects
  • use placement-new to create objects in that memory
  • call their destructors directly to destroy the objects without releasing memory
  • call a deallocation function to deallocate the memory.

which, in code, looks something like

void * memory = operator new(capacity() * sizeof(T));  // allocate memory
T * object = new(memory) T;                            // create an object
T->~T();                                               // destroy it
operator delete(memory);                               // deallocate memory

where operator new and operator delete are the default allocation and deallocation functions, used by new and delete expressions.

For standard containers, this is wrapped up in an "allocator" class, with a member function to do each of these operations; you can provide your own allocator if you have special needs that aren't met by the default std::allocator.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • So, basically you could say that placement new and manual destructor invocation were added to the language to enable black magic with raw memory segments? – Askaga Nov 11 '14 at 10:29
  • "use placement-new to create objects in that memory" - the allocator interface actually provides the functions for [creating objects at specific addresses](http://en.cppreference.com/w/cpp/memory/allocator/construct), and [destroying them](http://en.cppreference.com/w/cpp/memory/allocator/destroy), so the vector-level code probably shouldn't be doing that itself.... – Tony Delroy Nov 11 '14 at 10:29
  • 1
    @TonyD: Indeed, as I said in the last paragraph, the underlying mechanism is abstracted into a class, and the container uses that. – Mike Seymour Nov 11 '14 at 10:31
  • 1
    @BillAskaga: That's a common use for them, yes. They can also be useful for unions of non-trivial types (since C++11). – Mike Seymour Nov 11 '14 at 10:33
  • @MikeSeymour: oh yup - reads better with your edit too. Will leave my comment above for the links. Cheers and +1. – Tony Delroy Nov 11 '14 at 10:33
  • @BillAskaga: yet another (obscure) use for placement-`new` is to overwrite an object with another without having the first's destructor invoked - that's only valid if the rest of the program doesn't depend on the side effects of the not-invoked destructor - which is vague enough that the technique's best avoided unless there's a clear need and experienced programmer. – Tony Delroy Nov 11 '14 at 10:36