How is std::vector insert implemented? C++ -


recently rereading iso c++ standard, , found interesting note:

note std::vector, constraint on type t of std::vector<t> type t must have copy constructor. actually, if memory of vector full while insertion, allocate new memory of size = 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];

  1. how done, because type t may not have default constructor?
  2. then assignment, after allocating memory must assign old values new memory, right?
  3. 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

Popular posts from this blog

google api - Incomplete response from Gmail API threads.list -

Installing Android SQLite Asset Helper -

Qt Creator - Searching files with Locator including folder -