【ONE·C++||vector（一）】-创新互联

  学习笔记，慢慢补充。

• 总言
• 1、整体介绍：
• 2、常用各种接口介绍
• • 2.1、vector的基本结构：构造、析构、赋值
  • • 2.1.1、总体情况预览
    • 2.1.2、各项函数使用演示
  • 2.2、vector增删查改相关
  • • 2.2.1、增删查改总览
    • 2.2.2、如何在vector中插入、删除、遍历数据
    • 2.2.3、front、back函数
  • 2.3、vector扩容相关
  • • 2.3.1、容量问题总览
    • 2.3.2、resize、reserve函数介绍
  • 2.4、其它一些函数介绍
  • • 2.4.1、find、insert函数介绍
    • 2.4.2、erase函数介绍
    • 2.4.3、vector排序问题：sort
  • 2.5、一些现象、问题说明
  • • 2.5.1、一个问题讨论：vector存储char字符与string的比较
    • 2.5.2、vector与string结合使用：vector< string >
• 3、相关练习题：
• • 3.1、只出现一次的数字
  • 3.2、杨辉三角：vector>嵌套使用
  • 3.3、删除有序数组中的重复项
  • 3.4、电话号码的字母组合

   该文章参考网站是cplusplus.com。

  1、vector是类模板，其有两个模板参数class T、class Alloc = allocator。
  2、class Alloc = allocator：空间配置器(内存池)。默认配置了一个缺省参数，由库提供这个内存池。若自己有设计想法，也可自己显示实现。

  1）、构造函数总览

  
  
  2）、析构函数总览
   vector的析构函数，出了作用域自动调用。

  
  
  3）、赋值运算符重载总览
   赋值运算符重载就涉及到后续深浅拷贝的问题。

  
  4）、小结
   上述几个函数中，
      ①对构造函数，使用最多的是无参构造、拷贝构造。
      ②对析构函数调用默认的即可，故不用太过理会。
      ③对赋值运算符重载，偶尔用到。
  
  
  
  

  1）、演示构造函数：

  ①由下述代码可知，vector是一个类模板，因此需要显示实例化(详细学习请见模板初阶)。

template< class T, class Alloc = allocator>class vector;

  ②以下即为常见的vector的构造用法：

void test_vector01()
{vectorv1;//无参构造
	vectorv2(5, 10);//n个val
	vectorv3(v2);//拷贝构造
}

  ③通过调试观测如下：需要注意的是，对于vector的构造函数，后续我们在模拟实现时仍旧要解决深浅拷贝的问题。

  1）、对数据插入、删除：
   根据上述总览，目前我们知道可以使用push_back、pop_back、insert、erase来达成数据的插入删除。

vectorv1;//构造一个vector,名为v1
		v1.push_back(1);//尾插
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

  
  2）、对数据的遍历：

方式一：下标+[ ]

   相关函数：


   代码演示：

//遍历演示
		for (size_t i = 0; i< v1.size(); ++i)//vector::size
		{	cout<< v1[i]<< " ";//vector::operator[]
		}
		cout<< endl;

		//下标访问，遍历自增
		for (size_t i = 0; i< v1.size(); ++i)
		{	v1[i]++;
		}

		//再次遍历
		for (size_t i = 0; i< v1.size(); ++i)//vector::size
		{	cout<< v1[i]<< " ";//vector::operator[]
		}
		cout<< endl;

方式二：迭代器

   代码演示：

//使用迭代器遍历:需要注意的是这里迭代器对应的vector使用了模板参数
		vector::iterator it = v1.begin();
		while (it != v1.end())
		{	cout<< *it<< " ";
			++it;
		}
		cout<< endl;

   涉及函数：

   支持迭代器，就支持范围for：

//使用范围for
		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;

  1）、简介：
   获取vector首元素和尾元素。 关于front和back二者的使用请见下述练习3.2。

  1）、扩容机制的验证

