本篇文章主要讲解 vector模拟实现的相关内容
1. STL中vector的模式
在STL中
vector
是靠三个迭代器来维护的:
- start
- finish
- end_of_storage
如下图所示,其中
size
是现在有多少元素,而capacity
是现在的空间有多少:
因此很容易看出:
size = finsih - start;
capacity = end_of_storage - start;
所以可以写出vector
类中的成员变量:
namespace d1
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator start = nullptr;
iterator finish = nullptr;
iterator end_of_storage = nullptr;
};
}
2. 插入相关操作的模拟
2.1 push_back()
push_back
就是尾插操作,既然插入肯定要用到扩容,代码如下:
size_t size() const
{
return finish - start;
}
size_t capacity() const
{
return end_of_storage - start;
}
void push_back(const T& val)
{
if (end_of_storage == finish)
{
// 注意这里要记录以下原始size的大小,要不然找不到新的finish和end_of_storage的位置
size_t old_size = size();
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
T* tmp = new T[newcapacity];
memcpy(tmp, start, old_size * sizeof(T));
delete[] start;
start = tmp;
finish = start + old_size;
end_of_storage = start + newcapacity;
}
*finish = val;
++finish;
}
这里尝试插入5个数据测试一下:
2.2 reserve()
reserve
相当于就是扩容操作,刚才的尾插已经涉及到,把他放到reserve中即可:
void reserve(size_t newcapacity)
{
if (newcapacity > capacity())
{
size_t old_size = size();
T* tmp = new T[newcapacity];
memcpy(tmp, start, old_size * sizeof(T));
delete[] start;
start = tmp;
finish = start + old_size;
end_of_storage = start + newcapacity;
}
}
2.3 operator[]的重载 和 迭代器
为了更好的访问vector
和测试,我们可以先实现operator[]
的重载 和 iterator
。
- operator[]的重载
T operator[](size_t pos)
{
assert(pos >= 0 && pos < size());
return start[pos];
}
- iterator 和 const_iterator
iterator begin()
{
return start;
}
iterator end()
{
return finish;
}
const_iterator begin() const
{
return start;
}
const_iterator end() const
{
return finish;
}
test
代码:
void vector_test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
- 我们可以按照模板函数的方法将打印写成函数:
- 这里有一点需要特别注意,注意仔细看注释。
template<class T>
void print_vector(const vector<T>& v)
{
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
// 注意这里:
// 编译器会无法分清你写的vector<T>::const_iterator是一个静态成员变量还是一个类型
// 因为此时并没有被实例化,编译器也不会在此时实例化
// 为了告诉编译器这里是一个类型,要在前面加上typename
// 一般嵌套模板都要加上typename
// vector<T>::const_iterator it = v.begin();
typename vector<T>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
2.4 insert()
insert
允许你在任意位置插入元素,传入的是迭代器类型,这里需要注意是否需要扩容,如果需要扩容,就要更新pos的位置,模拟实现代码如下:
void insert(iterator pos, const T& val)
{
assert(pos >= begin() && pos <= finish);
if (finish == end_of_storage)
{
size_t old_pos = pos - start;
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
reserve(newcapacity);
pos = start + old_pos;
}
iterator end = finish - 1;
while (end >= pos)
{
*(end + 1)= *end;
--end;
}
*pos = val;
++finish;
}
测试代码:
void vector_test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.insert(v.begin(), 0);
v.insert(v.end(), 6);
v.insert(v.begin() + 1, 10);
print_vector(v);
}
2.5 resize()
resize 有三种情况:
- 小于size:删除数据
- 大于size,小于capacity:插入数据
- 大于capacity:扩容+插入数据
void resize(size_t n, const T& val = T())
{
if (n >= size())
{
reserve(n);
for (size_t i = size(); i < n; ++i)
{
start[i] = val;
++finish;
}
}
else
{
finish = start + n;
}
}
测试代码:
void vector_test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.insert(v.begin(), 0);
v.insert(v.end(), 6);
v.insert(v.begin() + 1, 10);
v.insert(v.begin() + 1, 10);
v.insert(v.begin() + 1, 10);
v.insert(v.begin() + 1, 10);
v.resize(20);
print_vector(v);
}
3. 删除相关操作的模拟
3.1 判空
当start==finish
时,为空:
bool Empty()
{
return start == finish;
}
3.2 pop_back()
尾删,直接 --finish
即可。
void pop_back()
{
assert(!Empty());
--finish;
}
3.3 erase()
在任意位置删除,将后面的元素往前挪动即可,最后再--finish
。
void erase(iterator pos)
{
assert(!(Empty()));
assert(pos >= start && pos < finish);
iterator begin = pos + 1;
while (begin < finish)
{
*(begin - 1) = *begin;
++begin;
}
--finish;
}
4. 构造函数相关操作模拟
4.1 拷贝构造的现代写法
正常拷贝构造的写法:
vector(const vector<T>& v)
{
T* tmp = new T[v.capacity()];
memcpy(tmp, v.start, sizeof(T) * v.size());
start = tmp;
finish = start + v.size();
end_of_storage = start + v.capacity();
}
现代写法:
- 先开辟一块大小相同的空间;
- 尾插到此块空间即可。
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
4.2 赋值重载现代写法
- 传值传参,调用拷贝构造,深拷贝一块空间;
- 进行交换。
void swap(vector<T>& v)
{
std::swap(start, v.start);
std::swap(finish, v.finish);
std::swap(end_of_storage, v.end_of_storage);
}
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
4.3 迭代器区间构造
类模板的成员函数可以是函数模板。
迭代器区间构造就是支持用一段**其他类型的迭代器区间**
来进行初始化vector。
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
测试代码:
void vector_test4()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
print_vector(v1);
vector<int> v2(v1.begin() + 1, v1.end() - 1);
print_vector(v2);
string str("abcd");
vector<int> v3(str.begin(), str.end());
print_vector(v3);
}
4.4 代参的构造函数
我这里实现的是用n
个数来构造vector
。
- 首先申请一块空间;
- 然后对这n个数依次尾插即可。
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
但是当运行以下的代码时,会报错:
void vector_test5()
{
vector<int> v1(10,1);
print_vector(v1);
}
他报错的位置并不是我们上面写的代码,而是跑到了迭代器区间构造那里,因为编译器认为迭代器区间构造更匹配,因为编译器认为这里的
10
为int
类型,不是size_t
类型,假如我们给10
加上u
(无符号整数),或者构造成char
类型,就不会报错:
void vector_test5()
{
vector<int> v1(10u,1);
print_vector(v1);
vector<char> v2(10, 'a');
print_vector(v2);
}
为了解决这个问题,其实直接加个重载函数即可:
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
push_back(val);
}
}
这样编译器在调用函数的时候会先调用int
参数的这个重载函数,因为这个最匹配。
5. initializer_list
在C
语言中我们构造数组通常是这样的:
int a[] = { 0 };
但是在C++
中,倘若我们右大括号来定义一个变量,那么它的类型将不是数组,而是initializer_list
,我们可以测试一下:
void vector_test6()
{
auto x = { 1,2,3,4,5 };
cout << typeid(x).name() << endl;
}
那么initializer_list
究竟是什么呢?
initializer_list
是C++中的一种容器,用于初始化同一类型的元素列表。它是C++11
引入的一个特性,旨在简化初始化容器的过程。
- 我们知道单参数类型的构造函数支持隐式类型转换,例如:
void vector_test6()
{
// 构造 + 拷贝构造 -> 优化 直接构造
string str1 = "11111";
// 这里加引用引用的是"2222"临时拷贝出来的空间,临时变量具有常性,因此要加const
const string& str2 = "22222";
vector<string> v;
v.push_back(str1);
v.push_back(str2);
// 甚至可以用匿名对象进行隐式类型转换
v.push_back(string("hello"));
// 也能这样
v.push_back("world");
print_vector(v);
}
- 了解了以上内容,那我们就可以用这个来初始化我们的
vector
,因为initializer_list
会隐式类型转换成vector<int>
类型:
void vector_test6()
{
/*auto x = { 1,2,3,4,5 };
cout << typeid(x).name() << endl;*/
std::vector<int> v = { 1,2,3,4,5,6 };
}
- 也可以直接构造:
vector<int> v2({ 10,20,30,40 });
6. 有关memcpy的问题
我们尝试运行以下这段代码:
void vector_test7()
{
vector<string> v;
v.push_back("11111");
v.push_back("22222");
v.push_back("33333");
v.push_back("44444");
v.push_back("55555");
v.push_back("66666");
v.push_back("77777");
v.push_back("88888");
v.push_back("99999");
for (auto& e : v)
{
cout << e << " ";
}
cout << endl;
}
为什么会发生运行错误呢?我们可以调试一下:
- 如果我们尝试传入
string
类型,在扩容的时候用memcpy
来拷贝一个自定义类型
,实际上也是把string
原来的地址传过去了,相当于虽然vector
类型是深拷贝,但是string
类型是浅拷贝,下图是存储示意图。
拷贝后:
- 因此我们要用
for
循环来取代memcpy
就可以完美的解决这个问题:
void reserve(size_t newcapacity)
{
if (newcapacity > capacity())
{
size_t old_size = size();
T* tmp = new T[newcapacity];
//memcpy(tmp, start, old_size * sizeof(T));
for (size_t i = 0; i < size(); ++i)
{
// 这里对于string这样的类型进行的是赋值重载,也是深拷贝。
tmp[i] = start[i];
}
delete[] start;
start = tmp;
finish = start + old_size;
end_of_storage = start + newcapacity;
}
}
7. 迭代器失效问题
- 迭代器失效,实际就是迭代器底层对应指针所指向的空间被销毁了,而
使用一块已经被释放的空间
,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。 - 带有扩容的操作都可能导致迭代器失效,例如push_back(),例如:
void vector_test8()
{
vector<int> v1;
vector<int>::iterator it = v1.begin();
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.push_back(6);
v1.push_back(7);
v1.push_back(8);
print_vector(v1);
v1.insert(it, 40);
print_vector(v1);
}
- 这里插入八个数据空间已经满了,这时候再插入数据就会扩容,v1.begin()的地址就会变,但是迭代器是在开头定义的,他不会变,所以一般在insert以后,不建议使用迭代器。
以下示例也会导致迭代器失效:
void vector_test9()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(4);
v1.push_back(5);
//v1.push_back(4);
// 删除偶数 -- 迭代器失效以后,不要直接使用,如果要使用按规则重新更新后使用
//std::vector<int>::iterator it = v1.begin();
vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
if (*it % 2 == 0)
{
it = v1.erase(it);
}
else
{
++it;
}
}
//print_vector(v1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}