之前一向在看侯捷大佬写的《STL源码剖析》的vector篇,看完了整个源码并把注释都写上去了.然后写写面试题内容,后来才发现SGI 版别没有emplace_back函数.本来打算看完这个过渡一下再去看gcc的libstdc++版别的STL源码.
直接索性一步到尾,看现代版别的STL源码,比较接近实践. SGI版别虽然代码写的好,但是确实是过期了.
依据libstdc++11.4版别,STL源码在 gcc-11.4.0/libstdc++-v3/include 文件夹中
从包括的头文件开端吧.
1. polymorphic_allocator(多态分配器)

效果主要是: 在曾经的版别中,每种分配器运用不同的类型.比方不同分配器类型假如想仿制给另一个,是不能做到的
vector<int> vec_1; // 默许分配器
vector<int, __gnu_cxx::new_allocator<int>> vec_2; // 运用new_allocator
vec_1 = vec_2; // 编译报错
假如承继memory_resource合作运用polymorphic_allocator
struct my_memory_resource : public std::pmr::memory_resource
{
/* 完成接口 */
void* do_allocate(size_t __bytes, size_t __alignment)
{
const char* str = "a";
return (void*)str;
}
void do_deallocate(void* __p, size_t __bytes, size_t __alignment) {}
bool do_is_equal(const memory_resource& __other) const noexcept
{ return true; }
};
struct other_memory_resource : public std::pmr::memory_resource
{
/* 完成接口 */
void* do_allocate(size_t __bytes, size_t __alignment)
{
// 测试代码
const char* str = "a";
return (void*)str;
}
void do_deallocate(void* __p, size_t __bytes, size_t __alignment) {}
bool do_is_equal(const memory_resource& __other) const noexcept
{ return true; }
};
int main()
{
// 界说两个对象
my_memory_resource mem_res;
auto my_vec = std::pmr::vector<int>(0, &mem_res);
other_memory_resource other_res;
auto my_other_vec = std::pmr::vector<int>(0, &other_res);
my_vec = my_other_vec; // 此处能够正常赋值
return 0;
}
假如想运用多态分配器polymorphic_allocator,将C++版别设置为17,然后运用 std::pmr::vector
就能够运用了,源码中现已给咱们声明晰一个别名.
2. 针对bool类型的vector
先来看一下怎么针对不同类型来匹配两种模板的

先看两个版别的界说
一般版别的vector

bool类型的vector

一般版别供给了默许分配器.
bool版别vector是模板偏特化.
当咱们界说如下代码时:
vector<bool> vec;
由于第二个是bool偏特化版别,所以第二个匹配愈加符合.然后模板参数 _Alloc 从第一个模板的默许值揣度出来.
1.1 剖析vetor<bool>源码
1.1.1 reference引证类型
我剖析源码一般是先看成员都界说了哪些东西,然后看一下当时类界说的类型萃取。vector中没有界说任何成员,但是界说了几种类型萃取,引证类型(reference)和迭代器类型(iterator、const_iterator)

_Bit_reference类的联系图如下

_Bit_reference界说了两个成员,其中一个是: 指针_M_p,类型是 _Bit_type 类型.
_M_p指向底层数组
- vector<bool>的底层类型便是unsigned long类型, 分配内存巨细都是以unsigned long为单位分配
- 枚举_S_word_bit的效果是: gcc编译器在不同平台下unsigned long类型的位数巨细. 比方32位unsigned为4字节,64位编译为8字节.用来表明偏移量是否超过了位数
_Bit_reference还界说了 _M_mask 成员,类型是unsigned long
合作_M_p运用, 对这个内存进行位操作. 比方对这段内存的第5位设置为1或许0.

1.1.2 迭代器类型

有一个常量和非常量迭代器都承继自 _Bit_iterator_base
基类_Bit_iterator_base又承继自std::iterator, random_access_iterator_tag表明这个迭代器能够随机拜访

基类界说了两个成员: 指针 _M_p 和无符号整数类型 _M_offset,效果和_Bit_reference里边的两个成员相同,只不过 _M_offset 是供给给 _Bit_reference 用来将第几个方位位.

_Bit_iterator_base供给了三个重要的成员函数: _M_bump_up()、_M_bump_down()、_M_incr()
_M_bump_up()
针对向容器添加元素,判别当时操作的位是否超过了上限.假如到达上限,将 _M_offset 设置为0,然后将 _M_p 添加一个单位.也便是表明在unsigned long巨细的位数现已悉数用完了,指向下一个unsigned long. 假如这句话还不明白,便是数组下标加加,指向数组下一个方位.然后在一个位一个位的设置.

_M_bump_down()
针对删除容器元素. 和_M_bump_up()相反

_M_incr()
针对随机拜访或数组下标拜访.

1.1.3 vector类
接下来就剖析主角vector了,联系图如下:

vector<bool>承继子Bvector_base
Bvector_base里边界说了两个类: 别离是Bvector_impl和_Bvector_impl_data
能够看到, _Bvector_base类界说了一个成员: _M_impl. vector<bool>底层操作的便是这个成员.这个成员追溯到便是 _Bvector_impl_data类型.
然后再看_Bvector_impl_data类型,该类界说了三个成员,别离是:
- _M_start: 指向内存首地址,也是begin()、rbegin()所运用的
- _M_finish: 指向下一个空闲的方位.比方容器容量为5,现已刺进了3个元素,那么finish则指向第4个方位,用于下一次刺进.
_M_finish – _M_start也便是size()函数的返回值,表明容器有多少个元素- _M_end_of_storage: 指向容器结尾元素, 这个值减去 _M_start 就表明容器总容量
画一个图便是下面这样,别离指向不同的方位

1.1.3.1 初始化
vector一共了运用以下几个函数用来初始化:
- _M_initialize: 分配内存,并设置相应的指针
- _M_initialize_value: 对已分配的内存设置相应的值
- _M_copy_aligned: 将first~last迭代器范围内的数据仿制到方针迭代器result中,返回方针迭代器复制后的结尾元素地址
- _M_initialize_range: 将first~last迭代器范围内的数据仿制到当时容器中
1.1.3.2 成员拜访
at()函数


详细原理便是:
获取begin()迭代器,该迭代器有成员_M_p和_M_offset.
然后设置_M_p偏移量, 将at函数的参数传给_M_incr()函数设置_M_offset. 然后 获取_M_p指向的内存中第 (1UL << _M_offset)位的内容
operator[] 和at()函数原理相同
front()

获取begin()指向的内存首元素内容
back()

data()返回底层指针

1.1.3.3 迭代器
begin()

end()

rbegin()、rend()


1.1.3.4 容量
empty()

size()

reserve()


capacity()

shrink_to_fit()


1.1.3.5 修饰符
clear()


insert()
_M_insert_aux函数:

- 版别1: 在position方位刺进元素

- 版别2: 在position方位刺进first~last迭代器范围内的元素
常量迭代器版别

非常量迭代器版别

- 版别3: 在position方位刺进个数n,刺进数据是参数x


emplace()

erase()