【C++第九课 - vector】vector介绍、vector使用，vector的底层实现、杨辉三角、全排列、只出现一次的数字

上次课回顾
windows和Linux下默认的string类型的大小
（1）windows
按理来说，大小应该是12，但是运行的结果却又28


多了个_Buf数组，这个数组大小是16，可以存15个字符
所以s1和s2的大小不是12，而是18

对于_Buf这个字符数组，如果string的_str的大小小于等于15就存在_Buf里面，如果大于15则_Buf这个字符数组就废弃重新开辟空间。目的：防止频繁开辟小空间

（2）Linux
Linux默认64位，默认release版本
上述代码放到Linux里面，大小就是八字节，也就是string里面就放了一个指针


浅拷贝问题
（1）析构两次 -> 引用计数
当最后一个对象删除时，才会释放这段空间

（2）一个修改会影响另一个 -> 写时拷贝(也有缺陷)

一、vector的介绍

就是顺序表

string类是一个保存字符的动态数组，由于其中有一个接口c_str,转化成c语言的字符串，要以\0结尾，所以string类最后会有一个\0.
string支持+=
string支持比较大小（通过ascii码）
vector是一个保存T类型的动态数组，vector也是保存字符的动态数组，但是，不会以\0结尾，不保存\0.
vector不支持+=
vector不支持比较大小（也可以通过ascii码比较，但意义不大）

二、vector的使用

1、vector的构造函数

（1）全缺省构造（无参的）

vector<int> v1;

（2）n个value的构造

vector<int> v2(5, 1);

（3）迭代区间的构造

	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(5);
	vector<int> v3(v1.begin(), v1.end());

2、vector的插入和三种遍历方式

（1）、下标

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);

	for (int i = 0; i < v1.size(); i++)
	{
		cout << v1[i];
	}
	cout << endl;


	return 0;
}

（2）、迭代器

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);

	vector<int>::iterator t = v1.begin();
	while (t != v1.end())
	{
		cout << *t;
		++t;
	}
	cout << endl;

	return 0;
}

（3）、范围for

#include<iostream>
#include<vector>
using namespace std;

int main()
{
	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;

	return 0;
}

3、开空间

（1）、开空间reserve

void test2()
{
	vector<int> v1;
	int sz = v1.capacity();
	for (int i = 0; i < 100; i++)
	{
		v1.push_back(i);
		if (sz != v1.capacity())
		{
			cout << "capacity: " << v1.capacity() << endl;
			sz = v1.capacity();
		}
	}
}

int main()
{
	test2();
	return 0;
}

1.5倍扩容，Linux一般是二倍扩容
减少频繁扩容的方式，使用reserve，而不使用resize，因为resize不仅扩容还会初始化那么再插入的时候还需要扩容

（2）、开空间加初始化resize

vector的resize不缩容，缩容用Shrink_to_fit

void test2()
{
	vector<int> v1;
	v1.reserve(100);
	int sz = v1.capacity();
	for (int i = 0; i < 100; i++)
	{
		v1.push_back(i);
		if (sz != v1.capacity())
		{
			cout << "capacity: " << v1.capacity() << endl;
			sz = v1.capacity();
		}
	}
	v1.resize(10);
	cout << "capacity: " << v1.capacity() << endl;
	cout << "size: " << v1.size() << endl;
}

4、insert

（1）在某一位置插入val

void test3()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(5);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	v1.insert(v1.begin(), 10);
	for (auto e: v1)
	{
		cout << e <<" ";
	}
	cout << endl;
}

2、在某一位置插入n个val

void test3()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(5);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	v1.insert(v1.begin(), 2,10);
	for (auto e: v1)
	{
		cout << e <<" ";
	}
	cout << endl;
}

（3）在某一位置插入一个迭代区间

	v1.insert(v1.begin(), v2.begin(), v2.end());
	cout << "v1:";
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

5、find

vector没有find，用的是算法里面的find

string为何要自己写find
（1）string查找的更为复杂，不仅要查一个字符还有可能查一个字串
（2）string返回下标更合适

void test4()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	v1.insert(find(v1.begin(), v1.end(), 2), 20);

	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

}

6、erase

补充

vector不支持流插入和流提取
因为vector打印时每个之间用什么隔开自己决定
string如果没有特殊需求一般打印的时候都是连着

三、vector的底层实现

相比于之前string的直接定义_a、_size、_capacity，这里的vector是间接定义的

1、成员变量

vector不使用下标，只使用迭代器进行访问、插入等

private:
		iterator start;
		iterator finish;
		iterator end_of_storage;

2、构造函数

3、push_back

namespace zyh
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		vector()
			:start(nullptr)
			,finish(nullptr)
			,end_of_storage(nullptr)
		{}
		size_t size()
		{
			return finish - start;
		}
		size_t capacity()
		{
			return end_of_storage - start;
		}
		void reverse(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* tmp = new T[n];
				if (start)
				{
					memcpy(tmp, start, old * sizeof(T));
				}
				delete[] start;
				start = tmp;
				finish = start + oldsize;
				end_of_storage = start + n;
			}
		}
		void push_back(const T& x)
		{
			if (finish == end_of_storage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reverse(newcapacity);
			}
			*finish = x;
			finish++;
		}
		iterator begin()
		{
			return start;
		}
		iterator end()
		{
			return finish;
		}
		const_iterator begin() const
		{
			return start;
		}
		const_iterator end() const
		{
			return finish;
		}
	private:
		iterator start;
		iterator finish;
		iterator end_of_storage;

4、访问方式

迭代器

iterator begin()
		{
			return start;
		}
		iterator end()
		{
			return finish;
		}
		const_iterator begin() const
		{
			return start;
		}
		const_iterator end() const
		{
			return finish;
		}

		vector<int>::iterator it1 = v1.begin();
		while (it1 != v1.end())
		{
			std::cout << *it1 << " ";
			it1++;
		}
		std::cout << std::endl;