//扩容机制验证
	void TestVectorExpand()
	{size_t sz;
		vectorv;
		sz = v.capacity();

		cout<< "making v grow:\n";
		for (int i = 0; i< 100; ++i)
		{	v.push_back(i);
			if (sz != v.capacity())
			{		sz = v.capacity();
				cout<< "capacity changed: "<< sz<< '\n';
			}
		}
	}

  此处是以VS2019为例的运行结果：

  
  2）、reserve、rsize介绍
   在已知要插入的数据量的情况下，我们可以提前扩容：

void TestVectorExpand()
	{size_t sz;
		vectorv;
		//v.resize(100);//resize在开空间的同时还会进行初始化，影响size。
		v.reserve(100);//reserve只负责开辟空间，可缓解vector增容的代价缺陷问题。
		sz = v.capacity();

		cout<< "making v grow:\n";
		for (int i = 0; i< 100; ++i)
		{	v.push_back(i);
			if (sz != v.capacity())
			{		sz = v.capacity();
				cout<< "capacity changed: "<< sz<< '\n';
			}
		}
	}

   在上述场景中不能使用resize，因为resize在开辟空间的同时进行初始化数据。假如上述场景中使用了resize，相当于我已经在resize的帮助下拥有了100个数据，后续的for循环又为我提供了100个数据。

  1）、对algorithm
   在vector中，可以看到并没有单独的find函数，是因为我们完全可以用[ ]来做到，另者，如果有需要，algorithm库中提供了find函数。

  同理，vector也不像string一样提供流插入、流提取。因为我们对vector的一般是遍历访问，而string有整体打印字符串的需求。
  
  
  2）、对vector::insert
   vector中insert的用法说明：注意iterator position，其使用的是迭代器。

iterator is a member type, defined as a random access iterator type that points to elements.

  
  3）、使用演示

vectorv1;//构造一个vector,名为v1
		v1.push_back(1);//尾插
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		//使用find在v1中查找值：范围[v1.begin(),v1.end()),val=3
		vector::iterator pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())//检查是否找到相关值。此处find的last=v1.end()
		{	v1.insert(pos,30);
		}
		//遍历：用于检测是否成功插入数据
		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;

  
  
  4）、一个边界说明
   如下图，分析现象并说明原因：

   原因：在v1中寻找300，find返回结果为v1.end()下标，相当于尾插。
   说明：虽然此处没有明确报错现象，但使用find找到值后最好还是检查一下。
  
  

  1）、对erase

  2）、使用演示：

vectorv1;//构造一个vector,名为v1
		v1.push_back(1);//尾插
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		//使用find在v1中查找值：范围[v1.begin(),v1.end()),val=3
		vector::iterator pos = find(v1.begin(), v1.end(), 3);
		if (pos != v1.end())//检查是否找到相关值。此处find的last=v1.end()
		{	v1.erase(pos);//删除单个元素
		}
		
		//遍历：用于检测是否成功插入数据
		for (auto e : v1)
		{	cout<< e<< " ";
		}
		cout<< endl;

  3）、不检查find返回值情况验证：
   如下图所示：报错。

  1）、基本介绍
   ①sort也是一个函数模板，其底层使用的原理是快排，默认排的是升序。

  
  2）、sort排升序

//乱序
		vectorv1;
		v1.push_back(11);
		v1.push_back(23);
		v1.push_back(6);
		v1.push_back(1);
		v1.push_back(9);
		v1.push_back(7);
		v1.push_back(3);
		v1.push_back(15);
		//排升序
		sort(v1.begin(), v1.end());
		//遍历查看
		vector::iterator it = v1.begin();
		while (it != v1.end())
		{	cout<< *it<< " ";
			it++;
		}
		cout<< endl;

  
  3）、sort排降序
   sort排降序涉及到Compare comp仿函数，此处我们只需要学习使用方法：
   两个函数介绍：less、greater

介绍：
		less也是一个类模板，int为此处需要的数据类型
		greater同上，但使用greater需要包含头文件。
		less不需要包含的这个头文件的原因是，sort默认升序。
		

		#includelessls;
		greatergt;
		
		//sort(v1.begin(), v1.end(), ls);
		sort(v1.begin(), v1.end(), gt);

  当然，上述只是一种写法介绍，也可以按照下述写法进行：

