allocator ---- (1)

Before talking about this topic, let's talk about new operator.

Ever since I started to use c++ instead of c, malloc, calloc is somehow replaced by new oeprator,

however I had the wrong feeling new is merely call malloc to allocate memory and then call the constructor of the class.

This is true for the global new operator, however too many malloc call to switch context between user mode and system mode is too expensive.

So we need another type of new which is called placement new.

What is placement new?

it's only target on the pointer which has been allocate space but not created and initialize one instance on the specified address

new (place_address) type

new (place_address) type (initializer-list)

So to reduce the significant time waste on repeated malloc call, we can simply allocate a big space, and use placement new to initialize the instances, and that's exactly std::vector allocator doing.

Let's have a look at VS2010's vector implementation of this line

std::vector<a>

(1000);

so the constructor will call resize function, in the resize function, it will call reserve to allocate the specified space. Here reserve will use the allocator's allocate function which will finally call

::operator new(_Count * sizeof (_Ty)) which will allocate a big space altogether first,

_Uninitialized_default_fill_n will truly call _Cons_val(_Al, _First, _Valty()); to construct the instances which basically will call _Count times placement new

::new ((void _FARQ *)_Ptr) _Ty(_STD forward<_ty>(_Val));

to initialize all the instances.

By this way there is only one time malloc happens here:

::operator new(_Count * sizeof (_Ty))

and N times placement new only initialize allocated space in user mode, no extra system mode switching, it's much faster than loop calling malloc or global operator new.

explicit vector(size_type _Count)

: _Mybase()

{ // construct from _Count * _Ty()

resize(_Count);

}

void resize(size_type _Newsize)

{ // determine new length, padding with _Ty() elements as needed

if (_Newsize <>

erase(begin() + _Newsize, end());

else if (size() <>

{ // pad as needed

_Reserve(_Newsize - size());

_Uninitialized_default_fill_n(this->_Mylast, _Newsize - size(),

(_Ty *)0, this->_Alval);

this->_Mylast += _Newsize - size();

}

}

void _Uninit_def_fill_n(_FwdIt _First, _Diff _Count,

const _Tval *, _Alloc& _Al,

_Valty *, _Nonscalar_ptr_iterator_tag)

{ // copy _Count * _Valty() to raw _First, using _Al, arbitrary type

#if _ITERATOR_DEBUG_LEVEL == 2

// if (_Count <>

// _DEBUG_ERROR("negative count in uninitialized fill");

#endif /* _ITERATOR_DEBUG_LEVEL == 2 */

_FwdIt _Next = _First;

_TRY_BEGIN

for (; 0 <>

_Cons_val(_Al, _First, _Valty());

_CATCH_ALL

for (; _Next != _First; ++_Next)

_Dest_val(_Al, _Next);

_RERAISE;

_CATCH_END

}

void _Cons_val(_Alloc& _Alval, _Ty1 *_Pdest, _Ty2&& _Src)
{ // construct using allocator
_Alval.construct(_Pdest, _STD forward<_ty2>(_Src));
}

void construct(pointer _Ptr, _Ty&& _Val)
{ // construct object at _Ptr with value _Val
::new ((void _FARQ *)_Ptr) _Ty(_STD forward<_ty>(_Val));
}