【C++】C++ STL探索:Vector使用与背后底层逻辑

25-03-07 11:29

8489

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-kimbie-light">

在这里插入图片描述

class="table-box">

C++语法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
命名空间	缺省参数与函数重载	C++相关特性	类和对象-上篇	类和对象-中篇
类和对象-下篇	日期类	C/C++内存管理	模板初阶	String使用
String模拟实现

在string类文章中提及了STL容器间的接口是大差不差的，本篇将直接通过模拟实现Vector来讲解底层实现与使用。

请添加图片描述
Alt
🌈个人主页：是店小二呀
🌈C语言专栏：C语言
🌈C++专栏： C++
🌈初阶数据结构专栏：初阶数据结构
🌈高阶数据结构专栏：高阶数据结构
🌈Linux专栏： Linux

🌈喜欢的诗句:无人扶我青云志我自踏雪至山巅请添加图片描述

class="toc">

前文:vector介绍

vector的文档介绍

vector是表示可变大小数组的序列容器，底层是动态开辟顺序表
vector插入新数据发生扩容，其做法是，分配一个新的数组，然后将全部元素移动到这个数组(单论时间，需要付出相对代价很高).每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小(不清楚这块空间剩余多少内存)
vector分配空间策略:vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大，不同的库采用不同的策略权衡空间的使用和重新分配。重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的
与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更

一、模拟实现Vector准备工作

在模拟实现vector过程中，为了避免跟库中vector发生冲突，需要创建个命名空间，在命名空间中实现vector。需要选择现实vector类模板去用于不同的类型(内置类型、自定义类型)

namespace vec
{
	template<class T>
	class vector
	{

	};
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1.1 vector的成员对象

适用于不同类型的操作，可以通过模板参数列表的类型指针，去对不同类型进行访问和修改。

template<class T>
    class vector
    {
        public:
        typedef T* iterator;
        typedef const T* const_iterator;

        private:
        iterator _start = nullptr;
        iterator _finish = nullptr;
        iterator _end_of_storage = nullptr;
    };
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

成员说明:

typedef T* iteratror:采用原生指针去模拟迭代器(不是真正的迭代器)
_start：指向空间的第一个位置
_finish：指向最后有效数据的位置
_end_of _storage：指向空间的最后一个位置

1.2 原生指针模拟迭代器

	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
        
        iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}
        
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

class="hide-preCode-box">

二、正式模拟实现Vector

2.1 构造函数

具体说明：allocator_type是内存配置器（内存池）和explicit这个阶段都不用去理会它。最经常使用是接口(1)和(4)，其中(1)就当作是无参的构造，不用传什么值，就使用它的缺省值()

value_type()是模板参数列表实例化转化的T类型

2.1.1 无参构造

    vector()
    {}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2

这里就算不显式写无参构造，编译器也会自动生成。从某种意义上无参构造不用写，但是我们需要实现拷贝构造，编译器就不会默认生成无参构造函数了。总之要显式写无参构造函数。

2.1.2 vector迭代区间构造

类模板的成员函数可以是函数模板

