C++ STL源码实现以及分析之vector

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/haluoluo211/article/details/80635782

本文主要内容如下:
1. 前篇blogC++ STL空间配置源码分析以及实现二介绍了空间配置器allocator以及vector构造、析构函数的基本实现。
2. 此篇blog主要通过一下几个方面,说明vector的实现原理
  • vectormove构造函数的定义
  • vectorerase clear pop_back 三个函数,以及size_tptrdiff_t的区别
  • vectoroperator[] 操作符重载

分析实现源码,其实我们只用实现,理解几个核心的函数就可以明白其中的原理,并不需要全部的实现。太多实现函数,会让我们分不清重点,而且看起来头大。


1 move构造函数的定义

下面给出move构造函数的定义(只需要交换内部指针即可):

template <typename T, typename Alloc>
SimpleVec<T, Alloc>::SimpleVec(SimpleVec&& v){
    start_ = v.start_;
    finish_ = v.finish_;
    end_of_storage_ = v.end_of_storage_;
    v.start_ = v.finish_ = v.end_of_storage_ = 0;
}

2 vector erase/clear/pop_back(删除操作)

2.1 pop_back函数最为简单,只需finish_向前移动,并析构对象即可
template<typename T, typename Alloc>
void SimpleVec<T, Alloc>::pop_back(){
    --finish_;
    destroy(finish_);
}
2.2 接下来clear,只析构vector中对象,vector中内存任然保留:
template<typename T, typename Alloc>
void SimpleVec<T, Alloc>::clear(){
    // 仅仅调用对象的析构函数,不释放内存
    destroy(start_, finish_);
    // end_of_storage_不改变,容量还是保留
    finish_ = start_;
}
2.3 erase函数就麻烦点,需要对象的移动
template<typename T, typename Alloc>
//terator SimpleVec<T, Alloc>::erase(iterator position){
typename SimpleVec<T, Alloc>::iterator SimpleVec<T, Alloc>::erase(iterator position){
    erase(position, position + 1);
}

template<typename T, typename Alloc>
typename SimpleVec<T, Alloc>::iterator SimpleVec<T, Alloc>::erase(iterator first, iterator last){
    // 尾部残留对象数
    difference_type len_of_tail = finish_ - last;
    // 删去的对象数目
    difference_type len_of_erase = last - first;
    // 如果len_of_erase < 0 就有问题
    finish_ -= len_of_erase;

    //由前往后赋值
    for (size_t i = 0; i < len_of_tail; ++i) {
        *(first + i) = *(last + i);
    }
    return first;
}

上面的erase函数要注意,必须要先destory [first, last)范围的对象,不然直接安装上面的赋值会导致对象的析构函数没有被调用。

2.4 size_tptrdiff_t的区别
不知道在看vector的源码中,你是否会对ptrdiff_t这个类型有疑问,下面说明下其与size_t的区别。
两个指针相减的结果的类型为ptrdiff_t,它是一种有符号整数类型。减法运算的值为两个指针在内存中的距离(以数组元素的长度为单位,而非字节),因为减法运算的结果将除以数组元素类型的长度。所以该结果与数组中存储的元素的类型无关

size_t是unsigned类型,用于指明数组长度或下标,它必须是一个正数,std::size_t.设计size_t就是为了适应多个平台,其引入增强了程序在不同平台上的可移植性。


ptrdiff_t是signed类型,用于存放同一数组中两个指针之间的差距,它可以使负数,std::ptrdiff_t.同上,使用ptrdiff_t来得到独立于平台的地址差值.

一般在STL中会定义 size_typedifference_type,如下:

typedef size_t     size_type;
typedef ptrdiff_t  difference_type;

下面给出,size_t, ptrdiff_t测试实例如下:

vector<int>    ivec{1, 2, 3, 4, 5, 6};
vector<double> dvec{1, 2, 3, 4, 5, 6};

// 无论double还是int长度都是6
ptrdiff_t i_p1 = ivec.end() - ivec.begin(); // 6
ptrdiff_t i_p2 = ivec.begin() - ivec.end(); // -6
cout<<"ptrdiff_t - i_p1: "<<i_p1<<" i_p2: "<<i_p2<<endl;
// ptrdiff_t - i_p1: 6 i_p2: -6

size_t s_p1 = ivec.end() - ivec.begin(); // 6
size_t s_p2 = ivec.begin() - ivec.end(); // 18446744073709551610
cout<<"size_t -  : s_p1: "<<s_p1<<" s_p2: "<<s_p2<<endl;
// size_t -  : s_p1: 6 s_p2: 18446744073709551610

ptrdiff_t d_p1 = dvec.end() - dvec.begin(); // 6
ptrdiff_t d_p2 = dvec.begin() - dvec.end(); // -6
cout<<"ptrdiff_t -  : d_p1: "<<d_p1<<" d_p2: "<<d_p2<<endl;
// ptrdiff_t -  : d_p1: 6 d_p2: -6

