【C++】vector

vector的常用接口使用

vector的文档介绍

动态二维数组理解

使用标准库中vector构建动态二维数组 构造一个vv动态二维数组，假设总共5个元素，每个元素都是vector类型的，每行没有包含任何元素，如下所示：

vector在oj中的使用

• 杨辉三角

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for(int i=0;i<numRows;i++)
{
vv[i].resize(i+1,1);
for(int j=1;j<vv[i].size()–1;j++)
{
vv[i][j]=vv[i–1][j]+vv[i–1][j–1];
}
}
return vv;
}
};

• 只出现一次的数字i

class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> vv(numRows);
for(int i=0;i<numRows;i++)
{
vv[i].resize(i+1,1);
for(int j=1;j<vv[i].size()–1;j++)
{
vv[i][j]=vv[i–1][j]+vv[i–1][j–1];
}
}
return vv;
}
};

• 只出现一次的数字ii

class Solution {
public:
int singleNumber(vector<int>& nums) {
int res=0;
for(int i=0;i<32;i++)
{
int a=0;
for(auto e:nums)
{
a+=((e>>i)&1);
}
a%=3;
res|=(a<<i);
}
return res;
}
};

• 只出现一次的数字iii

思路：

将数组中的数全部按位异或，这样就得到都是两个只出现一次的数的异或，记为x 那么x为1的比特位代表着那两个只出现一次的数的该比特位一个为1，一个为0 我们使用x&-x可以得到x的最低位

//比如：
s = 101100
~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s 效果：s 的最低 1 左侧取反，右侧不变
s & –s = 000100

那么数组中这一位为0的数&（x&-x）就是0，一位为1的数&（x&-x）就不是0 以此将数组中的数分为两组（两个只出现一次的数会分别出现在这两组） 此时在组内全部按位异或就可以分别得到两个只出现一次的数 这种情况下，x=INT_MIN, -x会溢出 int low =( x==INT_MIN? x : x&(-x) );

class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int x=0;
for(auto e:nums)
{
x^=e;
}
// 防溢出 0 INT_MIN
int low =(x==INT_MIN?x:x&(–x));
vector<int> res(2,0);
for(auto e:nums)
{
if((e&low)==0)
res[0]^=e;
else
res[1]^=e;
}
return res;
}
};

• 删除排序数组中的重复项

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
vector<int>::iterator it=nums.begin()+1;
while(it!=nums.end())
{
if(*it==*(it–1))
{
nums.erase(it);
}
else
{
it++;
}
}
return nums.size();
}
};

• 数组中出现次数超过一半的数字

class Solution {
public:

int MoreThanHalfNum_Solution(vector<int>& numbers)
{
int mode=0,count=0;
for(auto e:numbers)
{
if(count==0)
{
mode=e;
count++;
}
else if(mode==e)
{
count++;
}
else
{
count—;
}
}
return mode;
}
};

vector核心框架接口的模拟实现

vector迭代器失效问题

• 野指针 会引起其底层空间改变的操作，都有可能使迭代器失效。vector扩容时，旧空间被释放掉，迭代器还使用的是释放之间的旧空间，在对迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。 解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给迭代器重新赋值即可

• 意义失效 如erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了

memcpy拷贝问题

这样就可以了，会调用string的拷贝构造，完成深拷贝

vector模拟实现

• vector.h

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<string>
using namespace std;

namespace high_cool
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

vector()
{}
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;
}
}
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
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 clear()
{
_finish = _start;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
size_t size() const
{
return _finish – _start;
}
size_t capacity() const
{
return _end_of_storage – _start;
}
bool empty() const
{
return _start == _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 reserve(size_t n);
void resize(size_t n, T val = T());
void push_back(const T& x);
void pop_back(const T& x);
iterator insert(iterator pos, const T& x);
iterator erase(iterator pos);
private:
iterator _start=nullptr;
iterator _finish=nullptr;
iterator _end_of_storage=nullptr;
};

template<class T>
void vector<T>::reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * old_size);
for (int i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
_start = tmp;
_finish = tmp + old_size;
_end_of_storage = tmp + n;
}

}

template<class T>
void vector<T>::resize(size_t n, T val)
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}

template<class T>
void vector<T>::push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
_finish++;
}

template<class T>
void vector<T>::pop_back(const T& x)
{
assert(!empty());
_finish—;
}

//规定，没有实例化的类模板里面取东西，编译器不能区分这里vector<T>::iterator
//是类型还是静态成员变量
template<class T>
typename vector<T>::iterator vector<T>::insert(typename vector<T>::iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = 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;
}

template<class T>
typename vector<T>::iterator vector<T>::erase(typename vector<T>::iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it != end())
{
*(it – 1) = *it;
++it;
}

—_finish;
return pos;
}
}

• test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"vector.h"

void test1()
{
vector<int> v(5, 1);
vector<vector<int>> vv(10, v);
for(int j=0;j<vv.size();j++)
{
for (int i = 0; i < v.size(); i++)
{
cout << vv[j][i] << " ";
}
cout << endl;
}
cout << endl;
vv[2][1] = 2;
for (int j = 0; j < vv.size(); j++)
{
for (int i = 0; i < v.size(); i++)
{
cout << vv[j][i] << " ";
}
cout << endl;
}
cout << endl;
}

namespace high_cool
{
template<class T>
void print_vector(const vector<T>& v)
{
// 规定，没有实例化的类模板里面取东西，编译器不能区分这里const_iterator
// 是类型还是静态成员变量
//typename vector<T>::const_iterator it = v.begin();
auto it = v.begin();
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;

/*for (auto e : v)
{
cout << e << " ";
}
cout << endl;*/
}

void test1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);

print_vector(v);

vector<double> vd;
vd.push_back(1.1);
vd.push_back(2.1);
vd.push_back(3.1);
vd.push_back(4.1);
vd.push_back(5.1);

print_vector(vd);
}

void test2()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
print_vector(v);

int x;
cin >> x;
auto p = find(v.begin(), v.end(), x);
if (p != v.end())
{
// insert以后p就是失效，不要直接访问，要访问就要更新这个失效的迭代器的值
/*v.insert(p, 20);
(*p) *= 10;*/

p = v.insert(p, 40);
(*(p + 1)) *= 10;
}
print_vector(v);
}

void test3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
print_vector(v);

// 删除所有的偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
print_vector(v);
}

void test4()
{
vector<int> v;
v.resize(10, 1);
v.reserve(20);

print_vector(v);
cout << v.size() << endl;
cout << v.capacity() << endl;

v.resize(15, 2);
print_vector(v);

v.resize(25, 3);
print_vector(v);

v.resize(5);
print_vector(v);
}

void test5()
{
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;
print_vector(v2);

vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);

v1 = v3;
print_vector(v1);
print_vector(v3);
}

void test6()
{
vector<string> v;
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
print_vector(v);

v.push_back("11111111111111111111");
print_vector(v);
}
}

int main()
{
//test1();
//high_cool::test1();
//high_cool::test2();
//high_cool::test3();
//high_cool::test4();
//high_cool::test5();
high_cool::test6();
return 0;
}