How is std::vector insert implemented? C++ -
recently rereading iso c++ standard, , found interesting note:
note
std::vector
, constraint on typet
ofstd::vector<t>
typet
must have copy constructor. actually, if memory of vector full while insertion, allocate new memory ofsize = 2 * oldsize
(this implementation dependent) , copy old elements in , insert 1 element.
but wait??
to allocate new memory of type need this, ptr = new t[2*size];
- how done, because type
t
may not have default constructor? - then assignment, after allocating memory must assign old values new memory, right?
- to taking consideration 2 things, how
std::vector
"only copy constructor?" implementation , language idioms used?
it done call allocator function allocate() raw memory , following call allocator construct( iterator, val) construct element copy using placement new, i.e. similar this:
/* approach similar std::uninitialized fill taken */ template<typename t, typename > vector<t,a>::vector( size_type n, const t& val, const a& a) : alloc( a) // copy allocator { /* keep track of elements have been constructed * , destroy , in case of exception */ v = alloc.allocate( n); // memory elements iterator p; // declared before try{} still valid in catch{} block try { iterator end = v + n; for( p = v; p != end; ++p) alloc.construct( p, val); /* construct elements (placement new): e g. void construct( pointer p, const t& val) { ::new((void *)p) t( val); } */ last = space = p; } catch( ...) { for( iterator q = v; q != p; ++q) alloc.destroy( q); /* destroy constructed elements */ alloc.deallocate( v, n); /* free memory */ throw; /* re-throw signal constructor failed */ } }
in c++ allocator used insulate implementers of algorithms , containers must allocate memory details of physical memory.
approach using uninitialized_fill directly can taken:
std::uninitialized_fill( v, v + n, val); /* copy elements (placement new): e g. void construct( pointer p, const t& val) { ::new((void *)p) t( val); } */
this described more details in bjarne stroustrup's "c++...3rd edition". here sample written based on this.
Comments
Post a Comment