🪐🪐🪐欢迎来到程序员餐厅💫💫💫
今日主菜:vector类
主厨:邪王真眼
所属专栏:c++专栏
主厨的主页:Chef‘s blog
坚持下去,成功不是目的,而是结果!
前言:
刚刚开始学c++,相信很多朋友对这门新的语言都充满了好奇,那么今天就来份硬菜满足一下各位,铛铛铛铛,c++第二座大山:STL容器之vector,他来了!
【本节目标】
-
1.vector的介绍及使用
-
2.vector深度剖析及模拟实现
1.vector的介绍
- 1. vector是表示可变大小数组的序列容器。
- 2. 就像数组一样,vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问,和数组一样高效。但是又不像数组,它的大小是可以动态改变的,而且它的大小会被容器自动处理。
- 3. 本质讲,vector使用动态分配数组来存储它的元素。当新元素插入时候,这个数组需要被重新分配大小为了增加存储空间。其做法是,分配一个新的数组,然后将全部元素移到这个数组。就时间而言,这是一个相对代价高的任务,因为每当一个新的元素加入到容器的时候,vector并不会每次都重新分配大小。
- 4. vector分配空间策略:vector会分配一些额外的空间以适应可能的增长,因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何,重新分配都应该是对数增长的间隔大小,以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
- 5. 因此,vector占用了更多的存储空间,为了获得管理存储空间的能力,并且以一种有效的方式动态增长。
- 6. 与其它动态序列容器相比(deque, list and forward_list), vector在访问元素的时候更加高效,在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作,效率更低。比起list和forward_list统一的迭代器和引用更好。
- 使用STL的三个境界:能用,明理,能扩展 ,那么下面学习vector,我们也是按照这个方法去学习
二.成员变量
- _start(指向有效空间的头)
- _finish(指向有效空间的尾)
- _end_of_storage(指向可用空间的尾)
2.1细节:
- 三个成员变量均迭代器(此刻即指针)
- 在声明处使用缺省值,赋值为nullptr
2.2代码展示:
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;
};
二、默认成员函数
2.1构造函数(constructor)
2.1.1
第一个参数是存放元素个数,第二个是每个初始化的值并且是缺省参数
vector(size_t n,T val=T()):_start(new T[n]), _finish(_start + n), _end_of_storage(_finish)
{iterator it = _start;while (it != _finish){*it = val;it++;}
}
注意,我们缺省参数值不是'\0'或0,而是T(),T是数据类型,T()是匿名构造,不过这里可能有朋友要问了:“自定义类型可以匿名构造我懂,但是内置类型也可以吗?”你别说,还真行。
但是指针的内置类型只有在这种模板中才可以用例如:
具体原因不用去了解,只要知道在这里有这个用法就行了。
2.1.2迭代器区间构造
- 使用类模板,可以传任意类型的迭代器
- 迭代器访问,条件最好使用不等于(!=)
为什么不用大于或小于呢,在string,vector很容易写出大于小于的重载,可是链表呢树呢?他们的空间不连续啊,所以从普适性的角度来看还是用!=更合适。
template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);first++;}}
2.2析构函数(destructor)
~vector()
{delete[]_start;_start = nullptr;_finish = nullptr;_end_of_storage = nullptr;
}
2.3拷贝构造函数
2.3.1传统写法:
细节:memcpy可能造成浅拷贝,带来危害。例如vector<vector<int>>,则元素类型是vector<int>,使用memcpy会导致将vector<int>对象直接拷贝而没有重新开辟空间,并对vector<int>对象进行复制
所以我们用=赋值,因为已经对=进行了重载,属于深拷贝。
vector(vector<T>&v1)
{size_t size = v1.size();iterator it = new T[size];//memcpy(it, v1._start, sizeof(T) * size);for (int i = 0; i < v1.size(); i++){it[i] = v1[i];}_start = it;_finish = _start + size;_end_of_storage = _start + v1.capacity();
}
2.3.2现代写法:
通过迭代器区间实现,先构造临时对象,再用swap函数使*this和tmp交换
vector(vector<T>& v1){vector<T>tmp(v1.begin(), v1.end());swap(tmp);}
void swap(vector<T>v)
{swap(_start, v1._start);swap(_finish, v1._finish);swap(_end_of_storage, v1._end_of_storage);
}
2.4 赋值运算操作符重载(operator=)
2.4.1传统写法
vector<T> operator=(vector<T>&v1)
{if (&v1 != this){size_t size = v1.size();iterator it = new T[size];//memcpy(it, v1._start, sizeof(T) * size);for (int i = 0; i < v1.size(); i++){it[i] = v1[i];}delete[]_start;_start = it;_finish = _start + size;_end_of_storage = _start + v1.capacity();}return *this;
}
2.4.2现代写法
- 传参变成传值,这样就会拷贝构造出一个临时对象
- 再使用vector中的swap,交换*this和tmp的值,完成赋值重载
vector<T> operator=(vector<T>v1)
{swap(v1);return *this;
}
三.迭代器
3.1 begin
迭代器的实现和编译器有关,不同的编译器有不同的实现方式。这里用指针来实现迭代器。
同时,重载了普通迭代器和const迭代器。
typedef T* iterator;
typedef const T* const_iterator;
iterator begin(){return _start;}const_iterator begin()const{return _start;}
3.2 end
迭代器遵循左闭右开的原则,begin指向首元素,end指向末元素的下一位。
iterator end()
{return _finish;
}
const_iterator end()const
{return _finish;
}
关于rbegin和rend我们之后再讲
四、容量
4.1 size
获取当前有效数据个数
细节:const修饰,保证普通和const类型vector类都能访问
size_t size()const
{return _finish - _start;
}
4.2 capacity
获取当前最大有效容量
细节:
size_t capacity()const
{return _end_of_storage - _start;
}
4.3 reserve
细节:
- 只扩容,不缩容
- 用赋值重载,进行深拷贝
- 记得保存size的大小。因为更新_start后还没有更新_finish,所以此时size()的值是没有意义的。
- 只修改capacity,不修改size
- reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。
void reserve(size_t Size){if(Size>capacity()){int size_ = size();iterator it = new T[Size];for (size_t i = 0; i < size(); ++i){tmp[i] = _start[i];}delete[] _start;_start = it;_finish = _start + size_;_end_of_storage = _start + Size;}}
4.4 resize
改变当前有效数据个数
细节:
- 只扩容不缩容
- 如果n<size,则减少有效个数,如果n>size,则填充指定值,直至达到n个
- 运用赋值重载,实现深拷贝
- capacity和size都修改
void resize(size_t Size,T val=T())
{if (Size <= size()){_finish = _start + Size;}else{if (size > capacity()){iterator it = new T[Size];for (size_t i = 0; i < size(); ++i){tmp[i] = _start[i];}_start = it;_finish = _start + Size;_end_of_storage = _finish;}for (iterator it = _start + size(); it < _start + Size; it++){*it = val;}}
}
4.5 empty
判断是否为空
细节:const修饰,保证普通和const类型vector类都能访问
bool empty()const
{return _finish - _start == 0;
}
五、修改
5.1 push_back
尾插
细节:需要扩容时,判断容量是否为空
void push_back(const T &val)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = val;_finish++;
}
5.2 pop_back
尾删
细节:断言vector不为空,才进行删除
void pop_back()
{assert(!empty());_finish--;
}
5.3 insert
指定位置插入
细节:
- 断言判断pos的合法性
- 扩容前,先保存pos的相对位置,扩容后,刷新pos并返回,防止迭代器失效
- 接受返回值,防止迭代器失效
-
iterator insert(iterator pos,T&val) {assert(pos <= _finish);assert(pos >= _start);if (_finish == _end_of_storage){int Pos = pos - _start;int Size = size();iterator it = new T[capacity() == 0 ? 4 : capacity() * 2];memcpy(it, _start, size() * sizeof(T));_start = it;_finish = _start + Size;_end_of_storage = _finish;pos = _start + Pos;}iterator end = _finish;while (end > pos){*end = *(end - 1);}*end = val;_finish++;return pos; }
5.4 erase
指定位置删除
细节:
- 断言判断pos的合法性
- 返回指向删除元素的后一位的迭代器,防止迭代器失效
iterator erase(iterator pos)
{assert(pos < _finish);assert(pos >= _start);iterator it = pos;while (pos < _finish-1){*pos = *(pos + 1);pos++;}_finish--;return it;
}
void erase(iterator begin,iterator end)
{assert(begin < _finish);assert(begin >= _start);assert(end <= _finish);assert(end>= _start);assert(begin <= end);iterator a = begin;iterator b = end;while (b < _finish){*a = *b;a++, b++;}_finish = _start + size()-(end - begin);
}
5.5 swap
交换两个vector类的值
细节:使用std库中的swap函数,交换各个成员变量的值
void swap(vector<T>v)
{swap(_start, v1._start);swap(_finish, v1._finish);swap(_end_of_storage, v1._end_of_storage);
}
5.6 operator[ ]
为了方便的访问元素,我们重载了[ ]运算符。同时,也分为普通版本和const版本,对应const对象和非const对象
T& operator[](const int i)
{assert(i < size());return *(_start + i);
}
const T& operator[](const int i)const
{assert(i < size());return *(_start + i);
}
5.7 vector 迭代器失效问题。(重点)
5.7.1问题分析
- 1.会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、 push_back、
- 2.erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置没有元素的,那么pos就失效了。因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了。
- 3.注意:Linux下,g++编译器对迭代器失效的检测并不是非常严格,处理也没有vs下极端
- 4. 与vector类似,string在插入+扩容操作+erase之后,迭代器也会失效
5.7.2问题解决
5.8 使用memcpy拷贝问题
问题分析:
总结
在学习了string的基础之上,可以很明显发现vector的学习成本降低了不少,函数名和用法大体相同。但是,我们依旧遇到了新的问题与挑战,如深拷贝,迭代器失效等。不过都被一一克服了,ok,那么,vector,over!
客官留个赞再走吧