【C++】：C++中的STL序列式容器vector源码剖析

在这里插入图片描述
在这里插入图片描述

⛅️一 vector概述

vector的使用语法可以参考文章：​
总的来说：vector是可变大小数组
特点：
支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢
元素保存在连续的内存空间中，因此通过下标取值非常快
在容器中间位置添加或删除元素非常耗时
一旦vector内存不足，重新申请内存之后，和原vector相关的指针，引用，迭代器都失效。内存重分配耗时很长
通常，使用vector是最好的选择，如果没有什么特殊要求，最好使用vector
与其他容器的比较：

在这里插入图片描述

⛅️二、vector定义摘要

vector定于与<stl_vector.h>头文件中

//alloc是SGI STL的空间配置器
template <class T, class Alloc = alloc>
class vector {
public:
    // vector 的嵌套类型定义
    typedef T value_type;
    typedef value_type* pointer;
    typedef value_type* iterator;
    typedef value_type& reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

protected:
    // simple_alloc是SGI STL的空间配置器，见前面空间适配器文章的介绍
    typedef simple_alloc<value_type, Alloc> data_allocator;
    iterator start; // 表示目前使用空间的头
    iterator finish; // 表示目前使用空间的尾
    iterator end_of_storage; // 表示目前可用空间的尾

    void insert_aux(iterator position, const T& x);
    void deallocate() {
        if (start)
        data_allocator::deallocate(start, end_of_storage - start);
    }

    void fill_initialize(size_type n, const T& value) {
            start = allocate_and_fill(n, value);
            finish = start + n;
            end_of_storage = finish;
    }

public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const {
        return size_type(end_of_storage - begin()); 
    }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }

    vector() : start(0), finish(0), end_of_storage(0) {}
    vector(size_type n, const T& value) { fill_initialize(n,value); } 
    vector(int n, const T& value) { fill_initialize(n,value); } 
    vector(long n, const T&value) { fill_initialize(n,value); } 
    explicit vector(size_type n) { fill_initialize(n,T()); }

    ~vector()
        destroy(start, finish); //全局函式，见前面文章destroy函数的介绍
        deallocate(); //这是 vector的㆒个 member function
    }

    reference front() { return *begin(); } // 第一个元素
    reference back() { return *(end() - 1); } // 最后一个元素
    void push_back(const T& x) { // 将元素安插至最尾端
        if (finish != end_of_storage) {
            construct(finish, x); //全局函式，见前面文章construct函数的介绍
            ++finish;
        }
        else
            insert_aux(end(), x); //这是 vector的一个member function
        }

    void pop_back() { // 将最尾端元素取出
        --finish;
        destroy(finish); // 全局函式，见前面文章destroy函数的介绍
    }

    iterator erase(iterator position) { // 清除某位置上的元素
        if (position + 1 != end())
        copy(position + 1, finish, position); // 后续元素往前搬移
        --finish;
        destroy(finish); // 全局函式，见前面文章destroy函数的介绍
        return position;
    }

    void resize(size_type new_size, const T& x) {
        if (new_size < size())
            erase(begin() + new_size, end());
        else
            insert(end(), new_size - size(), x);
    }
        void resize(size_type new_size) { resize(new_size, T()); }
        void clear() { erase(begin(), end()); }

protected:
    // 配置空间并填满内容
    iterator allocate_and_fill(size_type n, const T& x) {
        iterator result = data_allocator::allocate(n);
        uninitialized_fill_n(result, n, x); // 全局函式，见前面uninitialized_fill_n函数的介绍
        return result;
    }

⛅️三、vector的迭代器

vector维护的是一个连续线性空间，所以不论其元素类别是什么，普通指针都可以作为vector的迭代器而满足所有必要条件
vector迭代器支持有操作有（普通指针也具备）：
operator*、operator->、operator++、operator–、operator+、operator-、operator+=、operator-=
vector支持随机存取，而普通指针正有着这样的能力，所以，vector提供的是随机访问迭代器（Random Access iterators）
vector的迭代器定义如下：

