| ❤️欢迎来到我的博客❤️ |
前言
vector示可变大小数组的序列容器
就像数组一样，vector也采用的连续存储空间来存储元素
既然都是数组并且都可以动态增长那么vector能不能替代string呢？
答案是不能
原因如下：
string和vector在结构上有所不同
不同点：string要求末尾有’\0’（自动添加），而vector并不要求有’\0’（虽然可以手动添加，但并不是所有人都这么做，所以这个方法是不靠谱的）
string兼容C语言并且string的接口比vector更丰富，比如+=和比较大小，vector没有这些接口， vector也可以实现比较大小，但是vector的比较大小是没有意义的
所以string和vector都是有各自存在的价值的
万物皆可模板化（只要是确定的类型），所以vector可以存string
void test()
{
//方法一
vector<string> v;
string name("十一");
v.push_back(name);
//方法二（匿名对象）
v.push_back(string("十一"));
//方法三（单参数的构造函数支持隐式类型转换）
v.push_back("十一");
}
vector的使用
构造
构造并初始化n个val
void test2()
{
//构造并初始化n个val
vector<int> v1(10, 1);
vector<string> v2(10, "xxx");
for (auto a : v1)
{
cout << a << " ";
}
cout << endl;
for (auto a : v2)
{
cout << a << " ";
}
cout << endl;
}
使用迭代器构造
void test2()
{
//构造并初始化n个val
vector<int> v1(10, 1);
for (auto a : v1)
{
cout << a << " ";
}
cout << endl;
//使用迭代器进行初始化构造
//自己类型的迭代器
vector<int> v2(v1.begin(), v1.end());
for (auto a : v2)
{
cout << a << " ";
}
cout << endl;
//其他容器的迭代器
string str("xxxx xxxx");
vector<char> v3(str.begin(), str.end());
for (auto a : v3)
{
cout << a << " ";
}
cout << endl;
//数组指针
int a[] = { 1,2,3,4,5 };
vector<int> v4(a, a + 5);
for (auto a : v4)
{
cout << a << " ";
}
cout << endl;
}
排序
void test2()
{
int a[] = { 2,123,5,12,83 };
vector<int> v4(a, a + 5);
for (auto a : v4)
{
cout << a << " ";
}
cout << endl;
//排序(需要<algorithm>头文件）
//默认升序 <
sort(v4.begin(), v4.end());
for (auto a : v4)
{
cout << a << " ";
}
cout << endl;
//降序 > （需要传类对象，库里有一个greater）
//也可以用反向迭代器
sort(v4.begin(), v4.end(), greater<int>());
for (auto a : v4)
{
cout << a << " ";
}
cout << endl;
}
其他类型也可以排序
void test2()
{
//其他容器的迭代器
string str("xxxx xxxx");
vector<char> v3(str.begin(), str.end());
//数组指针
int a[] = { 5,2,1,3,4 };
vector<int> v4(a, a + 5);
//排序string
sort(str.begin(), str.end());
cout << str << endl;
//排序数组
sort(a, a + 5);
for (auto e : a)
{
cout << e << " ";
}
cout << endl;
}
vector的空间
| 容量空间 | 接口说明 |
|---|---|
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
reserve的错误用法：
void test3()
{
vector<char> v1;
v1.reserve(10);
for (size_t i = 0; i < 10; i++)
{
v1[i] = i;
}
}
运行结果：
可以看到代码报错了，错误是数组越界
这是因为 [] 会检查越界
所以我们这里不能直接使用[]进行访问，而是使用push_back代码就能正常的运行了
void test3()
{
vector<int> v1;
v1.reserve(10);
for (size_t i = 0; i < 10; i++)
{
v1.push_back(i);
}
}
或者是使用resize：
void test3()
{
vector<int> v1;
v1.resize(10);
for (size_t i = 0; i < 10; i++)
{
v1[i] = i;
}
}
resize在开空间的同时还会进行初始化，影响size
reserve只是把空间开好了，是为了避免扩容（或减少扩容）提高效率
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题（提高效率）
vector的扩容逻辑
//vector的扩容逻辑
void test()
{
size_t sz;
vector<int> v;
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: " << sz << '\n';
}
}
}
运行结果：
vs下capacity是按1.5倍增长的，g++是按2倍增长的
增删查改
| vector | 接口说明 |
|---|---|
| push_back | 尾插 |
| pop_back | 尾删 |
| find | 查找（注：这个是算法模块实现，不是vector的成员接口） |
| insert | 在position之前插入val |
| erase | 删除position位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[] | 像数组一样访问 |
使用方法演示：
void test3()
{
vector<int> v1;
v1.resize(10);
for (size_t i = 0; i < 10; i++)
{
v1[i] = i;
}
//头删
v1.erase(v1.begin());
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//头插
v1.insert(v1.begin(), 20);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//删除第2个数据
v1.erase(v1.begin() + 1);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//查找并删除
//(如果找不到返回last（最后一个数据的下一个位置）
vector<int>::iterator pos = find(v1.begin(), v1.end(), 9);
if (pos != v1.end())
{
v1.erase(pos);
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
这里的find是算法模块实现的，不是vector的成员接口：
如果我们有很多个相同的数据，并且都要删除，那应该怎么办呢
void test4()
{
int a[] = { 1,2,3,3,3,3,3,3,3,10 };
vector<int> v1(a, a + sizeof(a) / sizeof(int));
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
//删除所有的3
auto pos = find(v1.begin(), v1.end(), 3);
while (pos != v1.end())
{
v1.erase(pos);
pos = find(pos + 1, v1.end(), 3);
}
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
运行效果：
这种写法看起来没什么问题，但是为什么程序会崩溃呢？
因为这里的迭代器失效了，当我们把pos位置删除了之后，迭代器就会失效，迭代器失效了之后如果我们再进行使用就会出现问题
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)
解决方法：
每次都从头查找，但效率会比较低
auto pos = find(v1.begin(), v1.end(), 3);
while (pos != v1.end())
{
v1.erase(pos);
//pos = find(pos + 1, v1.end(), 3);
//修改为：
pos = find(v1.begin(), v1.end(), 3);
}
vector存放其他对象
vector<vector< int >>
vector< string >
练习
了解了vector之后，我们来使用vector做两道练习题
比如我们输入"258"，那么
2对应的字母就是： a b c
5对应的字母就是： j k l
8对应的字母就是： t u v
不难看出，这个结构很像一颗多叉树，那么我们可以使用递归来解决这道题
题目给我们的是一个数字串，那我们首先需要根据数字串找到他对应的字母串
可以定义一个数组，存放数字所对应的字母串，然后再取出数字对应的字母串进行排列组合
class Solution {
string a[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:
//i - 层数
//combinestr - 组合成的字符串
void Combine(string digits, int i, string combinestr, vector<string>& v)
{
//当层数i和size相等的时候，组合就结束了
if(i == digits.size())
{
//组合成的字符串存放到vector中,退回到上一层
v.push_back(combinestr);
return;
}
//减去字符'0'才是我们需要的数字
int num = digits[i] - '0';
//取数字对应的字符串
string str = a[num];
//依次取所有的字母
for(size_t j = 0;j < str.size();++j)
{
//跟下一层组合
Combine(digits,i+1,combinestr + str[j],v);
}
}
vector<string> letterCombinations(string digits) {
vector<string> v;
//判断digits是否为空，为空返回
if(digits.empty())
{
return v;
}
Combine(digits,0,"",v);
return v;
}
};
假设digits为"258"，递归图如下：
vector的模拟实现
接下来我们要模拟实现vector的部分功能
在空间申请方面我们使用new delete实现
基本框架：
namespace Vector
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//普通迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//const迭代器
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
~vector()
{
if (_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
//保存旧空间
size_t sz = size();
//开n个空间
T* tmp = new T[n];
//原空间不为空，拷贝数据
if (_start)
{
memcpy(tmp, _start, sizeof(T) * sz);
//释放旧空间
delete[] _start;
}
//指向新空间
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void push_back(const T& x)
{
//判断是否满
if (_finish == _endofstorage)
{
//扩容
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//赋值
*_finish = x;
++_finish;
}
//获取capacity的大小
size_t capacity() const
{
return _endofstorage - _start;
}
//获取size大小
size_t size() const
{
return _finish - _start;
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
void test1()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
}
现在我们的vector已经可以跑起来了，我们接着实现其他的功能
[]
T& operator[](size_t pos)
{
assert(pos < size());
//返回pos位置的值
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
//返回pos位置的值
return _start[pos];
}
insert
//注：vector的insert用的是迭代器，不是下标
void insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
//判断容量
if (_finish == _endofstorage)
{
//扩容
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//pos位置插入数据
*pos = x;
++_finish;
}
我们来试着调用insert
void test()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.insert(v1.begin(), 100);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
可以正常调用，但如果我们让vector的数字更多一点
void test()
{
vector<int> v1;
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);
v1.insert(v1.begin(), 100);
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
可以看到，虽然我们的代码没有报错，但是我们需要的100并没有被添加进去，还多了一个随机值出来，引发这个问题的原因是因为迭代器失效了
迭代器失效
如果没有进行扩容操作，那么我们的insert是可以正常使用的，但是一旦有扩容迭代器就会失效
我们只需要在扩容的时候更新一下pos即可
//判断容量
if (_finish == _endofstorage)
{
//计算pos相对位置
size_t len = pos - _start;
//扩容
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//更新pos
pos = _start + len;
}
我们这只是解决了内部迭代器失效的问题，外部的迭代器在使用的时候一定要谨慎
void test()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<int>::iterator p = v1.begin() + 3;
v1.insert(p, 300);
//insert之后就不要使用这个形参迭代器了，因为他有可能已经失效了
*p += 10;//危险！有可能失效了(扩容之后就会失效)
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
并没有进行+=操作，因为迭代器已经失效了
erase
erase比较简单，只需要挪动数据就行了
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
//返回删除前pos的后一个数据
return pos;
}
vector在使用erase和insert迭代器对象后，不能再访问这个迭代器
我们认为他失效，访问结果是未定义
push_back和pop_back
这两个我们可以直接复用insert和erase
void push_back(const T& x)
{
判断是否满
//if (_finish == _endofstorage)
//{
// //扩容
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
赋值
//*_finish = x;
//++_finish;
//直接复用insert
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
resize
void resize(size_t n, const T& val = T())
{
//1.resize小于原空间
if (n < size())
{
_finish = _start + n;
}
else
{
//resize大于原空间
resever(n);
//添加数据
while (_finish != _strat + n)
{
*_finish = val;
++_finish;
}
}
}
拷贝构造
//深拷贝
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
_start = new T[v.capacity()];
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_endofstorage = _start + v.capacity();
}
另一种写法：
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}
赋值：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
//赋值 - v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
但是我们这里还会存在一个问题，虽然vector是深拷贝了，但是vector里的对象并不是深拷贝，比如vector< string >
vector是深拷贝
但是vector空间上存的对象是string的数组
使用memcpy导致string对象浅拷贝了，所以我们还需要对reserve进行修改
修改为：
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz);
//修改为
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
原理：如果T是string这样的深拷贝的类，调用的是string赋值重载，实现的string对象的深拷贝
n个val初始化
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
使用迭代器区间初始化：
//一个类模板还可以再套一个模板
//[first,last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
完整代码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace Vector
{
template<class T>
class vector
{
public:
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;
}
vector(size_t n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _endofstorage(nullptr)
{
resize(n, val);
}
//一个类模板还可以再套一个模板
//[first,last)
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
vector()
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{}
//深拷贝
vector(const vector<T>& v)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
reserve(v.capacity());
for (auto e : v)
{
push_back(e);
}
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
//赋值 - v1 = v2
vector<T>& operator=(vector<T> v)
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endofstorage = nullptr;
}
}
void reserve(size_t n)
{
if (n > capacity())
{
size_t sz = size();
T* tmp = new T[n];
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz);
//修改为
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T())
{
//1.resize小于原空间
if (n < size())
{
_finish = _start + n;
}
else
{
//resize大于原空间
reserve(n);
//添加数据
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
void push_back(const T& x)
{
判断是否满
//if (_finish == _endofstorage)
//{
// //扩容
// size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(newcapacity);
//}
赋值
//*_finish = x;
//++_finish;
//直接复用insert
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
//获取capacity的大小
size_t capacity() const
{
return _endofstorage - _start;
}
//获取size大小
size_t size() const
{
return _finish - _start;
}
T& operator[](size_t pos)
{
assert(pos < size());
//返回pos位置的值
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
//返回pos位置的值
return _start[pos];
}
//注：vector的insert用的是迭代器，不是下标
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start && pos <= _finish);
//判断容量
if (_finish == _endofstorage)
{
//计算pos相对位置
size_t len = pos - _start;
//扩容
size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(newcapacity);
//更新pos
pos = _start + len;
}
//挪动数据
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//pos位置插入数据
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
//返回删除前pos的后一个数据
return pos;
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
void test()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector<string> v2;
v2.push_back("1111111111111111111111111111111111");
v2.push_back("1111111111111111111111111111111111");
v2.push_back("1111111111111111111111111111111111");
v2.push_back("1111111111111111111111111111111111");
v2.push_back("1111111111111111111111111111111111");
vector<string> v3(v2);
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
}
}
总结
以上就是本篇文章的全部内容了，希望大家看完能有所收获
| ❤️创作不易，点个赞吧❤️ |