reserve和resizefind,insert,erase,clear二维数组迭代器迭代器失效问题memcpy问题vector的实现
reserve和resizereserve()是扩容 ，resize()是扩容加初始化或删除数据(不会改变容量)
void test_vector3()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//v.reserve(100);
v.resize(100);//默认都初始化为int类型的缺省值
v.resize(100, 5);
v.resize(2);
}
find,insert,erase,clear
find
在c++中，凡是使用迭代器区间，都是左闭右开[)
在vector里面没有find，但是可以使用算法库提供的find，只需要添加头文件#include,返回的是迭代器
void test_vector4()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector::iterator ret = find(v.begin(), v.end(), 3);
//找到返回那个位置，找不到返回end
if (ret != v.end())
{
cout << "找到" << endl;
//v.erase(ret);//不能在这删除，因为insert可能导致迭代器失效，ret也就失效了
}
}
insert
在指定位置插入
v.insert(ret, 30);//在ret位置插入30
erase
vector::iterator pos = find(v.begin(), v.end(),3);//先找到想删除的数字 if (pos != v.end())//要判断pos在不在,find找不到就会返回end { v.erase(pos); }
clear
清理数据，不清空间
c语言动态开辟一个二维数组：创建和释放都会很麻烦
//创建一个m行n列的二维数组
//因为每行村的是int* ,p的类型就是int**
int** p = (int**)malloc(sizeof(int*) * m);
for (size_t i = 0; i < m; i++)
{
p[i] = (int*)malloc(sizeof(int) * n);
}
C++创建二维数组vector
vv[i]返回的是一个vector的对象，vv[i][j]又是一个函数调用,访问第j个位置的值
所以* vv[i][j]是两次函数调用，p[i][j]是两次原生指针的解引用
for (size_t i = 0; i < 5; i++)
{
vv[i].resize(i + 1);//每个位置在开辟i+1个空间
}
杨辉三角
链接
class Solution {
public:
vector> generate(int numRows) {
vector> vv;
vv.resize(numRows);//先开好多少行，每一行存的是vector
for(size_t i=0;i
电话号码的排列组合
链接
class Solution {
string arr[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
//数字和字母直接映射
public:
void _letterCombinations(const string& digits, size_t i, string combine,vector& strv)
{
if (i == digits.size())
{
strv.push_back(combine);//得到一组数据就尾插
return;
}
string str = arr[digits[i] - '0'];//减去字符0得到数字
for (size_t j = 0; j < str.size(); j++)
{
_letterCombinations(digits, i + 1, combine + str[j], strv);//递归
//不能i++，也不能combine+=
}
}
vector letterCombinations(string digits) {
string combine;//接收一组排列
vector strv;//接收所有的排列组合
if (digits.empty())//如果为空就直接返回空
{
return strv;
}
_letterCombinations(digits, 0, combine,strv);
return strv;
}
};
迭代器
函数模板的模板参数要传迭代器区间时，命名规范
迭代器分类：input_iterator output_iterator forwad_iterator(单向迭代器) bidirectional_iterator (双向迭代器) randomaccess_iterator(随机迭代器) ;
迭代器失效问题
insert
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//满了就扩容
if (_finish == _endofstorage)
{
//扩容会导致pos失效，因为增容后原来的成员变量都指向新的空间
//而pos还指向老的空间，需要更新pos
size_t len = pos - _start;//扩容之前计算pos和start的长度
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end+1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
erase用下面这段代码验证会有问题
vector::iterator it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
//erase会挪动数据
//erase(it)之后，it指向的位置的意义已经变了，直接++可能会导致问题
//连续的偶数，导致后一个偶数没有判断和删除
}
it++;
//1 3 4 5 正常
//1 4 5 没删除完
//1 2 3 4 崩溃，it在_finsh之后，it越界访问
}
最后一个是偶数，会导致erase之后，it的意义变了，再次++，会导致it和end结束判断错过了
上面三种问题，本质都是erase(it)之后，it的意义变了（it失效了），再去++it是不对的
修改
while (it != v.end())
{
if (*it % 2 == 0)
{
it=v.erase(it);
//是偶数就不++
}
else
{
++it;
}
}
vector 的迭代器的失效主要发生在insert/erase
string 的insert/erase 迭代器也会失效，string一般很少迭代器失效，因为它insert和erase基本是用下标
只要使用迭代器访问的容器，都可能会涉及迭代器失效。
memcpy问题
我们发现vector本身没有问题，深拷贝了；但是vector里的对象string是memcpy过来的,是浅拷贝，导致一个空间被析构了两次
所以不用memcpy
for (size_t i = 0; i < size(); i++)
{
//T是int，一个一个拷贝没有问题
//T是string,一个一个拷贝调用，是深拷贝，也没有问题
tmp[i] = _start[i];
}
vector的实现
#pragma once
namespace cl
{
template
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
vector()
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)
{}
//v2(v1)深拷贝传统写法，自己开空间
void swap(vector& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
//用迭代器区间初始化
//一个类模板的成员函数，又可以是一个函数模板
template
//
vector(InputIterator first, InputIterator last)
:_start(nullptr)
,_finish(nullptr)
,_endofstorage(nullptr)
{
while (first != last)//指针就是天然的迭代器
{
push_back(*first);
first++;
}
}
//深拷贝现代写法(用到迭代器)
//v1(v2)
vector(const vector& v)
:_start(nullptr),
_finish(nullptr),
_endofstorage(nullptr)//一定要初始化，不然交换完后，tmp调用析构函数会析构随机值
{
vector tmp(v.begin(), v.end());//迭代器区间初始化tmp
swap(tmp);//swap有两个参数，一个this一个要交换的
}
//v1=v3，现代写法
vector& operator=(vector v)//vector v是传值传参是拷贝构造
//利用v实现
{
swap(v);
return *this;
}
~vector()
{
if (_start)
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
}
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _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];
}
size_t size()const
{
return _finish - _start;
}
size_t capacity()const
{
return _endofstorage - _start;
}
//迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)//有数据就得拷贝到新空间
{
memcpy(tmp, _start, sizeof(T) * size());
delete[] _start;
}
_finish = tmp + size();//finish计算的是起始位置+数据个数，这一行一定在下一行之前
//finish的计算一定要在start更新之前，或者先算size
_start = tmp;
_endofstorage = _start + n;
}
}
void resize(size_t n, const T& val = T())//注意缺省值T的类型
{
if (n < size)
{
_finish = _start + n;
}
else
{
if (n > capacity())
{
reserve(n);
}
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
//满了就扩容
if (_finish == _endofstorage)
{
//扩容会导致pos失效，因为增容后原来的成员变量都指向新的空间
//而pos还指向老的空间，需要更新pos
size_t len = pos - _start;//扩容之前计算pos和start的长度
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end+1) = *end;
end--;
}
*pos = x;
_finish++;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos <= _finish);
iterator begin = pos + 1;
while (begin < _finish)
{
*(begin - 1) = *begin;
begin++;
}
--_finish;
return pos;
}
void push_back(const T& x)
{
if (_finish == _endofstorage)
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity();
T* tmp = new T[newcapacity];
if (_start)//有数据就得拷贝到新空间
{
for (size_t i = 0; i < size(); i++)
{
//T是int，一个一个拷贝没有问题
//T是string,一个一个拷贝调用，是深拷贝，也没有问题
tmp[i] = _start[i];
}
delete[] _start;
}
_finish = tmp + size();//finish计算的是起始位置+数据个数，这一行一定在下一行之前
//finish的计算一定要在start更新之前，或者先算size
_start = tmp;
_endofstorage = _start + newcapacity;
}
*_finish = x;
++_finish;
}
void pop_back()//尾删
{
assert(_finish > _start);
--_finish;
}
private:
iterator _start;
iterator _finish;
iterator _endofstorage;
};
void test_vector1()//尾插
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (size_t i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;
vector::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
void test_vector2()
{
vector v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
vector v2;
v2 = v1;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
void test_vector3()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector::iterator it = find(v.begin(), v.end(),2);
if (it != v.end())
{
//如果insert中发生了扩容，那么会导致it指向的空间被释放
//it就是一个野指针，这种问题就是迭代器失效
v.insert(it, 20);//传值传参，pos是it临时拷贝，pos是不失效了，但是it失效了
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
vector::iterator it = v.begin();
//while (it != v.end())
//{
// if (*it % 2 == 0)
// {
// v.erase(it);
// //erase会挪动数据
// //erase(it)之后，it指向的位置的意义已经变了，直接++可能会导致问题
// //连续的偶数，导致后一个偶数没有判断和删除
// }
// it++;
// //1 3 4 5 正常
// //1 4 5 没删除完
// //1 2 3 4 崩溃，it在_finsh之后，it越界访问
//}
while (it != v.end())
{
if (*it % 2 == 0)
{
it=v.erase(it);
//是偶数就不++
}
else
{
++it;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
}