template <class T, class Alloc = alloc>
class vector {
public:
    typedef T value_type;
    typedef value_type* iterator; //vector的迭代器是原生指标
    ...
};

例如：

vector<int>::iterator ivite;   //等同于int* ivite;
vector<Shape>::iterator svite; //等同于Shape* svite;

⛅️四、vector的数据结构

vector的数据结构非常简单：一个线性连续空间
下面介绍vector的3个数据结构：
start：表示目前使用空间的头
finish：表示目前使用空间的尾
end_of_storage：表示目前可用空间的尾

template <class T, class Alloc = alloc>
class vector {
...
protected:
    iterator start; //表示目前使用空间的头
    iterator finish; //表示目前使用空间的尾
    iterator end_of_storage; //表示目前可用空间的尾
    ...
};

说明：为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求量更大一些，以备将来可能的扩充。这便是容量的概念。也就是说，一个vector的容量永远大于或等于其大小。一旦容量等于大小，下次再新增元素时就需要新开辟一块空间。如下图所示
在这里插入图片描述
运用start、finish、end_of_storage三个迭代器，vector提供了首尾标示、大小、容量、空容器判断、注标[]运算符、最前端元素值、最后端元素值…等机能，如下：

template <class T, class Alloc = alloc>
class vector {
...
public:
    iterator begin() { return start; }
    iterator end() { return finish; }
    size_type size() const { return size_type(end() - begin()); }
    size_type capacity() const {
        return size_type(end_of_storage - begin()); 
    }
    bool empty() const { return begin() == end(); }
    reference operator[](size_type n) { return *(begin() + n); }
    reference front() { return *begin(); }
    reference back() { return *(end() - 1); }
    ...
};

⛅️五、vector的构造与内存管理（constructor、push_back）

vector的内存管理：vector默认使用alloc做为空间配置器，并据此另外定义了一个data_allocator，为的是更方便以元素大小为配置单位：

template <class T, class Alloc = alloc>
class vector {
protected:
    // simple_alloc<>见前面文章介绍
    typedef simple_alloc<value_type, Alloc> data_allocator;
    ...
};

于是，data_allocator::allocate(n) 表示配置n个元素空间
构造函数：vector提供许多构造函数，其中一个允许我们指定空间大小及初值：

//构造函数，允许指定vector大小n和初值value
vector(size_type n, const T& value) { fill_initialize(n, value); }

// 充填并予初始化
void fill_initialize(size_type n, const T& value) {
    start = allocate_and_fill(n, value);
    finish = start + n;
    end_of_storage = finish;
}

// 配置而后充填
iterator allocate_and_fill(size_type n, const T& x) {
    iterator result = data_allocator::allocate(n); //配置n个元素空间
    uninitialized_fill_n(result, n, x); //全局函式，会根据第1个参数类型特性决定使用算法fill_n()或反复调用construct()来完成任务
    return result;
}

push_back()函数：当我们以push_back() 将新元素安插入于vector尾端时，该函式首先检查是否还有备用空间，如果有就直接在备用空间上建构元素，并调整迭代器finish，使vector变大。如果没有备用空间了，就扩充空间（重新配置、搬移数据、释放原空间）。push_back()原型如下：

