vector的使用及其模拟实现
文章目录
- vector的使用及其模拟实现
- 1. vector的使用
-
- 1.1 构造函数construct
- 1.2 获取当前存储的数据个数size()和最大容量capacity()
- 1.3 访问
-
- 1.3.1 operator[]运算符重载
- 1.3.2 迭代器访问
- 1.3.3 范围for
- 1.4 容量相关reserve()和resize()
- 1.5 增（插入数据）
-
- 1.5.1 push_back() 尾插
- 1.5.2 insert() 随机插入
- 1.6 删（删除数据）
-
- 1.6.1 pop_back() 尾删
- 1.6.2 erase() 随机删除
- 2. 模拟实现
-
- 2.1 vector的内部结构
- 2.2 部分细节的说明
-
- 2.2.1 C++对内置类型的”升级“
- 2.2.2 迭代器失效
- 2.2.3 memcpy的浅拷贝问题
- 2.3 模拟实现代码：
本章思维导图：
注：本章思维导图对应的
资源，可免费下载查阅。
1. vector的使用
template < class T, class Alloc = allocator<T> > class vector; // generic template
vector 也是STL中的一大容器- 可以将
vector 视为C语言的顺序表 - 他是一个类模板，因此在使用之前需要先用一个具体的类型对其进行实例化。例如
vector<int> 、vector<string>
1.1 构造函数construct
以下三种构造方式较为常用：
//用n个value构造
explicit vector (size_type n, const value_type& val = value_type(),
const allocator_type& alloc = allocator_type());
//用一段迭代器区间构造
template <class InputIterator>
vector (InputIterator first, InputIterator last,
const allocator_type& alloc = allocator_type());
//用另一个vector拷贝构造
vector (const vector& x);
注：
迭代器是一个用来访问容器数据的对象，其提供了统一的方式来遍历容器中的数据
- 对于
vector 类，我们可以将迭代器看成一个指针，其指向vector 对象存储的某个数据- 我们可以通过迭代器来访问或者修改容器中的数据
使用示例：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int a[] = { 1,2,3,4,5 };
vector<int> v1(a, a + 5); //可以认为只想一段连续空间的指针也是一个迭代器
vector<string> v2(3, "111"); //三个字符串"111"构造
vector<int> v3(v1); //v1拷贝构造v3
cout << "v1: ";
for (auto& e : v1)
cout << e << " ";
cout << endl;
cout << "v2: ";
for (auto& e : v2)
cout << e << " ";
cout << endl;
cout << "v3: ";
for (auto& e : v3)
cout << e << " ";
cout << endl;
return 0;
}
output:
v1: 1 2 3 4 5 v2: 111 111 111 v3: 1 2 3 4 5
1.2 获取当前存储的数据个数size()和最大容量capacity()
size_type size() const; //获取存储的数据个数 size_type capacity() const; //获取最大容量
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v(5, 1);
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << endl;
return 0;
}
output:
size: 5 capacity: 5
1.3 访问
1.3.1 operator[]运算符重载
reference operator[] (size_type n); //返回数据的引用 const_reference operator[] (size_type n) const;
- 有了
[] 这个运算符的重载，我们就可以像利用下标访问数组那样来访问vector 容器的数据了 - 同时对于
非const 对象，我们还可以在访问的同时对其进行修改
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({1,2,3});
for (int i = 0; i < v.size(); i++)
cout << ++v[i] << " ";
cout << endl;
return 0;
}
output:
2 3 4
1.3.2 迭代器访问
- 由于
vector 存储的是一段连续的地址空间，因此我们可以将他的迭代器看作是一个指针 - 同其他容器一样，
vector 也有正向迭代器和反向迭代器
正向迭代器：
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
begin() 返回的迭代器指向vector 存储的第一个元素，end() 返回的迭代器返回指向vector 存储的最后一个元素的后一个位置- 所以，
begin(), end() 包含的空间实际上是一个左闭右开的区间
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({ 1,2,3 });
vector<int>::iterator it = v.begin();
while (it != v.end())
{
(*it)++;
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
反向迭代器：
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
rbegin() 返回的迭代器指向vector 存储的最后一个元素，rend() 返回的迭代器指向vector 存储的第一个元素的前一个位置rbegin(), rend() 同样也是一个左闭右开区间
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({ 1,2,3 });
vector<int>::reverse_iterator it = v.rbegin();
while (it != v.rend())
{
cout << *it << " ";
it++;
}
cout << endl;
return 0;
}
output:
3 2 1
1.3.3 范围for
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({ 1,2,3 });
for (auto& e : v)
cout << e << " ";
cout << endl;
return 0;
}
output:
1 2 3
1.4 容量相关reserve()和resize()
void reserve (size_type n); void resize (size_type n, value_type val = value_type());
这里需要注意区分这两者的区别（VS 2019下）：
reserve：
- 如果
n < capacity ，那么该函数将不会做任何处理- 如果
n > capacity ，reserve() 只会为该容器重新开辟一块大小为n 的空间，并将原来的capacity置为n，但并不会实际的创建对象（插入数据），即既不会改变原来的数据也不会加入新的数据。
resize：
- 如果
n < size ，那么该函数就会只保留容器的前n 个数据，但并不会影响capacity - 如果
n > size && n <= capacity ，那么该函数就会将后面n - size 个空间初始化为val - 如果
n > capacity ，那么该函数首先会将capacity置为n ，再进行初始化
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v(5, 1);
for (auto& e : v)
cout << e << " ";
cout << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << "
";
v.reserve(1);
cout << "after reserve(1)" << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << "
";
v.reserve(9);
cout << "after reserve(9)" << endl;
for (auto& e : v)
cout << e << " ";
cout << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << "
";
v.resize(1);
cout << "after resize(1)" << endl;
for (auto& e : v)
cout << e << " ";
cout << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << "
";
v.resize(11, 8);
cout << "after resize(1)" << endl;
for (auto& e : v)
cout << e << " ";
cout << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << "
";
return 0;
}
output:
1 1 1 1 1 size: 5 capacity: 5 after reserve(1) size: 5 capacity: 5 after reserve(9) 1 1 1 1 1 size: 5 capacity: 9 after resize(1) 1 size: 1 capacity: 9 after resize(1) 1 8 8 8 8 8 8 8 8 8 8 size: 11 capacity: 13
1.5 增（插入数据）
1.5.1 push_back() 尾插
void push_back (const value_type& val);
vector的尾插就和顺序表的尾插一样，就是在最后面新增一个数据
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
for (auto& e : v)
cout << e << " ";
cout << endl;
return 0;
}
output:
1 2 3
1.5.2 insert() 随机插入
iterator insert (iterator position, const value_type& val);
- 这里需要注意，和顺序表不同的是，
position 表示插入的位置，但是这里不是一个整数，而是一个迭代器。
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v(5, 1);
v.insert(v.begin() + 1, 22);
for (auto& e : v)
cout << e << " ";
cout << endl;
return 0;
}
output:
1 22 1 1 1 1
1.6 删（删除数据）
1.6.1 pop_back() 尾删
void pop_back();
- 该函数功能十分简单，就是删除
vector 的最后一个数据
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({ 1,2,3 });
v.pop_back();
for (auto& e : v)
cout << e << " ";
cout << endl;
return 0;
}
output:
1 2
1.6.2 erase() 随机删除
iterator erase (iterator position);
- 和
insert 一样，position 表示要删除的元素的位置，同样是一个迭代器
例如：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({ 1,2,3 });
v.erase(v.begin() + 1);
for (auto& e : v)
cout << e << " ";
cout << endl;
return 0;
}
output:
1 3
2. 模拟实现
2.1 vector的内部结构
- 和C语言的顺序表不同，
vector 的内部并不是由一个指针start 再加上两个整数size 和capacity 来实现的 - 实际上，
vector 是靠三个迭代器来实现对数据的维护的：
template<class T>
class vector
{
private:
iterator _start = nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾
}
2.2 部分细节的说明
2.2.1 C++对内置类型的”升级“
在模拟实现中，在写插入函数的形参时，一般会这样写：
void push_back(const T& x = T())
我们知道，
vector、string 这种自定义类型好说，他们有构造函数，但如果T 是int 这种内置类型呢，难道它们也有自己的构造函数吗？
答案确实如此，为了适应类和对象，我们可以认为C++对内置了类型进行了”升级“，使它们也有自己的构造函数。
例如：
#include <iostream>
using namespace std;
int main()
{
int a = int();
double b = double();
cout << a << endl;
cout << b << endl;
return 0;
}
output:
0 0
2.2.2 迭代器失效
首先，让我们先来看看
void reserve(size_t n)
{
if (n > capacity())
{
int length = size();
T* tmp = new T[n];
for (int i = 0; i < length; i++)
{
tmp[i] = *(_start + i);
}
delete[] _start;
_start = tmp;
_finish = _start + length;
_endOfStorage = _start + n;
}
}
可以看到，这段代码的逻辑是：先
接着，我们再来看看
iterator insert(iterator pos, const T& x = T())
{
assert(pos <= end());
assert(pos >= begin());
//如果满了，就进行扩容
if (_finish == _endOfStorage)
{
size_t len = pos - begin();
reserve(capacity() == 0 ? 1 : 2 * capacity());
pos = begin() + len;
}
//将pos及其之后的元素向后移动一个
auto end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
//插入
*pos = x;
_finish++;
return pos;
}
可能有小伙伴对扩容部分的代码不是很理解：
扩容就扩容，为什么还要改变
pos 呢？
这里就涉及到迭代器失效的问题了：
因此，需要先记录
如果你认为这样就万无一失，那就大错特错了，我们可以来看一看下面的代码，看看结果如何：
#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> v({ 1,2,3,4 });
vector<int>::iterator it = v.begin();
cout << v.capacity() << "
";
v.insert(it, 100);
cout << v.capacity() << "
";
cout << *it << "
";
return 0;
}
我们来进行调试：
可以发现，竟然还是有错误。并且，这也是一个迭代器失效的问题，也就说
其实原因和上面所说的
事实上，函数
凡是
insert() 或者erase() 过的迭代器都不要使用
2.2.3 memcpy的浅拷贝问题
继续回到函数
void reserve(size_t n)
{
if (n > capacity())
{
int length = size();
T* tmp = new T[n];
for (int i = 0; i < length; i++)
{
tmp[i] = *(_start + i);
}
delete[] _start;
_start = tmp;
_finish = _start + length;
_endOfStorage = _start + n;
}
}
有同学会问：
for (int i = 0; i < length; i++) tmp[i] = *(_start + i); 这段代码我可以用库函数memcpy() 来替换吗
答案是不行。
假设替换为
void reserve(size_t n)
{
if (n > capacity())
{
int length = size();
T* tmp = new T[n];
memcpy(tmp, _start, sizeof(T) * length);
delete[] _start;
_start = tmp;
_finish = _start + length;
_endOfStorage = _start + n;
}
}
void push_back(const T& x = T())
{
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 1 : 2 * capacity());
}
*_finish = x;
_finish++;
}
int main()
{
vector<string> v2;
v2.push_back("111");
v2.push_back("111");
v2.push_back("111");
v2.push_back("111");
v2.push_back("111");
for (auto& e : v2)
cout << e << " ";
cout << endl;
return 0;
}
我们来进行调试：
竟然在插入的时候就出问题了，这是为啥？
让我们来进行分析：
- 众所周知，一个
string 对象可以由三部分构成：指向存储的字符序列的指针str、size、capacity memcpy() 拷贝的方式，是将每个字节的内容从源拷贝到目的地，是一种浅拷贝方式- 对于两个整数
size和capacity 自然没有大碍。但是对于一个指向了具体内容的指针，发生浅拷贝就意味着两个指针会指向相同的区域- 而扩容后原来的空间及其数据就会销毁，这就会使新的
str 成为野指针。之后当进行delete[] 操作时就会触发释放野指针这一操作，从而报错。
2.3 模拟实现代码：
如有错误，欢迎指正
#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
namespace TEST
{
template<class T>
class vector
{
public:
// Vector的迭代器是一个原生指针
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;
}
// construct and destroy
vector(){}
vector(int n, const T& value = T())
{
resize(n, value);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
vector<T>& operator= (vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
delete[] _start;
}
// capacity
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _endOfStorage - _start;
}
void reserve(size_t n)
{
if (n > capacity())
{
int length = size();
T* tmp = new T[n];
for (int i = 0; i < length; i++)
{
tmp[i] = *(_start + i);
}
delete[] _start;
_start = tmp;
_finish = _start + length;
_endOfStorage = _start + n;
}
}
void resize(size_t n, const T& value = T())
{
if (n <= size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = value;
_finish++;
}
}
}
///access///
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos)const
{
assert(pos < size());
return _start[pos];
}
///modify/
void push_back(const T& x = T())
{
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 1 : 2 * capacity());
}
*_finish = x;
_finish++;
}
void pop_back()
{
assert(_start != _finish);
_finish--;
}
void swap(vector<T>& v)
{
std::swap(v._start, _start);
std::swap(v._finish, _finish);
std::swap(v._endOfStorage, _endOfStorage);
}
iterator insert(iterator pos, const T& x = T())
{
assert(pos <= end());
assert(pos >= begin());
size_t len = pos - begin();
if (_finish == _endOfStorage)
{
reserve(capacity() == 0 ? 1 : 2 * capacity());
pos = begin() + len;
}
auto end = _finish;
while (end > pos)
{
*end = *(end - 1);
end--;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos < end());
assert(pos >= begin());
auto end = pos + 1;
while (end != _finish)
{
*(end - 1) = *end;
end++;
}
_finish--;
return pos;
}
private:
iterator _start = nullptr; // 指向数据块的开始
iterator _finish = nullptr; // 指向有效数据的尾
iterator _endOfStorage = nullptr; // 指向存储容量的尾
};
}