之前一向在看侯捷大佬写的《STL源码剖析》的vector篇,看完了整个源码并把注释都写上去了.然后写写面试题内容,后来才发现SGI 版别没有emplace_back函数.本来打算看完这个过渡一下再去看gcc的libstdc++版别的STL源码.
直接索性一步到尾,看现代版别的STL源码,比较接近实践. SGI版别虽然代码写的好,但是确实是过期了.

依据libstdc++11.4版别,STL源码在 gcc-11.4.0/libstdc++-v3/include 文件夹中

从包括的头文件开端吧.

1. polymorphic_allocator(多态分配器)

STL容器(libstdc++11.4版别) --- vector
在C++17版别中供给了一个多态分配器类,合作抽象基类memory_resource,memory_resource供给了接口,咱们承继完成接口,运用不同的分配算法或与特定的资源进行交互.这两个类在头文件 memory_resource中
效果主要是: 在曾经的版别中,每种分配器运用不同的类型.比方不同分配器类型假如想仿制给另一个,是不能做到的

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

先来看一下怎么针对不同类型来匹配两种模板的

STL容器(libstdc++11.4版别) --- vector

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

STL容器(libstdc++11.4版别) --- vector

bool类型的vector

STL容器(libstdc++11.4版别) --- vector

一般版别供给了默许分配器.
bool版别vector是模板偏特化.

当咱们界说如下代码时:

vector<bool> vec;

由于第二个是bool偏特化版别,所以第二个匹配愈加符合.然后模板参数 _Alloc 从第一个模板的默许值揣度出来.


1.1 剖析vetor<bool>源码

1.1.1 reference引证类型

我剖析源码一般是先看成员都界说了哪些东西,然后看一下当时类界说的类型萃取。vector中没有界说任何成员,但是界说了几种类型萃取,引证类型(reference)和迭代器类型(iterator、const_iterator)

STL容器(libstdc++11.4版别) --- vector

_Bit_reference类的联系图如下

STL容器(libstdc++11.4版别) --- vector

_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.

STL容器(libstdc++11.4版别) --- vector

1.1.2 迭代器类型

STL容器(libstdc++11.4版别) --- vector

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

STL容器(libstdc++11.4版别) --- vector

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

STL容器(libstdc++11.4版别) --- vector

_Bit_iterator_base供给了三个重要的成员函数: _M_bump_up()、_M_bump_down()、_M_incr()

_M_bump_up()

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

STL容器(libstdc++11.4版别) --- vector

_M_bump_down()

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

STL容器(libstdc++11.4版别) --- vector

_M_incr()

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

STL容器(libstdc++11.4版别) --- vector

1.1.3 vector类

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

STL容器(libstdc++11.4版别) --- 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 就表明容器总容量

画一个图便是下面这样,别离指向不同的方位

STL容器(libstdc++11.4版别) --- vector

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()函数

STL容器(libstdc++11.4版别) --- vector
以下是函数调用流程图

STL容器(libstdc++11.4版别) --- vector

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

operator[] 和at()函数原理相同

front()

STL容器(libstdc++11.4版别) --- vector

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

back()

STL容器(libstdc++11.4版别) --- vector
end()函数指向结尾元素的下一个方位,所以需求减去1,即获取最后一个元素内容

data()返回底层指针

STL容器(libstdc++11.4版别) --- vector
vector<bool>的data函数不返回任何东西


1.1.3.3 迭代器

begin()

STL容器(libstdc++11.4版别) --- vector
获取_M_p指向内存的数据

end()

STL容器(libstdc++11.4版别) --- vector
获取_M_finishi指向内存的数据

rbegin()、rend()

STL容器(libstdc++11.4版别) --- vector

STL容器(libstdc++11.4版别) --- vector


1.1.3.4 容量

empty()

STL容器(libstdc++11.4版别) --- vector

size()

STL容器(libstdc++11.4版别) --- vector

reserve()

STL容器(libstdc++11.4版别) --- vector
STL容器(libstdc++11.4版别) --- vector

capacity()

STL容器(libstdc++11.4版别) --- vector
结尾地址减去首地址获取的偏移量,然后乘上 _S_word_bit,则是容器容量

shrink_to_fit()

STL容器(libstdc++11.4版别) --- vector
STL容器(libstdc++11.4版别) --- vector


1.1.3.5 修饰符

clear()

STL容器(libstdc++11.4版别) --- vector
STL容器(libstdc++11.4版别) --- vector
将_M_finish重新指向内存首地址,这样就到达了清空的功能

insert()
_M_insert_aux函数:

STL容器(libstdc++11.4版别) --- vector

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

STL容器(libstdc++11.4版别) --- vector

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

常量迭代器版别

STL容器(libstdc++11.4版别) --- vector

非常量迭代器版别

STL容器(libstdc++11.4版别) --- vector

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

STL容器(libstdc++11.4版别) --- vector
STL容器(libstdc++11.4版别) --- vector

emplace()

STL容器(libstdc++11.4版别) --- vector
底层调用insert函数,在position方位刺进元素

erase()

未写完,明天再写。。。

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。