【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、因为vconst的,所以在使用范围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里面的frontback

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];
    }
};

最近更新

  1. Spring事务管理与Spring AOP详解

    2024-06-09 13:12:01       0 阅读
  2. MTU简介

    2024-06-09 13:12:01       0 阅读
  3. C语言笔记25 •顺序表介绍•

    2024-06-09 13:12:01       0 阅读
  4. 什么是内存泄漏?如何避免?

    2024-06-09 13:12:01       0 阅读
  5. spring-websocket实现(一)

    2024-06-09 13:12:01       0 阅读
  6. apache poi excel export

    2024-06-09 13:12:01       0 阅读
  7. 代码随想录算法训练营刷题复习4 :单调栈

    2024-06-09 13:12:01       0 阅读

热门阅读

  1. FPGA复位:(41)复位管脚PR报错?

    2024-06-09 13:12:01       4 阅读
  2. 逆运动学IK原理举例说明

    2024-06-09 13:12:01       5 阅读
  3. 浅谈单臂路由

    2024-06-09 13:12:01       4 阅读
  4. Vue基础篇--table的封装

    2024-06-09 13:12:01       3 阅读
  5. 数据结构——哈希表

    2024-06-09 13:12:01       3 阅读
  6. U9C的数据查询视图Sql

    2024-06-09 13:12:01       3 阅读
  7. kotlin gradle踩过的坑

    2024-06-09 13:12:01       6 阅读
  8. 关于xilinx srio ip复位问题

    2024-06-09 13:12:01       4 阅读
  9. Elasticsearch高效检索:基础查询详解

    2024-06-09 13:12:01       3 阅读
  10. MySQL入门学习-聚合和分组.计数(COUNT()函数)

    2024-06-09 13:12:01       4 阅读
  11. ch1计算机网络和因特网

    2024-06-09 13:12:01       5 阅读
  12. bpmn+vue 中文文档

    2024-06-09 13:12:01       5 阅读
  13. 大语言模型原理基础与前沿 为什么ICL有效

    2024-06-09 13:12:01       4 阅读
  14. React——组件通信方式

    2024-06-09 13:12:01       5 阅读