size_t d_s1 = dvec.end() - dvec.begin(); // 6
size_t d_s2 = dvec.begin() - dvec.end(); // 18446744073709551610
cout<<"size_t -  : d_s1: "<<d_s1<<" d_s2: "<<d_s2<<endl;
// size_t -  : d_s1: 6 d_s2: 18446744073709551610

无论是double(字节大小为8)还是int(字节大小为4)容器迭代器的长度差值与字节无关,如下我们可以看到-6 转为 size_t:

size_t s_minus = -6;
cout<<"-6 to size_t is: "<<s_minus<<endl;
// -6 to size_t is: 18446744073709551610

3 vector operator[]

接下来分析operator[], vector中返回的对象有引用版本和非要用版本,如果不返回引用那么=的时候会创建一个临时对象构造新的对象,在一定程度上导致程序性能下降。

stl::vector中声明如下:

reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

定义如下:

reference operator[](const size_t i){
    return *(begin() + i);//begin()

const_reference operator[](const size_t i)const{
    return *(begin() + i); //begin()const
}

注意:上面的operator[]下面的那个实用的是begin()const

iterator begin(){return start_;}
iterator begin()const{return start_;}

stack overflow中有个关于operators []的问题:Why std::vector has 2 operators [] realization ?

reference       operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;

原因如下:

void f(std::vector<int> & v1, std::vector<int> const & v2)
{
    //v1 is non-const vector
    //v2 is const vector

    auto & x1 = v1[0]; //invokes the non-const version
    auto & x2 = v2[0]; //invokes the const version

    v1[0] = 10; //okay : non-const version can modify the object
    v2[0] = 10; //compilation error : const version cannot modify 

    x1 = 10; //okay : x1 is inferred to be `int&`
    x2 = 10; //error: x2 is inferred to be `int const&`
}
声明非const版本好理解,我们定义一个引用到vector对象就可以改变vector中的成员了。
声明const版本,我们定义一个引用到vector对象不改变vector中的成员了。

下面在给出 operator== operator!=的实现:

template<typename T, typename Alloc>
bool SimpleVec<T, Alloc>::operator==(const SimpleVec& v)const{
    if(size() != v.size()){
        return false;
    } else{
        auto p1 = start_;
        auto p2 = v.start_;
        for(;p1 < finish_ && p2 < v.finish_;++p1, ++p2){
            if(*p1 != *p2)return false;
        }
        return true;
    }
};

template<typename T, typename Alloc>
bool SimpleVec<T, Alloc>::operator!=(const SimpleVec& v)const{
    return !(*this == v);
}

https://blog.csdn.net/honpey/article/details/8796386size_tptrdiff_t的区别部分参考)

https://stackoverflow.com/questions/14860622/c-stdvector-operator

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏琦小虾的Binary

map 学习(上)——C++中 map 的使用

map 学习(上)——C++中 map 的使用 欠下数据结构的债,迟早是要还的…… 最近写毕业论文过程中,需要用到哈希表的数据结构,此外空闲时间在刷 Leetc...

45360
来自专栏我和PYTHON有个约会

13.程序编程进阶:函数

写在前面: 经过前面几部分的学习,我们已经可以开发常规的一些简单功能处理程序了。 但是对于我们的项目开发还是远远不够的。本节内容开始进入基础进阶部分的学习

10220
来自专栏我是业余自学C/C++的

malloc、calloc、realloc

22030
来自专栏高性能分布式系统设计

Go的defer和方法修饰符的一个小坑

先看代码: ? ? https://play.golang.org/p/GlM23bSW6zf 可见: 1. for 循环变量只有一份  2. 单行的defer...

36450
来自专栏Python自动化测试

python内部函数学习(九)

python提供了很多的内置函数,这些内置的函数在某些情况下,可以起到很大的作用,而不需要专门去写函数实现XX功能,直接使用内置函数就可以实现,下...

12130
来自专栏恰童鞋骚年

你必须知道的指针基础-2.指针的声明和使用及数组和指针的关系

  At first,计算机中绝大部分数据都放到内存中的,不同的数据放到不同的内存区域中。But,内存角度没有数据类型,只有二进制;数据以字节(8位二进制)为单...

5010
来自专栏老司机的技术博客

宝宝都能学会的python编程教程8:条件判断与循环

先公布上期编程练习的答案,没错,L是一个指向三个列表的二维元祖。 条件判断 实际的项目中条件判断可以说是使用最多的语法之一了,不管是最简单的判断还是负责的业务逻...

35850
来自专栏大闲人柴毛毛

深入理解JVM(七)——Class文件结构

什么是JVM的“无关性”? Java具有平台无关性,也就是任何操作系统都能运行Java代码。之所以能实现这一点,是因为Java运行在虚拟机之上,不同的操作系统...

34740
来自专栏JavaEdge

(六)-class文件结构1 什么是JVM的“无关性”?2 纵观Class文件结构

30580
来自专栏javathings

解释一下 HashMap 的工作原理

HashMap 是基于散列表的数据结构。所谓散列表,它通过键值对的方式存储数据,把 key 通过散列算法计算出一个存储地址,将 value 放入这个地址中。散列...

47310

扫码关注云+社区

领取腾讯云代金券