一、vector
简介： vector是表示可变大小数组的容器，可以像数组一样连续存储数据，访问数据高效，在尾部添加、删除或修改数据时相对其他容器更高效，而对于其它位置的数据修改则效率相对更低。
重要的接口：
2.1 vector定义：
2.2 迭代器：
2.3 关于空间修改的函数
注意：在不同编译器环境下使用vector时，capacity的动态增长速度是不一样的，如在VS环境下capacity是按照1.5倍速度增长，而在g++下则是2倍。
使用resize在开空间的同时也会进行初始化，影响size；reserve只用于开辟空间，在已知需要使用多少空间时，可以一定程度上降低vector增容所需的代价。2.4 vector的增删查改
3. vector迭代器失效问题
迭代器在底层实际上就是指针或者对指针进行了封装，vector的迭代器就是原生态指针T*。迭代器失效是指底层指针所指向的空间被销毁了，实际指向了一块已经被释放的空间，如继续使用失效的迭代器，程序会面临崩溃风险。
可能引起迭代器失效的操作有：- 引起底层空间改变的操作如resize，reserve，insert，assign，push_back等
- 指定位置元素的删除操作erase
解决办法：进行以上操作后，对迭代器重新赋值即可。如用迭代器接收erase函数的返回值：it = v.erase(it);
4. vector重要接口的模拟实现
my_vector.h:
#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
template<class T>
class my_vector
{
public:
typedef T* iterator;
typedef const T* const_iterator; //所指向对象不可被更改
private:
iterator _start = nullptr; //default
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
public:
my_vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}
my_vector(size_t n, const T& val = T())
//注意：在想调用这个函数时会出现编译器调用my_vector(input_iterator first, input_iterator last)这个函数的情况，
//这是因为size_t与int&类型不一样，而编译器更倾向于采用形参类型一致的函数(T为int类型的前提下)
//解决方法，在调用这个函数的时候，输入形参时应该用类型转换，如 my_vector(10u, 1);
//又或者重载下函数
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
resize(n, val);
}
//如下
my_vector(int n, const T& val = T())
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
resize(n, val);
}
template<class input_iterator>
my_vector(input_iterator first, input_iterator last) //左闭右开区间
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
while (first != last)
{
push_back(*first);
first++;
}
}
~my_vector()
{
if (_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
}
//拷贝构造1
//my_vector(const my_vector<T>& v)
//{
// reserve(v.capacity());
// _finish = _start + v.size();
// _end_of_storage = _start + v.capacity();
// iterator temp = v.begin();
// while (temp != v.end())
// {
// push_back(*temp);
// temp++;
// }
//}
//拷贝构造2
my_vector(const my_vector<T>& v)
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{
_start = new T[v.capacity()];
//注意：此处不可行，因为出现了深拷贝错误问题。使用memcpy确实深拷贝了vector,但vector存的是其它类型的数据，
//memcpy对vector内存储的数据却是浅拷贝，即新vector内的对象指向的是旧vector内的对象的数据，如果旧vector内的对象
//的数据被delete掉，特别是自定义类型的对象，delete会首先调用析构函数，那么旧vector内的对象被销毁，影响到了新vector内的对象
//memcpy(_start, v._start, sizeof(T) * v.size());
//解决方案：采用自定义类型对象或内置对象的运算符重载函数进行深拷贝
for (size_t i = 0; i < v.size(); i++)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
//赋值运算符
void swap(my_vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
my_vector<T>& operator=(my_vector<T> v) //形参是新的构造，不影响原来的对象
{
swap(v);
return *this;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
int capacity() const //this指针所指向对象无法被更改
{
return _end_of_storage - _start;
}
int size() const
{
return _finish - _start;
}
void reserve(int n)
{
if (n > capacity())
{
int sz = size();
iterator temp = new T[n];
if (_start)
{
memcpy(temp, _start, sizeof(T) * sz);
delete[] _start;
}
_start = temp;
_finish = _start + sz;
_end_of_storage = _start + n;
cout << "扩容了" << n << endl;
}
}
void push_back(const T& x) //传引用，如果是传的常量，那么左值必须是const，否则就会出现权限放大
{
//if (_finish == _end_of_storage)
//{
// size_t new_cap = capacity() == 0 ? 4 : capacity() * 2;
// reserve(new_cap);
//}
//*_finish = x;
//_finish++;
insert(end(), x);
}
void insert(size_t pos, const T& x) //从pos从0开始计数
{
assert(_start + pos <= _finish);
if (_finish == _end_of_storage)
{
size_t new_cap = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_cap);
}
iterator end = _finish - 1;
while (end >= _start + pos ) //由于end是迭代器，迭代器持续自减不会出现像size_t类型的变量一样的减至nops的情况
{
*(end + 1) = *end;
end--;
}
*(_start + pos) = x;
++_finish;
}
iterator insert(iterator pos, const T& x)
{
assert(pos <= _finish);
if (_finish == _end_of_storage)
{
int gap = pos - _start; //防止扩容前后pos位置的不匹配
size_t new_cap = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_cap);
pos = _start + gap;
}
iterator end = _finish - 1; //如果_finish相对位置是0，那么end的相对位置就是-1
while (end >= pos) //由于end是迭代器，迭代器持续自减不会出现像size_t类型的变量一样的减至nops的情况
{
*(end + 1) = *end;
end--;
}
*pos = x;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos < _finish && pos >= _start);
iterator end = pos + 1;
while (end < _finish)
{
*(end - 1) = *end;
end++;
}
_finish--;
return pos;
}
void pop_back()
{
erase(--end());
}
void resize(size_t n, T& val = T()) //注意：T()是一个匿名函数，对内置类型和自定义类型都有效
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
T& operator[](size_t pos)
{
assert(pos < size());
return *(_start + pos);
}
const T& operator[](size_t pos) const //如果后面不加const，那么编译器无法区分这两个函数
//只有变成const成员函数，才可被编译器区分
/*
const 成员函数和非const成员函数虽然形参列表相同，
但它们在函数签名（函数的名字、参数列表和const修饰符）上有区别，
编译器可以借此区分它们
*/
{
assert(pos < size());
_start++;
return *(_start + pos);
}
void print()
{
iterator v = begin();
while (v != end())
{
cout << *v << " ";
v++;
}
cout << endl;
}
};
test.cpp:
#include "my_vector.h"
void test_1() //push_back测试
{
my_vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_2() //insert测试
{
my_vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.insert(3, 300); //插入第4个位置
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
my_vector<int>::iterator pos = v.begin() + 2;
// insert以后迭代器可能会失效(因为扩容)
// 记住，insert以后就不要使用这个形参迭代器了，因为他可能失效了
v.insert(pos, 200);
// 高危行为
// *pos += 10;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_3() //erase测试
{
my_vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v[1] = 3;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin());
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.end() - 1);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_4() //erase测试2
{
my_vector<int> v;
v.push_back(2);
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(8);
v.push_back(5);
v.push_back(10);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//删除v中所有偶数
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it); //注意：为防止迭代器失效问题出现，每次运行完erase或insert操作后，迭代器都应该重新赋值
}
else
{
it++;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_5() //拷贝构造测试
{
my_vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.print();
my_vector<int> v2(v);
v2.print();
my_vector<int> v3 = v2;
v3.print();
}
int main()
{
//test_1();
//test_2();
//test_3();
//test_4();
test_5();
return 0;
}
5. 部分考查vector的OJ题
题目1：找数组中只出现过1次的数字（每个重复数字的重复次数只有2次）
//题目：找数组中只出现过1次的数字：用异或！！！异或有交换律和分配律，任何数与0异或都为它自己。
int single_num(vector<int> v)
{
int val = 0;
for (auto e : v)
{
val ^= e;
}
return val;
}
题目2：杨辉三角
vector<vector<int>> pascal_triangle(int row_num)
{
vector<vector<int>> vv;
vv.resize(row_num); //用resize开空间，size和capacity都改变
for (size_t i = 0; i < vv.size(); i++)
{
vv[i].resize(i + 1, 0);
vv[i][0] = vv[i][i] = 1;
}
for (size_t i = 0; i < vv.size(); i++)
{
for (size_t j = 0; j <= i; j++)
{
if (vv[i][j] == 0)
{
vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j];
}
}
}
return vv;
}
题目3：电话号码的字母组合
class Solution {
vector<string> arr_str = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
void str_combination(string digits, int level, string combine, vector<string>& arr_combine) //digits为数字字符串，level为递归的层数，combine为组合字符串，arr_combine存储组合字符串
{
//递归结束条件
if (level == digits.size())
{
arr_combine.push_back(combine);
return;
}
//映射关系
int num = digits[level] - '0';
string letter = arr_str[num]; //获取对应字符串
for (size_t i = 0; i < letter.size(); i++)
{
str_combination(digits, level + 1, combine + letter[i], arr_combine);
}
}
public:
vector<string> letterCombinations(string digits)
{
vector<string> v;
if (digits == "")
{
return v;
}
str_combination(digits, 0, "", v);
return v;
}
};
题目4：只出现一次的数iii
//只出现一次的数iii
vector<int> singleNumber_3(vector<int>& nums) {
vector<int> v;
size_t val = 0;
for (auto e : nums)
{
val ^= e;
}
size_t lsb = val & (-val);
int a = 0, b = 0;
for (auto e : nums)
{
if (lsb & e)
{
a ^= e;
}
else
{
b ^= e;
}
}
v.push_back(a);
v.push_back(b);
return v;
}
题目5：删除排序数组中的重复项
int removeDuplicates(vector<int>& nums)
{
int val = nums[0];
int count = 1;
vector<int>::iterator it = nums.begin() + 1;
while (it != nums.end())
{
if (*it == val)
{
it = nums.erase(it);
}
else
{
val = *it;
it++;
count++;
}
}
return count;
}
题目6：找数组中出现次数超过数组元素数量一半的数字，并返回该数字在数组中出现的次数
int MoreThanHalfNum_Solution(vector<int>& numbers)
{
sort(numbers.begin(), numbers.end() - 1);
int cond = numbers[numbers.size() / 2];
int cnt = 0;
for (auto e : numbers)
{
if (e == cond)
cnt++;
}
if (cnt >= numbers.size() / 2)
return cond;
return 0;
}
题目7：只出现一次的数ii
int singleNumber_2(vector<int>& nums)
{
sort(nums.begin(), nums.end());
vector<int>::iterator v = nums.begin();
while (v < nums.end())
{
if (v == nums.end() - 1)
break;
if (*v == *(v + 1))
{
v += 3;
}
else
break;
}
if (v >= nums.end())
return nums[nums.size() - 1];
else
return *v;
}
6. 总结
本文主要简要介绍了stl的容器之一——vector的定义、重要接口和使用方法，也讲述了一些使用时的注意事项并模拟实现部分接口然后测试其功能，最后给出了7道考察vector使用的7道题目，这些题目都可以在leetcode上找到，望读者多做题，熟练掌握vector的使用方法和技巧。