前言 本篇博客继续介绍STL库里一个结构——vector,它是个顺序储存的容器,不仅可以包含字符串,还可以有其他类型,让我们一起来详细看一下它 💓 个人主页:小张同学zkf ⏩ 文章专栏:C++ 若有问题 评论区见📝 🎉欢迎大家点赞👍收藏⭐文章
vector介绍:vector
vector的定义
capacity 的代码在 vs 和 g++ 下分别运行会发现, vs 下 capacity 是按 1.5 倍增长的, g++ 是按 2 倍增长的 。这个问题经常会考察,不要固化的认为, vector 增容都是 2 倍,具体增长多少是 根据具体的需求定义的。 vs 是 PJ 版本 STL , g++ 是 SGI 版本 STL 。 reserve 只负责开辟空间,如果确定知道需要用多少空间, reserve 可以缓解 vector 增容的代 价缺陷问题。 resize 在开空间的同时还会进行初始化,影响 size。
迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对
指针进行了封装 ,比如: vector 的迭代器就是原生态指针 T* 。因此 迭代器失效,实际就是迭代器
底层对应指针所指向的空间被销毁了,而使用一块已经被释放的空间 ,造成的后果是程序崩溃 ( 即
如果继续使用已经失效的迭代器,程序可能会崩溃 ) 。
对于 vector 可能会导致其迭代器失效的操作有:
1. 会引起其底层空间改变的操作,都有可能是迭代器失效 ,比如: resize 、 reserve 、 insert 、
assign 、 push_back 等。
#include <iostream> using namespace std ; #include <vector> int main () { vector < int > v { 1 , 2 , 3 , 4 , 5 , 6 }; auto it = v . begin (); // 将有效元素个数增加到 100 个,多出的位置使用 8 填充,操作期间底层会扩容 // v.resize(100, 8); // reserve 的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容 量改变 // v.reserve(100); // 插入元素期间,可能会引起扩容,而导致原空间被释放 // v.insert(v.begin(), 0); // v.push_back(8); // 给 vector 重新赋值,可能会引起底层容量改变 v . assign ( 100 , 8 ); /* 出错原因:以上操作,都有可能会导致 vector 扩容,也就是说 vector 底层原理旧空间被释 放掉,而在打印时, it 还使用的是释放之间的旧空间,在对 it 迭代器操作时,实际操作的是一块 已经被释放的空间,而引起代码运行时崩溃。 解决方式:在以上操作完成之后,如果想要继续通过迭代器操作 vector 中的元素,只需给 it 重新赋值即可。 */ while ( it != v . end ()) { cout << * it << " " ; ++ it ; } cout << endl ; return 0 ; }
2. 指定位置元素的删除操作--erase
#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 ; // 此处会导致非法访问 return 0 ; }
erase 删除 pos 位置元素后, pos 位置之后的元素会往前搬移,没有导致底层空间的改变,理
论上讲迭代器不应该会失效,但是:如果 pos 刚好是最后一个元素,删完之后 pos 刚好是 end
的位置,而 end 位置是没有元素的,那么 pos 就失效了。因此删除 vector 中任意位置上元素
时, vs 就认为该位置迭代器失效了。
迭代器失效解决办法:在使用前,对迭代器重新赋值即可。
#include <assert.h>
#include <iostream>
using namespace std;
namespace zkf
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
{
}
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
bool empty()
{
return _start == _finish;
}
void reserve(const size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
for (size_t i = 0; i < size(); i++)
{
tmp[i] = _start[i];
}
delete[]_start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
void push_back(const T& x)
{
// 扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;
}
void pop_back()
{
assert(!empty());
--_finish;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i) const
{
assert(i < size());
return _start[i];
}
vector(const vector<T>& s)
{
reserve(s.size());
for (auto& e : s)
{
push_back(e);
}
}
vector(size_t n, const T& m = T())
{
for (size_t i = 0; i < n; i++)
{
push_back(m);
}
}
vector(int n, const T& m = T())
{
for (int i = 0; i < n; i++)
{
push_back(m);
}
}
template <class inputinerator>
vector(inputinerator s1, inputinerator s2)
{
while (s1 != s2)
{
push_back(*s1);
s1++;
}
}
void swap(vector<T>& s)
{
std::swap(_start, s._start);
std::swap(_finish, s._finish);
std::swap(_end_of_storage, s._end_of_storage);
}
vector<T>& operator=(vector<T> s)
{
swap(s);
return *this;
}
void clear()
{
_finish = _start;
}
iterator insert(iterator pos,const T& s)
{
assert(_start <= pos);
assert(_finish>pos);
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
iterator it = _finish -1;
while (it >= pos)
{
*(it+1) = *it;
it--;
}
*pos = s;
++_finish;
return pos;
}
void erase(iterator pos)
{
assert(_start <= pos);
assert(_finish > pos);
iterator it = pos+1;
while (it != end())
{
*(it-1) = *it;
it++;
}
_finish--;
}
void resize(size_t n, T s = T())
{
reserve(n);
if (n < size())
{
_finish = _start + n;
}
else
{
while (_finish != _start + n)
{
*_finish = s;
_finish++;
}
}
}
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
template<class T>
void print_vector(const vector<T>& s)
{
auto as = s.begin();
while (as != s.end())
{
cout << *as <<" ";
as++;
}
cout << endl;
}
}
假设模拟实现的 vector 中的 reserve 接口中,使用 memcpy 进行的拷贝,以下代码会发生什么问
题?
int main () { bite::vector < bite::string > v ; v . push_back ( "1111" ); v . push_back ( "2222" ); v . push_back ( "3333" ); return 0 ; }
问题分析:
1. memcpy 是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存
空间中
2. 如果拷贝的是内置类型的元素, memcpy 既高效又不会出错,但如果拷贝的是自定义类型
元素,并且自定义类型元素中涉及到资源管理时,就会出错,因为 memcpy 的拷贝实际是浅
拷贝。
结论:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为
memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。
结束语 vector系列介绍完了,下一部分我们就STL里的list介绍一下 OK,感谢观看!!!