template<class InputIterator>
    vector(InputIterator fist, InputIterator last)
{
    while (fist != last)
    {
        push_back(*fist);
        ++fist;
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9

使用场景：

vector<int> v2(v1.begin()+1, v1.end()-1);
print_vector(v2);

string str("abcd");
vector<int> v3(str.begin(), str.end());
print_vector(v3);
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6

具体说明：在使用该接口时，需要注意不可以(--v1.begin(), --v1.end()使用。这里begin()和end()函数是传值返回，返回临时对象具有常性，不能通过++或–修改临时对象

2.1.3 初始化构造

vector(size_t n, const T* val = T())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8

这段初始化构造逻辑是没有问题的，但是在调用过程可能会出现问题

首先给出三组数据，去使用初始化构造函数
    vector<int> v1(10, 1);
    print_vector(v1);

    vector<int> v2(10u, 1);
    print_vector(v2);

    vector<int> v3(10, 'a');
    print_vector(v3);
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9

具体说明：在调用过程中会报出非法的间接寻址错误，原因在于第一个实例化(就这个比较特别)，调用的是函数模板，这里*first就会报错，想走捷径，发现掉坑里面。

vector v1(10, 1)参数部分都是整型类型，如果使用下面的初始化构造，需要int转化为size_t（发生隐式类型转化）。对于模板初始化函数而言，自动推导类型，对此上面更加匹配(那就报错哦)
vector v2(10u, 1)参数部分都是无符号整数，有现成吃现成，就是调用第二个
vector v3(10, 'a')参数部分是不同类型，自然调不动第一个函数，调用第二个函数，进行类型转化

解决措施：实现函数重载，特殊情况特殊处理

vector(size_t n, const T* val = T())
{
    reserve(n);
    for (size_t i = 0; i < n; i++)
    {
        push_back(val);
    }
}
vector(int n, const T& val = T())
{
    reserve(n);
    for (int i = 0; i < n; i++)
    {
        push_back(val);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2 拷贝构造

vector(const vector<T>& v)
{
    //需要开一样大的空间
    reserve(v.capacity());
    for (auto& e : v)
    {
        push_back(e);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9

具体说明:这里可以采用string类拷贝构造方式，但是这个更加简洁。auto自动识别类型建议加&，如果T是自定义类型，就需要调用多次拷贝构造(深拷贝)

2.3 初始化列表

auto x = { 1,2,3,4,5,6 };
cout << typeid(x).name() << endl;
cout << sizeof(x) << endl;
输出结果:
class std::initializer_list<int>
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5

当我们想实现像数组nums[5] = {12,3,4,5}这样初始化，库提供初始化列表initializer_list的方式满足了我们的需求。

其中vector类也包含了这种方式

initializer_list y = {1,2,3,4,5};
vector x = {1,2,3,4,5};

通过类模板在vector类中实现该功能

vector(initializer_list<T> il)
{
    reserve(il.size());
    for (auto& e : il)
    {
        push_back(e);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8

2.4 析构函数

~vector()
{
    delete[]_start;
    _start = nullptr;
    _finish = _end_of_storage = nullptr;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6

2.5 operator[] 下标访问

T& operator[](size_t pos)
{
    assert(pos <= size());

    return _start[pos];
}

const T& operator[](size_t pos) const
{
    assert(pos <= size());

    return _start[pos];
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13

具体说明：

下标加方括号仅限于物理逻辑连续的容器，比如:string、vector、list之类。
针对对象是否被const修饰，需要重载两个函数(可读可写，可读不可写)。使用引用返回，可以修改到实参和提高效率

2.6 swap 交换函数

void swap(vector& v)
{
    std::swap(_start, v._start);
    std::swap(_start, v._start);
    std::swap(_start, v._start);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6

2.7 operator= 赋值运算符重载

    //v2 = v1;
    vector<T>& operator=(vector<T> v)
    {
        swap(v);

        return *this;
    }
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7

说明：跟string是同一套流程，这里就直接选用优化现代写法版本

2.8 得到当前元素空间信息

2.8.1 size(有效元素个数)

size_t size() const
{
    //指针 - 指针
    return _finish - _start;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5

2.8.2 capacity(当前空间容量)

size_t capacity()	const
{
    return _end_of_storage - _start;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4

说明:

size是有效元素的个数，capacity是当前空间的容量
都是通过指针-指针得到的大小

2.9 reserve

2.9.1 第一版本:野指针问题

void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        memcpy(tmp, _start, size(T) * n);

        delete[] _start;
        _start = tmp;
        _finish =  tmp + size();
        _end_of_storage =  tmp + n;
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13

不足之处:迭代器失效的问题，出现野指针_finish指向错误。在delete[] _start的时候，finish还在指向旧空间，导致调用size()得到数据错误。

解决办法:在销毁旧空间之前，提前保留size()的大小

void reserve(size_t n)
{
    if (n > capacity)
    {
        T& tmp = new T[n];
        size_t size = size();
        memcpy(tmp, _statr, sizeof(T) * n);

        delete[] _start;
        _start = tmp;
        _finish = tmp + size;
        _end_of_storage = tmp + n;
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.9.2 第二版本：浅拷贝问题

问题说明:这里memcpy是逐字节拷贝，属于浅拷贝。当T为自定义类型，使用memcpy进行浅拷贝操作，会指向同一块空间。

_str指向的空间没有拷贝，导致指向同一块空间，调用析构函数会造成野指针问题。

解决办法:

void reserve(size_t n)
{
    if (n > capacity())
    {
        size_t old_size = size();

        T* tmp = new T[n];
        //memcpy(tmp, _start, size(T) * n);
        for (size_t i = 0; i < old_size; i++)
        {
            //自定义类型会赋值运算符重载
            tmp[i] = _start[i];
        }

        delete[] _start;
        _start = tmp;
        _finish = tmp + old_size;
        _end_of_storage = tmp +n ;
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这属于一种更加暴力的解法，直接将_start里面的数据拷贝过来

2.10 resize(重点常用)

//重点实现resize
void resize(size_t n, const T& val = T())
{
    //缩容
    if (n <= size())
    {
        //类似截断
        _finish = _start + n;
    }
    else
    {
        //提前扩容
        //大于capacity才起作用
        reserve(n);

        while (_finish < _start + n)
        {
            *_finish = val;
            _finish++;
        }
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

具体说明:虽然没有reserve这么多坑，但是有几个知识点值得我们注意。

2.10.1 const T& val = T()解释

对于T可能是内置类型或自定义类型，对于自定义类型不能通过简单常量作为缺省值，所以选择了T()调用构造函数作为缺省值最合适。
对于内置类型不是说没有构造函数这一说法吗？好的，内置类型被迫升级下。内置类型也有了自己的构造函数和析构函数(平常一般不使用)，int就是0（char也是整型 ASCII码）、double就是0.0、指针就是空指针。
因为缺省值怎么给都不合理，只能用自身的构造(匿名对象实例化)

2.11 单或多参数构造支持隐式类型转化

string str="1111";//构造+拷贝构造-->优化 直接构造
const string& str1="1111";//构造临时对象，引用的是临时对象

vector<string>v;
v.push_back(str);
v.push_back(string("2222"));
v.push_back("33333");
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7

隐式类型+优化的情况:

vector<int> v1={1,2,3,4,5};

vector<int> v2({1,2,3,4,5}) //直接构造
    
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4

2.12 insert

2.12.1 insert使用

    void insert(iterator pos, const T& val)
    {
        assert(_start <= pos);
        assert(pos <= _finish);

        //考虑是否需要扩容
        //说明空间已经满了
        if (_finish == _end_of_storage)
        {
            reserve(capacity() == 0 ? 4 : capacity() * 2);

        }

        //开始移动数据
        iterator it = _finish - 1;

        while (it >= pos)
        {
            *(it + 1) = *it;
            it--;
        }

        *pos = val;
        _finish++;
    }
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

具体说明：使用迭代器去模拟实现insert比起string模拟实现，在 while (it >= pos)没有pos为0的坑。涉及到开辟或销毁空间时，都有可能涉及到迭代器失效，对此都需要考虑到位。

2.13 扩容前迭代器失效

void test_vector()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    v1.push_back(6);
    v1.push_back(7);
    v1.push_back(8);
    print_vector(v1);

    vector<int>::iterator it = v1.begin() + 3;
    v1.insert(it, 40);
    print_vector(v1);

    cout << *it << endl;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

问题:在进行insert操作后，迭代器it就会失效。

思考:在扩容接口中，不是解决迭代器失效的问题了吗？

具体说明：

在调用insert接口是it传参pos位置，而形参是实参的一份临时拷贝，那么需要传引用解决。一波未平一波又起，如果传引用v2.insert(v2.begin(),11.11)，这里v2.begin()返回的是临时变量，不能通过引用来接收。

没有给出解决办法，调用insert接口出现扩容操作，迭代器会失效，不要去使用

2.14 erase

2.14.1 erase使用

//迭代器实现erase
iterator erase(iterator pos)
{
    assert(_start <= pos);
    //删除不到_finish这个位置
    assert(pos < _finish);

    iterator it = pos+1;

    //it=pos+1=_finish就是最后一个位置
    while (it <= _finish)
    {
        *(it - 1) = *(it);
        it++;
    }
    _finish--;
    return pos;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.14.2 验证迭代器失效

接下来我将给出三个场景:都是关于删除偶数

第一个场景:没啥问题

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);

		vector<int>::iterator it = v1.begin();
		while (it != v1.end())
		{
			if (*it % 2 == 0)
			{
				v1.erase(it);
			}
			++it;
		}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第二个场景:少删除

		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(4);
		v1.push_back(5);

		vector<int>::iterator it = v1.begin();
		while (it != v1.end())
		{
			if (*it % 2 == 0)
			{
				v1.erase(it);
			}
			++it;
		}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

第三个场景:迭代器失效

vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(4);
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7

关于上面出现的问题分析:

在erase的逻辑是通移动数据覆盖不需要的数据，达到删除的效果。逻辑上会跳过一个值，移动++可能会导致错过了一些值。
如果it++操作跳过end()，it就会一路向北，错过了判断条件

解决措施:

vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
    if (*it % 2 == 0)
    {
        v1.erase(it);
    }
    else
    {
        it++;
    }
}
print_vector(v1);
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13

2.14.3缩容导致迭代器失效

上面解决措施在Linux下还可以，但是在Vs下就不行了。由于因为Vs下的iterator没有使用原生指针实现，是自定义类型的迭代器，内部会进行强制类型检查。

对于erase不同编译器迭代器是不同的，erase也可能会缩容。erase迭代器的解决方案有两个：迭代器失效以后不要直接使用，如果要使用按照规则重新更新后使用。

	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			it=v1.erase(it);
		}
		else
		{
			it++;
		}
	}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12

这样子就可以适应不同的版本，缩容以后。迭代器还是但会删除原生的下一个迭代器。

2.15 push_back

void push_back(const T& val )
{
    insert(end(), val);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4

2.16 pop_back

void pop_back()
{
    /*assert(!empty());

                --_finish;*/

    erase(end()-1);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8

2.17 pop_back

void pop_back()
{
    /*assert(!empty());

                --_finish;*/

    erase(end()-1);
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8

2.18 empty 判断空

bool empty()
{
    return _start == _finish;
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4

2.19 print_vector 打印数据

为了实现适用于不同类型的打印，这里需要涉及一个函数模板

void print_vector(const vector<T>& v)
{
    //下标加[]
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;

    //迭代器
    vector<T>::const_iterator it = v.begin();
    while (it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    //范围for
    for (auto e : v)
    {
        cout << e << " ";
    }
    cout << endl;、
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

不足之处：在三种遍历方式，使用迭代器遍历会出现报错。

问题在于: vector,这里类模板没有实例化，对于内嵌类型，那么不敢进去取，里面的东西也有没有实例化。编译器无法识别const_iterator是静态变量还是内中类,选择报错。

vector类模板没有完成实例化，对于内嵌类型const_iterator不敢进去取，对于内部是否实例。编译器无法编译器无法识别const_iterator是静态变量还是内中类。编译器选择报错。

解决措施:编译器规定typename告诉后面后面是一个类型，不是静态成员变量(先通过编译，之后再给你实例化)。在编译阶段才知道类型，如果需要一个类型接收，可以使用auto自动识别类型。

typename vector<T>::const_iterator it = v.begin();
auto it = v.begin();
while (it != v.end())
{
    cout << *it << " ";
    ++it;
}
cout << endl;
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8

三、vector.h

#pragma once
#include 
#include 
#include 

using namespace std;
namespace bit
{
    template<class T>
        class vector
        {
            public:
            typedef  T*  iterator;
            typedef const T* const_iterator;


            iterator begin()
            {
                return _start;
            }

            iterator end()
            {
                return _finish;
            }

            const_iterator begin() const
            {
                return _start;
            }


            const_iterator end() const
            {
                return _finish;
            }


            //构造函数
            //无参构造
            vector()
            {}
            //有参构造
            //.....

            //析构
            ~vector()
            {
                delete[]_start;
                _start = nullptr;
                _finish = _end_of_storage = nullptr;
            }

            //vector v1={1,2,3,4,5,6};
            vector(initializer_list<T> il)
            {
                reserve(il.size());
                for (auto& e : il)
                {
                    push_back(e);
                }
            }

            //拷贝构造
            //v2(v1)
            vector(const vector<T>& v)
            {
                //需要开一样大的空间
                reserve(v.capacity());

                for (auto& e : v)
                {
                    push_back(e);
                }
            }
            //v2 = v1;
            vector<T>& operator=(vector<T> v)
            {
                swap(v);

                return *this;
            }
            //通过下标访问
            //并且不知道会返回什么具体的类型
            T& operator[](size_t pos)
            {
                //不能等于size()，指向\0
                assert(pos < size());

                return _start[pos];
            }

            const T& operator[](size_t pos) const
            {
                assert(pos < size());

                return _start[pos];
            }

            //交换
            void swap(vector<T>& v)
            {
                std::swap(_start, v._start);
                std::swap(_start, v._start);
                std::swap(_start, v._start);
            }

            //得到当前元素空间信息

            //指针-指针
            size_t size()	const
            {
                return _finish - _start;
            }

            size_t capacity()	const
            {
                return _end_of_storage - _start;
            }

            //扩容
            //第一个问题，迭代器失效
            //void reserve(size_t n)
            //{
            //	if (n > capacity())
            //	{
            //		T* tmp = new T[n];
            //		memcpy(tmp, _start, size(T) * n);

            //		delete[] _start;
            //		_start = tmp;
            //		_finish =  tmpt + size();
            //		_end_of_storage =  tmp + n;
            //	}
            //}

            改良
            第二个问题，当T为自定义类型，就是浅拷贝，但是还是指向同一块空间
            //void reserve(size_t n)
            //{
            //	if (n > capacity())
            //	{
            //		size_t old_size = size();

            //		T* tmp = new T[n];
            //		memcpy(tmp, _start, size(T) * n);

            //		delete[] _start;
            //		_start = tmp;
            //		_finish =  tmp + old_size;
            //		_end_of_storage =  tmp + n;
            //	}
            //}

            正确写法
            void reserve(size_t n)
            {
                if (n > capacity())
                {
                    size_t old_size = size();

                    T* tmp = new T[n];
                    //memcpy(tmp, _start, size(T) * n);
                    for (size_t i = 0; i < old_size; i++)
                    {
                        tmp[i] = _start[i];
                    }

                    delete[] _start;
                    _start = tmp;
                    _finish = tmp + old_size;
                    _end_of_storage = tmp +n ;
                }
            }

            //vector的迭代区间
            //函数模板
            template<class InputIterator>
                vector(InputIterator fist, InputIterator last)
            {
                while (fist != last)
                {
                    push_back(*fist);
                    ++fist;
                }
            }

            //初始化 构造
            vector(size_t n, const T& val = T())
            {
                reserve(n);
                for (size_t i = 0; i < n; i++)
                {
                    push_back(val);
                }
            }

            vector(int n, const T& val = T())
            {
                reserve(n);
                for (int i = 0; i < n; i++)
                {
                    push_back(val);
                }
            }
            //重点实现resize
            void resize(size_t n, const T& val = T())
            {
                //缩容
                if (n <= size())
                {
                    _finish = _start + n;
                }
                else
                {
                    //提前扩容
                    //大于capacity才起作用
                    reserve(n);

                    while (_finish < _start + n)
                    {
                        *_finish = val;
                        _finish++;
                    }
                }
            }
            //核心操作
            void push_back(const T& val )
            {
                insert(end(), val);
            }


            void pop_back()
            {
                /*	assert(!empty());
			_finish--;*/

                //不能--
                erase(end() - 1);
            }

            //判断空
            bool empty()
            {
                return _start == _finish;
            }

            //实现插入操作时，可能会涉及到扩容操作，就有可能出现迭代器失效的可能
            void insert(iterator pos, const T& val )
            {
                assert(_start <= pos);
                assert(pos <= _finish);

                //考虑是否需要扩容
                //说明空间已经满了
                if (_finish == _end_of_storage)
                {
                    size_t len = pos - _start;
                    //这里迭代器失效的问题
                    //不是解决了吗！当时pos没有解决呀！
                    reserve(capacity() == 0 ? 4 : capacity() * 2);

                    pos = _start + len;
                }

                //开始移动数据
                iterator it = _finish - 1;

                while (it >= pos)
                {
                    *(it + 1) = *it;
                    it--;
                }

                *pos = val;
                _finish++;
            }

            //迭代器实现erase
            iterator erase(iterator pos)
            {
                assert(_start <= pos);
                //删除不到_finish这个位置
                assert(pos < _finish);

                iterator it = pos+1;

                //it=pos+1=_finish就是最后一个位置
                while (it <= _finish)
                {
                    *(it - 1) = *(it);
                    it++;
                }
                _finish--;
                return pos;
            }

            private:
            iterator _start=nullptr;
            iterator _finish=nullptr;
            iterator _end_of_storage=nullptr;
        };

    // 函数模板
    template<class T>
        void print_vector(const vector<T>& v)
    {
        //for (size_t i = 0; i < v.size(); i++)
        //{
        //	cout << v[i] << " ";
        //}
        //cout << endl;

        //typename vector::const_iterator it = v.begin();
        auto it = v.begin();
        while (it != v.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        /*for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;*/
    }

    void test1()
    {
        vector<int> v;
        v.push_back(12);
        v.pop_back();
        v.push_back(1);
        print_vector(v);
    }


    void test_vector2()
    {
        vector<int> v1(10, 1);
        print_vector(v1);

        vector<int> v2(10u, 1);
        print_vector(v2);

        vector<int> v3(10, 'a');
        print_vector(v3);
    }

    void test_vector3()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        v1.push_back(6);
        v1.push_back(7);
        v1.push_back(8);
        print_vector(v1);

        vector<int>::iterator it = v1.begin() + 3;
        v1.insert(it, 40);
        print_vector(v1);

        cout << *it << endl;
    }

    void test_vector4()
    {
        auto x = { 1,2,3,4,5,6 };
        cout << typeid(x).name() << endl;
        cout << sizeof(x) << endl;
    }

    void test_vector5()
    {
        vector<int> v1;
        v1.push_back(1);
        v1.push_back(2);
        v1.push_back(3);
        v1.push_back(4);
        v1.push_back(5);
        v1.push_back(4);

        //std::vector::iterator it = v1.begin();
        vector<int>::iterator it = v1.begin();
        while (it != v1.end())
        {
            if (*it % 2 == 0)
            {
                it=v1.erase(it);
            }
            else
            {
                it++;
            }
        }
        print_vector(v1);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405

以上就是本篇文章的所有内容，在此感谢大家的观看！这里是店小二呀C++笔记，希望对你在学习C++语言旅途中有所帮助！

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/2302_79177254/article/details/141309620","extend1":"pc","ab":"new"}">>

注：本文转载自blog.csdn.net的是店小二呀的文章"https://blog.csdn.net/2302_79177254/article/details/141309620"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

/ 登录

评论记录：

未查询到任何数据！