void push_back(const T& x) {
    if (finish != end_of_storage) { //还有备用空间
        construct(finish, x); //全局函式
        ++finish; //调整水位高度
    }
    else //已无备用空间
        insert_aux(end(), x); // vector member function，见下
}

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
    if (finish != end_of_storage) { //还有备用空间
        // 在备用空间起始处建构一个元素，并以 vector 最后一个元素值为其初值。
        construct(finish, *(finish - 1));
        // 调整水位。
        ++finish;
        T x_copy = x;
        copy_backward(position, finish - 2, finish - 1);
        *position = x_copy;
    }
    else { // 已无备用空间
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        // 以上配置原则：如果原大小为0，则配置 1（个元素大小）
        // 如果原大小不为 0，则配置原大小的两倍，
        // 前半段用来放置原数据，后半段准备用来放置新数据
        iterator new_start = data_allocator::allocate(len); // 实际配置
        iterator new_finish = new_start;
        try {
            // 将原 vector 的内容拷贝到新vector
            new_finish = uninitialized_copy(start, position, new_start);
            // 为新元素设定初值 x
            construct(new_finish, x);
            // 调整水位
            ++new_finish;
            // 将原vector的备用空间中的内容也忠实拷贝过来
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
        catch(...) {
            // "commit or rollback" semantics.
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        //析构并释放原vector
        destroy(begin(), end());
        deallocate();

        // 调整迭代器，指向新vector
        vector start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

⛅️六、vector内存重分配策略

vector的内存重分配策略：
vector是以数组的形式存储的，当往vector中增加元素时，如果vector的容量不足，那么vector就会进行扩容
扩容的规则是：并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是申请一块比现在大的新的内存空间（gcc和vc申请规则不同，见下面介绍），然后原来内存中的内容拷贝到新内存中，然后释放原来的内存
重点：在gcc和vc的环境下，vector的扩容规则是不一样的
注意（重点）：对vector 的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。这是程序员易犯的一个错误，务需小心

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  std::vector<int> iv;
  iv.push_back(1);

  cout << iv.capacity() << endl; //1

  iv.push_back(1);
  cout << iv.capacity() << endl; //2

  iv.push_back(1);
  cout << iv.capacity() << endl; //3

  iv.push_back(1);
  cout << iv.capacity() << endl; //4

  iv.push_back(1);
  cout << iv.capacity() << endl; //6

  iv.push_back(1);

  iv.push_back(1);
  cout << iv.capacity() << endl; //9

  return 0;
}

⛅️七、vector的元素操作（pop_back、erase、clear、insert）

所提供的元素操作动作很多，不就在此文章中一一说明
pop_back：

//将尾端元素拿掉，并调整大小
void pop_back() {
    --finish; //将尾端标记往前移一格，表示将放弃尾端元素
    destroy(finish); // destroy是全局函式
}

erase：

// 清除[first,last)中的所有元素
iterator erase(iterator first, iterator last) {
    iterator i = copy(last, finish, first); //copy是全局函式
    destroy(i, finish); //destroy是全局函式
    finish = finish - (last - first);
    return first;
}

下图是上面这个erase函数的版本
在这里插入图片描述

// 清除某个位置上的元素
iterator erase(iterator position) {
    if (position + 1 != end())
        copy(position + 1, finish, position); //copy是全局函式
    --finish;
    destroy(finish); //destroy是全局函式
    return position;
}

clear：

//清除容器内所有元素
void clear() { erase(begin(), end()); }

insert：

//从position开始，插入n个元素，元素初值为x
template<class T,class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x)
{
    if (n != 0) { //当n!= 0才进行以下所有动作
        if (size_type(end_of_storage - finish) >= n){
            //备用空间大于等于“新增元素个数”
            T x_copy = x;
            // 以下计算插入点之后的现有元素个数
            const size_type elems_after = finish - position;
            iterator old_finish = finish;
            if (elems_after > n){
                //“插入点之后的现有元素个数”大于“新增元素个数”
                uninitialized_copy(finish - n, finish, finish);
                finish += n; // 将vector尾端标记后移
                copy_backward(position, old_finish - n, old_finish);
                fill(position, position + n, x_copy); //从插入点开始填入新值
            }
        }
        else {
            //“插入点之后的现有元素个数”小于等于“新增元素个数”
            uninitialized_fill_n(finish, n - elems_after, x_copy);
            finish += n - elems_after;
            uninitialized_copy(position, old_finish, finish);
            finish += elems_after;
            fill(position, old_finish, x_copy);
        }
    }
    else {
        // 备用空间小于“新增元素个数”（那就必须配置额外的内存）
        // 首先决定新长度：旧长度的两倍，或旧长度+新增元素个数
        const size_type old_size = size();
        const size_type len = old_size + max(old_size, n);
        // 以下配置新的vector空间
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        
        STL_TRY {
            // 以下首先将旧vector的安插点之前的元素复制到新空间
            new_finish = uninitialized_copy(start, position, new_start);
            // 以下再将新增元素（初值皆为n）填入新空间
            new_finish = uninitialized_fill_n(new_finish, n, x);
            // 以下再将旧 vector 的插入点之后的元素复制到新空间
            new_finish = uninitialized_copy(position, finish, new_finish);
        }
# ifdef STL_USE_EXCEPTIONS
        catch(...) {
        // 如有异常发生，实现"commit or rollback" semantics.
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
        }
# endif /* STL_USE_EXCEPTIONS */

        // 以下清除并释放旧的vector
        destroy(start, finish);
        deallocate();
        // 以下调整水位标记
        start = new_start; finish =
        new_finish; end_of_storage =
        new_start + len;
    }
}

注意，插入完成后，新节点将位于哨兵迭代器（即上缪按的position，标示出插入点） 所指之节点的前方——这是STL对于“插入操作”的标准规范。下面的图片展示了insert(position,n,x)的操作
备用空间>=新增元素个数的情况：
①备用空间2>=新增元素个数2
②插入点之后的现有元素个数3>新增元素个数2
在这里插入图片描述
③插入点之后的现有元素个数2<=新增元素个数3
在这里插入图片描述
备用空间>=新增元素个数的情况：例如下面备用空间2<新增元素个数n==3
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/314586.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Laravel 框架中队列的使用

Laravel 框架中队列的使用

概述 Laravel 框架内置了强大的队列系统&#xff0c;用于处理异步任务、提高系统性能等。队列可以让任务异步执行&#xff0c;而不会阻塞当前进程&#xff0c;可以提高系统的处理能力。 Laravel 的队列系统支持多种驱动&#xff0c;如 Redis、Beanstalkd、SQS 等&#xff0c;…
阅读更多...
VSCode 搭建Java开发环境

VSCode 搭建Java开发环境

笔者使用最多的语言是C&#xff0c;也使用过不少其它语言&#xff0c;像Erlang&#xff0c;Python&#xff0c;Lua&#xff0c;C#等等&#xff0c;目前项目中在使用Go&#xff0c;但是没使用过Java。最近看到C#夺冠&#xff0c;首次荣获 TIOBE 年度编程语言&#xff0c;同时也看…
阅读更多...
计算机缺失msvcp140.dll的修复教程，教你快速解决dll问题

计算机缺失msvcp140.dll的修复教程，教你快速解决dll问题

“针对计算机系统中出现的msvcp140.dll文件丢失问题&#xff0c;小编将详细阐述一系列有效的解决方法。首先&#xff0c;msvcp140.dll是Microsoft Visual C Redistributable Package中的一个关键动态链接库文件&#xff0c;对于许多应用程序的正常运行至关重要。当系统提示该文…
阅读更多...
关于Python里xlwings库对Excel表格的操作（三十一）

关于Python里xlwings库对Excel表格的操作（三十一）

这篇小笔记主要记录如何【如何使用“Chart类”、“Api类"和“Axes函数”设置绘图区外框线型、颜色、粗细及填充颜色】。前面的小笔记已整理成目录&#xff0c;可点链接去目录寻找所需更方便。 【目录部分内容如下】【点击此处可进入目录】 &#xff08;1&#xff09;如何安…
阅读更多...
【DevOps-08-3】Jenkins容器内部使用Docker

【DevOps-08-3】Jenkins容器内部使用Docker

一、简要描述 构建镜像和发布镜像到harbor都需要使用到docker命令。而在Jenkins容器内部安装Docker官方推荐直接采用宿主机带的Docker即可。 设置Jenkins容器使用宿主机Docker。 二、配置和操作步骤 1、修改宿主机docker.sock权限 # 修改docker.sock 用户和用户组都为root $ …
阅读更多...
计算机找不到msvcr100.dll的多种解决方法分享，轻松解决dll问题

计算机找不到msvcr100.dll的多种解决方法分享，轻松解决dll问题

msvcr100.dll作为系统运行过程中不可或缺的一部分&#xff0c;它的主要功能在于提供必要的运行时支持&#xff0c;确保相关应用程序能够顺利完成编译和执行。因此&#xff0c;当操作系统或应用程序在运行阶段搜索不到该文件时&#xff0c;自然会导致各类依赖于它的代码无法正常…
阅读更多...
vue3+acro实现日期组件可以直接展示在界面上，不用非得弹框展示

vue3+acro实现日期组件可以直接展示在界面上，不用非得弹框展示

前言&#xff1a; 在很多时候&#xff0c;我们使用日期组件的时候&#xff0c;不希望每次都是点击弹出日期弹框&#xff0c;而是&#xff0c;点击日期弹框直接能展示在界面上&#xff0c;在这里我们介绍下 使用 acro 来更加轻松的实现他的效果。 实现效果&#xff1a; 实现步骤…
阅读更多...
Skywalking UI页面中操作的各种实用功能汇总

Skywalking UI页面中操作的各种实用功能汇总

刚刚接触skywalking不久&#xff0c;在这里总结一下在UI页面中操作的各种实用功能&#xff0c;随着使用的不断深入&#xff0c;我也会对文章进行持续补充。 本文skywalking 的ui入口是官方demo &#xff0c;版本是10.0.0-SNAPSHOT-593bd05 http://demo.skywalking.apache.org…
阅读更多...
Linux(Debina12)系统安装

Linux(Debina12)系统安装

在开发或学习中&#xff0c;linux系统是我们必须要熟悉的系统&#xff0c;那么今天就记录一下&#xff0c;较为稳定&#xff0c;也是小编这几年当做开发环境的发行版吧 官网地址 https://www.debian.org 下载链接 http://mirrors.163.com/debian-cd/12.4.0/amd64/iso-dvd/ …
阅读更多...
【LeetCode每日一题】2085. 统计出现过一次的公共字符串（哈希表）

【LeetCode每日一题】2085. 统计出现过一次的公共字符串（哈希表）

2024-1-12 文章目录 [2085. 统计出现过一次的公共字符串](https://leetcode.cn/problems/count-common-words-with-one-occurrence/)思路&#xff1a;哈希表计算 2085. 统计出现过一次的公共字符串 思路&#xff1a;哈希表计算 1.用两个哈希表分别统计word1和word2中字符出现的…
阅读更多...
MySQL表结构转换为ES索引Mapping

MySQL表结构转换为ES索引Mapping

背景 日常开发过程中肯定会存在MySQL表数据迁移至ES的情况&#xff0c;以canal为例&#xff0c;数据迁移时需要提前在ES中创建索引Mapping&#xff0c;但是如果碰到字段特别的表时&#xff0c;创建Mapping将是一件耗费心神的事情。为了解决这些重复工作&#xff0c;我使用Pyth…
阅读更多...
C++学习笔记——多态与静态联编和动态联编

C++学习笔记——多态与静态联编和动态联编

目录 一、多态 二、静态联编&#xff08;Static Binding&#xff09;和动态联编&#xff08;Dynamic Binding&#xff09; 2.1静态联编 2.2动态联编 一、多态 是C中面向对象编程的一个核心概念&#xff0c;它允许派生类对象替代其基类对象&#xff0c;从而实现代码重用和扩…
阅读更多...
Jmeter接口自动化02--JMeter的安装和使用

Jmeter接口自动化02--JMeter的安装和使用

p02 高清B站视频链接 2.1 Windows环境 首先需要安装JDK&#xff0c;然后再部署JMeter。注意&#xff0c;JMeter对JDK的版本是有要求的&#xff0c;一般至少要JDK8&#xff0c;这也是目前开发过程中使用频繁的版本。 1. 安装JDK 从官网下载JDK&#xff1a;https://www.oracl…
阅读更多...
Abaqus2023安装下载教程

Abaqus2023安装下载教程

用钢铁意志&#xff0c;成就不平凡的人生。 今天博主整理了一下Abaqus2023安装下载教程&#xff0c;希望大家学习。 安装之前请关闭电脑所有杀毒软件和防火墙&#xff0c;并保证计算机名不是中文&#xff01;&#xff01;&#xff01;&#xff01; 1.首先创建一个用于Abaqus…
阅读更多...
从vue小白到高手，从一个内容管理网站开始实战开发第七天，登录功能后台功能设计--通用分页、枚举以及相关工具类

从vue小白到高手，从一个内容管理网站开始实战开发第七天，登录功能后台功能设计--通用分页、枚举以及相关工具类

上一篇实现了数据库访问层的相关功能，还没有了解的小伙伴可以去看前面文章实现的内容，因为每一篇内容都是连贯的，不学习的话可能下面的内容学习起来会有点摸不着头脑 从vue小白到高手，从一个内容管理网站开始实战开发第六天，登录功能后台功能设计--API项目中的登录实现(二…
阅读更多...
先锋WEB燃气收费系统 Upload.aspx 文件上传漏洞复现

先锋WEB燃气收费系统 Upload.aspx 文件上传漏洞复现

0x01 产品简介 先锋WEB燃气收费系统是一种先进的在线燃气收费解决方案，旨在简化和优化燃气收费的流程和管理。该系统基于Web平台，提供了一系列功能和工具，使燃气公司能够高效地进行收费、账单管理和客户服务。 0x02 漏洞概述 先锋WEB燃气收费系统/AjaxService/Upload.asp…
阅读更多...
PHP版学校教务管理系统源码带文字安装教程

PHP版学校教务管理系统源码带文字安装教程

PHP版学校教务管理系统源码带文字安装教程 运行环境 服务器宝塔面板 PHP 7.0 Mysql 5.5及以上版本 Linux Centos7以上 系统介绍&#xff1a; 后台权限控制&#xff1a;支持多个管理员&#xff0c;学生管理&#xff0c;学生成绩&#xff0c;教师管理&#xff0c;文章管理&#x…
阅读更多...
vscode+opencv基础用法学习1

vscode+opencv基础用法学习1

案例1&#xff1a;读取图片信息 如果是使用云服务器的话&#xff0c;由于图形界面的问题&#xff0c;使用cv::show来显示图片会报错 // 图片的读取和显示 // 导入opencv头文件 #include "opencv2/opencv.hpp" #include <iostream>int main(int argc, char** …
阅读更多...
代码结构：为何重要算法不和接口编译到一个dll里面

代码结构：为何重要算法不和接口编译到一个dll里面

这里是vision master的例子。 有两点需要向他学习的。 1 需要每个算子是一个dll。优点是方便业务上&#xff0c;针对不同的算子精细化的更新&#xff0c;或者售卖。 2 每个算子的dll我们理解&#xff0c;内容主要是其接口的实现。而真正的算法内容是在上面的algorithm.dll中…
阅读更多...
边缘计算AI智能分析网关V4算力分析及应用场景

边缘计算AI智能分析网关V4算力分析及应用场景

一、硬件介绍 智能分析网关V4是TSINGSEE青犀视频推出的一款高性能、低功耗的软硬一体AI边缘计算硬件设备&#xff0c;硬件采用BM1684芯片&#xff0c;集成高性能8核ARM A53&#xff0c;主频高达2.3GHz。硬件内置近40种AI算法模型&#xff0c;支持对接入的视频图像进行人、车、…
阅读更多...
最新文章

Copyright @ 2022~2023