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 模拟实现代码：
本章思维导图：
注：本章思维导图对应的
.png文件已同步导入至
资源，可免费下载查阅。
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
范围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() << "\n\n";
v.reserve(1);
cout << "after reserve(1)" << endl;
cout << "size: " << v.size() << endl;
cout << "capacity: " << v.capacity() << "\n\n";
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() << "\n\n";
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() << "\n\n";
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() << "\n\n";
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())
我们知道，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 迭代器失效
首先，让我们先来看看reserve()的模拟实现：
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;
}
}
可以看到，这段代码的逻辑是：先new一块大小为n的空间，再将原来的数据复制过来，最后再释放原来的空间。如图：
接着，我们再来看看insert()的模拟实现：
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呢？
这里就涉及到迭代器失效的问题了：
pos是一个迭代器，其指向原始数据的某一个位置。但是如果要进行扩容操作，由上面的分析可以知道，如果要进行扩容，那么原始数据就会被释放，这就会导致pos这个迭代器就会变成一个野指针。
因此，需要先记录pos和_start的相对位置，扩容之后再对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() << "\n";
v.insert(it, 100);
cout << v.capacity() << "\n";
cout << *it << "\n";
return 0;
}
我们来进行调试：
可以发现，竟然还是有错误。并且，这也是一个迭代器失效的问题，也就说it这个迭代器失效了。为什么？
其实原因和上面所说的pos类似，因为扩容之后原来的空间和数据都被释放了，指向原来数据的迭代器it也就成为了野指针。
事实上，函数erase()也可能存在和insert()类似的迭代器失效的问题。因此，为了避免迭代器失效带来的影响，我们得遵循以下原则
凡是
insert()或者erase()过的迭代器都不要使用
2.2.3 memcpy的浅拷贝问题
继续回到函数reserve()的实现：
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()来替换吗
答案是不行。
假设替换为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、capacitymemcpy()拷贝的方式，是将每个字节的内容从源拷贝到目的地，是一种浅拷贝方式- 对于两个整数
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; // 指向存储容量的尾
};
}
