大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
vector是C++在STL库中提供的一个模板类,是一个容器(container),通过指定类模板类型可以用来存储不同类型的数据,它有连续和动态的两个特点。
- 连续(contiguous):开辟一块连续的空间用于存储数据,类比数组。
- 动态(dynamic):根据存储需求,所开辟的空间可以动态变化
(本文暂且不讨论空间配置器allocator)
🔎特性:
[]
加下标来访问某个位置的元素,十分高效。与数组不同的是,它的容量会根据元素个数的增加而自动改变。(假设将上图的vector进行扩容)
2.1 vector的定义💭学习STL不同容器时,包括学习vector,查看官方的文档最为重要(点击查看:vector官方文档),追根溯源方能修行成道。vector在我们日常使用中十分场景,也十分重要,因此我们需要掌握vector的一些常用的接口。
构造函数(constructor)的声明 | 接口说明 |
---|---|
vector() | 无参构造 |
vector( size_type n, const value_type& val = value_type() ) | 构造并用n个val初始化(如果val没有传值,缺省调用val的默认构造函数,内置类型也有默认构造函数,如:int的默认构造将其初始化为0) |
vector(InputIterator first, InputIterator last) | 迭代器范围初始化构造 |
vector(const vector | 拷贝构造 |
💬测试代码
// 定义一个函数模板PrintVector,方便我们观察测试用例
templatevoid PrintVector(const vector& v)
{for (auto e : v)
{cout<< e<< " ";
}
cout<< endl;
}
void test1()
{// 1.
vectorv1; // 类模板,注意指定类型
PrintVector(v1);
// 2.
vectorv2(10, 2);
PrintVector(v2);
vectorvv2(10);
PrintVector(vv2);
// 3.
vectorv3(v2.begin(), v2.end()); // v2.begin()和v2.end()是v2的迭代器,下文会提到
PrintVector(v3);
string s("abcde");
vectorv4(s.begin(), s.end()); // 试试用指向不同类型元素的迭代器范围初始化
PrintVector(v4);
// 4.
vectorv5(v4);
PrintVector(v5);
}
⭕运行结果
接口 | 使用说明 |
---|---|
begin | 获取第一个元素位置的iterator |
end | 获取最后一个元素下一个位置的iterator |
rbegin | 获取最后一个元素位置的reverse_iterator |
rend | 获取第一个元素前一个位置reverse_iterator |
图片来源:cppreference.com
💦迭代器的各种操作与指针类似,解引用操作用操作符*
,自增自减用++
--
,但迭代器并不一定等于指针
💦迭代器的类型有四种,iterator相当于普通迭代器,而加上了const_表示iterator指向的元素不可修改,加上reverse_表示该迭代器是反向迭代器,++和–的方向与iterator相反。
begin接口有不带const和带const两个重载,当const类型的vector对象调用begin时,传入const类型的this指针,调用的就是带const的begin。其他几个iterator接口同理。
💬 测试
接口 | 接口说明 |
---|---|
size | 返回容器中的数据个数 |
capacity | 返回容器的容量 |
empty | 判断容器是否为空 |
resize( size_type n, const value_type& val = value_type() ) | 改变容器的数据个数 |
reserve( size_type n )(重点) | 改变容器的容量 |
🔎关于reserve和resize
If new_cap is greater than the current capacity(), new storage is allocated, otherwise the function does nothing.(引用自cppreference.com)
看如下数轴:
💬测试代码
// 为了方便观察每次resize后的size和capacity变化,定义一个PrintVectorSizeCap函数模板
templatevoid PrintVectorSizeCap(const vector& v)
{for (auto e : v)
{cout<< e<< " ";
}
printf("size:%d capacity:%d\n", v.size(), v.capacity());
}
void test3()
{vectorv1(10, 1);
v1.resize(4);
PrintVectorSizeCap(v1);
v1.resize(8);
PrintVectorSizeCap(v1);
v1.resize(16, 1);
PrintVectorSizeCap(v1);
}
⭕运行结果
📌注意:有关capacity扩容的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。
验证:
// 观察这段代码在vs和g++下的运行情况
void TestVectorExpand()
{size_t sz;
vectorv;
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
g++
接口 | 接口说明 |
---|---|
push_back | 尾插 |
pop_back | 尾删 |
insert | 在某位置插入 |
erase | 在某位置删除 |
find( iterator first, iterator last, value_type val ) | 查找(算法模块实现,并不是vector的成员函数) |
swap | 交换两个vector |
[ ] | 像数组一样通过下标随机访问容器数据 |
💭这些接口都比较简单,不再过多介绍,这里主要注意一些insert和erase
// 1个val
iterator insert( const_iterator pos, const T& val );
// n个val
iterator insert( const_iterator pos, size_type n, const T& val );
// range
template< class InputIt >iterator insert( const_iterator pos, InputIt first, InputIt last );
// 删除pos迭代器指向的元素
iterator erase( iterator pos );
// 删除区间[first, last)
iterator erase( iterator first, iterator last );
2.5.2 迭代器失效💡 迭代器设计的本意就是为了给所有容器提供一种通用的访问方式,让使用者无需关注底层的数据结构。迭代器本质上就是一个指针,或是将指针封装成一个类,按照需要控制它的行为。 例如:vector的迭代器就是一个原生指针value_type*,因为vector的空间是连续的,原生指针恰好能满足其访问需求。
💡 指针会有野指针问题,类似的,迭代器存在失效的问题。迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了,或使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)
造成迭代器失效的行为有以下几种:reserve、insert、erase、push_back等,下面具体分析这几种行为如何导致迭代器失效。
reserve导致的迭代器失效很好理解,因为reserve的扩容机制是重新开辟一块空间,所以指向原空间的迭代器就会失效。
假设容器vector有一个迭代器it
insert主要有两种情况。第一种是需要扩容的insert,第二种是不需要扩容的insert。
- 情况一:当insert插入数据需要扩容时,很显然迭代器肯定会失效,道理和reserve相同。
- 情况二:当insert插入数据不需要扩容时,插入后迭代器依然指向原空间,按理说应该不会失效。我们通过画图分析一下。
假设我们现在有下面这样一个容器,迭代器it指向它的begin位置,it1在it后两个位置
该容器目前capacity>size,进行insert操作不会扩容。若在it位置插入元素0,如下
插入后it、it1虽然指向的内容发生变化,但是依然指向的是有效空间,那么这到底算不算失效呢?我们来看看编译器怎么说
// 实现代码模拟上图过程,分别在vs和g++下编译
void test4()
{vectorv;
// 先开好足够的空间
v.reserve(9);
// 填入数据
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
// 定义迭代器it、it1
vector::iterator it = v.begin();
vector::iterator it1 = it + 2;
v.insert(it, 0);
// 试着访问一下迭代器指向内容
cout<< *it<< endl;
cout<< *it1<< endl;
}
vs下引发异常,在vector头文件中的*运算符重载函数出现断点,解引用访问失败,说明在vs下这种做法是不允许的,认为迭代器失效了。
同样的代码在g++下运行,检查并没有那么严格,运行成功,打印出it和it1指向的新元素0和2
所以insert第二种情况在不同编译器下会产生不同结果。
⭕结论
不同库版本的STL对迭代器失效问题的判别有所差异(vs是PJ版本,g++是SGI版本),因此,为了保证代码的可移植性,我们默认insert和erase函数在任何情况下都会导致迭代器失效(若有扩容则所有迭代器失效,若没有则插入、删除位置及之后的迭代器失效)。失效后就不能再对迭代器进行*、++、--
等操作了
而解决这一问题的方法STL已经帮我们提供了,insert和erase的返回值是插入和删除后的第一个位置的迭代器,因此每次插入或删除后,下次使用迭代器之前,接收函数返回值更新一下迭代器即可。
💭与vector类似,string在 插入+扩容+erase 之后,迭代器也会失效
void TestString()
{string s("hello");
auto it = s.begin();
//s.resize(20, '!');
// 上面这行代码放开后会崩溃,因为resize到20会string会进行扩容
// 扩容之后,it指向之前旧空间已经被释放了,该迭代器就失效了
// 后续打印时,再访问it指向的空间程序就会崩溃
while (it != s.end())
{cout<< *it;
++it;
}
cout<< endl;
it = s.begin();
while (it != s.end())
{it = s.erase(it);// right
//s.erase(it);
//++it;
// 按照屏蔽掉的这种方式写,运行时程序会崩溃
// 因为erase(it)之后,it位置的迭代器就失效了,后续再erase就会出错
}
}
🧿掌握了STL中vector的使用,我们可以尝试模拟实现一下vector。模拟失效不是为了造出更好的“轮子”,而是在摸清底层实现逻辑后,更好地使用vector,达到融会贯通的效果。
// 整体框架
templateclass vector
{public:
// definition
typedef T* iterator;
typedef const T* const_iterator;
typedef T* pointer;
typedef T value_type;
// Member functions
// ...
private:
// 与string不同的是,vector用了三个指针来控制空间
iterator start; // 指向目前使用空间的头
iterator finish; // 指向目前使用空间的尾
iterator end_of_storage; // 指向目前可用空间的尾
};
3.1 迭代器// Iterators:
iterator begin()
{ return start;
}
const_iterator begin() const
{ return start;
}
iterator end()
{ return finish;
}
const_iterator end() const
{ return finish;
}
3.2 构造函数// Constructors:
// 1.无参构造
vector()
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{}
// 2.n个val
vector(size_t n, const value_type& val = value_type())
// 缺省值用匿名对象,调用了类value_type的默认构造函数
{ // 开辟空间
start = new value_type[n];
// 导入数据
for (size_t i = 0;i< n;++i)
{ start[i] = val;
}
// 值处理
finish = start + n;
end_of_storage = finish;
}
// 3.copy
// 拷贝构造
vector(const vector& v)
{ // 开辟空间
size_t n = v.capacity();
start = new value_type[n];
// 传输数据
//memcpy(start, v.start, n * sizeof(value_type));//err
// 这种写法是错误的,这里涉及到一个深浅拷贝的问题
// 下面这种写法才是正确的
for (size_t i = 0;i< v.size();++i)
{ start[i] = v.start[i];
}
// 值处理
finish = start + v.size();
end_of_storage = start + n;
}
// 赋值重载
vector& operator=(const vector& v)
{ // 开辟空间
size_t n = v.capacity();
pointer newStart = new value_type[n];
// 传输数据
size_t len = v.size();
for (size_t i = 0;i< len;++i)
{ newStart[i] = v.start[i];
}
// 释放旧空间
delete[] start;
//值处理
start = newStart;
finish = newStart + len;
end_of_storage = newStart + n;
return *this;
}
🔎memcpy的拷贝异常问题传输数据为什么不能用memcpy?
📃先来看看memcpy函数的文档介绍
读完文档我们知道,memcpy是按内存的二进制格式拷贝的,也就是source指向的内存里面存着什么它就原封不动地拷贝到destination上。若是存储内置类型的vector,尚且能够完成传输数据的工作。如下图。
⭕但若容器中存放的是自定义类型, 且自定义类型的元素涉及内存空间管理,事情就没那么简单了。
例如,vector
类,vector中存放的类型是> vector
,就会出错,因为memcpy其实是浅拷贝。如下图。
vector
类的成员变量是三个指针,所以vector 类在内存空间里存放的是三个指针。那么,vector >类若用memcpy来传输数据,就会直接将每个vector 类元素的指针传过去,传输成功后,就会出现两个指针同时指向一块空间的情况。这样一来,不仅两个容器不能独立开来进行各种操作,而且会导致析构同一块空间两次,出现错误。
💡 为了解决这个问题,我们可以采用下面这个方法来传输数据,无论是容器装的是什么类型,如果是自定义类型,只要该类型有赋值重载,就不会出现错误。
// 传输数据
for (size_t i = 0;i< v.size();++i)
{start[i] = v.start[i];
}
3.3 析构函数// Destructor:
~vector()
{delete[] start;
start = finish = end_of_storage = nullptr;
}
💭其实上面实现的构造函数都过于冗余,我们称之为传统写法。我们可以借助vector的其它成员函数的复用来优化构造函数,也就是构造函数的现代写法。那废话不多说,先把vector的其它成员函数都是实现了,再来看怎么运用它们优化构造函数。
// Capacity:
size_t capacity() const
{ return end_of_storage - start;
}
size_t size() const
{ return finish - start;
}
bool empty() const
{ return finish == start;
}
// !!!很重要的一个!!!
void reserve(size_t n)
{ // 要注意新旧指针位置不匹配问题
if (n >capacity())
{ // 开辟新空间
pointer newStart = new value_type[n];
// 传输数据
size_t len = size();
//memcpy(newStart, start, len * sizeof(value_type));//err
// 这里同样不能用memcpy传输数据,就拿vector>举例
// 用memcpy传输后,释放旧空间后,容器内部的vector元素指向的空间就被释放掉了
// 而传到新空间上的指针自然也失效了
for (size_t i = 0;i< len;++i)
{newStart[i] = start[i];
}
// 释放旧空间
delete[] start;
// 值处理
start = newStart;
finish = newStart + len;
// 不能finish = newStart + size(),size()函数内部会出问题,
// finish还在旧空间,而start已经在新空间了
end_of_storage = newStart + n;
}
}
void resize(size_t n, const value_type& val = value_type())
{ if (n >size())
{ reserve(n); // reserve会自动判断需不需要扩容
while (finish< start + n)
{*(finish++) = val;
}
}
else
{ finish = start + n;
}
}
// Modifiers:
value_type& operator[](size_t pos)
{ assert(pos< size()); // 检查pos的合法性
return *(start + pos);
}
void push_back(const value_type& val)
{ // 当finish == end_of_storage为满额状态,需要扩容才能插入数据
if (finish == end_of_storage)
{ size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
// 当capacity为0时,给一个初始值为4
reserve(newCapacity);
}
// 尾插数据
*finish = val;
++finish;
}
void pop_back()
{ assert(!empty());
--finish;
}
void swap(vector& v)
{ std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(end_of_storage, v.end_of_storage);
}
iterator insert(iterator pos, const value_type& val)
{ assert(pos< finish && pos >= start);
// check capacity
if (finish == end_of_storage)
{ size_t lentoPos = pos - start;
size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newCapacity);
// 扩容会导致迭代器失效,要更新迭代器
pos = start + lentoPos;
}
// 挪动数据
iterator tmp = finish;
while (tmp >pos)
{ *tmp = *(tmp - 1);
--tmp;
}
// 值处理
*pos = val;
++finish;
return pos;
}
void insert(iterator pos, size_t n, const value_type& val)
{ size_t lentoPos = pos - start;
// check capacity
if (finish + n >end_of_storage)
{ reserve(capacity() + n);
pos = start + lentoPos;
}
// 挪动数据
iterator it = finish - 1;
while (it >= pos)
{ *(it + n) = *it;
--it;
}
// 导入数据
iterator end = pos + n;
while (pos< end)
{ *(pos++) = val;
}
// 值处理
finish += n;
}
iterator erase(iterator pos)
{ assert(pos< size());
// 挪动数据,直接覆盖预删除数据
iterator tmp = pos;
while (tmp< finish - 1)
{ *tmp = *(tmp + 1);
++tmp;
}
--finish;
return pos;
}
iterator erase(iterator first, iterator last)
{ iterator tmp = first;
while (last< finish)
{ *(first++) = *(last++);
}
finish = first;
return tmp;
}
🔎 A little problem:
为什么库里面已经有一个swap函数了,vector不选择直接用,而是设计一个属于自己的swap呢?
查阅文档了解到库里面swap的实现是这样的。
💡若T是vector类,这里还要调用一次拷贝构造+两次赋值重载,效率比较低。而vector自己实现的swap则是直接交换两个vector的指针,即交换两个vector指向的空间,效率很高。
// 1.n个val
vector(size_t n, const value_type& val = value_type())
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ reserve(n);
while (n--)
{ push_back(val); // 在push_back函数中发生变化
}
}
// 复用了reserve和push_back函数,
// finish和end_of_storage两个指针都在成员函数中处理了
// 代码简洁了很多。
// 为了实现拷贝构造的现代写法,先实现一个迭代器范围构造函数
templatevector(InputIterator first, InputIterator last)
:start(nullptr)
,finish(nullptr)
,end_of_storage(nullptr)
{ while (first != last)
{ push_back(*first);
// *first传入push_back会有一个隐式类型转换
// *first的类型会转换成value_type
++first;
}
}
🔎range构造和fill构造的冲突问题问题:
⭕要特别注意一个问题。我们将迭代器范围构造函数称为range构造
,n个val构造函数称为fill构造
。这两个构造函数会发生意想不到的冲突,看下面代码。
void test6()
{vectorv(10, 'a');
for (auto e : v)
{cout<< e<< " ";
}
cout<< endl;
}
用10个字符'a'
去构造一个vector'a'
存入时会发生一个小小的类型转换之外,没有任何问题。
⭕运行结果
再看这个代码
void test6()
{vectorv(10, 1);
for (auto e : v)
{cout<< e<< " ";
}
cout<< endl;
}
程序运行出错,并且报了非法的间接寻址这个错误。
原因:
观察fill构造
和range构造
的参数列表。
// fill
vector (size_type n, const value_type& val = value_type())
// range
templatevector (InputIterator first, InputIterator last)
vectorv(10,'a')
第一个参数
10
的类型是int,第二个参数'a'
的类型是char,构造函数中有两个参数的只有range构造和fill构造。range构造是函数模板,要求两个参数必须是同类型。显然,这里只能调用fill构造,传参时会发生隐式类型转换,int->size_t,char->value_type。
vectorv(10,1)
第一个参数
10
的类型是int,第二个参数1
的类型也是int,两个参数类型一样,而传入fill构造又要隐式类型转换,编译器会偷懒,调用它觉得最省事的那个构造函数,那就是range构造了。传入range构造函数模板后,本来InputIterator希望得到迭代器类型,这下传入了int类型,range构造函数内部解引用first时就会引发非法的间接寻址的错误。
解决方法:
// 效仿PJ库版STL的做法,重载两个fill构造函数即可,n的类型一个为size_t一个为int
vector(int n, const value_type& val = value_type())
// 两个参数类型都为int时,调用该构造函数
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ reserve(n);
while (n--)
{ push_back(val);
}
}
vector(size_t n, const value_type& val = value_type())
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ reserve(n);
while (n--)
{ push_back(val);
}
}
⭕ 运行通过
🧐OK,解决了这个棘手的问题,继续我们的构造函数现代写法。
// copy
// 构造函数
vector(const vector& v)
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ vectortmp(v.begin(), v.end());
swap(tmp);
}
💡 构造函数的现代写法复用了range构造函数,相当于让“打工人”tmp先帮我们把v的数据和空间拷贝过来,然后再把tmp和*this一交换,*this就成功拷贝了v,而出了作用域tmp也就被销毁了,就没他什么事了(纯纯地压榨)。这样一来,代码十分简洁,复用性也很强。
有了如此简洁的拷贝构造,作为它的孪生兄弟赋值重载,不也得进化一下?
// 赋值重载的现代写法
vector& operator=(vectorv)
{ swap(v);
return *this;
}
看起来是不是十分简洁?这里其实不仅复用了swap,还复用了拷贝构造。注意到这里的参数并不是引用,所以v是调用拷贝构造实例化出来的,与外部传入的类对象相等却无关。所以我们都不需要自己创造一个“打工人”,直接有了一个现成的“打工人”!!直接让*this和v交换一下就实现了。
// 1. fill
vector(int n, const value_type& val = value_type())
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ reserve(n);
while (n--)
{ push_back(val);
}
}
vector(size_t n, const value_type& val = value_type())
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ reserve(n);
while (n--)
{ push_back(val);
}
}
// 2.range
templatevector(InputIterator first, InputIterator last)
:start(nullptr)
,finish(nullptr)
,end_of_storage(nullptr)
{ while (first != last)
{ push_back(*first);
++first;
}
}
// 3.拷贝构造
vector(const vector& v)
:start(nullptr),
finish(nullptr),
end_of_storage(nullptr)
{ vectortmp(v.begin(), v.end());
swap(tmp);
}
// 4."="
vector& operator=(vectorv)
{ swap(v);
return *this;
}
ending:
如果本文对你有帮助的话,不妨点赞关注收藏支持一下博主呀🍻
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