sort(v1.begin(), v1.end(), greater());

  此处相当于匿名对象的使用。

  
  
  4）、sort在string中的使用演示

string s("hello string 1144579");
		sort(s.begin(), s.end());
		cout<< s<< endl;

   sort在string中是按照ASCII码排序的：

   也可以排降序：

string s("hello string 1144579");
		sort(s.begin(), s.end(), greater());
		cout<< s<< endl;

   问题描述：

vectorv;
		string s;

   上述二者有什么差异？能否用前者代替后者？
   回答：
   ①string中s后面默认追加\0；
   ②相比于vector，string中的相关函数比较多，实现功能也更全，比如+=(一个字符/字符串)，流插入流提取，find(查字符串)，比较大小、to_string等。
  
  
  

//void push_back (const value_type& val);
		//void push_back (const T& val);

		vectorstrV;

		string str1("张龙");
		strV.push_back(str1);//深拷贝：push_back中val为什么要加&的原因

		strV.push_back(string("赵虎"));//匿名对象：push_back中val为什么要加const的原因

		strV.push_back("王朝");//日常使用习惯：隐式类型转换

//for (auto str : strV)
		//{//	cout<< str<< endl;
		//}
		
		//1、这里也涉及一个深浅拷贝的问题，所以需要十分谨慎处理
		//2、如果不涉及改变内容，可以加上const
		for (const auto& str : strV)
		{	cout<< str<< endl;
		}

   题源

   代码如下：

class Solution {public:
    int singleNumber(vector& nums) {int value=0;
        for(auto e:nums)
        {value^=e;//异或
        }
        return value;
    }
};

   要满足时间复杂度O(n)，空间复杂度O(1)，最简单的方式就是使用异或。
   其余不满足上述条件下，也可以使用排序遍历、直接遍历等方法。
  
  
  

class Solution {public:
    vector>generate(int numRows) {vector>vv;//定义一个vector>类型的数据
        vv.resize(numRows);//第一次开辟空间：numRows，表示总行数(整体大小)
        for(size_t i=0;ivv[i].resize(i+1,0);//第二次开辟空间，表示初始化杨辉三角的每行大小
            vv[i].front()=vv[i].back()=1;//杨辉三vv.size()角每行首尾数据为1

            //vv[i].resize(i+1,1);//上述代码也可以合并为一行实现
        }

        for(size_t i=2;ifor(size_t j=1;jvv[i][j]=vv[i-1][j-1]+vv[i-1][j];
            }
        }

        return vv;
    }
};

int removeDuplicates(int* nums, int numsSize){int src,det;
det=0;src=1;
while(srcif(nums[src]!=nums[det])
    {nums[++det]=nums[src];
    }
    src++;
}
return det+1;
}

class Solution {public:
    int removeDuplicates(vector& nums) {int src,det;
    det=0;src=1;
    while(srcif(nums[src]!=nums[det])
        {nums[++det]=nums[src];
        }
        src++;
    }
    return det+1;
    }
};

nums.riseze(det+1);//此处det+1是因为我们输入的n是数据个数，而det标记的是下标。

class Solution {//numToStr：主要是用于映射2-9数字对应的字母
    char* numToStr[10]={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    //string numToStr[10]={"","","abc","def","ghi"."jkl","mno","pqrs","tuv","wxyz"};

public:

    //digits:系统输入的数字字符串
    //di：这些字符串对应的顺序：第一个、第二个
    //retV：用于存储获取的排列组合，总数目
    //combineStr：用于存储单次递归获取的组合
    void Combine(string digits,int di,vector& retV,string combineStr)
    {if(di==digits.size())
        {retV.push_back(combineStr);
            return;
        }
        
        int num=digits[di]-'0';//将输入的数字字符转换为数字
        string str=numToStr[num];//当前数字对应的字母
        for(auto ch :str)
        {Combine(digits,di+1,retV,combineStr+ch);
        }
    }



    vectorletterCombinations(string digits) {vectorv;
        if(digits.empty())//如果输入的字符串为空时
        {return v;
        }
        string str;
        Combine(digits,0,v,str);
         return v;
    }
};