Learn vector -- how to use common interfaces

What is? vector

Vectors are sequence containers representing arrays that can change in size.
vector Is said Variable size arrays Sequence container for .
In short ： vector Is a variable size array

Constructors , Copy structure , Assignment overload

    vector<int> v1;           // Empty 
	vector<int> v2(10, 5);    //10 individual 5
	vector<int> v3(v2.begin(), v2.end()); // use v2 Iterator to initialize 

	int arr[5] = {
     1,2,3,4,5 };
	vector<int> v4(arr, arr + 5); // Iterators are something like pointers , This is no problem 

	v1 = v4; // Assignment overload 

How to traverse ？

void test2()
{
    
	vector<int> v1;
	v1.push_back(1);  // Tail check interface , Not much 
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	v1.push_back(7);
	v1.push_back(8);
	v1.push_back(9);
	v1.push_back(10);

	// Subscript traversal   utilize operator[] overloaded 
	for (size_t i = 0; i < v1.size(); i++)
	{
    
		cout << v1[i] << " ";
	}
	cout << endl;

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

	// iterator 
	//vector<int>::iterator it = v1.begin();
	auto it = v1.begin();  // Steal a wave of laziness , Direct use of auto Push it to 
	while (it != v1.end())
	{
    
		cout << *it << " ";
		it++;
	}
	cout << endl;
}

And I want to say a little more about iterators

Interface about capacity , Relatively simple , Just briefly

Add, delete, check and modify interfaces and various situations of iterator failure

Tail inserting and tail deleting are very simple . Come straight to insert and erase, And talk about the problem of iterator failure

insert The interface of

vector<int> v1;
	v1.insert(v1.begin(), 5); // stay begin()  Insert at 5 
	v1.insert(v1.begin(), 4);
	v1.insert(v1.begin(), 3);
	v1.insert(v1.begin(), 2);
	v1.insert(v1.begin(), 1);
	v1.insert(v1.begin(), 5, -1);  // stay begin() Insert at 5 individual -1

	vector<int> v2(10, 100); // establish v2 And give the element 10 individual 100
	v1.insert(v1.begin(), v2.begin(), v2.end()); // stay begin Insert at v2

erase and find The interface of , It is simpler to say

iterator erase (iterator position);  // Delete element at iterator position 
iterator erase (iterator first, iterator last); // Delete the element between two iterator ranges  * Before closed after opening *

template <class InputIterator, class T>
   InputIterator find (InputIterator first, InputIterator last, const T& val);
   // In the iterator first and last Search between val, return val The iterator where the 

On the problem of iterator failure

Here's the code , You will find that the program crashes when you run it
What's the reason ？

void test5()
{
    
	vector<int> v = {
     1,2,3,4};

	for (auto& e : v)
	{
    
		cout << e << " ";
	}
	cout << endl;
	//vector<int>::iterator rit = find(v.begin(), v.end(), 3);
	auto it = find(v.begin(), v.end(), 3);  // Before closed after opening 
 	if (it != v.end())  //find The function did not find the return end() Location 
	{
    
		v.insert(it, 400); 
	}

	v.erase(it); // Delete 3
	for (auto& e : v)
	{
    
		cout << e << " ";
	}
}

Is there a good solution ？
1, Reuse find（） Look for
2, With the help of erase（） and insert（） The return value of

use vector Practice questions

Power button ：118, Yang hui triangle

class Solution {
    
public:
    vector<vector<int>> generate(int numRows)
    {
    
      vector<vector<int>> vv;
      vv.resize(numRows);  // Several rows and arrays 
      
      for(int i = 0; i < numRows; i++)
      {
    
          // The first n That's ok , want n Space of elements 
          vv[i].resize(i+1); //  Make room for each array 
      }

      for(int i = 0; i < numRows; i++)
      {
    
          vv[i][0] = 1;  //  Just give the first of each line to 1
          vv[i][i] = 1;  //  Just give the last one in every line to 1
          
          for(int j = 1; j <= i-1; j++)
          {
    
             // law 
             vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
          }
      }
      return vv;
    }
};

Power button 136— Relatively simple , Not much to say

26, Remove duplicate items from an ordered array
Use the front and back pointers , Stop when the front and back are not equal

class Solution {
    
public:
    int removeDuplicates(vector<int>& nums) 
    {
    
        int i = 0, j = 0;
        int len = nums.size();
        while( i < len)
        {
    
            nums[j++] = nums[i];

            while(i+1 < len && nums[i] == nums[i+1]) 
            {
    
                i++;
            }
            i++;
        }
        return j;
    }
};

Power button 137：
Give you an array of integers nums , Except that one element only appears once Outside , Every other element just happens to appear Three times .
Please find and return the element that only appears once .

class Solution {
    
public:
    int singleNumber(vector<int>& nums)
    {
    
        int ret = 0;
        //1, Use bitwise operation , There are always three same numbers 
        // The three numbers add up , They used bit Bits must be divisible 3
        // If one of them bit Bits are not divisible 3, That must be the only number involved 
        for(size_t i = 0; i < 32; i++)
        {
    
            int tmp = 0;
            for(const auto& e : nums)
            {
    
                tmp += ((e >> i) & 1);   //  All the numbers add up to one bit Position of bit 
            }

            if(tmp % 3 != 0)            // If one of them bit Bits are not divisible 3, That must be the only number involved 
            {
    
                ret |= 1 << i;
            }
        }
        return ret;
    }
};