(constructor)构造函数声明 | 接口说明 |
---|---|
vector()(重点) | 无参构造 |
vector(size_type n, const value_type& val = value_type()) | 构造并初始化 n 个 val |
vector (const vector& x) (重点) | 拷贝构造 |
vector (InputIterator first, InputIterator last) | 使用迭代器进行初始化构造 |
iterator 的使用 | 接口说明 |
---|---|
begin() 、end() | begin() 获取第一个数据位置的 iterator / const_iterator, end() 获取**最后一个数据的下一个位置**的iterator/const_iterator |
rbegin() 、rend() | rbegin() 获取最后一个数据位置的reverse_iterator,rend() 获取第一个数据前一个位置的reverse_iterator |
容量空间 | 接口说明 |
---|---|
size | 获取数据个数 |
capacity | 获取容量大小 |
empty | 判断是否为空 |
resize(重点) | 改变 vector 的 size |
reserve (重点) | 改变 vector 的 capacity |
// 测试vector的默认扩容机制
void
TestVectorExpand()
{ size_t sz; vector<int> v; sz = v.capacity(); cout <<
"making v grow:\n";
for
(int i =
0; i <
100;
++i)
{ v.push_back(i);
if
(sz != v.capacity())
{ sz = v.capacity(); cout <<
"capacity changed: "
<< sz <<
'\n';
}
}
}
//vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容 making foo grow: capacity changed:
1 capacity changed:
2 capacity changed:
3 capacity changed:
4 capacity changed:
6 capacity changed:
9 capacity changed:
13 capacity changed:
19 capacity changed:
28 capacity changed:
42 capacity changed:
63 capacity changed:
94 capacity changed:
141
//g++运行结果:linux下使用的STL基本是按照2倍方式扩容 making foo grow: capacity changed:
1 capacity changed:
2 capacity changed:
4 capacity changed:
8 capacity changed:
16 capacity changed:
32 capacity changed:
64 capacity changed:
128
// 如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void
TestVectorExpandOP()
{ vector<int> v; size_t sz = v.capacity(); v.reserve(100);
// 提前将容量设置好,可以避免一遍插入一遍扩容 cout <<
"making bar grow:\n";
for
(int i =
0; i <
100;
++i)
{ v.push_back(i);
if
(sz != v.capacity())
{ sz = v.capacity(); cout <<
"capacity changed: "
<< sz <<
'\n';
}
}
}
vector增删查改 | 接口说明 |
---|---|
push_back(重点) | 尾插 |
pop_back (重点) | 尾删 |
find | 查找。(注意这个是算法模块实现,不是vector的成员接口) |
insert | 在position之前插入val |
erase | 删除position位置的数据 |
swap | 交换两个vector的数据空间 |
operator[] (重点) | 像数组一样访问 |
对于vector可能会导致其迭代器失效的操作有:
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
// 1、将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容
// v.resize(100, 8);
// 2、reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变
// v.reserve(100);
// 3、插入元素期间,可能会引起扩容,而导致原空间被释放
// v.insert(v.begin(), 0);
// v.push_back(8);
// 4、给vector重新赋值,可能会引起底层容量改变
// v.assign(100, 8);
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout<<endl;
return 0;
/*
出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉,
而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的
空间,而引起代码运行时崩溃。
解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新
赋值即可。
*/
}
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 删除pos位置的数据,导致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此处会导致非法访问,因为pos的意义已经变了
return 0;
}
erase 删除 pos 位置元素后,pos 位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果 pos 刚好是最后一个元素,删完之后 pos 刚好是end的位置,而 end 位置是没有元素的,那么pos就失效了。因此删除vector 中任意位置上元素时,vs 就认为该位置迭代器失效了(linux下可能不会报错,但是意义也是变了)。
解决方案如下: 迭代器失效解决办法:在使用前,对迭代器重新赋值即可。
#include <iostream>
using namespace std;
#include <vector>
//很显然这个是错的,因为判断到2的时候,2是偶数,所以erase掉,但是这个时候 迭代器it 就失效了
//再者,当erase掉2后,数组元素会向前挪动,但是it又被++了,导致3并没有被判断,造成漏判了
//而到4的时候,将4 erase掉后,数组元素向前挪动,而end()也会向前更新挪动,导致it++后移到了end()后面,造成越界
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
return 0;
}
//这个写法是对的,也是erase避免迭代器失效的解决方法
//因为erase后迭代器就失效了,但是erase函数会返回一个有效的迭代器,所以当我们要删除某个元素的时候
//需要让 it = v.erase(it),这样子就能避免失效问题
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it);
else
++it;
}
return 0;
}
// 1. 扩容之后,迭代器已经失效了,程序虽然可以运行,但是运行结果已经不对了
int main()
{
vector<int> v{1,2,3,4,5};
for(size_t i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
auto it = v.begin();
cout << "扩容之前,vector的容量为: " << v.capacity() << endl;
// 通过reserve将底层空间设置为100,目的是为了让vector的迭代器失效
v.reserve(100);
cout << "扩容之后,vector的容量为: " << v.capacity() << endl;
// 经过上述reserve之后,it迭代器肯定会失效,在vs下程序就直接崩溃了,但是linux下不会
// 虽然可能运行,但是输出的结果是不对的
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
程序输出:
1 2 3 4 5
扩容之前,vector的容量为: 5
扩容之后,vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5
// 2. erase删除任意位置代码后,linux下迭代器并没有失效
// 因为空间还是原来的空间,后序元素往前搬移了,it的位置还是有效的,但是意义已经变了
#include <vector>
#include <algorithm>
int main()
{
vector<int> v{1,2,3,4,5};
vector<int>::iterator it = find(v.begin(), v.end(), 3);
v.erase(it);
cout << *it << endl;
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
程序可以正常运行,并打印:
44 5
// 3: erase删除的迭代器如果是最后一个元素,删除之后it已经超过end
// 此时迭代器是无效的,++it导致程序崩溃
int main()
{
vector<int> v{1,2,3,4,5};
// vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
while(it != v.end())
{
if(*it % 2 == 0)
v.erase(it);
++it;
}
for(auto e : v)
cout << e << " ";
cout << endl;
return 0;
}
========================================================
// 使用第一组数据时,程序可以运行
[liren@VM-0-3-centos 20220729]$ g++ testVector.cpp -std=c++11
[liren@VM-0-3-centos 20220729]$ ./a.out
1 3 5
=========================================================
// 使用第二组数据时,程序最终会崩溃
[liren@VM-0-3-centos 20220729]$ vim testVector.cpp
[liren@VM-0-3-centos 20220729]$ g++ testVector.cpp -std=c++11
[liren@VM-0-3-centos 20220729]$ ./a.out
Segmentation fault
//因为判断6的时候,erase掉后,数组元素向前挪动,end()也向前挪动,然后it++,导致跳到了end()后面,造成越界
从上述三个例子中可以看到:SGI STL中,迭代器失效后,代码并不一定会崩溃,但是运行结果肯定不对,但是如果 it 不在 begin和end范围内,也就是越界了,肯定会崩溃的。
#include <string>
void TestString()
{
string s("hello");
auto it = s.begin();
// 放开之后代码会崩溃,因为resize到20会string会进行扩容
// 扩容之后,it指向之前旧空间已经被释放了,该迭代器就失效了
// 后序打印时,再访问it指向的空间程序就会崩溃
//s.resize(20, '!');
while (it != s.end())
{
cout << *it;
++it;
}
cout << endl;
it = s.begin();
while (it != s.end())
{
it = s.erase(it);
// 按照下面方式写,运行时程序会崩溃,因为erase(it)之后
// it位置的迭代器就失效了
// s.erase(it);
++it;
}
}
总结:
其中的几个要点问题:
为何要重载一个 int 版本的构造函数,而不是直接使用 size_t 版本的?
为什么不能用memcpy进行拷贝而用 “=” 就可以呢?(具体看下面的解释)
对于内置类型,用memcpy就是一个一个字节拷过去当然没问题
但是对于自定义类型,用memcpy拷贝可能涉及到深拷贝的问题,因为像string、list这些类,里面都含有指针,若只是将他们拷贝过去,相当于只是浅拷贝,这样子调用了析构函数,对同一块空间析构了两次,程序就奔溃了。
而如果用 “=”,其实相当于调用自定义类型自己实现的赋值运算符拷贝,这是深拷贝,如下赋值运算符的实现,_start[i] 和 v._start[i]都为string类型,用了 “=” 实则又就是调用了string自己的赋值运算符拷贝函数,这样子就实现了深拷贝。
vector<T>& operator=(const vector<T>& v)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
_start[i] = v._start[i];
_finish = _start + v.size();
return *this;
}
#pragma once
#include<iostream>
#include<cassert>
using namespace std;
namespace liren
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
typedef T* iterator;
typedef const T* const_iterator;
public:
vector()
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{}
//(注意,使用reserve的话需要初始化一下变量,因为reserve中需要用到这些变量,若为随机值则乱套了)
// 但是调试发现,vs2022做了优化,默认替我们初始化为nullptr,但是为了可移植性,强烈建议还是加上初始化列表
vector(const vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
/*
// 第一种写法,memcpy有缺陷,会引发深层次的深浅拷贝问题
_start = new T[v.capacity()];
memcpy(_start, v.cbegin(), v.size() * sizeof(T));
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
*/
// 第二种写法,复用reserve开空间,用循环给空间拷贝
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
push_back(v._start[i]);
}
//第一种写法,自己实现
/*vector<T>& operator=(const vector<T>& v)
{
reserve(v.capacity());
for (size_t i = 0; i < v.size(); ++i)
_start[i] = v._start[i];
_finish = _start + v.size();
return *this;
}*/
// 第二种写法,复用拷贝构造,且不需要接收引用的参数,只需传值
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
// 类模板的成员函数,还可以再是函数模板
template<class InputIterator>
vector(InputIterator first, InputIterator last)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
//对于需要继续构造一个int参数的函数,其实这里改成模板T,让编译器去推类型即可
//这里的T()表示构造函数,对于内置类型也会调用其构造函数,若不给值则默认初始化为0
vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
/*
* 理论上将,提供了vector(size_t n, const T& value = T())之后
* vector(int n, const T& value = T())就不需要提供了,但是对于:
* vector<int> v(10, 5);
* 编译器在编译时,认为T已经被实例化为int,而10和5编译器会默认其为int类型
* 就不会走vector(size_t n, const T& value = T())这个构造方法,
* 最终选择的是:vector(InputIterator first, InputIterator last)
* 因为编译器觉得区间构造两个参数类型一致,因此编译器就会将InputIterator实例化为int
* 但是10和5根本不是一个区间,编译时就报错了
* 故需要增加该构造方法
*/
vector(int n, const T& value = T())
: _start(new T[n])
, _finish(_start + n)
, _end_of_storage(_finish)
{
for (int i = 0; i < n; ++i)
{
_start[i] = value;
}
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
iterator begin()
{
return _start;
}
const_iterator cbegin() const
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator cend() const
{
return _finish;
}
T& operator[](size_t index)
{
assert(index < capacity());
return _start[index];
}
const T& operator[](size_t index) const
{
assert(index < capacity());
return _start[index];
}
void resize(size_t n, const T val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
for (iterator i = _finish; i < _start + n; ++i)
{
*i = val;
}
_finish = _start + n;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//拷贝的第一种写法,但是如果传的是string等自定义类型,就会出现深层次的深浅拷贝问题,不推荐
//memcpy(tmp, _start, sz * sizeof(T));
//拷贝的第二种写法,用了赋值运算符,string等底层已经实现了深拷贝,所以不会有问题
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_end_of_storage = _start + n;
}
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
*_finish = x;
++_finish;
}
bool empty() const
{
return _start == _finish;
}
void pop_back()
{
assert(!this->empty());//防止_finish相等时候减到_start前面越界
--_finish;
}
void swap(vector<T>& v)
{
if (&v == this)
return;
::swap(_start, v._start);
::swap(_finish, v._finish);
::swap(_end_of_storage, v._end_of_storage);
}
//STL中的insert不采用在函数中解决失效问题是因为有缺陷
//但是如果面试官要求解决失效问题,可以把下面的两点要点补上,即可解决
//所以用insert时候尽量用一次就重新查找pos的位置,避开失效问题
void insert(iterator pos, const T& x) //解决pos失效的方法一:pos用传引用
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//更新pos,解决扩容后pos变成野指针后失效的问题
pos = _start + len;
}
iterator tmp = _finish - 1; //记得是减1,因为_finish是指向最后一个元素的后面一位
while (tmp >= pos)
{
*(tmp + 1) = *tmp;
tmp--;
}
*pos = x;
++_finish;
//解决pos失效的方法二:将每次插入后pos位置向后移动一个位置,保持原来的相对位置不变
//pos = pos + 1;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
assert(!empty());
iterator begin = pos;
while (begin < _finish - 1)
{
*begin = *(begin + 1);
begin++;
}
_finish--;
return pos;
}
~vector()
{
if(_start)
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start;
iterator _finish;
iterator _end_of_storage;
};
}
假设模拟实现的vector中的reserve接口中,使用memcpy进行的拷贝,以下代码会发生什么问题?答案是奔溃。
int main()
{
liren::vector<liren::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
return 0;
}
问题分析:
以下面的代码为例子,这里有两种情况:
1、在多次的尾插中,若发生扩容,则会导致浅拷贝,最后同一块空间被析构两次,导致奔溃
int main()
{
liren::vector<liren::string> v;
v.push_back("1111");
v.push_back("2222");
v.push_back("3333");
v.push_back("4444");
v.push_back("5555");
return 0;
}
2、还有一种奇怪的现象,就是在vs编译器下,对于string类型,vs多了个buf成员数组变量,用于存储比较短的字符串,一般为16个字节,当字符串长度大于buf长度时候,vs下的string才会去堆区开辟空间存放字符串。
若随着不断地插入,vector会扩容,这个时候新的数组的空间位置已经变了,但是由于第一个字符串长度大于buf长度,所以第一个字符串是存在堆区的,而因为空间位置的改变,_ptr 指向的位置被销毁了,但是由于是浅拷贝,新空间的 _ptr 也是该空间,由于被析构了,新的_ptr 就变成了野指针了,打印出来的可能是随机值。(vs2022做了优化,可能已经把这种给优化了)
//注:该情况只适用于vs下,因为每个编译器的设计方式不一样 (且vs2022做了优化,可能已经把这种给优化了)
int main()
{
liren::vector<liren::string> v;
v.push_back("111111111111111111111111111111111111111"); //插入的字符串长度大于buf的长度
v.push_back("2222");
v.push_back("3333");
v.push_back("4444");
v.push_back("5555");
for (size_t i = 0; i < v.size(); ++i)
cout << v[i] << endl;
cout << endl;
return 0;
}
总结: T 如果是内置类型(如int)或者浅拷贝自定义类型(如Date),他们增容或者拷贝构造时,用memcpy是没有问题的。 但是 T 如果是深拷贝的自定义类型(如string),他们增容或者拷贝构造时,不能用memcpy。
STL 中是用类型萃取来区分类型的,也就是对于内置类型使用 memcpy,而对于自定义类型使用 for + 赋值。 这体现了C++极致追求效率的特点,但是缺点就是太复杂。