范围for

		v1.push_back(5);
		for (auto v : v1)
		{
			std::cout << v << " ";
		}
		std::cout << std::endl;

[]

		T& operator[](size_t pos)
		{
			assert(pos < size());
			return start[pos];
			//return *(start + pos);
		}

		v1.push_back(6);
		for (int i = 0; i < v1.size(); i++)
		{
			std::cout << v1[i] << " ";
		}
		std::cout << std::endl;

5、pop_back

		void pop_back()
		{
			assert(size() > 0);
			--finish;
		}

6、insert - pos位置插入x

		void insert(iterator pos,const T& x)
		{
			assert(pos >= start && pos <= finish);
			if (finish == end_of_storage)
			{
				reverse(capacity() == 0 ? 4 : capacity() * 2);
			}
			memmove(pos + 1, pos, sizeof(T) * (finish - pos));
			++finish;
			*pos = x;
		}

问题：扩容时，pos迭代器失效

		void insert(iterator pos,const T& x)
		{
			assert(pos >= start && pos <= finish);
			int len = pos - start;
			if (finish == end_of_storage)
			{
				reverse(capacity() == 0 ? 4 : capacity() * 2);
				pos = start + len;
			}
			memmove(pos + 1, pos, sizeof(T) * (finish - pos));
			++finish;
			*pos = x;
		}

7、resize

capacity和size都要变

T()是个匿名对象，因为要给一个缺省值，又因为T是不确定的，因此使用匿名对象
在模板里面无论是内置类型还是自定义类型都是可以初始化的

		void resize(size_t n, T val = T())
		{
			if (n <= size())
				finish = start + n;
			else if (n > size() && n <= capacity())
			{
				while (finish != start + n)
				{
					*finish = val;
					++finish;
				}
			}
			else
			{
				reverse(n);
				while (finish != start + n)
				{
					*finish = val;
					++finish;
				}
			}
		}

8、拷贝构造

		//拷贝构造
		vector(const vector<T>& v)
		{
			reverse(v.capacity());
			for (const auto& i : v)
			{
				push_back(i);
			}
		}

1、因为v是const的，所以在使用范围for进行遍历的时候注意也要是const auto

9、赋值

下面这样写是不对的，全局的swap两个变量都不能有const的

		vector<T>& operator=(vector<T> v)
		{
			//swap(v);
			std::swap(start, v.start);
			std::swap(finish, v.finish);
			std::swap(end_of_storage, v.end_of_storage);
			return *this;
		}

10、erase

		void erase(iterator pos)
		{
			assert(pos < finish);
			assert(pos >= start);
			iterator it = pos + 1;
			while (it < finish)
			{
				*(it - 1) = *it;
				++it;
			}
			finish--;
		}

四、迭代器失效

insert和erase形参pos都可能会失效
原则是insert和erase过的迭代器不要使用

1、insert在pos位置插入时，发生扩容，pos这个迭代器就失效了

2、erase进行删除的时候会发生迭代器失效

erase有一个返回值，返回的是刚刚删除元素的下一个位置

删除所以元素中的偶数

五、vector和string的优势

1、尾插和尾删
2、随机访问

四、算法题

1、电话号码的字母组合 – 全排列问题

class Solution {
public:
    string num2str[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv", "wxyz"};
    void combinstr(string& digits, int dinum, string str, vector<string>& v)
    {
        if(dinum == digits.size())
        {
            v.push_back(str);
            return;
        }
        int num = digits[dinum] - '0';
        string numstr = num2str[num];
        for(int i = 0; i < numstr.size(); i++)
        {
            combinstr(digits, dinum + 1, str + numstr[i], v);
        }
        

    }
    vector<string> letterCombinations(string digits) {
        vector<string> v;
        if(digits.size() == 0)
            return v;
        combinstr(digits, 0, "", v);
        return v;
    }
};

2、只出现一次的数字

对于此题的解法：就是异或^
0和任意数a异或还是a：0^a = a
任意数a和其自身异或为0：a^a = 0;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            res = res ^ nums[i];
        }
        return res;
    }
};

3、杨辉三角

&& ：逻辑与，两个结果都为真时才为真
|| ：逻辑或，两个结果有一个为真则为真

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

改进：
if(j == 0 || j == i || i == 0) { vv[i][j] = 1; }
对于这行代码可以使用vector里面的front和back

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

也可以把所有的位置都初始化为0vv[i].resize(i+1, 0);
在对v[i][j]进行赋值的时候可以直接判断只给0的位置，因为1的位置已经赋值了

4、删除排序数组中的重复项

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        if(nums.size() == 1)
            return 1;
        size_t i = 1;
        size_t j = 0;
        int len = 1;
        while(i < nums.size())
        {
            if(nums[i] == nums[j])
            {
                i++;
            }
            else
            {
                nums[len] = nums[i];
                len++;
                j = i;
                i++;
            }
        }
        return len;
    }
};

对于排序的序列去重使用双指针

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

使用两个指针遍历数组，当两个指针指向的内容不同时就删除，最后留下的就是多个一样的数或一个数

#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int MoreThanHalfNum_Solution(vector<int>& numbers) {
        // write code here
        size_t len = numbers.size();
        if(len == 1)
            return numbers[0];
        auto i = numbers.begin();
        auto j = numbers.end()-1;
        while(i != j)
        {
            if(*i != *j)
            {
                numbers.erase(j);
                numbers.erase(i);
                j = numbers.end() - 1;
                i = numbers.begin();
            }
            else
            {
                i++;
            }

        }
        return numbers[0];
    }
};