C++笔记归纳6：vector
·
vector
目录
十、非成员函数（non-member function overloads）
一、vector模板
标准库中的模板
模板参数1：数据类型
模板参数2：空间配置器
二、成员函数（member functions）
2.1.构造函数（constructor）
默认构造（无参构造）
普通构造（带参构造）
迭代器区间构造
拷贝构造
2.2.析构函数（destrutor）
2.3.赋值运算符重载（operator=）
三、迭代器（Iterators）
正向迭代器
const正向迭代器
反向迭代器
const反向迭代器
四、初始化方法
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
void test_vector1()
{
//默认构造函数初始化
vector<int> v1;
//普通构造函数初始化
vector<int> v2(10, 1);
//迭代器区间构造初始化
vector<int> v3(++v2.begin(), --v2.end());
//拷贝构造初始化
vector<int> v4 = v3;
}
int main()
{
test_vector1();
return 0;
}五、遍历方法
#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
void test_vector1()
{
//默认构造函数初始化
vector<int> v1;
//普通构造函数初始化
vector<int> v2(10, 1);
//迭代器区间构造初始化
vector<int> v3(++v2.begin(), --v2.end());
//operator[]下标访问遍历
for (size_t i = 0; i < v3.size(); i++)
{
cout << v3[i] << " ";
}
cout << endl;
//迭代器遍历
//注：与string不同，vector为标准库模板，使用时要加实例化的模板参数
vector<int>::iterator it = v3.begin();
while (it != v3.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test_vector1();
return 0;
}六、容量（capacity）
size：有效数据个数
max_size：最大能存放数据个数
capacity：当前空间大小
reserve：改变空间大小
注：
每次扩容最少开n个元素的空间
在vector中，如果n比capacity小，是不会进行缩容的
在string中，如果n比capacity小，有可能会进行缩容，但不会比size小
示例：
扩容机制
vs2019：1.5倍扩容
g++4.8：2倍扩容
resize：改变有效数据个数
如果传值，就使用传的值进行初始化
如果没有传值，就使用默认构造函数中的缺省值
七、元素访问（element access）
八、修改器（modifiers）
assign：赋值
push_back：尾部插入
insert：指定位置前插入
九、空间配置器（allocator）
get_allocator：获取空间配置器
十、非成员函数（non-member function overloads）
十一、手动实现流插入与流提取
vector模板中没有流插入和流提取操作
可以借助遍历手动实现
void test_vector3()
{
vector<int> v1(5, 0);
//流提取
for (size_t i = 0; i < 5; i++)
{
cin >> v1[i];
}
//流插入
for (auto e : v1)
{
cout << e << ",";
}
cout << endl;
}
int main()
{
test_vector3();
return 0;
}注：
不能用vector<char> v1替代string s1
字符数组的需求比较多，顺序表无法满足
十二、隐式类型转换
void test_vector4()
{
vector<string> v1;
string s1("xxxx");
v1.push_back(s1);
//隐式类型转换
//常量字符指针类型转换为string类类型
v1.push_back("yyyy");
//为了避免类类型赋值时调用拷贝构造
//最好使用引用，如果不修改，还需加const
for (const auto& e : v1)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test_vector4();
return 0;
}十三、二维数组实现
表面是动态二维数组
本质是运算符重载函数调用
void test_vector5()
{
//二维数组
//10 * 5
vector<int> v(5, 1);
vector<vector<int>> vv(10,v);
vv[2][1] = 2;
}
int main()
{
test_vector5();
return 0;
}
//operator[]访问行（返回值为vector<int>）
class vector
{
vector<int>& operator[](int i)
{
assert(i < _size);
return _a[i];
}
private:
int* _a;
size_t _size;
size_t _capacity;
};
//operator[]访问列（返回值为int）
class vector
{
int& operator[](int i)
{
assert(i < _size);
return _a[i];
}
private:
int* _a;
size_t _size;
size_t _capacity;
};动态二维数组遍历
void test_vector5()
{
//二维数组
//10 * 5
vector<int> v(5, 1);
vector<vector<int>> vv(10,v);
vv[2][1] = 2;
//等价于：
vv.operator[](2).operator[](1) = 2;
//动态二维数组遍历
for (size_t i = 0; i < vv.size(); i++)
{
for (size_t j = 0; j < vv[i].size(); ++j)
{
cout << vv[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
int main()
{
test_vector5();
return 0;
}十四、试题
试题1：杨辉三角
题目内容：
给定一个非负整数numRows，生成杨辉三角的numRows行
在杨辉三角中，每个数是它左上方和右上方的数的和
示例：
输入：numRows = 5
输出：[[1]，[1,1]，[1,2,1]，[1,3,3,1]，[1,4,6,4,1]]
class Solution
{
public:
vector<vector<int>> generate(int numRows)
{
vector<vector<int>> vv(numRows);
//将每行数据初始化为1
for(size_t i = 0;i < numRows;++i)
{
vv[i].resize(i+1,1);
//vv[i][0] = v[i][vv[i].size() - 1] = 1;
//vv[i].front() = vv[i].back() = 1;
}
//从第二行开始
for(int i = 2;i < vv.size();++i)
{
//去除每行的第一个和最后一个
for(int j = 1;j < vv[i].size() - 1;++j)
{
//上一行的同下标位置与前一个位置和
vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
}
}
return vv;
}
};十五、vector实现
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace bit
{
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()
//{ }
//C++11前置生成默认构造
vector() = default;
//拷贝构造
vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
//类模板的成员函数还可以继续是函数模板
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//n个值初始化
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
//清除数据
void clear()
{
_finish = _start;
}
//赋值运算符重载
/*vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
clear();
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}
return *this;
}*/
//交换函数
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;
}
//析构函数
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
}
//扩容
void reserve(size_t n)
{
//如果n大于当前空间
if (n > capacity())
{
//临时存放数据个数
size_t old_size = size();
//临时申请n个新空间
T* tmp = new T[n];
//将原空间数据拷贝到新空间
//注：使用memcpy会出现浅拷贝问题
//memcpy(tmp, _start, size() * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
//使用_tmp赋值完成深拷贝
_tmp[i] = _start[i]
}
//释放原空间
delete[] _start;
//更新新空间
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}
}
//默认构造匿名对象，再进行拷贝构造->优化为直接构造
void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}
//计算有效数据个数
size_t size() const
{
return _finish - _start;
}
//计算当前容量
size_t capacity() const
{
return _end_of_storage - _start;
}
//判空
bool empty() const
{
return _start == _finish;
}
//传引用，防止传自定义类型时拷贝构造
void push_back(const T& x)
{
//如果当前空间不足
if (_finish == _end_of_storage)
{
//扩容
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
//将值赋给结束位置
*_finish = x;
//往后移一位
++_finish;
}
//删除数据
void erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_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];
}
//尾删
void pop_back()
{
assert(!empty());
--_finish;
}
//指定位置前插入
void insert(iterator pos,const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//扩容
if (_finish == _end_of_storage)
{
//临时存放pos的位置，避免迭代器失效（类似野指针）
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}
private:
//起始位置
iterator _start = nullptr;
//结束位置
iterator _finish = nullptr;
//备用位置
iterator _end_of_storage = nullptr;
};
//不确定打印的类型，需要创建一个函数模板
template<class Cotainer>
void print_cotainer(const Cotainer& v)
{
//因为没有实例化
//编译器不知道const_iterator是类型还是静态成员变量
//所以需要加typename
//typename vector<T>::const_iterator it = v.begin();
//可以使用auto自动推导
auto it = v.begin();
//迭代器遍历
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
//尾插与访问运算符测试
void test_vector1()
{
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;
}
//迭代器测试
void test_vector2()
{
vector<int> v;
v.push_back(1);
//初始化迭代器
vector<int>::iterator it = v.begin();
//迭代器遍历
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//范围for遍历
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
print_cotainer(v);
vector<double> vd;
vd.push_back(1.1);
vd.push_back(2.1);
vd.push_back(3.1);
print_cotainer(v);
}
//插入数据测试
void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//v.push_back(5);
print_cotainer(v);
v.insert(v.begin() + 2, 30);
print_cotainer(v);
int x;
cin >> x;
//传左闭右开的区间
auto pos = find(v.begin(), v.end(),x);
if (pos != v.end())
{
//插入后的pos就失效了，不要直接访问
//（位置发生改变）
v.insert(pos, 40);
//要访问就要更新这个失效的迭代器的值
(*(pos + 1)) *= 10;
}
print_cotainer(v);
}
//删除数据测试
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_cotainer(v);
//删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
else//不加else会跳过下一个偶数，也有可能会跳过结尾
{
++it;
}
}
print_cotainer(v);
}
//测试resize
void test_vector5()
{
vector<int> v;
v.resize(10, 1);
v.reserve(20);
print_cotainer(v);
cout << v.size() << endl;
cout << v.capacity() << endl;
v.resize(15, 2);
print_cotainer(v);
}
//测试拷贝构造
void test_vector6()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_cotainer(v);
vector<int> v1 = v;
print_cotainer(v);
}
//测试迭代器遍历拷贝
void test_vector7()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
print_cotainer(v);
vector<int> v1(v.begin(), v.end() + 2);
print_cotainer(v1);
}
//测试n个值初始化
void test_vector8()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//注：此时会与迭代器遍历初始化相冲突
//vector<int> v5(10, 1);
//需要传unsigned变量才可以
vector<int> v6(10u, 1);
print_cotainer(v6);
}
//浅拷贝问题vector<vector<int>> vector<string>
void test_vector9()
{
vector<string> v;
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
print_cotainer(v);
}
}
汇聚全球AI编程工具，助力开发者即刻编程。
更多推荐
12
0- 0
已为社区贡献2条内容
所有评论(0)