STL 源码剖析 -- Allocator 内存分配全揭秘
1、std::allocator
操作符 new 申请内存成功后，调用构造函数初始化内存。另外一种申请内存的方法是调用 operator new() 函数，该函数只申请内存，不执行构造函数。
#include <iostream>
class Foo {
public:
Foo() { std::cout << "Foo::ctor" << std::endl; }
~Foo() { std::cout << "Foo::dtor" << std::endl; }
};
int main() {
{
std::cout << "======" << std::endl;
Foo* foo = new Foo;
delete foo;
}
{
std::cout << "======" << std::endl;
Foo* foo = static_cast<Foo*>(::operator new(sizeof(Foo)));
::operator delete(foo);
}
return 0;
}
上述程序输出为
====== Foo::ctor Foo::dtor ======
申请内存后如何构造对象呢，可以使用 placement new 函数，如下。
Foo* foo = static_cast<Foo*>(::operator new(sizeof(Foo))); new (foo) Foo(); foo->~Foo(); ::operator delete(foo);
1.1、std::allocator
std::allocator 旨在将内存申请与对象构造分离。std::allocator 直接继承 __new_allocator
template<typename _Tp>
using __allocator_base = __new_allocator<_Tp>;
template<typename _Tp>
class allocator : public __allocator_base<_Tp>
{
public:
typedef _Tp value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
#if __cplusplus <= 201703L
// These were removed for C++20.
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
template<typename _Tp1>
struct rebind
{ typedef allocator<_Tp1> other; };
#endif
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2103. std::allocator propagate_on_container_move_assignment
using propagate_on_container_move_assignment = true_type;
using is_always_equal
_GLIBCXX20_DEPRECATED_SUGGEST("std::allocator_traits::is_always_equal")
= true_type;
#endif
/* ... */
};
allocator::rebind 是为了从一种类型，获取另外一种类型的 allocator，两种 allocator 是相同种类的分配器。
1.2、__new_allocator
__new_allocator 是一个空类，没有任何成员变量
template<typename _Tp>
class __new_allocator
{
public:
typedef _Tp value_type;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
#if __cplusplus <= 201703L
typedef _Tp* pointer;
typedef const _Tp* const_pointer;
typedef _Tp& reference;
typedef const _Tp& const_reference;
template<typename _Tp1>
struct rebind
{ typedef __new_allocator<_Tp1> other; };
#endif
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 2103. propagate_on_container_move_assignment
typedef std::true_type propagate_on_container_move_assignment;
#endif
allocate/deallocate 分配调用 operator new() 和 operator delete() 申请和释放内存。
_GLIBCXX_NODISCARD _Tp*
allocate(size_type __n, const void* = static_cast<const void*>(0))
{
#if __cplusplus >= 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3308. std::allocator<void>().allocate(n)
static_assert(sizeof(_Tp) != 0, "cannot allocate incomplete types");
#endif
if (__builtin_expect(__n > this->_M_max_size(), false))
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 3190. allocator::allocate sometimes returns too little storage
if (__n > (std::size_t(-1) / sizeof(_Tp)))
std::__throw_bad_array_new_length();
std::__throw_bad_alloc();
}
#if __cpp_aligned_new
if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
{
std::align_val_t __al = std::align_val_t(alignof(_Tp));
return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp),
__al));
}
#endif
return static_cast<_Tp*>(_GLIBCXX_OPERATOR_NEW(__n * sizeof(_Tp)));
}
// __p is not permitted to be a null pointer.
void
deallocate(_Tp* __p, size_type __n __attribute__ ((__unused__)))
{
#if __cpp_sized_deallocation
# define _GLIBCXX_SIZED_DEALLOC(p, n) (p), (n) * sizeof(_Tp)
#else
#endif
#if __cpp_aligned_new
if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
{
_GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n),
std::align_val_t(alignof(_Tp)));
return;
}
#endif
_GLIBCXX_OPERATOR_DELETE(_GLIBCXX_SIZED_DEALLOC(__p, __n));
}
construct()/destroy() 赋值对象的构造和析构。
template<typename _Up, typename... _Args>
void
construct(_Up* __p, _Args&&... __args)
noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
{ ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
template<typename _Up>
void
destroy(_Up* __p)
noexcept(std::is_nothrow_destructible<_Up>::value)
{ __p->~_Up(); }
2、allocator_traits
用户不仅可以使用 std::allocator，还可以使用自定义的 allocator。allocator_traits 提供了一种标准的接口取访问 allocator 的成员变量、成员函数，以及定义的类型。
struct __allocator_traits_base
{
template<typename _Tp, typename _Up, typename = void>
struct __rebind : __replace_first_arg<_Tp, _Up> { };
template<typename _Tp, typename _Up>
struct __rebind<_Tp, _Up,
__void_t<typename _Tp::template rebind<_Up>::other>>
{ using type = typename _Tp::template rebind<_Up>::other; };
protected:
template<typename _Tp>
using __pointer = typename _Tp::pointer;
template<typename _Tp>
using __c_pointer = typename _Tp::const_pointer;
template<typename _Tp>
using __v_pointer = typename _Tp::void_pointer;
template<typename _Tp>
using __cv_pointer = typename _Tp::const_void_pointer;
template<typename _Tp>
using __pocca = typename _Tp::propagate_on_container_copy_assignment;
template<typename _Tp>
using __pocma = typename _Tp::propagate_on_container_move_assignment;
template<typename _Tp>
using __pocs = typename _Tp::propagate_on_container_swap;
template<typename _Tp>
using __equal = typename _Tp::is_always_equal;
};
template<typename _Alloc, typename _Up>
using __alloc_rebind
= typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;
/// @endcond
/**
* @brief Uniform interface to all allocator types.
* @headerfile memory
* @ingroup allocators
* @since C++11
*/
template<typename _Alloc>
struct allocator_traits : __allocator_traits_base
{
/// The allocator type
typedef _Alloc allocator_type;
/* ... */
};
allocate() 和 deallocate() 调用底层 allocator 对应的函数。
_GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
allocate(_Alloc& __a, size_type __n)
{ return __a.allocate(__n); }
static _GLIBCXX20_CONSTEXPR void
deallocate(_Alloc& __a, pointer __p, size_type __n)
{ __a.deallocate(__p, __n); }
construct() 需要判断底层 allocator 是否定义了 construct 函数（能够处理传入的参数），如果可以，就调用，否则使用 placement new() 调用构造函数
template<typename _Tp, typename... _Args>
static _GLIBCXX20_CONSTEXPR auto
construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
noexcept(noexcept(_S_construct(__a, __p,
std::forward<_Args>(__args)...)))
-> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }
_S_construct() 的第二个定义就是使用 placement new() 构造对象。
template<typename _Tp, typename... _Args>
static _GLIBCXX14_CONSTEXPR _Require<__has_construct<_Tp, _Args...>>
_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
{ __a.construct(__p, std::forward<_Args>(__args)...); }
template<typename _Tp, typename... _Args>
static _GLIBCXX14_CONSTEXPR
_Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
is_constructible<_Tp, _Args...>>>
_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
noexcept(std::is_nothrow_constructible<_Tp, _Args...>::value)
{
#if __cplusplus <= 201703L
::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
#else
std::construct_at(__p, std::forward<_Args>(__args)...);
#endif
}
destroy() 也是如此
template<typename _Tp>
static _GLIBCXX20_CONSTEXPR void
destroy(_Alloc& __a, _Tp* __p)
noexcept(noexcept(_S_destroy(__a, __p, 0)))
{ _S_destroy(__a, __p, 0); }
template<typename _Alloc2, typename _Tp>
static _GLIBCXX14_CONSTEXPR auto
_S_destroy(_Alloc2& __a, _Tp* __p, int)
noexcept(noexcept(__a.destroy(__p)))
-> decltype(__a.destroy(__p))
{ __a.destroy(__p); }
template<typename _Alloc2, typename _Tp>
static _GLIBCXX14_CONSTEXPR void
_S_destroy(_Alloc2&, _Tp* __p, ...)
noexcept(std::is_nothrow_destructible<_Tp>::value)
{ std::_Destroy(__p); }
如果是 std::allocator，construct() 和 destroy() 直接调用 std::allocator 的函数构造和释放对象。
template<typename _Tp>
struct allocator_traits<allocator<_Tp>>
{
/* ... */
template<typename _Up, typename... _Args>
static _GLIBCXX20_CONSTEXPR void
construct(allocator_type& __a __attribute__((__unused__)), _Up* __p,
_Args&&... __args)
noexcept(std::is_nothrow_constructible<_Up, _Args...>::value)
{
#if __cplusplus <= 201703L
__a.construct(__p, std::forward<_Args>(__args)...);
#else
std::construct_at(__p, std::forward<_Args>(__args)...);
#endif
}
template<typename _Up>
static _GLIBCXX20_CONSTEXPR void
destroy(allocator_type& __a __attribute__((__unused__)), _Up* __p)
noexcept(is_nothrow_destructible<_Up>::value)
{
#if __cplusplus <= 201703L
__a.destroy(__p);
#else
std::destroy_at(__p);
#endif
}
};
__gnu_cxx::__alloc_traits 是对 std::allocator_traits 的封装
template<typename _Alloc, typename = typename _Alloc::value_type>
struct __alloc_traits
#if __cplusplus >= 201103L
: std::allocator_traits<_Alloc>
#endif
{
typedef _Alloc allocator_type;
#if __cplusplus >= 201103L
typedef std::allocator_traits<_Alloc> _Base_type;
typedef typename _Base_type::value_type value_type;
typedef typename _Base_type::pointer pointer;
typedef typename _Base_type::const_pointer const_pointer;
typedef typename _Base_type::size_type size_type;
typedef typename _Base_type::difference_type difference_type;
// C++11 allocators do not define reference or const_reference
typedef value_type& reference;
typedef const value_type& const_reference;
using _Base_type::allocate;
using _Base_type::deallocate;
using _Base_type::construct;
using _Base_type::destroy;
using _Base_type::max_size;
private:
template<typename _Ptr>
using __is_custom_pointer
= std::__and_<std::is_same<pointer, _Ptr>,
std::__not_<std::is_pointer<_Ptr>>>;
public:
// overload construct for non-standard pointer types
template<typename _Ptr, typename... _Args>
static _GLIBCXX14_CONSTEXPR
std::__enable_if_t<__is_custom_pointer<_Ptr>::value>
construct(_Alloc& __a, _Ptr __p, _Args&&... __args)
noexcept(noexcept(_Base_type::construct(__a, std::__to_address(__p),
std::forward<_Args>(__args)...)))
{
_Base_type::construct(__a, std::__to_address(__p),
std::forward<_Args>(__args)...);
}
// overload destroy for non-standard pointer types
template<typename _Ptr>
static _GLIBCXX14_CONSTEXPR
std::__enable_if_t<__is_custom_pointer<_Ptr>::value>
destroy(_Alloc& __a, _Ptr __p)
noexcept(noexcept(_Base_type::destroy(__a, std::__to_address(__p))))
{ _Base_type::destroy(__a, std::__to_address(__p)); }
static constexpr _Alloc _S_select_on_copy(const _Alloc& __a)
{ return _Base_type::select_on_container_copy_construction(__a); }
static _GLIBCXX14_CONSTEXPR void _S_on_swap(_Alloc& __a, _Alloc& __b)
{ std::__alloc_on_swap(__a, __b); }
static constexpr bool _S_propagate_on_copy_assign()
{ return _Base_type::propagate_on_container_copy_assignment::value; }
static constexpr bool _S_propagate_on_move_assign()
{ return _Base_type::propagate_on_container_move_assignment::value; }
static constexpr bool _S_propagate_on_swap()
{ return _Base_type::propagate_on_container_swap::value; }
static constexpr bool _S_always_equal()
{ return _Base_type::is_always_equal::value; }
static constexpr bool _S_nothrow_move()
{ return _S_propagate_on_move_assign() || _S_always_equal(); }
template<typename _Tp>
struct rebind
{ typedef typename _Base_type::template rebind_alloc<_Tp> other; };
#else // ! C++11
#endif // C++11
};
3、std::_Construct()/std::_Destroy()
这两个是内部函数，分别用于构成和析构对象。
3.1、std::_Construct()
_Construct() 的实现比较简单，调用 placement new() 使用构造函数构造对象。
#if __cplusplus >= 201103L
template<typename _Tp, typename... _Args>
_GLIBCXX20_CONSTEXPR
inline void
_Construct(_Tp* __p, _Args&&... __args)
{
#if __cplusplus >= 202002L
/* ... */
#endif
::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
}
#else
/* ... */
#endif
3.2、std::_Destroy()
析构单个对象，直接调用对象的析构函数。
template<typename _Tp>
_GLIBCXX14_CONSTEXPR inline void
_Destroy(_Tp* __pointer)
{
#if __cplusplus > 201703L
std::destroy_at(__pointer);
#else
__pointer->~_Tp();
#endif
}
如果析构 [first, last) 迭代器范围内的对象，需要借助 _Destroy_aux 对象。
template<typename _ForwardIterator>
_GLIBCXX20_CONSTEXPR inline void
_Destroy(_ForwardIterator __first, _ForwardIterator __last)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_Value_type;
#if __cplusplus >= 201103L
// A deleted destructor is trivial, this ensures we reject such types:
static_assert(is_destructible<_Value_type>::value,
"value type is destructible");
#endif
#if __cplusplus >= 202002L
/* ... */
#endif
std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
__destroy(__first, __last);
}
_Destroy_aux 如果模板参数为 true，其成员函数 __destroy() 为空，什么都不做。
template<bool>
struct _Destroy_aux
{
template<typename _ForwardIterator>
static _GLIBCXX20_CONSTEXPR void
__destroy(_ForwardIterator __first, _ForwardIterator __last)
{
for (; __first != __last; ++__first)
std::_Destroy(std::__addressof(*__first));
}
};
template<>
struct _Destroy_aux<true>
{
template<typename _ForwardIterator>
static void
__destroy(_ForwardIterator, _ForwardIterator) { }
};
结合 _Destroy 的定义，如果对象的析构函数是 trivial 的（比如默认析构析构函数），则 _Destroy() 不会调用其析构函数，直接返回。
4、std::copy()
std::copy() 会尽量使用 memmove() 函数来完成对象的拷贝。
template<typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
inline _OI
copy(_II __first, _II __last, _OI __result)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_II>)
__glibcxx_function_requires(_OutputIteratorConcept<_OI,
typename iterator_traits<_II>::reference>)
__glibcxx_requires_can_increment_range(__first, __last, __result);
return std::__copy_move_a<__is_move_iterator<_II>::__value>
(std::__miter_base(__first), std::__miter_base(__last), __result);
}
__copy_move_a ==> __copy_move_a1 ==> __copy_move_a2
这里没有考虑 deque 和 istreambuf_iterator。 __copy_move_a1 对于 deque 有不同的实现， __copy_move_a2 也针对 istreambuf_iterator 做了区分，这里不深究。
template<bool _IsMove, typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
inline _OI
__copy_move_a(_II __first, _II __last, _OI __result)
{
return std::__niter_wrap(__result,
std::__copy_move_a1<_IsMove>(std::__niter_base(__first),
std::__niter_base(__last),
std::__niter_base(__result)));
}
template<bool _IsMove, typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
inline _OI
__copy_move_a1(_II __first, _II __last, _OI __result)
{ return std::__copy_move_a2<_IsMove>(__first, __last, __result); }
template<bool _IsMove, typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
inline _OI
__copy_move_a2(_II __first, _II __last, _OI __result)
{
typedef typename iterator_traits<_II>::iterator_category _Category;
#ifdef __cpp_lib_is_constant_evaluated
/* ... */
#endif
return std::__copy_move<_IsMove, __memcpyable<_OI, _II>::__value,
_Category>::__copy_m(__first, __last, __result);
}
抽丝剥茧，最后调用 __copy_move::__copy_m() 成员函数完成对象拷贝。
__copy_move 三个模板函数
- _IsMove表示是否支持 move
- _IsSimple 表示对象是否可以直接拷贝内存，不用执行构造函数
- _Category 表示迭代器类型
__copy_move 只有两个目的
- 尽量使用 memmove
- 如果是 random access iterator，循环使用确切的 count
template<bool _IsMove, bool _IsSimple, typename _Category>
struct __copy_move
{
template<typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
static _OI
__copy_m(_II __first, _II __last, _OI __result)
{
for (; __first != __last; ++__result, (void)++__first)
*__result = *__first;
return __result;
}
};
4.1、IsMove(true) + IsSimple(false)
使用移动赋值函数
template<typename _Category>
struct __copy_move<true, false, _Category>
{
template<typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
static _OI
__copy_m(_II __first, _II __last, _OI __result)
{
for (; __first != __last; ++__result, (void)++__first)
*__result = std::move(*__first);
return __result;
}
};
4.2、IsMove(false) + IsSimple(false) + random
使用普通赋值函数，loop 使用 count 计数
template<>
struct __copy_move<false, false, random_access_iterator_tag>
{
template<typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
static _OI
__copy_m(_II __first, _II __last, _OI __result)
{
typedef typename iterator_traits<_II>::difference_type _Distance;
for(_Distance __n = __last - __first; __n > 0; --__n)
{
*__result = *__first;
++__first;
++__result;
}
return __result;
}
4.3、IsMove(true) + IsSimple(false) + random
使用移动赋值函数，loop 使用 count 计数
template<>
struct __copy_move<true, false, random_access_iterator_tag>
{
template<typename _II, typename _OI>
_GLIBCXX20_CONSTEXPR
static _OI
__copy_m(_II __first, _II __last, _OI __result)
{
typedef typename iterator_traits<_II>::difference_type _Distance;
for(_Distance __n = __last - __first; __n > 0; --__n)
{
*__result = std::move(*__first);
++__first;
++__result;
}
return __result;
}
};
4.4、IsSimple(true) + random
使用 memmove 拷贝对象
template<bool _IsMove>
struct __copy_move<_IsMove, true, random_access_iterator_tag>
{
template<typename _Tp>
_GLIBCXX20_CONSTEXPR
static _Tp*
__copy_m(const _Tp* __first, const _Tp* __last, _Tp* __result)
{
#if __cplusplus >= 201103L
using __assignable = __conditional_t<_IsMove,
is_move_assignable<_Tp>,
is_copy_assignable<_Tp>>;
// trivial types can have deleted assignment
static_assert( __assignable::value, "type must be assignable" );
#endif
const ptrdiff_t _Num = __last - __first;
if (_Num)
__builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
return __result + _Num;
}
};
5、std::fill()
std::fill() 具有和 std::copy() 相似的逻辑：尽量调用 memset() 完成赋值。
template<typename _ForwardIterator, typename _Tp>
_GLIBCXX20_CONSTEXPR
inline void
fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
{
// concept requirements
__glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
_ForwardIterator>)
__glibcxx_requires_valid_range(__first, __last);
std::__fill_a(__first, __last, __value);
}
template<typename _FIte, typename _Tp>
_GLIBCXX20_CONSTEXPR
inline void
__fill_a(_FIte __first, _FIte __last, const _Tp& __value)
{ std::__fill_a1(__first, __last, __value); }
__fill_a1() 对于 scalar 和 byte 类型做了优化
- scalar 类型添加 const 做编译优化
- byte 类型使用 memset
template<typename _ForwardIterator, typename _Tp>
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<!__is_scalar<_Tp>::__value, void>::__type
__fill_a1(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
{
for (; __first != __last; ++__first)
*__first = __value;
}
template<typename _ForwardIterator, typename _Tp>
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type
__fill_a1(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __value)
{
const _Tp __tmp = __value;
for (; __first != __last; ++__first)
*__first = __tmp;
}
// Specialization: for char types we can use memset.
template<typename _Tp>
_GLIBCXX20_CONSTEXPR
inline typename
__gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type
__fill_a1(_Tp* __first, _Tp* __last, const _Tp& __c)
{
const _Tp __tmp = __c;
#if __cpp_lib_is_constant_evaluated
/* ... */
#endif
if (const size_t __len = __last - __first)
__builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
}
6、uninitialized* 算法
6.1、uninitialized_copy/uninitialized_copy_n
uninitialized_copy() 函数使用 __uninitialized_copy::__uninit_copy() 成员函数拷贝对象。
template<typename _InputIterator, typename _ForwardIterator>
inline _ForwardIterator
uninitialized_copy(_InputIterator __first, _InputIterator __last,
_ForwardIterator __result)
{
typedef typename iterator_traits<_InputIterator>::value_type
_ValueType1;
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType2;
// _ValueType1 must be trivially-copyable to use memmove, so don't
// bother optimizing to std::copy if it isn't.
// XXX Unnecessary because std::copy would check it anyway?
const bool __can_memmove = __is_trivial(_ValueType1);
#if __cplusplus < 201103L
/* ... */
#else
using _From = decltype(*__first);
#endif
const bool __assignable
= _GLIBCXX_USE_ASSIGN_FOR_INIT(_ValueType2, _From);
return std::__uninitialized_copy<__can_memmove && __assignable>::
__uninit_copy(__first, __last, __result);
}
__uninitialized_copy 针对对象类型做了优化：
- trivial 类使用 __do_uninit_copy()，调用 std::_Construct 在内存上构造对象。构造函数抛出异常，已经构造的对象会被析构。
- 否则使用 std::copy() 拷贝对象
template<bool _TrivialValueTypes>
struct __uninitialized_copy
{
template<typename _InputIterator, typename _ForwardIterator>
static _ForwardIterator
__uninit_copy(_InputIterator __first, _InputIterator __last,
_ForwardIterator __result)
{ return std::__do_uninit_copy(__first, __last, __result); }
};
template<>
struct __uninitialized_copy<true>
{
template<typename _InputIterator, typename _ForwardIterator>
static _ForwardIterator
__uninit_copy(_InputIterator __first, _InputIterator __last,
_ForwardIterator __result)
{ return std::copy(__first, __last, __result); }
};
template<typename _InputIterator, typename _ForwardIterator>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__do_uninit_copy(_InputIterator __first, _InputIterator __last,
_ForwardIterator __result)
{
_ForwardIterator __cur = __result;
__try
{
for (; __first != __last; ++__first, (void)++__cur)
std::_Construct(std::__addressof(*__cur), *__first);
return __cur;
}
__catch(...)
{
std::_Destroy(__result, __cur);
__throw_exception_again;
}
}
uninitialized_copy_n() 直接调用 __uninitialized_copy_n() 函数
template<typename _InputIterator, typename _Size, typename _ForwardIterator>
inline _ForwardIterator
uninitialized_copy_n(_InputIterator __first, _Size __n,
_ForwardIterator __result)
{ return std::__uninitialized_copy_n(__first, __n, __result,
std::__iterator_category(__first)); }
__uninitialized_copy_n() 函数区分迭代器类型做优化，如果不是 random_access_iterator_tag，就依次调用 [first, first + n) 迭代器构造。否则借助 uninitialized_copy() 拷贝。
template<typename _InputIterator, typename _Size,
typename _ForwardIterator>
_ForwardIterator
__uninitialized_copy_n(_InputIterator __first, _Size __n,
_ForwardIterator __result, input_iterator_tag)
{
_ForwardIterator __cur = __result;
__try
{
for (; __n > 0; --__n, (void) ++__first, ++__cur)
std::_Construct(std::__addressof(*__cur), *__first);
return __cur;
}
__catch(...)
{
std::_Destroy(__result, __cur);
__throw_exception_again;
}
}
template<typename _RandomAccessIterator, typename _Size,
typename _ForwardIterator>
inline _ForwardIterator
__uninitialized_copy_n(_RandomAccessIterator __first, _Size __n,
_ForwardIterator __result,
random_access_iterator_tag)
{ return std::uninitialized_copy(__first, __first + __n, __result); }
6.2、uninitialized_fill/uninitialized_fill_n
uninitialized_fill() 直接调用 __uninitialized_fill::__uninit_fill() 成员函数赋值
template<typename _ForwardIterator, typename _Tp>
inline void
uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __x)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
// Trivial types do not need a constructor to begin their lifetime,
// so try to use std::fill to benefit from its memset optimization.
const bool __can_fill
= _GLIBCXX_USE_ASSIGN_FOR_INIT(_ValueType, const _Tp&);
std::__uninitialized_fill<__can_fill>::
__uninit_fill(__first, __last, __x);
}
如果是 trivial 类型，__uninitialized_fill 使用 std::fill() 完成赋值，否则调用构造函数。
template<typename _ForwardIterator, typename _Tp>
_GLIBCXX20_CONSTEXPR void
__do_uninit_fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __x)
{
_ForwardIterator __cur = __first;
__try
{
for (; __cur != __last; ++__cur)
std::_Construct(std::__addressof(*__cur), __x);
}
__catch(...)
{
std::_Destroy(__first, __cur);
__throw_exception_again;
}
}
template<bool _TrivialValueType>
struct __uninitialized_fill
{
template<typename _ForwardIterator, typename _Tp>
static void
__uninit_fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __x)
{ std::__do_uninit_fill(__first, __last, __x); }
};
template<>
struct __uninitialized_fill<true>
{
template<typename _ForwardIterator, typename _Tp>
static void
__uninit_fill(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __x)
{ std::fill(__first, __last, __x); }
};
uninitialized_fill_n() 也是相同的逻辑
template<typename _ForwardIterator, typename _Size, typename _Tp>
inline _ForwardIterator
uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
{
typedef typename iterator_traits<_ForwardIterator>::value_type
_ValueType;
// Trivial types do not need a constructor to begin their lifetime,
// so try to use std::fill_n to benefit from its optimizations.
const bool __can_fill
= _GLIBCXX_USE_ASSIGN_FOR_INIT(_ValueType, const _Tp&)
// For arbitrary class types and floating point types we can't assume
// that __n > 0 and std::__size_to_integer(__n) > 0 are equivalent,
// so only use std::fill_n when _Size is already an integral type.
&& __is_integer<_Size>::__value;
return __uninitialized_fill_n<__can_fill>::
__uninit_fill_n(__first, __n, __x);
}
__uninitialized_fill_n 如果是 trivial 类型，调用 std::fill_n() 完成赋值，否则使用构造函数构造对象
template<typename _ForwardIterator, typename _Size, typename _Tp>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__do_uninit_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
{
_ForwardIterator __cur = __first;
__try
{
for (; __n > 0; --__n, (void) ++__cur)
std::_Construct(std::__addressof(*__cur), __x);
return __cur;
}
__catch(...)
{
std::_Destroy(__first, __cur);
__throw_exception_again;
}
}
template<bool _TrivialValueType>
struct __uninitialized_fill_n
{
template<typename _ForwardIterator, typename _Size, typename _Tp>
static _ForwardIterator
__uninit_fill_n(_ForwardIterator __first, _Size __n,
const _Tp& __x)
{ return std::__do_uninit_fill_n(__first, __n, __x); }
};
template<>
struct __uninitialized_fill_n<true>
{
template<typename _ForwardIterator, typename _Size, typename _Tp>
static _ForwardIterator
__uninit_fill_n(_ForwardIterator __first, _Size __n,
const _Tp& __x)
{ return std::fill_n(__first, __n, __x); }
};
欢迎关注公众号“源知源为”，阅读更多技术干货
#八股文##c++##STL#C/C++基础 文章被收录于专栏
C/C++ 语言基础
深信服一面223人在聊
查看8道真题和解析
百度公司福利 556人发布